- 1 名前：デフォルトの名無しさん [2006/07/21(金) 19:10:18 ]
- パズルを出題してそれを解くプログラムを作るスレです。
みんなで楽しくアルゴリズムを考えましょう。
- 95 名前：デフォルトの名無しさん [2006/07/26(水) 02:21:43 ]
- >>92
感動した
- 96 名前：デフォルトの名無しさん mailto:sage [2006/07/26(水) 09:07:41 ]
- >>5
最初と最後を合わせなくていいのなら
#!perl
$max=shift||die"pls spec len\n";$max<1&&die"too small len\n";
($len,@list,@old,$newchar)=(1,'a');
while($len++<$max){($n,@old,@list)=(chr(0x60+$len),@list);
for($i=length($old[0]);$i>=0;--$i){
for(@old){$v=$_;substr($v,$i,0,$n);push@list,$v;}
@old=reverse@old;}}print"$_\n"for@list;
- 97 名前：デフォルトの名無しさん mailto:sage [2006/07/26(水) 17:19:44 ]
- 新しい問題キボン。
- 98 名前：デフォルトの名無しさん mailto:sage [2006/07/26(水) 17:29:01 ]
- >>5
一応、始めと終わりもつなぐようにはできたが。。。
www.uploda.org/uporg458911.cpp.html
まず単純な並びをつくって、規則性のある並びに並び替える。
文字数n=4なら
00:abcd 06:bacd 12:cabd 18:dabc
01:abdc 07:badc 13:cadb 19:dacb
02:acbd 08:bcad 14:cbad 20:dbac
03:acdb 09:bcda 15:cbda 21:dbca
04:adbc 10:bdac 16:cdab 22:dcab
05:adcb 11:bdca 17:cdba 23:dcba
という並びから、
00:abcd 01:bacd 02:cabd 03:dabc
04:abdc 05:badc 06:cadb 07:dacb
08:acbd 09:bcad 10:cbad 11:dbac
12:acdb 13:bcda 14:cbda 15:dbca
16:adbc 17:bdac 18:cdab 19:dcab
20:adcb 21:bdca 22:cdba 23:dcba
という並びにする。このとき横の並びは互いに２文字異なっている。
次に00の行、04の行・・・20の行を互いに２文字異なるように並び替えるために、
先頭の'a'を除いて、n=3の時を応用する。
あと適当にreverseする。
グレイ符号のやり方は知らん
- 99 名前：デフォルトの名無しさん mailto:sage [2006/07/26(水) 23:08:13 ]
- 01:bacd 02:cabd
なってないですよ？
- 100 名前：デフォルトの名無しさん mailto:sage [2006/07/27(木) 02:48:41 ]
- >>99
「互いに２文字異なっている」に「なってないですよ？」と言いたいのかな？
01:bacd
02:cabd
b,cを入れ替えた2文字違いだね。
ソースみると検算までしてるみたいだし、いいんでは。
5文字の時になんで始めと終わりが揃うのかフシギ
- 101 名前：デフォルトの名無しさん mailto:sage [2006/07/27(木) 05:09:13 ]
- ああ、なってますね。すみません。
A) 00:abcd 06:bacd 12:cabd 18:dabc
B) 01:abdc 07:badc 13:cadb 19:dacb
C) 02:acbd 08:bcad 14:cbad 20:dbac
D) 03:acdb 09:bcda 15:cbda 21:dbca
E) 04:adbc 10:bdac 16:cdab 22:dcab
F) 05:adcb 11:bdca 17:cdba 23:dcba
番号を付け替える必要性は良く分からないのですが、
縦方向から横方向にスキャンを変える発想はよさそうですね。
さらに、
A) を左から右
C) を右から左
E) を左から右
B) を右から左
D) を左から右
F) を右から左
で A) に戻ればうまく循環できますね。
横方向に左右逆転しながら１行とびにスキャンすると循環という
規則性ありそうです。
- 102 名前：デフォルトの名無しさん mailto:sage [2006/07/27(木) 05:18:02 ]
- 0)0000 8)1000
1)0001 9)1001
2)0010 A)1010
3)0011 B)1011
4)0100 C)1100
5)0101 D)1101
6)0110 E)1110
7)0111 F)1111
0) -> 8) -> C) -> 4) -> 6) -> E) -> A) -> 2) -> 3) -> B) -> F) -> 7) -> 5) -> D) -> 9) -> 1) ->
とかで戻ってこれるのですが
これでグレイコードになってるのかどうか不明
- 103 名前：デフォルトの名無しさん mailto:sage [2006/07/27(木) 05:35:00 ]
- 0 - 8 - A - 2 - 6 - E - C - 4 - 5 - D - F - 7 - 3 - B - 9 - 1
の方が規則性あるかな
- 104 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 18:32:45 ]
- Ｎ*Nの格子状のグラフの部分グラフのうち連結なものの個数を数えよ。
エレガントな解法があるのかどうかは知りません。
- 105 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 18:39:42 ]
- さめがめとかマインスイーパーみたいなアルゴリズムかな
- 106 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 19:11:13 ]
- 数学者のオナニーみたいな問題だな
- 107 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:07:03 ]
- 塗りつぶしのアルゴリズム使えば超簡単だな
- 108 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 00:17:47 ]
- >>107
詳しく。
- 109 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 01:07:55 ]
- ノードと方眼紙の各マスが対応するから
ノードの連結＝マスの隣接 → 塗りつぶしで区分け可能
- 110 名前：デフォルトの名無しさん [2006/07/29(土) 06:36:22 ]
- おもしろい問題くれよ！
- 111 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 06:44:41 ]
- D言語用のFrameWorkを作れ
- 112 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 11:35:21 ]
- >>111
乞食は死ね
- 113 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 14:28:25 ]
- >>111
それ何てパズル？
- 114 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 21:35:32 ]
- 数独ってＮＰ完全なんだってね。
数学板でやってた。
- 115 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 22:42:07 ]
- 他のどんなＮＰ問題を数独に帰着させられるんだろうな
- 116 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 23:10:13 ]
- SEND
+) MORE
----------
MONEY
- 117 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 23:24:22 ]
- なるほど、確かに数独と似ている・・・。
FIVE + SEVEN + ELEVEN + TWELVE + FIFTEEN + TWENTY = SEVENTY
- 118 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 23:40:49 ]
- SEND+MORE=MONEYは一意に解けてしまうからプログラムのネタにならなくて詰まらん。
語呂合わせにはなってないけど、A*BCDE=FGHIJを解く方が(個人的には)余程面白い。
- 119 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 23:41:12 ]
- 答えあるのか？
- 120 名前：118 mailto:sage [2006/07/29(土) 23:45:22 ]
- >>119
数学的には(漏れには)解けなかったけど、単一解があるよ。
#記憶に間違いがなければw
- 121 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 23:55:33 ]
- 一意に解けてしまうのはつまんないのではなかったのか
- 122 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 23:57:09 ]
- 禿和露酢
- 123 名前：118 mailto:sage [2006/07/30(日) 01:28:13 ]
- んにゃ、数学的に解けなかったところに意味を見出しているだけだから。
例えば、SEND+MORE=MONEYだとS=9, M=1から始まって式を展開していけばすぐに求まってしまうから。
#まぁ、笑う前にやって味噌。
- 124 名前：デフォルトの名無しさん mailto:sage [2006/07/30(日) 03:40:29 ]
- >>117 のはなしは？
- 125 名前：デフォルトの名無しさん [2006/07/30(日) 05:12:59 ]
- 覆面算と数独が本質的に同じって話だが、何か？
- 126 名前：デフォルトの名無しさん mailto:sage [2006/07/30(日) 11:39:00 ]
- >>118 がNP完全で >>116 はNP完全ではないという意味でよろしかったでしょうか？
- 127 名前：デフォルトの名無しさん mailto:sage [2006/07/30(日) 18:12:30 ]
- そんな話はしていないのでは・・・
- 128 名前：デフォルトの名無しさん mailto:sage [2006/08/10(木) 21:49:28 ]
- >>12
空いてる枡を─│└┘┌┐のいずれかで埋めて
全パターンやれば解けそう。
バックトラックでどこまで計算量削れるか？
- 129 名前：デフォルトの名無しさん mailto:sage [2006/08/11(金) 09:21:09 ]
- >>12はナンリン（ナンバーリンク）という同じルールのパズルがあって
下のスレでそれを解くプログラムが既に作られている。
【解答】パズルのプログラミング【作成】
hobby8.2ch.net/test/read.cgi/puzzle/1092459010/
- 130 名前：デフォルトの名無しさん mailto:age [2006/10/25(水) 21:04:39 ]
- だれか次の言語をBrainFuckにコンパイルするコンパイラ作って。
> ポインタをインクリメント
< ポインタをデクリメント
+ ポインタが示すメモリ位置のデータをインクリメント
- ポインタが示すメモリ位置のデータをデクリメント
. ポインタが示すメモリ位置のデータを出力
, ポインタが示すメモリ位置のデータに入力
[ ポインタが示すメモリ位置のデータがヌルなら対応する]までジャンプ
] ポインタが示すメモリ位置のデータがヌルじゃないなら対応する[までジャンプ
@n (nは整数)ポインタをn番地に設定
BrainFuckのスレ
pc8.2ch.net/test/read.cgi/tech/1036013915/l50
- 131 名前：デフォルトの名無しさん [2006/10/31(火) 20:58:56 ]
- 単位円周上にＮ個の点が与えられたときに、
そのうちのＭ個の点を頂点とする多角形の取りうる最大面積の値を求めよ。
仕様：
入力データは、最初の行はＮとＭの値が半角空白で区切られており、
直後に単位円周上の点のＸ座標とＹ座標の値が半角空白で区切られた行がＮ行続く。
解は小数点以下３桁以上の精度で１行に出力。
入力例：
4 3
1.0 0.0
0.7071 0.7071
0.0 1.0
-1.0 0.0
解答例：
1.000
- 132 名前：デフォルトの名無しさん [2006/10/31(火) 20:59:45 ]
- 漏れは４時間考えたが結局ヒントもらうまで解けなかったorz
- 133 名前：デフォルトの名無しさん mailto:sage [2006/11/01(水) 02:43:26 ]
- >>131
超典型 DP
- 134 名前：デフォルトの名無しさん [2006/11/02(木) 01:15:21 ]
- どうやって小問題に分割するか
- 135 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 02:00:39 ]
- 素数が無限個存在することを1行で証明せよ
- 136 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 11:15:53 ]
- (有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数
- 137 名前：デフォルトの名無しさん [2006/11/03(金) 00:04:17 ]
- >>136
3*5+1=16
- 138 名前：デフォルトの名無しさん mailto:sage [2006/11/03(金) 01:34:36 ]
- (有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数の倍数
- 139 名前：デフォルトの名無しさん [2006/11/03(金) 01:41:24 ]
- 何の証明にもなってないという事実は伏せておこう
- 140 名前：デフォルトの名無しさん mailto:sage [2006/11/03(金) 02:06:37 ]
- 望むだけ長く区間素数が現れないような条件を求めよ。
- 141 名前：デフォルトの名無しさん [2006/11/03(金) 02:34:35 ]
- ここは数学のスレではありません＞＜
- 142 名前：デフォルトの名無しさん mailto:sage [2006/11/05(日) 04:03:11 ]
- >>136
(ある素数Ｎ以下の全素数の積)+1 = 左辺の素数の集合に含まれない素数
- 143 名前：デフォルトの名無しさん [2006/11/08(水) 21:13:38 ]
- それが何故なのかを説明しないと証明にならんっつーの
- 144 名前：デフォルトの名無しさん mailto:sage [2006/11/09(木) 09:45:36 ]
- 素数の定義より明らか
|
 |
