問題18164・・・ http://www.nurs.or.jp/~lionfan/mainichi_2004_101.html より 引用 Orz〜
いま長方形の、ある程度の厚みがあるプラスチックのカードが1024枚あり、
1〜1024までの連番が振ってあります。
そして、ごちゃごちゃに混ぜられています。
ところがいたずらな子供が、一枚を盗んで捨ててしまいました。
1〜1024まで、すべてのカードが揃っている必要があるので、
子供が捨てた番号のカードを、急いで作り直す必要があります。
つまり問題は、
「欠番となってしまった番号を、すばやく探し出す方法を述べよ」です。
1〜1024までのカードを、番号順に並べなおせばいいのでしょうが、それはとてつもない時間がかかります。
もう少しラクな方法はないでしょうか?
・上記サイトより Orz〜
「まず1024枚のカードを、「小」つまり1〜512までと、「大」つまり513〜1024に分けます。
その2つの山を積み重ねると、どちらか一方だけが1枚、少ないはずです。
欠番はその山にあります。いま仮に「大」の山のほうが少なかったとしましょう。
あとは繰り返しです。つまり
「大」の山513〜1024を、さらに半分、つまり「513〜768」と「769〜1024」に分けます。
すると、どちらか一方だけが1枚、少ないはずです。
そして・・・と続けていくと、欠番のカードがみつかる、という話です。」
*確かに!! この方が楽ですね♪
Maxのカウントは...512+256+128+64+32+16+8+4+2=1022回で見つかるわけね ^^
*以下の方法の方が簡単かもしれません ^^☆
・鍵コメY様からのもの Orz〜
1024・1025/2=524800 から、すべての数を引いていけば答が出ます。 珠算の達人なら暗算で、一般人なら、電卓でも良いし、 打ち間違いの恐れがあれば、Excelを使って。
・鍵コメT様からのもの Orz〜
その方法は本当に楽でしょうか. まず,1024枚のカードをすべて見て,1〜512と513〜1024に分け, どちらか一方を数えて,512枚揃っていれば欠番なし,511枚なら欠番あり. この時点ですでに,「すべてのカードに目を通して分類し, 511〜512枚を数える」必要があります. 次に,511枚のカードについて同様の作業,次に255枚のカードについて… となると,すべて並べ替えるよりはずっと楽ですが,かなり面倒な気がします.
カードを順に見て,その合計を計算していく方法が優る気がします. かなり大きい数になるのが少しつらいので, 合計を2000で割った余りを計算していくのでもよいと思います. 1+2+…+1024=1024*1025/2=524800なので, 合計を2000で割った余りは,欠番がなければ800になるはずで, 得られた合計を800または2800から引いた数が欠番です.
*100未満、100台、200台、...、900台、1000台
に仕分けして、それぞれの枚数が合わない(少ない)ところだけの合計を求めるという折衷案はどうかいなぁ ^^;...?
1024*2カウント+100個分の合計の計算...質が違うものの手間を比較できないとは思いますです...が...^^;
|