人気ブログランキング | 話題のタグを見る

金銭上の利益のためだけでなく、専ら個人的な興味によって行う自己満足、通信及び技術的遊戯のための備忘的ブログです。


by jq1ocr

計算時間を見積もってみる

telmic-gunma 高井さんのブログhp 電卓を使ってパズルを解いてみたというエントリがありました.電卓でやったら 10 分,WinXP だと 1 秒だったそうです.

私の場合はプログラムを書くといったら gcc です.中身は単純(よく見たら1行.笑)

for(a=1;a<7;a++)
for(b=1;b<7;b++)
for(c=1;c<7;c++)
for(d=1;d<7;d++)
for(e=1;e<7;e++)
for(f=1;f<7;f++)
if(a+a+b==13
&& b+e+d==9
&& c+c+f==13
&& a+b+c==14
&& a+e+c==15
&& b+d+f==6)
printf("%d, %d, %d, %d, %d, %d\n",a,b,c,d,e,f);

リターン(実行)を押した瞬間答えが出ました.早っ.ちなみに使ったのは iMac late 2015 です.

ちなみにプログラムを書くときはコピペでループを深く出来るからすぐ書けちゃうと思いきや,xcode のエディタに予測変換みたいなことをされて,かなり手間取りました.苦笑 あ,さすがに初期設定はうざすぎるので,今は直しましたよ.(Preferences > Text Editing > Editing > Suggest completions while typing をオフにする)しかし,こんなのでも書くのに何分かかかってしまいました.

その後,このくらいだったら手計算でも出来るか?と思って上から順にやっていったら,なんと一番下の式が 0=0 になってしまいました.結局独立な式が足りないのです.ということは解がいくつもありえるということです.まず x=f(a) の形にして,今回の問題では数字が1から6の間をとると限定されているので,二番目の d=4a-18 から a は 5 か 6 しか取り得ず,その次の f=11-2a から a は 6 が棄却され 5 で確定して,他の変数も全て決定されます.というわけで,これも数分でできましたから,コンピュータを使ったからといって,必ずしも早いわけではない問題の一例かも知れません.笑

計算時間を見積もってみる_d0106518_10331308.jpg

ところで気になるのが数字の範囲を広げた場合の解ですね.全てが正になるのは上のパターンしかないでしょうから,試しに上のプログラムで -100 から 100 まででやってみました.すると一晩経っても計算が終わりません.まあ計算量は 2006 ですからとんでもないことをさせているわけです.ループの出入り口で時間を出すようプログラムし,-20 から 20 までやってみたら 8 秒かかっていました.次いでこれを ±25 にしたら 29 秒でした.計算域が 1.25 倍なので,計算量は 1.256=3.8 倍となり,時間も大体その比率になっています.

従ってもしここを ±100 でやってみたら 8 秒の 56 = 15,625 倍かかるということです.ざっと 35 時間といったところでしょうか.そりゃ一晩くらいじゃ終わらないわけだ.笑

しかし,こんな総当たりをしなくても手計算すれば早かったりします.というのも,まず上の式は以下のように変形できます.

b=13-2a
c=1+a
d=4a-18
e=14-2a
f=11-2a

結局解は無限にあることが分かりますね.ただ各変数の取り得る範囲を -100 から 100 までとすれば,d=4a-18 から a の上下限が -20 から 29 に限定されます.各変数の値は異なるという条件があるなら,交点を除く必要がありますが,まあいずれにしても劇的に短い時間で計算できるわけです.総当たりだと計算時間は6乗のオーダーで増えていきますが,このようにすれば1乗ですからね.笑

さて令和元年もそろそろ終わりますね.今年は計算ネタで締めとなりました.ではみなさん,よいお年を.

Commented by telmic-gunma at 2020-01-02 07:44
あけましておめでとうございます。
高井です。
面白いですね、 一行プログラム 
あと ちょこっとしたイラスト 雰囲気がグッと明るくなりますね
勉強させてもらいます。
Commented by jq1ocr at 2020-01-02 11:07
高井さん,あけましておめでとうございます.

無理矢理つないでますが,確かに;は一個ですものね.笑 イラストはいろんなところで目にされると思います「いらすとや」さんのフリー素材です.
名前
URL
削除用パスワード

※このブログはコメント承認制を適用しています。ブログの持ち主が承認するまでコメントは表示されません。

by jq1ocr | 2019-12-31 19:30 | 徒然話 | Comments(2)