- 1 名前：１３２人目の素数さん [2008/05/02(金) 21:53:23 ]
- 面白い問題、教えてください
- 357 名前：１３２人目の素数さん mailto:sage [2008/08/14(木) 23:05:28 ]
- >>356
> 断面図書いて
問題は↑ココだろ
- 358 名前：１３２人目の素数さん [2008/08/15(金) 06:16:44 ]
- 体積条件でエンベロープの接平面群を出すのがものすごく難しい。数値解析に回す。
バリエーショナルならいけるかも。
学部２年の演習問題レベル。
- 359 名前：１３２人目の素数さん [2008/08/15(金) 06:18:11 ]
- 解をしっているのは、ラーメン屋のおやじぐらいだ。
- 360 名前：１３２人目の素数さん [2008/08/15(金) 06:31:10 ]
- どんぶりにある長さの箸を縁から滑らせればいい。それが接平面
- 361 名前：１３２人目の素数さん [2008/08/15(金) 06:33:26 ]
- いっきに高３レベルに落ちてしまった・・・中３でもできるかも。
- 362 名前：１３２人目の素数さん [2008/08/15(金) 06:34:32 ]
- 体積を箸の長さで計算してから体積条件で長さを決める。
- 363 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 08:26:22 ]
- >>355
意味不明
- 364 名前：１３２人目の素数さん [2008/08/15(金) 08:30:18 ]
- U(t):v*(p-s)=0
v=(cost,sint)
p=(x,y)
s=12(cost,sint)
Ut:vt*(p-s)-v*st=0
vt*p=0
(-s,c)*(x,y)=-sintx+costy=0
cost(x-12cost)+sint(y-12sint)=costx+sinty-12=0
(y^2+x^2)cost=12x cost=12x/(x^2+y^2)
sint=12y/(x^2+y^2)
(12^2)/(x^2+y^2)=1
x^2+y^2=12^2
途中から円であとは直線の壁・・・
- 365 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 08:58:17 ]
- 微分方程式からフィボナッチの一般項求める問題が面白かった。
有名なんかな？
f(x)=∑a_nx^n を弐階まで微分して求める。
- 366 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 19:35:52 ]
- 1,2,3 の 3つの数字で演算子（重複無しで高校レベルまで）を使って出来る限り大きな数を作ってください
123など繋げるのもありです
()はいくつつかってもいいです
- 367 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 19:55:28 ]
- >>365
線形の場合に母関数を考えるのは常套手段。
- 368 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 19:55:57 ]
- (3^21)!
- 369 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 19:57:52 ]
- >>368
不正解
(2^31)!の方が大きいしね
- 370 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 20:02:03 ]
- 1/(3-2-1)
- 371 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 20:05:50 ]
- >>370
1を二つも使ってる
- 372 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 20:16:19 ]
- なんかわろた
>>370せめて-log(3-2-1)と書けよ
- 373 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 20:43:32 ]
- (3^21)!の方が大きいぜ！
- 374 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 23:46:52 ]
- おまえが作った値がｘだとしたら俺は(x)!を提出してやる。
というわけで、いくらでも大きくできるでFAだろう。
- 375 名前：１３２人目の素数さん [2008/08/15(金) 23:54:53 ]
- >>374
チッチッ！
>演算子（重複無しで・・・
- 376 名前：１３２人目の素数さん mailto:sage [2008/08/15(金) 23:58:21 ]
- 2^31!かな。
- 377 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:00:16 ]
- >>376
正解です
31!>2^31 ですしね
- 378 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:03:49 ]
- エクセルの画面出して、どこでもいいからセルを右クリックして
ハイパーリンクを選んで「ファイル・ウェブページ」の
「ブラウズしたページ」をクリックする。
- 379 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:21:47 ]
- 2^(31!) だろう。
- 380 名前：１３２人目の素数さん [2008/08/16(土) 00:29:48 ]
- 3^(21!)と比べるとどうなんだろう？
そもそも >>374 の (3^21)! は明らかにダメなのか？
- 381 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:30:45 ]
- >>379
そうですね 書き方の問題です
それで正しいです
- 382 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:31:32 ]
- >>380
これは対数をとればいいですね
21!log3 31!log2
後者が大きいのは自明です
- 383 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:36:12 ]
- ９を３つ使って作れる最大の整数を求めよ。
ただし階乗は使っちゃダメ。
- 384 名前：１３２人目の素数さん mailto:sage [2008/08/16(土) 00:37:16 ]
- >>383
当然、９を三つ使いさえすればいいんだから
9999999999999999999999999999999
とかもOKなんだな？
- 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
エレガントな解法？
どう解いたかぜひ教えていただきたい。
|
 |
