これは、ほぼ同じタイトル（その２が付いてないもの）のブログの続編です。
　前回は
http://www.nicotto.jp/blog/detail?user_id=288939&aid=16691800
です。

　さて、鶏ドリアさんが、何やら数学的な解法を用いたようなのですが、人のプログラムは、解説がないと良く分からないので、自分でやってみました。
　まあ数学的な解法を用いる功罪は別として(^_^;)

　まずテーマの確認。

課題は以下の通り。

自然数nを入力させる。

そのnに対して、「1」、「2」、…「n-1」、「n」の番号が書かれたn枚のカードを仮定する。
このn枚のカードを「n」が最上面になるように番号の順に積む。

その後、「最上面のカードを最下面に移動し、その次に最上面になったカードを捨てる」

という操作を繰り返し、最後にのこったカードの番号を出力せよ。


というわけです。

　ここで用語を決めておきます。

その後、「最上面のカードを最下面に移動し、その次に最上面になったカードを捨てる

という操作を１回することを１操作、２回することを２操作、と略記することとします。

　さて、この操作を、「一通り」続けて行なうことを考えます。一通りというのは、カードの上からしたまでという感じ。
　正確に言うと、枚数が偶数枚なら、枚数÷２　回、奇数枚なら（枚数＋１）÷２　回、繰り返すということです。この一通りを、「セット処理」と呼ぶことにします。
　そうすると、１番上、３番目、５番目、…のカードが残り、２番目、４番目、６番目のカードが捨てられます。
　問題は最後の一操作で、偶数枚の時には、ちょうど終りで、一番上のカードがまた一番上になります。奇数枚の時には、最後の一操作の後半が残っていて、一番上のカードがまた一番上に来た時、その一番上のカードが取り去られます。

　セット処理を１回行なうごとに、偶数番目のカードが無くなり、カードとカードの番号の間隔は、２倍になります。

　以上のことが分かれば、そのままアルゴリズムが出来ますので、プログラミング可能です。

　セット処理ごとに毎回枚数が偶数なら、一番上のカードは変わりません。つまり２のべき乗枚数の時には、一番上のカードははじめと同じです。試しに、前のプログラムで、2,4,8,16…を入力すると、確かめられます。
　最初に奇数になり、あとは全部偶数なら、最初に１枚取られて２小さなカードが一番上になり以後そのままそれが応えになります。つまり、２のべき乗＋１なら、枚数－２が答えです。
　3→1、5→3、9→7……

　例によって、Cではなくて「なでしこ」で書いてみます。
##################################################
# トリさんの課題、別解
# 2010/08/01

# 自然数 N の入力
「自然数 N を入力してください」で尋ねてNに代入する。

# 入力チェック
もし（Nの整数部分<>N）OR （N<=0）ならば
　「入力するのは自然数だけにしてね(^_-)-☆」と言う。
　終わる。

# 枚数が1になったら終りである。
枚数=N

# 一番上のカードが、元の何番目か（先頭カード番号）を追跡していく
先頭カード番号=N
落差=1

枚数>1の間
　移動廃棄処理

先頭カード番号を言う。
終わる。

# main routine 終了

●移動廃棄処理
# 要するに枚数が偶数の場合には、偶数番目だけが残る。
# 枚数が奇数の場合には、偶数番目だけが残り、さらに１番上が取られて、２番目が出る。
# 上から２番目が、一番上からいくつ離れているかを「落差」で記憶している。
　落差に2を直接掛ける
　もし枚数が2の倍数ならば
　　枚数を2で直接割る
　違えば
　　先頭カード番号から落差を直接引く
　　枚数は（枚数－1）÷2

##################################################

　答えは同じですが、配列を使わないこと、ステップ数がたぶんlogN級に減ることなどで、高速でかつより大きなNまで対応可能になります。いずれにせよ、実務プログラミングでは、Nの上限を仕様で定め、範囲外入力は弾かなければなりませんが(^_^;)

　一方で保守点検性は落ちます。クライエント様から仕様を「はじめの２枚を後ろに回し、そのあと３枚を捨てる」に「ちょこっと」変更してくれ、みたいに言われることは、実務ではしばしばあります。最初から言ってくれ～～。で一つ前の愚直なプログラムなら、元のプログラマー以外の人が担当になっても、仕様書見てプログラム見て修正可能ですが、このような数学的解を用いた方法では、他人が見て理解しづらく、保守性が格段に落ちるわけです。なので現実的には、一長一短、どちらが勝るかはまさに状況次第ですね～～。

　今みたいに遊びで楽しむ分にはよりエレガントな解を捻り出して楽しむだけでいいんですけどね～～(^o^)ﾉ

　ということで、人の課題で遊んでみました～～♫