10/08/02③ 不思議ちゃんに触発された
Cygwinで動作確認済み
#include <stdio.h>
#include <math.h>
main()
/*
・操作過程で 「2の(0以上の整数)乗×(-1)」の公差の等差数列（便宜上、最上面のカードを初項とする）
が次々と出現するのを利用
・項数が奇数か偶数か、によって次の等差数列の初項、及び項数が異なるので
場合分けが生じる点に注意
（偶数→初項、項数は元の半分、
奇数→第3項、項数は自身から1引いたものを半分、ただし整数で処理してるのであまりここでは関係ない）
*/
{
int n, i, j, flag = 0, ii = 0;
printf("仮定として「1」、「2」、…「n-1」、「n」の番号が書かれたn枚のカードがあり、\n"
"このn枚のカードが「n」が最上面になるように番号の順に積まれている。\n\n"
"この状態から、\n「最上面のカードを最下面に移動し、その次に最上面になったカードを捨てる」\n"
"という操作を繰り返すと、最後にカードが1枚残る。\n\n"
"このプログラムではその番号を出力する。\n\n自然数nを入力せよ。\n\n");
while (flag == 0){
flag = 1;
printf("n = ");
scanf("%d", &n);
j = n;
if (n >= 1){
for (i = 0; j <= 2; i++){
if (j%2 == 1){
n -= pow(2, i)*2;
}
j /= 2;
}
printf("result = %d \n", n);
}else{
printf("数値が不正です。\n最初からやり直してください。\n\n");
flag = 0;
ii++;
if (ii >= 10){
flag = 1;
printf("ハングアップしました。\n"
"数値以外を入力するとこのようになります。\n\n");
}
}
}
}
不思議ちゃん
2010/08/03 02:59:58
結局、さらに検討して、処理部分は１行になっちゃいました。ループもありません。くわしくは
http://www.nicotto.jp/blog/detail?user_id=288939&aid=16790980
にて～♫
不思議ちゃん
2010/08/02 23:20:17
解説で良く分かりました～～♫ ありがと～ございました～♫
私の説明は泥臭いですが、ほぼ同じですね～。「公差」が「落差」に。言葉に落差が～(^_^;)
ループ制御のフラグが直感的には分かりませんが、そこはまあそんなもので。アルゴリズムはほぼ同じで、敢えて言えば違うのは、「公差」をそのつど 2^i とかで直接計算するのか、前の「落差」の２倍だと一つずつ計算を重ねていくのかくらいでしょうか(^_^;)
あ、終了条件、確かに、N=2 まで下がればそれでいいですね。私の幅か正直にN=1までもう一ループ回ってます。結果は同じですが無駄でしたか(^_^;)
処理の感触としては N を２進数で表わして、下の桁から１ビットずつ取り出して、０か１かで違う処理をする、というのを繰り返すという感じですね～。
ところで Ｃの何のところの課題？？
⊹⊱煌華⊰⊹
2010/08/02 23:08:58
うわ～・・・・・さっぱり意味がわからんｗｗ
もうただただ何かよくわからないものの羅列でしかないｗ
すげ～
鶏ドリアン
2010/08/02 23:06:20
例えば、n = 100のとき、
{100, 99, 98,……, 2, 1}
初項 100, 項数100, 公差 -1(= -pow(2, 0))
↓
{100, 98, 96,……, 4, 2}
初項 100, 項数50, 公差 -2(= -pow(2, 1))
↓
{100, 96, 92,……, 8, 4}
初項 100, 項数25, 公差 -4(= -pow(2, 2))
↓
{92, 84, 76,……, 12, 4}
初項 92, 項数12, 公差 -8(= -pow(2, 3))
↓
{92, 76, 60, 44, 28, 12}
初項 92, 項数 6, 公差 -16(= -pow(2, 4))
↓
{92, 60, 28}
初項 92, 項数 3, 公差 -32(= -pow(2, 5))
↓
{28}
初項 28, 項数 1, 公差 なし
n = 128のとき
{128, 127, 126,……, 2, 1}
初項 128, 項数128, 公差 -1(= -pow(2, 0))
↓
{128, 126, 124,……, 4, 2}
初項 128, 項数64, 公差 -2(= -pow(2, 1))
↓
{128, 124, 120,……, 8, 4}
初項 128, 項数32, 公差 -4(= -pow(2, 2))
↓
{128, 120, 112,……, 16, 8}
初項 128, 項数16, 公差 -8(= -pow(2, 3))
↓
{128, 112, 96,……, 32, 16}
初項 128, 項数 8, 公差 -16(= -pow(2, 4))
↓
{128, 96, 64, 32}
初項 128, 項数 4, 公差 -32(= -pow(2, 5))
↓
{128, 64}
初項 128, 項数 2, 公差 -64(= -pow(2, 6))
↓
{128}
初項 128, 項数 1, 公差 なし
2項以下になったら
初項を出力すればよい。