06/07/21 19:10:18
パズルを出題してそれを解くプログラムを作るスレです。
みんなで楽しくアルゴリズムを考えましょう。
2:デフォルトの名無しさん
06/07/21 19:13:50
ずるしてらくしてかれいに２げっと
3:1
06/07/21 19:24:30
では数学板で見かけた問題。
ネズミが一匹、無限の広さをもつ碁盤の上に居る。
プレーヤーは一ターンの間にネズミの居ない任意の座標にブロックを一つおくことができる。
ネズミは一ターンの間に上下左右のいずれかの方向に一歩動くことができる。
ただし、ブロックのある座標には移動できない。
ネズミの四方がブロックで囲まれ、一歩も動けない状態になればプレーヤーの勝ち。
ネズミがいつまでも逃げることができればネズミの勝ち。
プレイヤーの先行として、ゲームはどちらが勝つか。
このゲームはプレイヤーが勝つことが数学板で証明されていたので
最短手数を求めてください。
4:1
06/07/21 19:27:35
数学板の面白い問題おしえて～な 11問目の381に載ってました。
5:1
06/07/21 21:40:58
もう一問だしときますね。
ｎ個の異なる文字を並べてできる長さnの文字列を考える。
このような文字列はn!個あるがこのn!個の文字列を
一列に並べ、隣り合う文字列がちょうど2文字だけ異なるように
するアルゴリズムを作れ。
たとえば3文字なら
abc
acb
bca
bac
cab
cba
と並べれば隣り合う文字列がちょうど2文字違うようになります。
6:デフォルトの名無しさん
06/07/22 00:05:28
>>5
それって任意のnに対して可能なの？
7:デフォルトの名無しさん
06/07/22 02:33:58
グレイ符号が応用できそうな予感
8:デフォルトの名無しさん
06/07/22 04:39:25
スマソ
意味が分からん
9:デフォルトの名無しさん
06/07/22 04:46:26
n = 4 で普通に並べてみた
abcd
abdc
acbd ↑ ここがだめ
acdb
adbc ↑ ここがだめ
adcb
bacd ↑ ここがだめ
badc
bcad ↑ ここがだめ
bcda
bdac ↑ ここがだめ
bdca
cabd ↑ ここがだめ
cadb
cbad ↑ ここがだめ
cbda
cdab ↑ ここがだめ
cdba
dabc ↑ ここがだめ
dacb
dbac ↑ ここがだめ
dbca
dcab ↑ ここがだめ
dcba
こういう意味か
確かにグレイコードで置き換えたらうまくいくと思う
10:デフォルトの名無しさん
06/07/22 14:57:08
普通に全通りの並べ方をしらみつぶしにやればいいんじゃね？
計算時間？しらね。
11:デフォルトの名無しさん
06/07/22 15:54:30
単純に、隣り合う二文字を入れ替えた。
#include <stdio.h>
#include <string>
using namespace std;
int factorial(int i) {
if(i==0) {
return 1;
}
else if(i>0) {
return i*factorial(i-1);
}
else {
exit(1);
}
}
void main() {
int i,n;
string s;
char t;
printf("enter the number of sequence\n");
scanf("%d",&n);
for(i=0;i<n;i++) s+=(char)(i+'a');
for(i=0;i<factorial(n);i++) {
printf("%d: %s\n",i,s.c_str());
t=s[i%n]; s[i%n]=s[(i+1)%n]; s[(i+1)%n]=t;
}
}
12:デフォルトの名無しさん
06/07/22 16:13:31
誰かこれ解くプログラム書いて。
URLﾘﾝｸ(yoshimaruxxx.web.fc2.com)
13:デフォルトの名無しさん
06/07/22 16:28:00
>>11
実行してみたけど重複する文字列があるみたい。
14:デフォルトの名無しさん
06/07/22 16:34:32
これって結局階乗を出す問題だよね。
交換だけで階乗が出せればかなり有名になっているはずだから、スマートな解法はないと思う。
15:デフォルトの名無しさん
06/07/22 16:41:16
>>14
階乗を出すってどういうこと？
16:デフォルトの名無しさん
06/07/22 17:06:32
順列ですた。
という事で、順列を交換だけで出せるのって話です。
17:デフォルトの名無しさん
06/07/22 17:12:59
文字列を頂点として２文字違う文字列に辺があるグラフを考えれば
ハミルトン閉路問題に帰着される。
辺の数は結構多いし、ハミルトン閉路はありそうにも思えるがさて。
18:デフォルトの名無しさん
06/07/22 17:29:42
グラフの作成に O(n!) かかるのでは。
結局しらみつぶしと同じ予感。
19:デフォルトの名無しさん
06/07/22 17:45:15
もともと出力のサイズがn!なんだからそれは気にすること無い。
しらみつぶしの計算量は(n!)!なんだから全然違う。
20:デフォルトの名無しさん
06/07/22 18:10:52
普通出力ってひとまとめで一処理とみなす気が
21:デフォルトの名無しさん
06/07/22 20:13:02
出力の大きさがO(n!)なんだからどんなにがんばったって計算量がO(n!)を下回ることはない。
出力をひとまとめで一処理なんておかしいよ。
22:デフォルトの名無しさん
06/07/22 21:07:22
n文字の場合の結果をつかってn+1文字の場合を解けないものか。
23:デフォルトの名無しさん
06/07/22 23:37:12
, -: ': : : : : : :"⌒:￣:` : ､
／: : : : へ._ : : : :へ、: : : ＼
__,く;へ＿: : :| : : : : : : : ＼￣:ヽ、＼
. /:__/: : :/: : |: :ｌ: : : : : : : : ＼.: :ヽ: ヽ
/_//: : :/: / :|: ｌ: : :ヽ: ヽ: : : : ヽ: : ヽﾊ
／/: /: : : : : |: : ｌ: : |: : |: : ヽ: :ヽ: : ヽ: : : : : : :ヽ: : ヽﾊ
. /:/: /: /: ｌ: |: :,|: : ﾊ: : |: : : ヽ: :ヽ: : ヽ: : : : : : :ヽ : ヽ|
//: : ｌ: :ｌ: ::|: :|: :|: : :| ヽ ｌヽ : : :＼: ヽ.: :＼: : : ヽ:ﾊ: : : |
| ｌ: : |: :|: : |: :|: ハ__,L. ヽ ＼"￣｢ T ト- ､;_: : : : :|: : :.|
| |: : |: :|: : |: ;|イ｢ ヽ| ＼´＼ヽ __｣__ｉ.＼ ＼ : : |: : :| もう・・・仕方の無いことばかり言って・・・
| |: : |: :|: : くｖ' _｣＝ｉ ヽ ／｢ ｉ::::::o｢＼|ヽﾄ: |: :/|
ｉ ｌ: : ﾊ: ｌ: : :.ト / {:::::::〉 ﾚﾍ:.::::}ﾟｉ|/|: ::| .}ﾚ': :|
∨:| Ｖﾍ: ::ﾍヽ ｖﾍ:ﾊ ..く_二ｉつ|: :.:ﾚ: :| : :|
ヽヽ∨へ:ﾊ ヾツ /／//ﾊ:/::|: :|: : :|
∧: :ｉ:ﾍ.ｌ // ` /: {:::::|: :ｌ: : ﾊ
/:/: ∧: ＼ ｡ ,.ｲ:|: :|::ｉ:::|: :ｌ: ::∧
//: : :}: ヽ`ｉ:: ､. ／ .|::| :|:::ｉ::::|: ｉ:: : ∧
://: : : ハ: ヽ::::::ノＴ ' ‐ ' |::|: :Ｖ::::ｉ∧: : : : ﾍ
/／: : ノ二 ヽ: :＼ 〈ｰ ､ ＿＿___,ﾄﾍ: :∨::ｉ::∧: : : :.∧
／/:/ /⌒ ＼ ヽト､: :ヽ＼__＿＿___ハ ＼:∨ﾊ:::∧: : : :} ＼
24:デフォルトの名無しさん
06/07/23 00:17:11
>>3
ネズミの問題は２３手詰めと出た。この手順はピンとこないけど、うまく収束している。
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼┼┼┼ ┼┼●┼┼ ┼┼●○┼ ┼┼●○┼ ┼┼●┼┼ ┼┼●┼┼
┼┼┼○┼ ┼┼┼○┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼○┼ ┼┼┼○┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼●
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼○┼ ┼┼┼○┼ ┼┼○┼┼ ┼●○┼┼
┼┼┼○● ┼┼┼○● ┼┼┼┼● ┼┼┼┼● ┼┼┼┼● ┼┼┼┼●
┼┼┼┼┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼
┼●┼┼┼ ┼●┼┼┼ ┼●┼┼┼ ┼●┼┼┼ ┼●┼┼┼ ┼●●┼┼
┼┼○┼● ┼┼○┼● ┼┼┼┼● ┼┼┼┼● ┼┼○┼● ┼┼○┼●
┼┼┼●┼ ┼●┼●┼ ┼●○●┼ ┼●○●┼ ┼●┼●┼ ┼●┼●┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼
┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼
┼●●┼┼ ┼●●┼┼ ┼●●┼┼ ┼●●●┼ ┼●●●┼ ┼●●●┼
┼○┼┼● ●○┼┼● ●┼○┼● ●┼○┼● ●┼┼┼● ●┼●┼●
┼●┼●┼ ┼●┼●┼ ┼●┼●┼ ┼●┼●┼ ┼●○●┼ ┼●○●┼
┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼
25:デフォルトの名無しさん
06/07/23 00:22:09
自己レス>>24
ただし、ブロックの置き方はネズミの八方のみしか探索していないので。
26:デフォルトの名無しさん
06/07/23 02:40:48
正解なのかどうかすらわからん
27:デフォルトの名無しさん
06/07/23 09:05:40
テストケースの組み合わせを自動生成してくれるプログラム作ってくれんか？
たとえば入力を2,3,3としたら以下のような文字を出力してくれるような。
言葉ではうまく言えないが全ての組み合わせを生成してくれるやつ。
○、○、○、○、○、○、○、○、○、 、 、 、 、 、 、 、 、
、 、 、 、 、 、 、 、 、○、○、○、○、○、○、○、○、○
○、○、○、 、 、 、 、 、 、○、○、○、 、 、 、 、 、
、 、 、○、○、○、 、 、 、 、 、 、○、○、○、 、 、
、 、 、 、 、 、○、○、○、 、 、 、 、 、 、○、○、○
○、 、 、○、 、 、○、 、 、○、 、 、○、 、 、○、 、
、○、 、 、○、 、 、○、 、 、○、 、 、○、 、 、○、
、 、○、 、 、○、 、 、○、 、 、○、 、 、○、 、 、○
28:27
06/07/23 09:07:13
ちょっとずれた。
でも雰囲気はわかるよね。
29:24
06/07/23 09:24:01
>>26
それでは、実際にやってみましょう。必ず２３手以内に詰ませてみせます。
一手目
┼┼┼
●○┼
┼┼┼
誰でもいいです。どうぞ
30:デフォルトの名無しさん
06/07/23 09:25:34
>>24
それ、探索にどのくらい時間かかるんだ？
ネズミの移動方向を入力できるようにして up してくれよ。
面白いゲームになりそうじゃね？ｗ
31:デフォルトの名無しさん
06/07/23 09:26:21
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼●┼┼ ┼┼●┼┼
┼┼┼○┼ ┼┼┼○┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼○┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
脱出成功
32:24
06/07/23 09:28:47
>>31
実はそれでも詰みますが、変化が複雑（時間がかかる）なので
>>29からどうぞ
33:デフォルトの名無しさん
06/07/23 09:38:49
┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼
●○┼┼┼ ●┼○┼┼
┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼
34:24
06/07/23 09:40:46
>>30
Javaで書いてしまいましたが、１時間ぐらいで解けました。
３手目
┼┼┼┼┼
┼┼┼●┼
●┼○┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
書き込みを楽にする為、最後の局面のみにしましょう。
35:デフォルトの名無しさん
06/07/23 09:43:10
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼┼┼┼
┼┼┼┼┼
でもさ、>>31 のが時間かかるってことは23手で詰まないっていう意味じゃないの？
36:24
06/07/23 09:44:12
３手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼●┼┼
┼┼┼┼┼
いえ、探索に時間がかかります。
37:デフォルトの名無しさん
06/07/23 09:44:34
そういえばアレニウスの円っていう問題もあったね
38:デフォルトの名無しさん
06/07/23 09:45:22
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼┼
┼┼┼┼┼
ジダンの華麗なダンス炸裂してほしい
39:デフォルトの名無しさん
06/07/23 09:46:22
>>34
１時間は長いな。
最初の数手をテーブルにしたらインタラクティブな待ち時間にならんかな。
ネズミ側だけでいいんだけど。
40:デフォルトの名無しさん
06/07/23 09:46:54
既に２手サバ読まれてるし
41:24
06/07/23 09:47:04
７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼●
┼┼┼┼┼
じつは４手目は最善手ではありません。
42:デフォルトの名無しさん
06/07/23 09:48:23
ほっほー
43:デフォルトの名無しさん
06/07/23 09:51:10
ネズミは曲がるとかなり手数損しそうですね
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼┼┼
┼┼●┼●
┼┼┼○┼
ジダン突破
44:デフォルトの名無しさん
06/07/23 10:00:19
４手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
45:24
06/07/23 10:05:00
>>40
ばれましたか。
５手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
46:デフォルトの名無しさん
06/07/23 10:06:14
４手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
47:24
06/07/23 10:08:02
５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
>>44は最善手の一つですがこちらは違います。
48:デフォルトの名無しさん
06/07/23 10:08:11
６手目
┼┼┼┼┼
┼┼┼●○
●┼┼┼●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
49:24
06/07/23 10:08:53
５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼●┼┼┼
┼┼┼┼┼
┼┼┼┼┼
50:デフォルトの名無しさん
06/07/23 10:11:27
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
51:24
06/07/23 10:12:54
７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼●┼
┼┼┼┼┼
52:デフォルトの名無しさん
06/07/23 10:28:22
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼┼○
┼┼┼●┼
┼┼┼┼┼
53:24
06/07/23 10:38:19
┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼
┼┼┼●┼┼┼ ┼┼┼●┼┼┼ ┼┼┼●┼┼┼ ┼┼┼●┼┼┼
●┼┼┼●┼┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼
┼┼┼┼○┼┼ ┼┼┼┼○┼┼ ┼┼┼┼┼○┼ ┼┼┼┼┼○●
┼┼┼●┼┼┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼●┼
┼┼┼●┼┼┼ ┼┼┼●┼┼● ┼┼┼●┼○● ┼┼┼●┼○●
●┼┼┼●○┼ ●┼┼┼●○┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼
┼┼┼┼┼┼● ┼┼┼┼┼┼● ┼┼┼┼┼┼● ┼┼┼┼┼┼●
┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼
┼┼┼●┼┼● ┼┼┼●●┼● ┼┼┼●●┼● ┼┼┼●●┼●
●┼┼┼●○┼ ●┼┼┼●○┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼
┼┼┼┼┼┼● ┼┼┼┼┼┼● ┼┼┼┼┼○● ┼┼┼┼●○●
┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼
┼┼┼●●┼● ┼┼┼●●┼● ┼┼┼●●○● ┼┼┼●●○●
●┼┼┼●○┼ ●┼┼┼●○● ●┼┼┼●┼● ●┼┼┼●●●
┼┼┼┼●┼● ┼┼┼┼●┼● ┼┼┼┼●┼● ┼┼┼┼●┼●
┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
これで終わりにします。ちょいとでしゃばりすぎた感がありますので
54:デフォルトの名無しさん
06/07/23 11:03:33
明らかに勝負が見えたあとの収束が遅いように思います
55:デフォルトの名無しさん
06/07/23 11:05:27
>>27
意味が分からないんですけど
解説してください
56:27
06/07/23 11:44:04
うーん俺がアホなせいでなかなかうまく説明できないんだが。
テストというのは入力がいくつかあってその選択肢の組み合わせを考える。
>>27の例は入力が３つあって、一番目は選択肢が２つ、２番目、３番目は選択肢が３つあると思って。
で、１行目、２行目は一番目の入力の選択肢をどちらを選ぶかを表している。
３，４，５行目は２番目の入力の選択肢のうちどれを選ぶかを表している。
６，７，８行目は３番目の入力の選択肢のうちどれを選ぶかを表している。
各列はひとつのテストケースを表している。
たとえば一行目は一番目の入力＝１、２番目の入力＝１、３番目の入力＝１
５行目は一番目の入力＝１、２番目の入力＝２、３番目の入力＝２といった感じ。
で、選択肢の組み合わせを網羅的に生成してほしい。出力は>>27のフォーマットで。
うまく説明できたかわからんがこんな感じです。
57:デフォルトの名無しさん
06/07/23 16:32:42
>>56
こんなんでいいかな、
URLﾘﾝｸ(www.uploda.org)
>>27は1列ごとにテストケース1パターンを表してるようだけど、
それもフォーマット？
めんどいから、1行1ケース表示にしたけど。
つか、パズルじゃないだろ
58:デフォルトの名無しさん
06/07/23 16:35:53
#include <string>忘れてた
59:デフォルトの名無しさん
06/07/23 16:37:40
修正
URLﾘﾝｸ(www.uploda.org)
60:27
06/07/23 16:47:41
そうそう。そんな感じなんですが、何とか１列１テストケースになりませんかね。
そのほうが何かとありがたいんですが。
61:デフォルトの名無しさん
06/07/23 16:49:19
>>56
主語や目的語を省略しすぎなんだよ
自分だけが分かってて相手が分かってないときに説明するんだから
62:27
06/07/23 16:55:52
>>61
精進します。
63:デフォルトの名無しさん
06/07/23 17:03:17
ネズミが８方向に動けたら、つかまんなくなりそう。
どうなんだろ。
64:デフォルトの名無しさん
06/07/23 18:05:30
>>63
それじゃパズルとして綺麗じゃないような気がする（移動距離が長いものと短いものがあってイヤ）
どうせならヘックスでやってみるとおもしろいかもしれない。
65:デフォルトの名無しさん
06/07/23 18:24:24
>>60
１列１テストケースにしたよ。
URLﾘﾝｸ(www.uploda.org)
ところで、どうしてここで質問？質問スレ行くといいよ。
66:27
06/07/23 18:29:29
>>65
いや、考えようによってはパズルといえなくもないかなーと。
これからは注意します。
ありがとうございました。
67:デフォルトの名無しさん
06/07/23 18:31:13
あのな、パズルってのは（ｒｙ
68:デフォルトの名無しさん
06/07/23 18:34:46
HEXのねずみ捕り面白そうだけど
ここで表現するの自体が難しそう
69:デフォルトの名無しさん
06/07/23 19:22:03
3x3のマス目で行なうマスターマインド（値は重複しない1～9）の解答を得る
アルゴリズムってできないでしょうか？
3手で正解を得られるようなんですが。
難しくてｻﾊﾟｰﾘわからん。
70:デフォルトの名無しさん
06/07/23 19:29:06
最低限ルールぐらい書いてもらおうか
71:デフォルトの名無しさん
06/07/23 19:53:08
どんなルールか知らんが３ｘ３ならしらみつぶしで終わりそうな予感。
72:デフォルトの名無しさん
06/07/23 22:11:20
○○○
○○○
○○○
１２３
４５６
７８９
場所 1
数字 9
73:デフォルトの名無しさん
06/07/23 22:14:37
７８９
４５６
１２３
場所 1
数字 9
74:デフォルトの名無しさん
06/07/23 22:15:38
９８７
６５４
３２１
場所 4
数字 9
75:デフォルトの名無しさん
06/07/23 22:17:46
９７８
６４５
３１２
場所 8
数字 9
76:デフォルトの名無しさん
06/07/23 22:18:44
糞スレ化している・・・
77:デフォルトの名無しさん
06/07/23 22:25:33
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
HEXなってないかな・・・
78:デフォルトの名無しさん
06/07/23 23:38:46
盤だけ表示できても駒が
79:デフォルトの名無しさん
06/07/23 23:53:55
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
どぞ
80:デフォルトの名無しさん
06/07/24 07:13:27
六角形の碁盤
ｽﾚﾘﾝｸ(gamestones板)l50
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜ ｜ ｜ ｜ ｜ ｜○｜ ｜ ｜ ｜ ｜ ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜ ｜ ｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
81:デフォルトの名無しさん
06/07/24 07:34:18
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜ ｜ ｜ ｜ ｜○｜ ｜ ｜ ｜ ｜ ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜ ｜ ｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
82:デフォルトの名無しさん
06/07/24 13:34:38
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜ ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜ ｜ ｜ ｜ ｜○｜ ｜ ｜ ｜ ｜ ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜ ｜ ｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
83:デフォルトの名無しさん
06/07/24 13:36:11
これ対称性を考えると意外とパターン少ないな
84:デフォルトの名無しさん
06/07/24 17:49:24
ＨＥＸだとつかまんない予感。
85:デフォルトの名無しさん
06/07/25 02:00:43
オセロのパーフェクト決着の最短推移と最長推移をそれぞれ一種類ずつ求めよ。
盤面の左下のマスを [0,0] とし、はじめ [3,3] に置いてある色のプレイヤーが先攻とする。
ゲームの推移の記法は [3,5] [4,6] ... とする。
・・・こういうのはパズルとは言わないかも
86:デフォルトの名無しさん
06/07/25 02:08:54
>>5
こんなかんじか。
URLﾘﾝｸ(www.uploda.org)
この問題って、始めの文字列と終わりの文字列も「ちょうど2文字だけ異なる」っていう条件を満たさなければならない？
多分可能だが、まだやっていない。
87:デフォルトの名無しさん
06/07/25 03:06:56
満たすべきだろうね
グレイコードから作る方法なら満たせるでしょう
88:デフォルトの名無しさん
06/07/25 16:28:49
>>85
NP問題の予感
89:デフォルトの名無しさん
06/07/25 18:05:54
ところでＨＥＸの座標ってどう表すの？
90:デフォルトの名無しさん
06/07/25 18:08:35
>>88
むしろＰＳＰＡＣＥ問題の予感。
91:デフォルトの名無しさん
06/07/25 18:17:48
>>89
普通の表の片方の斜めだけに進めるようにする。
■■□
■☆■
□■■
■：進めるマス
□：進めないマス
92:デフォルトの名無しさん
06/07/25 18:19:40
--■■□
-■☆■
□■■
表示はこう
93:90
06/07/25 20:35:07
いや、俺の勘違い。やっぱＰＳＰＡＣＥじゃなくてＮＰかも。
94:デフォルトの名無しさん
06/07/25 21:36:03
>>5の問題にグレイコードを応用するのは言うほど簡単じゃないとおも。
なかなか手ごわい。
95:デフォルトの名無しさん
06/07/26 02:21:43
>>92
感動した
96:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/07/26 17:19:44
新しい問題キボン。
98:デフォルトの名無しさん
06/07/26 17:29:01
>>5
一応、始めと終わりもつなぐようにはできたが。。。
URLﾘﾝｸ(www.uploda.org)
まず単純な並びをつくって、規則性のある並びに並び替える。
文字数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:デフォルトの名無しさん
06/07/26 23:08:13
01:bacd 02:cabd
なってないですよ？
100:デフォルトの名無しさん
06/07/27 02:48:41
>>99
「互いに２文字異なっている」に「なってないですよ？」と言いたいのかな？
01:bacd
02:cabd
b,cを入れ替えた2文字違いだね。
ソースみると検算までしてるみたいだし、いいんでは。
5文字の時になんで始めと終わりが揃うのかフシギ
101:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/07/27 05:35:00
0 - 8 - A - 2 - 6 - E - C - 4 - 5 - D - F - 7 - 3 - B - 9 - 1
の方が規則性あるかな
104:デフォルトの名無しさん
06/07/28 18:32:45
Ｎ*Nの格子状のグラフの部分グラフのうち連結なものの個数を数えよ。
エレガントな解法があるのかどうかは知りません。
105:デフォルトの名無しさん
06/07/28 18:39:42
さめがめとかマインスイーパーみたいなアルゴリズムかな
106:デフォルトの名無しさん
06/07/28 19:11:13
数学者のオナニーみたいな問題だな
107:デフォルトの名無しさん
06/07/28 23:07:03
塗りつぶしのアルゴリズム使えば超簡単だな
108:デフォルトの名無しさん
06/07/29 00:17:47
>>107
詳しく。
109:デフォルトの名無しさん
06/07/29 01:07:55
ノードと方眼紙の各マスが対応するから
ノードの連結＝マスの隣接 → 塗りつぶしで区分け可能
110:デフォルトの名無しさん
06/07/29 06:36:22
おもしろい問題くれよ！
111:デフォルトの名無しさん
06/07/29 06:44:41
D言語用のFrameWorkを作れ
112:デフォルトの名無しさん
06/07/29 11:35:21
>>111
乞食は死ね
113:デフォルトの名無しさん
06/07/29 14:28:25
>>111
それ何てパズル？
114:デフォルトの名無しさん
06/07/29 21:35:32
数独ってＮＰ完全なんだってね。
数学板でやってた。
115:デフォルトの名無しさん
06/07/29 22:42:07
他のどんなＮＰ問題を数独に帰着させられるんだろうな
116:デフォルトの名無しさん
06/07/29 23:10:13
SEND
+) MORE
----------
MONEY
117:デフォルトの名無しさん
06/07/29 23:24:22
なるほど、確かに数独と似ている・・・。
FIVE + SEVEN + ELEVEN + TWELVE + FIFTEEN + TWENTY = SEVENTY
118:デフォルトの名無しさん
06/07/29 23:40:49
SEND+MORE=MONEYは一意に解けてしまうからプログラムのネタにならなくて詰まらん。
語呂合わせにはなってないけど、A*BCDE=FGHIJを解く方が(個人的には)余程面白い。
119:デフォルトの名無しさん
06/07/29 23:41:12
答えあるのか？
120:118
06/07/29 23:45:22
>>119
数学的には(漏れには)解けなかったけど、単一解があるよ。
#記憶に間違いがなければw
121:デフォルトの名無しさん
06/07/29 23:55:33
一意に解けてしまうのはつまんないのではなかったのか
122:デフォルトの名無しさん
06/07/29 23:57:09
禿和露酢
123:118
06/07/30 01:28:13
んにゃ、数学的に解けなかったところに意味を見出しているだけだから。
例えば、SEND+MORE=MONEYだとS=9, M=1から始まって式を展開していけばすぐに求まってしまうから。
#まぁ、笑う前にやって味噌。
124:デフォルトの名無しさん
06/07/30 03:40:29
>>117 のはなしは？
125:デフォルトの名無しさん
06/07/30 05:12:59
覆面算と数独が本質的に同じって話だが、何か？
126:デフォルトの名無しさん
06/07/30 11:39:00
>>118 がNP完全で >>116 はNP完全ではないという意味でよろしかったでしょうか？
127:デフォルトの名無しさん
06/07/30 18:12:30
そんな話はしていないのでは・・・
128:デフォルトの名無しさん
06/08/10 21:49:28
>>12
空いてる枡を─│└┘┌┐のいずれかで埋めて
全パターンやれば解けそう。
バックトラックでどこまで計算量削れるか？
129:デフォルトの名無しさん
06/08/11 09:21:09
>>12はナンリン（ナンバーリンク）という同じルールのパズルがあって
下のスレでそれを解くプログラムが既に作られている。
【解答】パズルのプログラミング【作成】
ｽﾚﾘﾝｸ(puzzle板)
130:デフォルトの名無しさん
06/10/25 21:04:39
だれか次の言語をBrainFuckにコンパイルするコンパイラ作って。
> ポインタをインクリメント
< ポインタをデクリメント
+ ポインタが示すメモリ位置のデータをインクリメント
- ポインタが示すメモリ位置のデータをデクリメント
. ポインタが示すメモリ位置のデータを出力
, ポインタが示すメモリ位置のデータに入力
[ ポインタが示すメモリ位置のデータがヌルなら対応する]までジャンプ
] ポインタが示すメモリ位置のデータがヌルじゃないなら対応する[までジャンプ
@n (nは整数)ポインタをn番地に設定
BrainFuckのスレ
ｽﾚﾘﾝｸ(tech板)l50
131:デフォルトの名無しさん
06/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:デフォルトの名無しさん
06/10/31 20:59:45
漏れは４時間考えたが結局ヒントもらうまで解けなかったorz
133:デフォルトの名無しさん
06/11/01 02:43:26
>>131
超典型 DP
134:デフォルトの名無しさん
06/11/02 01:15:21
どうやって小問題に分割するか
135:デフォルトの名無しさん
06/11/02 02:00:39
素数が無限個存在することを1行で証明せよ
136:デフォルトの名無しさん
06/11/02 11:15:53
(有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数
137:デフォルトの名無しさん
06/11/03 00:04:17
>>136
3*5+1=16
138:デフォルトの名無しさん
06/11/03 01:34:36
(有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数の倍数
139:デフォルトの名無しさん
06/11/03 01:41:24
何の証明にもなってないという事実は伏せておこう
140:デフォルトの名無しさん
06/11/03 02:06:37
望むだけ長く区間素数が現れないような条件を求めよ。
141:デフォルトの名無しさん
06/11/03 02:34:35
ここは数学のスレではありません＞＜
142:デフォルトの名無しさん
06/11/05 04:03:11
>>136
(ある素数Ｎ以下の全素数の積)+1 = 左辺の素数の集合に含まれない素数
143:デフォルトの名無しさん
06/11/08 21:13:38
それが何故なのかを説明しないと証明にならんっつーの
144:デフォルトの名無しさん
06/11/09 09:45:36
素数の定義より明らか