M.Hiroi's Home Page
Guest Book Log
120.完全ハッシュ関数の逆関数
投稿者:高橋謙一郎 - 2000年 12月 21日 20時 32分 53秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.5; Windows 98; Win 9x 4.90)
メールアドレス:takaken@ic-net.or.jp
広井さん、deepgreenさん、鎌田さん こんばんは。
お久しぶりです。コンピュータ&パズルの高橋です。
完全ハッシュ関数は面白いですね。とても勉強になりました。
ところで、完全ハッシュ値から逆算して元の状態を復元できる
逆関数があれば「局面を保存する場所は不要」になりますね。
メモリが不足する場合などには便利に使えると思います。
さっそく作ってみたのが下のコードですが、組合せ型の最後の
2行は若干の不安が残ります。
/*
順列型の完全ハッシュ逆関数(広井さんのコードより) */
void change_board(int value, char
*board)
{
int i, j;
for (i=0; i<SIZE-1; i++) {
board[i] =
value / fact_table[i];
value -= fact_table[i] *
board[i];
}
board[i] = 0;
for (i=SIZE-2; i>=0; i--)
{
for (j=i+1; j<SIZE; j++)
if (board[i] <= board[j])
board[j]++;
}
}
/* 組合せ型の完全ハッシュ逆関数(鎌田さんのコードより) */
void ncr2inv(int
n, int r, int value, char *p)
{
int c;
n--;
c = ncr(n, r); /*
nCr */
while (n>=r && r>0) {
if (value / c)
{
value -= c;
c = (c * r) / (n - r + 1); /* nC(r-1)
*/
r--;
*p++ = 1;
} else {
*p++ =
0;
}
c = (c * (n - r)) / n; /* (n-1)Cr */
n--;
}
for
(n++; n; n--)
*p++ = (n > r)? 0: 1;
}
119.KaMemo
投稿者:M.Hiroi - 2000年 12月 21日 18時 42分 00秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geicoties.co.jp
xyzzy
の作者である亀井さんのホームページでは、
リンク先ホームページの紹介のほかに、コメントがつく場合が
あります。これを KaMemo [(C)
Toy] といいます。
このたび、私のところにもついに KaMemo が書いてありました。
よっしゃー!
さて内容はなんだろうと読んでみたら、
あうあう、そうでした。defmacro はそれが使えるのね(笑)。
ということで、「xyzzy
Lisp:マクロ」を更新しました。
亀井さんに感謝です!
118.うさぎと犬
投稿者:M.Hiroi - 2000年 12月 12日 22時 16分 22秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
>少し前のCマガに「うさぎと犬」というゲームの問題がありました。
>丁度、状態の数が少ないので使えそうです。
Cマガジン10月号ですね。なるほど、組み合わせが使えそうです。
解答発表は次号(12/18発売予定)なので、どんなプログラムが掲載
されるか楽しみです。
思考ゲームといえば、ミニマックス法+αβ枝刈りが定番アルゴリズム
ですが、例題にぴったりのゲームがあります。8行8列に+と-の数字
が配置されていて、その数字を取り合うもので、名前が「MinMax」だっ
たはずです(笑)。これは簡単にプログラムできるので、そのうちに
紹介したいと思います。
117.re^8:組み合わせ
投稿者:deepgreen - 2000年 12月 12日 21時 00分 48秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
こんばんは、deepgreenです。
少し前のCマガに「うさぎと犬」というゲームの問題がありました。
(先手必勝なのでその手順をもとめよというもの)
丁度、状態の数が少ないので使えそうです。それに、α・β枝刈りも解説が
ありましたし、ぴったりの問題かもしれませんね。
116.re^7:組み合わせ
投稿者:M.Hiroi - 2000年 12月 10日 18時 04分 43秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
鎌田さん、deepgreen
さん、こんばんは。
せっかく良い方法を教えてもらったのですから、
実際のパズルの解法に応用してみたいですね。
逆に、そのようなパズルを考えてみるのも
面白いかもしれません(笑)。
115.re^6:組み合わせ
投稿者:deepgreen - 2000年 12月 09日 21時 43分 34秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
kamadaさん、広井さん こんばんは。 deepgreenです。
どうもありがとうございます。意外と簡単にできましたね。
チャンスがあれば、どこかで利用してみます。
114.re^5:組み合わせ
投稿者:M.Kamada - 2000年 12月 09日 15時 48分 17秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.01; Windows 98)
メールアドレス:m_kamada@nifty.com
ホームページ:http://homepage2.nifty.com/m_kamada/index.htm
広井さん、こんにちは。
>最上位ビットが0の場合、ncr(7,4)=35
通りの組み合わせがあるので、
>0 - 34 の数値を割り当てる、1の場合は残りの組み合わせが
>ncr(7,3)=35
通りあるので、35 - 69
の数値を割り当てる、
>あとは各ビットに対してこれを繰り返せば求めることができる、
>というわけですね。
そうそう、そんな感じ。
パスカルの三角形の上の経路に番号を振っているだけです。
下の位からやったほうがncr(n,r)を計算しなくて済むぶん速いかも。
そうすればncr(n,r)の計算中のオーバーフローを気にしなくて済むし。
113.re^4:組み合わせ
投稿者:M.Hiroi - 2000年 12月 09日 14時 30分 24秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
鎌田さん、こんにちは。
>nCrの組み合わせを0~(nCr)-1の番号に変換する方法ですが、
>基数変換の応用で簡単にできます。
書き込み、ありがとうございます!
最上位ビットが0の場合、ncr(7,4)=35
通りの組み合わせがあるので、
0 - 34 の数値を割り当てる、1の場合は残りの組み合わせが
ncr(7,3)=35 通りあるので、35 - 69
の数値を割り当てる、
あとは各ビットに対してこれを繰り返せば求めることができる、
というわけですね。
なるほど、納得しました。さすが鎌田さんです。
目からウロコが落ちました(笑)。
素晴らしい方法を教えていただき、大感謝です。
112.re^3:組み合わせ
投稿者:M.Kamada - 2000年 12月 09日 04時 25分 32秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.01; Windows 98)
メールアドレス:m_kamada@nifty.com
ホームページ:http://homepage2.nifty.com/m_kamada/index.htm
広井さん、deepgreenさん、こんにちは。
nCrの組み合わせを0~(nCr)-1の番号に変換する方法ですが、
基数変換の応用で簡単にできます。
てきとーに書いたサンプルなので不完全and/or無駄があるかも知れませんが、
下のCの関数で
ncr2num(8,4,"00001111")==0
ncr2num(8,4,"00010111")==1
:
ncr2num(8,4,"11110000")==69
になります。
--------
int
ncr2num(int n, int r, char *p)
{
int c, a = 0;
n--;
c = ncr(n, r);
/* nCr */
while (n >= r && r > 0) {
if (*p++ & 1) {
a
+= c;
c = (c * r) / (n - r + 1); /* nC(r-1) */
r--;
}
c = (c * (n -
r)) / n; /* (n-1)Cr */
n--;
}
return a;
}
111.re^2:組み合わせ
投稿者:M.Hiroi - 2000年 12月 08日 22時 50分 30秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
>やはり、簡単な方法はないのでしょうか。
>ときどきでてくるパターンなので、よい方法あるといいなぁ
>と思っていました。
Google
で検索してみましたが、やはり見つかりません。
よい方法を知っている方がいましたら、書き込みお願いいたします。
110.re:組み合わせ
投稿者:deepgreen - 2000年 12月 08日 20時 53分 26秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
広井さん、こんばんは。 deepgreenです。
>>しかし、不思議なことに組み合わせ
nCkの完全ハッシュ関数を解説して
>>いるところはありません。
>たとえば、8個の中から4個を選ぶ組み合わせは70通りありますが、
>それを
0 から 69 の数値に変換する方法ならば、M.Hiroi
もわかり
>ません。
そうそう、これが知りたかったのですが、やはり、簡単な方法はないの
でしょうか。ときどきでてくるパターンなので、よい方法あるといいなぁ
と思っていました。
109.組み合わせ
投稿者:M.Hiroi - 2000年 12月 08日 20時 03分 04秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
>しかし、不思議なことに組み合わせ
nCkの完全ハッシュ関数を解説して
>いるところはありません。
たとえば、8個の中から4個を選ぶ組み合わせは70通りありますが、
それを
0 から 69 の数値に変換する方法ならば、M.Hiroi
もわかり
ません。
ところで、組み合わせは次の方法で簡単に数値へ変換することができます。
たとえば、0 - 7
の数字の組み合わせを考える場合、0 - 7 を 0 bit から
7 bit に対応させます。すると、2,3,4,6 という組み合わせは
01011100
になるので 92 と表すことができます。
たしか、値が衝突しないハッシュ関数を完全ハッシュ関数、N個のデータ
を 0
から N - 1
に変換するハッシュ関数を最小完全ハッシュ関数と呼ん
でいたように記憶しています。すいません、記憶があやふやです(苦笑)。
そうだとすると、この方法でも値は衝突しないので、完全ハッシュ関数と
考えてよいと思うのですが、どうでしょうか。
108.単なる興味の質問:組み合わせ nCk の完全ハッシュ関数は?
投稿者:deepgreen - 2000年 12月 08日 00時 01分 26秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
こんばんは、deepgreenです。
単なる興味ですが、8パズルの解法でn個の順列の完全ハッシュ関数の
説明がありました。この方法は他のサイトでも目にしたことがあります。
しかし、不思議なことに組み合わせ
nCk の完全ハッシュ関数を解説して
いるところはありません。(私が知らないだけでしょうけど)
もし、ご存知でしたら教えてください。
107.Vivisimo Search
投稿者:M.Hiroi - 2000年 12月 07日 20時 54分 24秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
Memo
に書いた Vivisimo Search の続きです。
M.Hiroi's Home Pageを検索すると、「anime,
sakura」という
カテゴリに分類されるHPがあります。これは、どうやら作家(?)
の広井王子氏に関連したホームページのようです。
sakura
は「CCさくら」ではなくて、「サクラ大戦」みたいで
す。なるほど、きちんと分類されているんですね。
Vivisimo
Search、ただ者ではないようです(笑)。
106.Re.Prolog:平面上の蛙とびゲーム&ペグ・ソリテア
投稿者:M.Hiroi - 2000年 11月 29日 21時 38分 05秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
> ついでに、平面上の蛙とびゲームをPrologで解いてみました。
46手と長い手数かかりますが、それを
Prolog で解くとは、さすが
deepgreen さんですね。お見事です。
>
広井さんの枝刈り(グループ化)を追加した場合、以下のような
>
結果となりました。
さっそく試していただき、ありがとうございます。
なるほど、deepgreen
さんの枝刈りと組み合わせた場合でも、
効果は出ていますね。おかげさまで、有効な枝刈りであることを
確かめることができました。
幅優先探索の場合、枝刈りの効果は少ないですが、それだけ無駄な
状態を生成していないのでしょう。双方からの幅優先探索の効果は
絶大であることを、あらためて実感しました。
105.Prolog:平面上の蛙とびゲーム&ペグ・ソリテア
投稿者:deepgreen - 2000年 11月 29日 01時 26分 26秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
こんばんは、deepgreenです。
ついでに、平面上の蛙とびゲームをPrologで解いてみました。
やはり、最短手数は46手です。直線の場合と違って、解はたくさんあります。
探索時間:525秒 ノード数:45297
それから、広井さんの枝刈り(グループ化)を追加した場合、以下のような
結果となりました。
前回 今回
前回/今回
反復深化 2384秒 1683秒 1.42
(ノード数)1,083,994 840,926
1.29
幅優先 727秒 642秒 1.13
(ノード数) 94,396 88,514
1.07
104.Re.Prolog:変形三角盤(ペグソリティア)
投稿者:M.Hiroi - 2000年 11月 23日 20時 27分 04秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
> 割り算を1桁間違えていました。約280倍でした。
はい、そうでしたね。M.Hiroi
も後から気がつきました(笑)。
280 倍でも大きな違いであることは、かわりありません。
>
反復深化の方の結果がでました。
> 探索時間:約40分
ノード数:1,083,994
おめでとうございます!
いやー、凄いです。M.Hiroi
は、1時間以上かかるだろうと思ってい
ましたが、40 分とはとても速いです。
deepgreen
さんの枝刈りは凄いですね。探索ノード数が拙作の約半分
なのを見て、目が点になりましたよ(笑)。must と need
に分けて
管理する方法は素晴らしいと思います。
プログラムの公開、ありがとうございます。
Prolog
に興味のある方は、ぜひ参考にしてください。
とても勉強になります。
103.Re.Prolog:変形三角盤(ペグソリティア)
投稿者:deepgreen - 2000年 11月 23日 02時 12分 57秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
ホームページ:http://www2.tokai.or.jp/deepgreen/shortnotes/pegida.txt
こんばんは、deepgreenです。
>
ノード数は、(目安ですが)約2800倍の差があります。
すみません。割り算を1桁間違えていました。約280倍でした。
反復深化の方の結果がでました。下記のURLにあります。
枝刈りの着眼点は同じですが、実装は少し違うようです。
A B
C
D E
F G H
・ ・ ・ ・
隅のA,B,Cのパターンに着目すると、
(1)A,Bにピンがある場合は、そこが始点になる必要がありますので
これをmustカウントとします。
(2)A,Bにピンがあり、Cの位置にピンがないときは、Cの位置にピンが
こなければなりません。これをneedカウントとします。
(3)A,Bにピンがなく、Cの位置にピンがあるときは、Cの位置が始点に
なる必要があります。これはmustカウントとします。この場合連続
跳びで別の隅のneedカウントをさげる可能性があるため、need
カウントは-1にします。
C B A must need
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 2 2
1 0 0 1 -1
1 0 1 1 0
1 1 0 1 0
1 1 1 2 1
下限値は、3つの隅について、上記のmustの合計+needの合計とな
ります。ただし、needの合計が負のときは0にします。また、最終手の
位置の考慮も必要です。
探索時間:約40分 ノード数:1,083,994
102.Re.Prolog:変形三角盤(ペグソリティア)
投稿者:M.Hiroi - 2000年 11月 22日 22時 58分 46秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
> 私も、IDAサーチの方は、この方法でやっています。この枝刈りは、ちょっと
>
面倒なところがあります。今までは、それ以前の探索制御でトラブッていました。
いやー、実は M.Hiroi
もトラブってしまいました。
連続跳びの途中で枝刈りを行うとダメなことに気づかず、
最初は何で動かないんだ?
と混乱してしまいました(苦笑)。
詳しいことは、Puzzle DE Programming
でプログラムを公開するときに
説明する予定です。
それで、結果は Memo
に書きましたが、うまくいきません(泣)。
そのほかの枝刈りも試しましたのですが、探索ノード数は減っても、
幅優先探索の約95000個には及びません。
うーん、残念です。なにか効率的な枝刈りがありましたら、
教えてくださいませ。>ALL
101.re:Re.Prolog:変形三角盤(ペグソリティア)
投稿者:deepgreen - 2000年 11月 22日 21時 22分 15秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
広井さん、こんばんは。deepgreenです。
>コーナーペグが移動するためには、自分で跳ぶしかありません。この
>時、跳び越すペグが必要になります。つまり、この位置にペグが無い
>場合は、そこにペグを移動させてから、コーナーペグを移動させることに
>なります。つまり、それだけ手数がかかるわけです。この条件も下限値と
>して利用すれば、もっと効率的に枝刈りができると思われます。
私も、IDAサーチの方は、この方法でやっています。この枝刈りは、ちょっと
面倒なところがあります。今までは、それ以前の探索制御でトラブッていました。
ようやく、それがわかったので少し前進です。これで答えがでてくれると
Happyですが、。。。
100.Re.Prolog:変形三角盤(ペグソリティア)
投稿者:M.Hiroi - 2000年 11月 21日 20時 13分 01秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
Prolog ソースプログラムを公開していただき、ありがとうございました。
いやー、M.Hiroi
が考えていた以上のアイデアが盛り込まれていて、
もはや脱帽するしかありません(笑)。
>
ノード数は、(目安ですが)約2800倍の差があります。
おおっと、そんなに差がありましたか。幅優先探索の場合、スタート
からの探索と平行に、ゴールからも探索すると、探索する局面数(ノード数)
を劇的に減らすことができます。
(詳しい説明は、「変形版:おしどりの遊び」で行う予定です。)
となると、抜本的に枝刈りを見直さないと、反復深化で解くのは難しい
ですね。そこで、次のような方法を思いつきました。
コーナーペグが移動するためには、自分で跳ぶしかありません。この
時、跳び越すペグが必要になります。つまり、この位置にペグが無い
場合は、そこにペグを移動させてから、コーナーペグを移動させることに
なります。つまり、それだけ手数がかかるわけです。この条件も下限値と
して利用すれば、もっと効率的に枝刈りができると思われます。
とりあえず、Cプログラムを改造して試してみるつもりですが、探索
ノード数が劇的に減少しないと、別の枝刈りを考えないといけませんね。
それではまた。
99.Re.Prolog:変形三角盤(ペグソリティア)
投稿者:deepgreen - 2000年 11月 20日 23時 42分 47秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
ホームページ:http://www2.tokai.or.jp/deepgreen/
広井さん、こんばんは。deepgreenです。
Prologソースは、量が多いので私のHPの掲示板にupしました。
探索ノード数 探索時間
幅優先探索(prolog) 約95000ノード 726秒
反復深化(広井さんのC) 約28Mノード 81秒
ノード数は、(目安ですが)約2800倍の差があります。
98.Re.Prolog:変形三角盤(ペグソリティア)
投稿者:M.Hiroi - 2000年 11月 20日 21時 20分 00秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
> やっと、Prologで変形三角盤(ペグソリティア)が解けました。
>
探索方式は幅優先探索(双方向)で、約12分かかりました。
それは凄いです! たしか、deepgreen さんのPCは Pentium 133
MHz
だったと思いますが、それで12分というのは、そうとうに速いのでは
ないですか。ぜひ、プログラムを拝見したいものです。
>
反復深化もトライしていますが、時間的にちょっと無理のようです。
> Prologのデバッグは大変でこちらはまだ解けていません。
>
うまい方法があればアドバイスをお願いしたいなぁ。。。
私も挑戦してみますね。うまい方法が見つればいいのですが、
力及ばずギブアップするかもしれません。
今のところ、盤面の操作はビット演算かな、という方向で
考えています(笑)。Prolog
好きの方は、チャレンジして
みてください。
97.Prolog:変形三角盤(ペグソリティア)
投稿者:deepgreen - 2000年 11月 19日 23時 44分 22秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
こんばんは、deepgreenです。
やっと、Prologで変形三角盤(ペグソリティア)が解けました。
探索方式は幅優先探索(双方向)で、約12分かかりました。
反復深化もトライしていますが、時間的にちょっと無理のようです。
Prologのデバッグは大変でこちらはまだ解けていません。
うまい方法があればアドバイスをお願いしたいなぁ。。。
96.re^2:白黒n個ずつの蛙跳びゲーム
投稿者:M.Hiroi - 2000年 11月 16日 00時 10分 59秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
>
わかってしまえば、簡単な手順ですけど、なかなかそこまではいけない。
西山氏の移動手順を見ると簡単なように思えますが、自分で考えるとなると、
なかなか難しいことですね。まあ、そこがパズルの面白いところなのでしょ
うが、自力で解けないとやっぱりくやしいですね(笑)。
>
Prologでペグソリチア(3)をやって遊ばれてます。(なかなか
>
うまくいかないけど、こちらの方ははなんとかしたい。。。)
うーん、変形三角盤を Prolog
で解くのは大変ではないですか。
それでも、deepgreen さんなら、なんとかなるかもしれませんね。
うまくいったら、教えてください。
95.re:白黒n個ずつの蛙跳びゲーム
投稿者:deepgreen - 2000年 11月 15日 21時 01分 22秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
こんばんは、deepgreenです。
広井さん、ありがとうございます。いつもながらすばやいうごきですね。
わかってしまえば、簡単な手順ですけど、なかなかそこまではいけない。
Prologでペグソリチア(3)をやって遊ばれてます。(なかなか
うまくいかないけど、こちらの方ははなんとかしたい。。。)
94.白黒n個ずつの蛙跳びゲーム
投稿者:M.Hiroi - 2000年 11月 13日 19時 43分 36秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
蛙跳びゲームを検索したところ、白黒n個ずつの移動手順を
具体的に示し、その手順から移動回数を求めているホームページが
ありました。このほかにも、数学関連や数理パズルで面白い
ホームページがありましたので、Memorandom
にて紹介しました。
興味のある方はご覧くださいませ。
93.Re.蛙跳びゲームの最短手数は?
投稿者:M.Hiroi - 2000年 11月 12日 23時 19分 47秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
deepgreen
さん、こんばんは。
> この説明は、もし解が存在する場合にはこうなるといっているだけで、
>
本当に解が存在するかどうかはわからないようにおもいましたが、
>
いかがでしょうか?
ご指摘ありがとうございます。たしかに、そのとおりだと思います。
参考文献にあげた「ゲームにひそむ数理」を読み直してみましたが、
移動のルールを2つ示して、「それに従えばn個ずつのときも確実に
成功する」という記述しかなく、n個ずつでも解が存在することを
厳密に証明していないように思いました。
さて、実際に証明するとなると、M.Hiroi
はお手上げです(笑)。
証明できた方は、書き込みよろしくお願いしますね。
92.Re.蛙跳びゲームの最短手数は?
投稿者:deepgreen - 2000年 11月 12日 21時 05分 48秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
deepgreenです。
一言、多いようなきがしますが、この説明は、もし解が存在する場合には
こうなるといっているだけで、本当に解が存在するかどうかはわからない
ようにおもいましたが、いかがでしょうか?
91.Re.蛙跳びゲームの最短手数は?
投稿者:M.Hiroi - 2000年 11月 12日 20時 43分 44秒
ブラウザ:Mozilla/4.0 (compatible;
MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp
問題の解答です。
白黒n個ずつの移動回数は
n*n+2n となります。
説明は Puzzle DE Programming:蛙飛びゲーム を
ご覧くださいませ。