一歩で一度移動できる360度のメモリ付きトラックがある。1歩,2歩と時計の針の方向に歩き始め途中2回ほど逆方向に歩く。
ある時ちょうど180度の位置で止まり,その後ちょうど360度の位置で止まった。
このように移動する最小の歩数とその時逆に動いた歩数は?
ポイントは以下の3つ。
以上3つのポイントを踏まえてサクッとプログラミングする。
#include "puzutl.h" const int N = 100; // まあこれくらいの数字の中に見つかるでしょ。 int sum[1+N] = {0}; // 事前に歩数の合計値は計算しておく YesNo check180( int n, int i, int j) // ちょうど180度で止まるか? // n :I:1歩,2歩,…,n歩進む // i :I:この歩数の時逆方向に進む // j :I:この歩数の時逆方向に進む { … // 360度で止まる場合もYESを返さないように注意する } int main( int argc, cstring argv[]) { int minn = 0; // 最低360度回転しなければならないので必ず進む歩数があるはず for( int i=1; i<= N; i++) { // 最初にトータルの歩数を求めておく sum[i] += i+sum[i-1]; // トータルの歩数は前の歩数に次の歩数を足したもの if( minn == 0 && sum[i] > 360) { // 最低1周する所から調べ始める minn = i; // minnを使わないで1から調べた方がバグが少ないプログラムになる } } for( int n=minn; n< N; n++) { // 合計数字が針の動く回数だから小さい数字から調べていく for( i=1; i< n; i++) { // その中から2つの数字を選択して調べる(一つめの数字) for( int j=i+1; j< n; j++) { // もう一つの数字(一つめより必ず大きな数字) int back = i+j; // 2つの数字の合計 if( ((sum[n]-back-back)%360) == 0) { // 2回引き算するのは,回ったと仮定してある分を取り消し,更にその分元に戻る if( check180( n, i, j)) { // その中にちょうど180で止まっているものがあるか? 発見 return 0; // 答えが見つかったので終了 } } } } } pe( "答えが見つからない\n"); return 0; }
小さくもなく,大きくもないそこそこの数が見つかりました。
実は上記minnのような変数を用意するのは止めた方が良い。バグの元になるだけ。プログラムはシンプルに!
もちろん実行時間が掛かる計算の場合なら用意する意味はある。
sum[ ]は用意しておいても良い。sum[ ] と minn を用意する違いは理解しておきたいところ。
金魚の体調が優れない。満足に動くことも出来ないのでスポイトで口の部分に餌を運んであげる。
要介護5だ。もう2週間近くこの状態。
(2006.12.2)本日永眠しました。私にとって12月2日は人生の節目の日。よりによって今日とは。何回も死にかけては復活してきただけに悲しみもひとしお。
解速度
即