- 1 名前：１３２人目の素数さん [2008/05/02(金) 21:53:23 ]
- 面白い問題、教えてください
- 385 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:40:15 ]
- >>383
9^99
- 386 名前：１３２人目の素数さん [2008/08/16(土) 01:10:36 ]
- 9^9^9
- 387 名前：１３２人目の素数さん [2008/08/16(土) 01:17:07 ]
- 次の極限値を求めよ。（ガウス記号を使用してもよい）
lim [x + h] （xは実数、[]はガウス記号）
h→1-0
- 388 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 01:27:31 ]
- [x+1](x∈R-N)
x(x∈N)
- 389 名前：１３２人目の素数さん [2008/08/16(土) 01:38:43 ]
- xの場合分けで来ましたか。まんまやねｗ
ちなみに、場合分けなしの以下の表現を想定してました。
-[-x]
- 390 名前：１３２人目の素数さん [2008/08/16(土) 19:05:51 ]
- 今､自分を含めて100人の死刑囚がいます.この100人に対して悪い王様から次の様な問題が出されました
｢1から100までの数字(整数に限る)の中から一つの数字を紙に書きなさい
次に紙に書かれた100人全員の数字の平均の1／2を予想(整数に限る)しなさい｣
最も近い数字(整数)を予想した人だけが釈放され､残りはその場で処刑される事になっています
釈放される確率をできるだけ高くするにはどんな数字を書き､どんな数字を予想したらいいでしょうか？
ただし100人の死刑囚は互いに相談する事はできず､全員が死刑は嫌だと考え合理的な判断をするものとします
- 391 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 19:09:47 ]
- >>390
１かな？
- 392 名前：１３２人目の素数さん [2008/08/17(日) 01:39:12 ]
- >>386
正解
- 393 名前：１３２人目の素数さん [2008/08/17(日) 02:28:44 ]
- >390
単純に25かと考えてしまうけど、違うんだろうなぁ。分からない。
- 394 名前：１３２人目の素数さん [2008/08/17(日) 20:48:14 ]
- A君(自分)とB君は階段(段数は20)を使って勝負をしています
じゃんけんをしてグーで勝てば3段,チョキで勝てば5段,パーで勝てば6段上れます
じゃんけんを繰り返して先に階段の一番上に到達すれば勝ちです
今,二人は階段の下にいます.A君は勝つ確率を高める為にはグーチョキパーをどう出すのが最良でしょうか？
ただしB君も勝つ為に最良の手を出すものとします
- 395 名前：１３２人目の素数さん mailto:sage [2008/08/18(月) 16:40:34 ]
- グーチョキパーをそれぞれ以下の確率で出すときに進める期待値は315/196歩で最大
グー⇒5/14、チョキ⇒3/14、パー⇒6/14
- 396 名前：１３２人目の素数さん mailto:sage [2008/08/18(月) 16:59:46 ]
- >>390
数字、予想ともに1
もしそうでない考えをする人が何人かいたときに
もっとも予想が外れにくいから
（平均の1/2を整数で予想というのがミソだな）
- 397 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 10:25:05 ]
- >>395
相手がそういった確率出すとして
こちらも対策を練れば変わってくるのでは
そしてそれに相手が対策を練れば…
- 398 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 10:31:48 ]
- 永遠にあいこですね
- 399 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 12:03:51 ]
- >>397
そういうことを言うなら、変わることを示せよ。
- 400 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 12:15:42 ]
- >>395
には全部チョキで対抗するのがいいだろうな
- 401 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 12:16:40 ]
- >>399
変わらないことを示してくださいよベイベ〜
- 402 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 12:20:12 ]
- >>400
そしてそれには全部グーで返してループするのね
- 403 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 14:24:32 ]
- そもそも勝つための最良の手とは何だろう？
>>395は進める歩数の期待値を最大にしたが、はたしてそれでいいのだろうか？
進める歩数の期待値がどんなに大きくても、自分と相手のその期待値が等しいならば
勝つのは五分五分、ということはそれは勝つための手とはいえないのではないか？
勝つための最良の手とは、（自分の期待値-相手の期待値）が最大になるような手ではないのだろうか？
ここで、「相手も自分もどちらも最良の手を出す」ということを考えると
（自分の期待値-相手の期待値）は０にしかならないのではないか？
- 404 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 15:08:57 ]
- >>394
これって、今いる段数によって
各手を出す確率の配分が変わる？
17,18,19段目にいればどんな手で勝ってもいいし
いやそもそも、相手のいる段数も関わってくるのかな
そうすると、グーチョキパーそれぞれを出す最適な確率Pg,Pc,Ppは
Pg(n,m), Pc(n,m), Pp(n,m)というように
自分の今居る段数nと相手のいる段数mの関数にならなきゃいけないのかな
- 405 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 15:19:29 ]
- >>394 こういう問題いっつもみるけど
相手も最良の手考えるなら結局相子しかでなくね？
- 406 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 15:31:20 ]
- >>405
ランダムという要素を入れればあいこではなくなる。
もちろん統計的に長い目で見れば引き分けかもしれないが
- 407 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 15:33:06 ]
- もしくは裏のかき合いになって結局運否天賦
確率の問題としては適してない題材だな。
- 408 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 18:15:41 ]
- もし最強の手というものがあるとしたら
あいても自分も同じ手がとれる以上
相手も自分も同じ勝率にしかならない。
このことから、以下のことがわかる。
・最強の手があるとしてもたかだか５０％の勝率である。
- 409 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 18:25:34 ]
- >>408
いや逆だろ。最低50％だ。
相手も同じ手を使ってくるとは限らないし。
- 410 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 18:51:14 ]
- >>409
同じ手を使ってこない時点で最強の手ではないことになるね
- 411 名前：１３２人目の素数さん mailto:sage [2008/08/20(水) 19:01:26 ]
- 最強の手が"あったら"その勝率は50%だな
- 412 名前：404 mailto:sage [2008/08/20(水) 20:29:35 ]
- 自分がn段,相手がm段のとき
両者が最適戦略をとったときの自分の勝率を V(n,m) とする
V(n,m)を再帰的に算出し、その過程で、最適な戦略( Px(n,m)の値 )を得る。
・再起計算の初期値
V(n,m) =1 ( x=g,c,p, 20≦n, m＜20 )
V(n,m) =0 ( x=g,c,p, n＜20, 20≦m )
・V(n,m)の再帰計算
V(n,m)
= (PgPg'+PcPc'+PpPp') V(n,m)
+ PgPc' V(n+3,m) + PcPp' V(n+5,m) + PpPg' V(n+6,m)
+ PcPg' V(n,m+3) + PpPc' V(n,m+5) + PgPp' V(n,m+6)
≡ (sum[x] PxPx')V(n,m) + (sum[x,y] PxP'y C(n,m,x,y))
( ただし >>404の Px(n,m) を Pxと略記, 相手の手の確率をPx'と書く, x,y は g,c,pを渡る変数 )
C(n,m,x,y) は (x≠yのとき) 右辺PxPy'の係数, x=y の時 0 と定義
C(n,m,x,y) は 再帰計算の過程ですでに算出されている
以上から
V(n,m) = (sum[x,y] PxP'y C(n,m,x,y))/(1-sum[x] PxPx')
上記のV(n,m)を Px, Px' の関数V(Pg,Pc,Pp,Pg',Pc',Pp')とみなし
sum[x]Px=sum[x]Px'=1 の拘束条件のもと
VがPxに関して極大,Px'に関して極小となるようなPg,Pc,Pp,Pg',Pc',Pp'を見つけることで
最適戦略が得られる、と思う
- 413 名前：１３２人目の素数さん mailto:sage [2008/08/21(木) 07:59:15 ]
- 戦略をいつ決定するかとか、どのような戦略がありうるかとかを
定めない以上、数学の問題としては不備。
- 414 名前：１３２人目の素数さん mailto:sage [2008/08/21(木) 12:12:04 ]
- >>394
AはA:B:C(A+B+C=1)の確率でグー、チョキ、パーを出すとすると、
(Aが進む歩数の期待値)
=3(Aがグーを出す確率)(Bがチョキを出す確率)
+5(Aがチョキを出す確率)(Bがパーを出す確率)
+6(Aがパーを出す確率)(Bがグーを出す確率)
=3Ab+5Bc+6Ca
(Bが進む歩数の期待値)
=3(Aがチョキを出す確率)(Bがグーを出す確率)
+5(Aがパーを出す確率)(Bがチョキを出す確率)
+6(Aがグーを出す確率)(Bがパーを出す確率)
=3Ba+5Cb+6Ac
よって(Aが進む歩数の期待値)=(Bが進む歩数の期待値)のとき、
3Ab+5Bc+6Ca=3Ba+5Cb+6Ac
(6C-3B)a+(3A-5C)b+(5B-6A)c=0
6C-3B=0かつ3A-5C=0かつ5B-6A=0
A:B:C=5:6:3
よって5:6:3の確率で出せばよい
- 415 名前：１３２人目の素数さん mailto:sage [2008/08/21(木) 21:51:52 ]
- >>414
の通り5：6：3でグーチョキパーを出す予定の相手には
全部グーで挑ませてもらおう。
- 416 名前：１３２人目の素数さん mailto:sage [2008/08/22(金) 02:39:20 ]
- A=5/14, B=6/14, C=3/14
a=1, b=0, c=0
Aの進む歩数の期待値
3Ab+5Bc+6Ca=6Ca=18/14
Bの進む歩数の期待値
3Ba+5Cb+6Ac=3Ba=18/14
>>415
ジャンケンそのものの勝率は上がっても
歩数の期待値の意味では相打ちじゃね？
- 417 名前：１３２人目の素数さん mailto:sage [2008/08/22(金) 04:42:27 ]
- >>416
Bの進む歩数の期待値は
5Ba+6Cb+3Ac=5Ba=30/14
- 418 名前：１３２人目の素数さん mailto:sage [2008/08/22(金) 07:17:01 ]
- >>416
期待値を競ってるわけじゃないので>>415の勝ち。
>>417
Ｂａはグーで勝ち。
>>355
０。
- 419 名前：１３２人目の素数さん mailto:sage [2008/08/22(金) 19:44:10 ]
- >>418
期待値が同じならゲームの勝率も同じじゃね？
- 420 名前：416 mailto:sage [2008/08/22(金) 21:33:51 ]
- ゲーム勝利条件は
どちらが先に20段以上まで登ったか、だろうから
厳密には歩数の期待値が多ければ
勝率も高いとは言えないだろうけどね
実際、双方ともに17段から19段でゴール間近のときは
>>414 の戦略に対しては >>415 のようにグーを出した方がいい
やっぱりここは
自分と相手の段数に対して各々
グーチョキパーの割合を変えて決めなければいけないと思う
- 421 名前：１３２人目の素数さん mailto:sage [2008/08/22(金) 23:15:49 ]
- >>420
相手が過去に選んだ手によって現在の手を変える戦略は考えないの？
- 422 名前：１３２人目の素数さん mailto:sage [2008/08/23(土) 03:56:02 ]
- >>419
>>414がグーを出す場合は影響がないので省ける。
チョキかパーを出した場合１０回の内
パーが４回以上なら>>414の勝ちで
３回以下なら>>415の勝ち。
- 423 名前：１３２人目の素数さん mailto:sage [2008/08/23(土) 10:59:40 ]
- あ、なるほど。 ２０段以上は無駄になるからか。
- 424 名前：１３２人目の素数さん [2008/08/23(土) 21:54:56 ]
- 最強戦略が存在することの(不完全な)証明
π1,...,πnを全ての戦略をとし、V(πi,πj) を 戦略πjが戦略πiに勝つ確率とする
ゲーム開始時に確率Piで戦略πiを選択し、以後その戦略を突き通すという戦略を新たにπ(P1,...,Pn)とする
この戦略はP1,...,Pnのパラメータを適当に調整することでどんな戦略もエミュレートできる
自分が戦略π(P1,...,Pn)を用い、相手が戦略π(Q1,...,Qn)で挑んでくるとする。Qiのパラメータの選び方によらず勝率50%を達成するPjの存在を示す
行列V を i,j成分が V(πi,πj) である行列と定義する
P,Qをそれぞれ、P1,...,Pn、Q1,...,Qnを並べた縦ベクトルとする
P = V^(-1) [1/2,...,1/2]' と、すべての要素が1/2の縦ベクトルにVの逆行列をかけたものを選ぶ
(Vの正則性、Pi>0,sum[i]Pi=1が成り立つ事の証明は…まだしていない、多分 "V+V'=1を並べた行列" 等の性質を使う)
このときの自分の勝率は
V(π(Q1,...,Qn),π(P1,...,Pn)) = sum[i,j] Qi V(πi,πj)Pj = Q'VP= Q' [1/2,...,1/2] = sum[i] Qi (1/2) = 1/2
とQjの値に依存することなく常に50%になる。つまりπ(P1,...,Pn)は最強の戦略になる。
- 425 名前：１３２人目の素数さん mailto:sage [2008/08/24(日) 12:30:44 ]
- >>424
「戦略」を定義せずに議論しても全く無意味でしょ．
(1)
> π1,...,πnを全ての戦略をとし
ここから破綻している。「戦略」は有限個しかないの？
実際 π(P1,...,Pn) は任意のパラメタに対して「戦略」ではないの？
(2)
> Vの正則性
普通に「戦略」を定義するとVは正則にならないと思われる．
実際，ある「戦略」が複数の「戦略」の和で書けている場合を考えれば
逆が無いのはかなり直感的に分かる．
- 426 名前：１３２人目の素数さん mailto:sage [2008/08/24(日) 12:45:04 ]
- >>424
結局君の証明は，戦略集合 C が凸集合（「戦略」の凸結合が取れる）
ことを踏まえたうえで，
『C の端点が高々有限個（基本的な「戦略」π1, ..., πn が存在）』
を仮定している（こうすれば，その証明を正当化できる）．
しかしこの仮定は相当強くて，C がコンパクトになってしまう．
よって勝率関数 V: C×C → R が最適解を持つのはほとんど自明．
凸集合であることは通常認められる仮定だが，
端点が有限個という仮定は，ほぼ絶望的だろう．
- 427 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 19:16:45 ]
- 次のような非常に制限の強いプログラム言語X_1を考える。
1.使用できるデータ型（変数、定数とも）はC言語で言うところのunsigned charのみである。
2.使用できる演算は代入、足し算、引き算、論理演算(AND,OR,NOT,XOR,右シフト、左シフト)のみである。
3.if,while,goto,関数呼び出し等の制御構造は一切なし。プログラムは上から下へ順番に実行されるのみである。
4.unsigned char型の変数を使うことが出来る。個数に制限はない。
5.一ステップで代入一回、演算一回行うことが出来る。つまり１ステップは以下のどれか。
a=b;
a=~b;
a=b+c;
a=b-c;
a=b&c;
a=b|c;
a=b^c;
a=b<<c;
a=b>>c;
(※単項の-は禁止）
6.プログラムの終わりに次のような値を返す文を入れる。
return a;
この値をプログラムの値と呼ぶ。
7.プログラム中で使用できる定数は0x01のみである。
問題1
プログラム言語Pにおいてプログラムの値がaになるもので
最小ステップのプログラムを、Pにおけるaを返すエレガントなプログラムと呼ぶ。
0〜255についてそれぞれその値を返すX_1におけるエレガントなプログラムを一つ挙げよ。
問題2
プログラム言語X_1に対してプログラム中で使用できる定数を0x01では無く、他の値aに変えたものをプログラム言語X_aと呼ぶ。
また、エレガントなプログラムのステップ数が最も大きくなるような値をそのプログラム言語の最悪の値と呼ぶ。
プログラム言語X_0〜X_255の内、最悪の値に対するステップ数が最も小さくなるプログラム言語はどれか。
- 428 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 19:35:52 ]
- ×プログラム言語X_0〜X_255の内、最悪の値に対するステップ数が最も小さくなるプログラム言語はどれか。
○プログラム言語X_0〜X_255の内、最悪の値に対するエレガントなプログラムのステップ数が最も小さくなるプログラム言語はどれか。
- 429 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 20:17:31 ]
- 問題1って、回答は256個書かないといけないの？
- 430 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 20:21:03 ]
- 256個が面倒だったら、X_1における最悪の値どれか一つとそのエレガントなプログラム１個でいいや。
- 431 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 20:36:55 ]
- よく分からんけど
「エレガント」ってのは計算機科学では
何か厳密な定義があるの？
>>428見る限りはあるんだろうね。
そういう出題の仕方だから。
- 432 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 20:38:09 ]
- >>431
出題者じゃないが、問題文はちゃんと読もうぜ。
> 最小ステップのプログラムを、Pにおけるaを返すエレガントなプログラムと呼ぶ。
と定義がある。
- 433 名前：427 mailto:sage [2008/08/27(水) 20:57:06 ]
- >>431
グレゴリーチャイティンて言う人の知の限界って本を読んだらエレガントなLisp式という言葉が出てきた。
これはその本を読んでみて作った問題。
- 434 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 21:09:49 ]
- ああ、Kolmogorov計算量とかそういう話題ね
- 435 名前：427 mailto:sage [2008/08/27(水) 21:16:44 ]
- ちなみに俺も答え知らないので宜しくｗ
ひょっとしたらめちゃくちゃ難しい問題なのかもしれない。
とくに問題２は。
- 436 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 21:29:49 ]
- 2項演算子で枝刈りがうまくできん。キレイに解く方法あるんだろうか。
- 437 名前：427 mailto:sage [2008/08/27(水) 21:58:16 ]
- とりあえず。
「エレガントなプログラムを作るためには一度値を代入した変数に再度値を代入する必要はない。」
多分正しいと思う。
- 438 名前：427 mailto:sage [2008/08/27(水) 22:05:52 ]
- あと、もう一つ。
「エレガントなプログラムの実行過程で異なる変数が同じ値になることはない。」
これも多分正しいと思う。
- 439 名前：１３２人目の素数さん mailto:sage [2008/08/27(水) 22:28:23 ]
- X_1 で 0 を返すエレガントなプログラムってこうならない？
a=0x01;
b=0x01;
c=b-a;
return c;
以下みたいな別解もあるけど、上のもエレガントだよね？ >>438って正しいかなあ。
a=0x01;
b=~a;
c=b&a;
return c;
- 440 名前：427 mailto:sage [2008/08/27(水) 22:38:17 ]
- 紛らわしかったかもしれませんが、一応演算の引数に定数を書くのはありとします。
だから０を返すエレガントなプログラムは
a=0x01-0x01;
return a;
ということで。
return文の中での演算は禁止としましょう。
- 441 名前：427 mailto:sage [2008/08/27(水) 22:39:46 ]
- あと、２項演算の引数に同じ変数を用いるのも可とします。
a=b<<bとか。
- 442 名前：427 mailto:sage [2008/08/27(水) 23:29:30 ]
- もう一つあった。
「X_1におけるエレガントなプログラムのステップ数が１４を越えることはない。」
証明は各ビットが立った変数を用意するのに７ステップつかって、
さらに各ビットのオアをとるのに７ステップ使えばどんなデータも生成できる。
１４と言う数字はとっても荒くて、ちょっと頑張ればもっと良い数字が得られると思う。
- 443 名前：１３２人目の素数さん mailto:sage [2008/08/28(木) 09:18:36 ]
- プログラムが豊富すぎて解析が難しいが、
さらにプログラム言語を制限し、加減とビットシフトのみが許される言語で、
数値 n が k 手以下で作れるかどうかの判定がNP完全になる。
(STOC2005くらいだったと思う）
なので、きっとこの問題も、エレガントな解答があると
P=NPの解決に近づく問題だと思われる。
- 444 名前：１３２人目の素数さん mailto:sage [2008/08/28(木) 21:09:43 ]
- X_1におけるエレガントなプログラムのステップ数は7以下。
返したい値のビット表示において1の個数が5個以上の時は、
最後にNOT演算を使えばよい。
以下説明が面倒なので例だけｗ
（例）55(=00110111)を返す
a=0x01<<0x01
b=a|0x01
b=b<<a
b=b<<a
b=b|a
b=<<a
b=~b
return b
ちなみに必要な演算は<<と|と~のみ。
- 445 名前：１３２人目の素数さん mailto:sage [2008/08/28(木) 21:45:53 ]
- X_aにおけるエレガントなプログラムのステップ数は多めに見積もって11以下。
何故なら定数をCと置いて
a=C-C
b=~C
b=b+C
a=a-b
により1を生成できるため。
- 446 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 07:03:47 ]
- >>445
a=C-C
b=~a
a=a-b
で1を生成できる。
よって、
X_aにおけるエレガントなプログラムのステップ数は10以下。
- 447 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 22:10:48 ]
- 今休刊になってる古いパズル雑誌の問題ですが
あなたは役人で７種類の通貨の単位を設定できる
(１円玉、２円玉、３０円玉など)
一度に使用する硬貨を三枚以内で(同じ額の硬貨複数使用も可能)で1円〜70円の70通りを表現できるように
硬貨を設定するには、７種類の単位をどうするべきだろう？
(考え中)
最低単位の１円玉は絶対必要。また、24円玉以上が一つはないと70円が表現できないですね
- 448 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 22:46:46 ]
- >>447
>>427の問題とかなり近い気がする。
- 449 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 23:16:33 ]
- >>447
ボトムアップでやっていけば解けないかな？
ちゃんと確かめてないけどイメージはこんな感じ。
for(i=1;i<=70;i++)
{
if(iを今までの硬貨３枚以内で表現できない)
{
iを通貨の単位として設定する。
}
}
- 450 名前：449 mailto:sage [2008/08/29(金) 23:30:48 ]
- ごめん、なんか全然駄目っぽい。
>>449は忘れて。
- 451 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 23:35:46 ]
- >>447
１円玉の次に低い単位が
２円玉か３円玉か４円玉かのどれかになるんですが
分岐が多くなりそうで
- 452 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 23:37:15 ]
- まぁ樹形図書いて二時間くらいしらみつぶしにやってればできるね。
うまい解法はなさそうだし。
- 453 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:03:21 ]
- ３５円玉は必要になる予感。
- 454 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:13:56 ]
- この流れで言ってしまってはミもフタもないが
たとえ造れたとしても現在流通している以外の貨幣（紙幣）って要らないよな
一と五のみで構成された金額体系は秀逸すぎる
だからこそ五万札や十万札でなく、二千札考えた奴にはポカーンとしてしまう
ミレニアムのしょぼい魔力にとり憑かれただけだろうな
- 455 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:23:14 ]
- >>454
> 一と五のみで構成された金額体系は秀逸すぎる
そろばんやってりゃ誰にでも思いつくと思う。
> だからこそ五万札や十万札でなく、二千札考えた奴にはポカーンとしてしまう
> ミレニアムのしょぼい魔力にとり憑かれただけだろうな
これには、同意。
- 456 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:52:25 ]
- >>447
1, 4, 5, 15, 18, 27, 34で作れるな．
また，多分これ以外では不可能．
1,1+1,1+1+1,4,5,1+5,1+1+5,4+4,4+5,5+5
1+5+5,4+4+4,4+4+5,4+5+5,15,1+15,1+1+15,18,1+18,5+15
1+5+15,4+18,5+18,1+5+18,5+5+15,4+4+18,27,1+27,1+1+27,15+15
4+27,5+27,1+5+27,34,1+34,18+18,5+5+27,4+34,5+34,1+5+34
5+18+18,4+4+34,4+5+34,5+5+34,18+27,1+18+27,5+15+27,15+15+18,15+34,1+15+34
15+18+18,18+34,1+18+34,27+27,1+27+27,4+18+34,5+18+34,4+27+27,5+27+27,15+18+27
27+34,1+27+34,18+18+27,15+15+34,4+27+34,5+27+34,15+18+34,34+34,1+34+34,34+18+18
- 457 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:57:07 ]
- >>456
エレガントな解法？
どう解いたかぜひ教えていただきたい。
- 458 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 01:10:37 ]
- >>457
期待させて申し訳ないが，全くエレガントでない．
プログラムを書いて探索した．
参考までにソースコード（C言語）：
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/7662.c
- 459 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 01:20:33 ]
- >>458
数学はもうコンピュータ無しでは立ち行かない時代になってしまったのだなぁ。（大げさか
- 460 名前：447 mailto:sage [2008/08/30(土) 01:25:21 ]
- 皆様ありがとうございました
- 461 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 07:58:06 ]
- >>454
全くだ。ユーロ圏に住んでるが
2セント、20セント、2ユーロコインは無駄すぎる
- 462 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 16:10:17 ]
- >>461
ユーロ圏で日本語版のWindowsだかMacintoshだかが使える事に驚いたわ
人間の行動そのものが無駄でしかない。損得勘定無しに動ける故の欠陥かね
- 463 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 16:38:28 ]
- そもそも無駄とは何か？
文学は無駄か？
芸術は無駄か？
- 464 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 22:38:00 ]
- >>427
適当に枝刈しながら、総当りでやってみた。
問題１の最悪のステップは 7
最悪のステップの例として、例えば 71 を求めるには。
1: a = ~1 [254]
2: b = a - 1 [253]
3: c = 1 - b [4]
4: d = c << c [64]
5: e = d + c [68]
6: f = e - b [71]
7: return f
ステップ数が 7 ぐらいなら数分で解けるから、問題２も２日ぐらいあれば
解けると思う。
- 465 名前：427 mailto:sage [2008/08/30(土) 23:09:31 ]
- >>464
解けましたか。乙です。
X_1における最悪の値になにか特徴は見出せますか？
もしかしてunsigned char じゃなくてunsigned shortでもいけそうですか？
- 466 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 02:23:21 ]
- >>464
ステップ数は6の間違い？
- 467 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 07:30:27 ]
- >>465
> X_1における最悪の値になにか特徴は見出せますか？
ぱっと見、特に特徴はなさそう。
各ステップの分布は以下の通り。
Step 1: 1
Step 2: 0, 2, 254
Step 3: 3, 4, 8, 127, 252, 253, 255
Step 4:5, 6, 7, 9, 10, 12, 16, 24, 31, 32, 63, 64, 125, 126, 128, 129, 130, 240, 244, 247, 248, 249, 250, 251
Step 5: 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 33, 34, 36, 40, 48, 60, 61, 62, 65, 66, 68, 80, 96, 120, 122, 123, 124, 131, 132, 160, 176, 190,
191, 192, 193, 194, 195, 196, 208, 216, 220, 223, 224, 225, 226, 228, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 241, 242, 243, 245, 246
Step 6: 35, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 67, 69, 70, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 88, 90, 91, 92, 93, 94, 95,
97, 98, 99, 100, 101, 102, 104, 108, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 144, 152, 155, 156, 157, 158,
159, 161, 162, 163, 164, 165, 166, 168, 171, 172, 174, 175, 177, 178, 180, 181, 183, 184, 186, 187, 188, 189, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 209,
210, 211, 212, 213, 214, 215, 217, 218, 219, 221, 222, 227, 229
Step 7: 71, 74, 77, 83, 86, 87, 89, 103, 105, 106, 107, 109, 143, 145, 146, 147, 148, 149, 150, 151, 153, 154, 167, 169, 170, 173, 179, 182, 185
> もしかしてunsigned char じゃなくてunsigned shortでもいけそうですか？
俺の頭とマシンじゃとても無理。
- 468 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 07:33:21 ]
- >>466
どういう意味？
- 469 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 08:31:31 ]
- >>468
return文をステップ数にカウントするかどうかってことじゃない？
- 470 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 08:52:04 ]
- >>464
71 って 6 手で作れない？ビットシフトの仕様が違うのかしら。
1: a = ~1 [254]
2: b = 1 + 1 [2]
3: c = b << b [8]
4: d = a >> b [63]
5: e = c + d [71]
6: return e
- 471 名前：470 mailto:sage [2008/08/31(日) 10:33:53 ]
- 俺の手元の結果では >>467 のリストと
71 103 143 151 153 185 が違う（これらが6手で作れる）
あと，問題2は，最悪に対するステップ数最小は
使える定数が 29 67 98 99 101 163 226 227 の場合で，
そのステップ数は5手になった．
ちなみに最悪ステップ数最大は定数が 0 の場合で9手．
- 472 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 11:20:53 ]
- 右シフトの挙動ってunsignedとsignedで変化するからなぁ。
- 473 名前：>>467 mailto:sage [2008/08/31(日) 12:10:04 ]
- >>470-471
すまん、バグってて刈り込みすぎてた。orz
修正したら、>>471 の言う通りだった。
>>472
今回の場合は、unsigned が前提でしょ。
- 474 名前：427 mailto:sage [2008/08/31(日) 12:31:26 ]
- チャイティンさんの本によると、問題１の最悪の値はランダム性の高いビット列になるはずです。
半丁博打の親をやるとき最悪の値のビット列によって出す手を決めると負けにくいかもしれません。
そして使用するレジスタのビット幅を８から１６、３２と大きくしていって、レジスタ幅を無限大へ飛ばしたときの
最悪の値こそ真の乱数列と呼ばれるものにひょっとしたらなるかもしれません。
>>464さんの作成しているプログラムが完成したら、それは真の乱数検定アルゴリズムと呼べるかも？
万が一そうだとしたらちょっとすごいですね。
- 475 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 12:52:28 ]
- 乱数は定数とは違うだろ
乱数の種にルドルフ数を使おうとネイピア数を使おうと勝手だけど、それは乱数とは言いがたいと思われ
- 476 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 13:59:57 ]
- 何か誤解しているか、文章が不正確だと思う。とりあえず
> 問題１の最悪の値はランダム性の高いビット列になるはずです。
これは嘘。最悪の値 = 7 = 111b のランダム性は低い。
- 477 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 14:51:40 ]
- 最悪の値となる数値 (74, 77, 83, ...) も複数あるから、その並び順によって
ランダム性も違うし。
とにかく、>>474 はそのチャイティンさんの本の題名ぐらい示すべきかと。
- 478 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 15:04:18 ]
- どうでもいいけどステップ数の数え方を統一しようよ。
>>444はreturn文を数えてない。
>>427の5番目のルールを見る限り、return文は数えなくていい。
- 479 名前：474 mailto:sage [2008/08/31(日) 15:34:35 ]
- >>476-477
>>433に書きましたが知の限界という本です。
たしかにこの本の内容は私には難しめなので全部は理解してないし誤解があるかもしれません。
ランダム性の高いビット列といってるのは>>477の方の意味です。
- 480 名前：474 mailto:sage [2008/08/31(日) 15:43:06 ]
- 真の乱数というキーワードは刺激が強すぎてフレームの元かもしれませんね。
十分良い乱数、ぐらいに弱めておいたほうが無難でしょうか。
- 481 名前：474 mailto:sage [2008/08/31(日) 15:58:40 ]
- これです。
www.amazon.co.jp/知の限界-G-J-チャイティン/dp/443401238X/ref=sr_1_1?ie=UTF8&s=books&qid=1220165773&sr=8-1
- 482 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 16:28:01 ]
- >>479
>>477 に書いた通り最悪の値になる数値は複数あるからその並び順が問題になる
と思うが、そう言うことには言及してないの？
あと、そもそも 0 より 1 のビットの方が多いし。(0 は、89個、1 は 95個)
74: 01001010
77: 01001101
83: 01010011
86: 01010110
87: 01010111
89: 01011001
105: 01101001
106: 01101010
107: 01101011
109: 01101101
145: 10010001
146: 10010010
147: 10010011
148: 10010100
149: 10010101
150: 10010110
154: 10011010
167: 10100111
169: 10101001
170: 10101010
173: 10101101
179: 10110011
182: 10110110
- 483 名前：474 mailto:sage [2008/08/31(日) 16:41:43 ]
- >>482
乱数の種（プログラムに使用できる定数が0x01であること）が関係しているのかもしれません。
この定数は0x00のほうがよりふさわしいかもしれません。
あと演算もNOTを廃止してNORやNANDを追加したほうがより綺麗な議論になるかもしれません。
プログラムによって圧縮不能なビット列をランダムであると呼ぶ、と本に書いてありました。
もっともこの場合のプログラムはチューリング完全なプログラム言語での話なのですが。
私はX_1においても最小ステップ数の大きい値ほどランダムであると予想しました。
- 484 名前：474 mailto:sage [2008/08/31(日) 16:49:42 ]
- あと、真の乱数が複数あってもおかしく無いと思ってますし、
レジスタ幅が大きくなるほど0より1のビットのほうが多いといった誤差のようなものは小さくなっていくと期待しています。
どっちにしろ真の乱数は言いすぎですかね。
- 485 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 17:03:09 ]
- そこまで機能を限定したいなら、Malbolgeのcrzで同じ事をやろうか
|
 |
