« 今、もやもやサマーズ2でサンドピクチャーの紹介していた。これ欲しい! | トップページ | へえ!あの元ハードル選手の為末大さん、東京大学先端科学技術研究センターの特任研究員になったって。 »

2014年7月13日 (日)

フカシギの数え方、おねえさん問題ってすでにN=26まで数え上げられてるのか!

非常に話題になったこの動画、格子点を通る経路を数え上げるものですが!

もう10x10で恐ろしいことに。で、あるアルゴリズムを使うと早くなり、16x16でも数十分で計算出来ると言う話になってます。

で、これがどんどん進んでいて、、、アルゴリズムの開発者、湊真一さんの解説を見ると、

http://www.nii.ac.jp/userimg/openhouse/2013/lec_minato.pdf

去年の4月の時点で25x25まで計算できていたとのこと。

でさらに進んで、、

http://h50146.www5.hp.com/products/servers/proliant/whitepaper/pdfs/WhitePaper_HokkaidoUni_ST.pdf

によると、もう26x26までも計算できている。

http://oeis.org/A007764/b007764.txt

でその総数が見られます。

 0  1
 1  2
 2  12
 3  184
 4  8512
 5  1262816
 6  575780564
 7  789360053252
 8  3266598486981642
 9  41044208702632496804
10  1568758030464750013214100
11  182413291514248049241470885236
12  64528039343270018963357185158482118
13  69450664761521361664274701548907358996488
14  227449714676812739631826459327989863387613323440
15  2266745568862672746374567396713098934866324885408319028
16  68745445609149931587631563132489232824587945968099457285419306
17  6344814611237963971310297540795524400449443986866480693646369387855336
18  1782112840842065129893384946652325275167838065704767655931452474605826692782532
19  1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844
20  3962892199823037560207299517133362502106339705739463771515237113377010682364035706704472064940398
21  31374751050137102720420538137382214513103312193698723653061351991346433379389385793965576992246021316463868
22  755970286667345339661519123315222619353103732072409481167391410479517925792743631234987038883317634987271171404439792
23  55435429355237477009914318489061437930690379970964331332556958646484008407334885544566386924020875711242060085408513482933945720
24  12371712231207064758338744862673570832373041989012943539678727080484951695515930485641394550792153037191858028212512280926600304581386791094
25  8402974857881133471007083745436809127296054293775383549824742623937028497898215256929178577083970960121625602506027316549718402106494049978375604247408
26  17369931586279272931175440421236498900372229588288140604663703720910342413276134762789218193498006107082296223143380491348290026721931129627708738890853908108906396

« 今、もやもやサマーズ2でサンドピクチャーの紹介していた。これ欲しい! | トップページ | へえ!あの元ハードル選手の為末大さん、東京大学先端科学技術研究センターの特任研究員になったって。 »

日記・コラム・つぶやき」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/512682/59979403

この記事へのトラックバック一覧です: フカシギの数え方、おねえさん問題ってすでにN=26まで数え上げられてるのか!:

« 今、もやもやサマーズ2でサンドピクチャーの紹介していた。これ欲しい! | トップページ | へえ!あの元ハードル選手の為末大さん、東京大学先端科学技術研究センターの特任研究員になったって。 »

最近のコメント

2017年10月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
フォト
無料ブログはココログ