- 1 名前：デフォルトの名無しさん [2006/07/21(金) 19:10:18 ]
- パズルを出題してそれを解くプログラムを作るスレです。
みんなで楽しくアルゴリズムを考えましょう。
- 2 名前：デフォルトの名無しさん mailto:sage [2006/07/21(金) 19:13:50 ]
- ずるしてらくしてかれいに２げっと
- 3 名前：1 mailto:sage [2006/07/21(金) 19:24:30 ]
- では数学板で見かけた問題。
ネズミが一匹、無限の広さをもつ碁盤の上に居る。
プレーヤーは一ターンの間にネズミの居ない任意の座標にブロックを一つおくことができる。
ネズミは一ターンの間に上下左右のいずれかの方向に一歩動くことができる。
ただし、ブロックのある座標には移動できない。
ネズミの四方がブロックで囲まれ、一歩も動けない状態になればプレーヤーの勝ち。
ネズミがいつまでも逃げることができればネズミの勝ち。
プレイヤーの先行として、ゲームはどちらが勝つか。
このゲームはプレイヤーが勝つことが数学板で証明されていたので
最短手数を求めてください。
- 4 名前：1 mailto:sage [2006/07/21(金) 19:27:35 ]
- 数学板の面白い問題おしえて〜な 11問目の381に載ってました。
- 5 名前：1 mailto:sage [2006/07/21(金) 21:40:58 ]
- もう一問だしときますね。
ｎ個の異なる文字を並べてできる長さnの文字列を考える。
このような文字列はn!個あるがこのn!個の文字列を
一列に並べ、隣り合う文字列がちょうど2文字だけ異なるように
するアルゴリズムを作れ。
たとえば3文字なら
abc
acb
bca
bac
cab
cba
と並べれば隣り合う文字列がちょうど2文字違うようになります。
- 6 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 00:05:28 ]
- >>5
それって任意のnに対して可能なの？
- 7 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 02:33:58 ]
- グレイ符号が応用できそうな予感
- 8 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 04:39:25 ]
- スマソ
意味が分からん
- 9 名前：デフォルトの名無しさん mailto:sage [2006/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 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 14:57:08 ]
- 普通に全通りの並べ方をしらみつぶしにやればいいんじゃね？
計算時間？しらね。
- 11 名前：デフォルトの名無しさん mailto:sage [2006/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 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 16:13:31 ]
- 誰かこれ解くプログラム書いて。
yoshimaruxxx.web.fc2.com/sentunagi.html
- 13 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 16:28:00 ]
- >>11
実行してみたけど重複する文字列があるみたい。
- 14 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 16:34:32 ]
- これって結局階乗を出す問題だよね。
交換だけで階乗が出せればかなり有名になっているはずだから、スマートな解法はないと思う。
- 15 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 16:41:16 ]
- >>14
階乗を出すってどういうこと？
- 16 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 17:06:32 ]
- 順列ですた。
という事で、順列を交換だけで出せるのって話です。
- 17 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 17:12:59 ]
- 文字列を頂点として２文字違う文字列に辺があるグラフを考えれば
ハミルトン閉路問題に帰着される。
辺の数は結構多いし、ハミルトン閉路はありそうにも思えるがさて。
- 18 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 17:29:42 ]
- グラフの作成に O(n!) かかるのでは。
結局しらみつぶしと同じ予感。
- 19 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 17:45:15 ]
- もともと出力のサイズがn!なんだからそれは気にすること無い。
しらみつぶしの計算量は(n!)!なんだから全然違う。
- 20 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 18:10:52 ]
- 普通出力ってひとまとめで一処理とみなす気が
- 21 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 20:13:02 ]
- 出力の大きさがO(n!)なんだからどんなにがんばったって計算量がO(n!)を下回ることはない。
出力をひとまとめで一処理なんておかしいよ。
- 22 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 21:07:22 ]
- n文字の場合の結果をつかってn+1文字の場合を解けないものか。
- 23 名前：デフォルトの名無しさん mailto:sage [2006/07/22(土) 23:37:12 ]
- , -: ': : : : : : :"⌒:￣:` : ､
／: : : : へ._ : : : :へ、: : : ＼
__,く;へ＿: : :| : : : : : : : ＼￣:ヽ、＼
. /:__/: : :/: : |: :ｌ: : : : : : : : ＼.: :ヽ: ヽ
/_//: : :/: / :|: ｌ: : :ヽ: ヽ: : : : ヽ: : ヽﾊ
／/: /: : : : : |: : ｌ: : |: : |: : ヽ: :ヽ: : ヽ: : : : : : :ヽ: : ヽﾊ
. /:/: /: /: ｌ: |: :,|: : ﾊ: : |: : : ヽ: :ヽ: : ヽ: : : : : : :ヽ : ヽ|
//: : ｌ: :ｌ: ::|: :|: :|: : :| ヽ ｌヽ : : :＼: ヽ.: :＼: : : ヽ:ﾊ: : : |
| ｌ: : |: :|: : |: :|: ハ__,L. ヽ ＼"￣｢ T ト- ､;_: : : : :|: : :.|
| |: : |: :|: : |: ;|イ｢ ヽ| ＼´＼ヽ __｣__ｉ.＼ ＼ : : |: : :| もう・・・仕方の無いことばかり言って・・・
| |: : |: :|: : くｖ' _｣＝ｉ ヽ ／｢ ｉ::::::o｢＼|ヽﾄ: |: :/|
ｉ ｌ: : ﾊ: ｌ: : :.ト / {:::::::〉 ﾚﾍ:.::::}ﾟｉ|/|: ::| .}ﾚ': :|
∨:| Ｖﾍ: ::ﾍヽ ｖﾍ:ﾊ ..く_二ｉつ|: :.:ﾚ: :| : :|
ヽヽ∨へ:ﾊ ヾツ /／//ﾊ:/::|: :|: : :|
∧: :ｉ:ﾍ.ｌ // ` /: {:::::|: :ｌ: : ﾊ
/:/: ∧: ＼ ｡ ,.ｲ:|: :|::ｉ:::|: :ｌ: ::∧
//: : :}: ヽ`ｉ:: ､. ／ .|::| :|:::ｉ::::|: ｉ:: : ∧
://: : : ハ: ヽ::::::ノＴ ' ‐ ' |::|: :Ｖ::::ｉ∧: : : : ﾍ
/／: : ノ二 ヽ: :＼ 〈ｰ ､ ＿＿___,ﾄﾍ: :∨::ｉ::∧: : : :.∧
／/:/ /⌒ ＼ ヽト､: :ヽ＼__＿＿___ハ ＼:∨ﾊ:::∧: : : :} ＼
- 24 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 00:17:11 ]
- >>3
ネズミの問題は２３手詰めと出た。この手順はピンとこないけど、うまく収束している。
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼┼┼┼ ┼┼●┼┼ ┼┼●○┼ ┼┼●○┼ ┼┼●┼┼ ┼┼●┼┼
┼┼┼○┼ ┼┼┼○┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼○┼ ┼┼┼○┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼●
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼○┼ ┼┼┼○┼ ┼┼○┼┼ ┼●○┼┼
┼┼┼○● ┼┼┼○● ┼┼┼┼● ┼┼┼┼● ┼┼┼┼● ┼┼┼┼●
┼┼┼┼┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼
┼●┼┼┼ ┼●┼┼┼ ┼●┼┼┼ ┼●┼┼┼ ┼●┼┼┼ ┼●●┼┼
┼┼○┼● ┼┼○┼● ┼┼┼┼● ┼┼┼┼● ┼┼○┼● ┼┼○┼●
┼┼┼●┼ ┼●┼●┼ ┼●○●┼ ┼●○●┼ ┼●┼●┼ ┼●┼●┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼
┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼ ┼┼┼●┼
┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼ ┼┼●●┼
┼●●┼┼ ┼●●┼┼ ┼●●┼┼ ┼●●●┼ ┼●●●┼ ┼●●●┼
┼○┼┼● ●○┼┼● ●┼○┼● ●┼○┼● ●┼┼┼● ●┼●┼●
┼●┼●┼ ┼●┼●┼ ┼●┼●┼ ┼●┼●┼ ┼●○●┼ ┼●○●┼
┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼ ┼┼●┼┼
- 25 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 00:22:09 ]
- 自己レス>>24
ただし、ブロックの置き方はネズミの八方のみしか探索していないので。
- 26 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 02:40:48 ]
- 正解なのかどうかすらわからん
- 27 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:05:40 ]
- テストケースの組み合わせを自動生成してくれるプログラム作ってくれんか？
たとえば入力を2,3,3としたら以下のような文字を出力してくれるような。
言葉ではうまく言えないが全ての組み合わせを生成してくれるやつ。
○、○、○、○、○、○、○、○、○、 、 、 、 、 、 、 、 、
、 、 、 、 、 、 、 、 、○、○、○、○、○、○、○、○、○
○、○、○、 、 、 、 、 、 、○、○、○、 、 、 、 、 、
、 、 、○、○、○、 、 、 、 、 、 、○、○、○、 、 、
、 、 、 、 、 、○、○、○、 、 、 、 、 、 、○、○、○
○、 、 、○、 、 、○、 、 、○、 、 、○、 、 、○、 、
、○、 、 、○、 、 、○、 、 、○、 、 、○、 、 、○、
、 、○、 、 、○、 、 、○、 、 、○、 、 、○、 、 、○
- 28 名前：27 mailto:sage [2006/07/23(日) 09:07:13 ]
- ちょっとずれた。
でも雰囲気はわかるよね。
- 29 名前：24 mailto:sage [2006/07/23(日) 09:24:01 ]
- >>26
それでは、実際にやってみましょう。必ず２３手以内に詰ませてみせます。
一手目
┼┼┼
●○┼
┼┼┼
誰でもいいです。どうぞ
- 30 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:25:34 ]
- >>24
それ、探索にどのくらい時間かかるんだ？
ネズミの移動方向を入力できるようにして up してくれよ。
面白いゲームになりそうじゃね？ｗ
- 31 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:26:21 ]
- ┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼●┼┼ ┼┼●┼┼
┼┼┼○┼ ┼┼┼○┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼○┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼ ┼┼┼┼┼
脱出成功
- 32 名前：24 mailto:sage [2006/07/23(日) 09:28:47 ]
- >>31
実はそれでも詰みますが、変化が複雑（時間がかかる）なので
>>29からどうぞ
- 33 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:38:49 ]
- ┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼
●○┼┼┼ ●┼○┼┼
┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼
┼┼┼┼┼ ┼┼┼┼┼
- 34 名前：24 mailto:sage [2006/07/23(日) 09:40:46 ]
- >>30
Javaで書いてしまいましたが、１時間ぐらいで解けました。
３手目
┼┼┼┼┼
┼┼┼●┼
●┼○┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
書き込みを楽にする為、最後の局面のみにしましょう。
- 35 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:43:10 ]
- ┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼┼┼┼
┼┼┼┼┼
でもさ、>>31 のが時間かかるってことは23手で詰まないっていう意味じゃないの？
- 36 名前：24 mailto:sage [2006/07/23(日) 09:44:12 ]
- ３手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼●┼┼
┼┼┼┼┼
いえ、探索に時間がかかります。
- 37 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:44:34 ]
- そういえばアレニウスの円っていう問題もあったね
- 38 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:45:22 ]
- ┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼┼
┼┼┼┼┼
ジダンの華麗なダンス炸裂してほしい
- 39 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:46:22 ]
- >>34
１時間は長いな。
最初の数手をテーブルにしたらインタラクティブな待ち時間にならんかな。
ネズミ側だけでいいんだけど。
- 40 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:46:54 ]
- 既に２手サバ読まれてるし
- 41 名前：24 mailto:sage [2006/07/23(日) 09:47:04 ]
- ７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼●
┼┼┼┼┼
じつは４手目は最善手ではありません。
- 42 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:48:23 ]
- ほっほー
- 43 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 09:51:10 ]
-
ネズミは曲がるとかなり手数損しそうですね
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼┼┼
┼┼●┼●
┼┼┼○┼
ジダン突破
- 44 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 10:00:19 ]
- ４手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
- 45 名前：24 mailto:sage [2006/07/23(日) 10:05:00 ]
- >>40
ばれましたか。
５手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
- 46 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 10:06:14 ]
- ４手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
- 47 名前：24 mailto:sage [2006/07/23(日) 10:08:02 ]
- ５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
>>44は最善手の一つですがこちらは違います。
- 48 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 10:08:11 ]
- ６手目
┼┼┼┼┼
┼┼┼●○
●┼┼┼●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
- 49 名前：24 mailto:sage [2006/07/23(日) 10:08:53 ]
- ５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼●┼┼┼
┼┼┼┼┼
┼┼┼┼┼
- 50 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 10:11:27 ]
- ┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
- 51 名前：24 mailto:sage [2006/07/23(日) 10:12:54 ]
- ７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼●┼
┼┼┼┼┼
- 52 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 10:28:22 ]
- ┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼┼○
┼┼┼●┼
┼┼┼┼┼
- 53 名前：24 mailto:sage [2006/07/23(日) 10:38:19 ]
- ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼
┼┼┼●┼┼┼ ┼┼┼●┼┼┼ ┼┼┼●┼┼┼ ┼┼┼●┼┼┼
●┼┼┼●┼┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼
┼┼┼┼○┼┼ ┼┼┼┼○┼┼ ┼┼┼┼┼○┼ ┼┼┼┼┼○●
┼┼┼●┼┼┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼┼┼ ┼┼┼┼┼●┼
┼┼┼●┼┼┼ ┼┼┼●┼┼● ┼┼┼●┼○● ┼┼┼●┼○●
●┼┼┼●○┼ ●┼┼┼●○┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼
┼┼┼┼┼┼● ┼┼┼┼┼┼● ┼┼┼┼┼┼● ┼┼┼┼┼┼●
┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼
┼┼┼●┼┼● ┼┼┼●●┼● ┼┼┼●●┼● ┼┼┼●●┼●
●┼┼┼●○┼ ●┼┼┼●○┼ ●┼┼┼●┼┼ ●┼┼┼●┼┼
┼┼┼┼┼┼● ┼┼┼┼┼┼● ┼┼┼┼┼○● ┼┼┼┼●○●
┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼ ┼┼┼┼┼●┼
┼┼┼●●┼● ┼┼┼●●┼● ┼┼┼●●○● ┼┼┼●●○●
●┼┼┼●○┼ ●┼┼┼●○● ●┼┼┼●┼● ●┼┼┼●●●
┼┼┼┼●┼● ┼┼┼┼●┼● ┼┼┼┼●┼● ┼┼┼┼●┼●
┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼ ┼┼┼●┼●┼
これで終わりにします。ちょいとでしゃばりすぎた感がありますので
- 54 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 11:03:33 ]
- 明らかに勝負が見えたあとの収束が遅いように思います
- 55 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 11:05:27 ]
- >>27
意味が分からないんですけど
解説してください
- 56 名前：27 mailto:sage [2006/07/23(日) 11:44:04 ]
- うーん俺がアホなせいでなかなかうまく説明できないんだが。
テストというのは入力がいくつかあってその選択肢の組み合わせを考える。
>>27の例は入力が３つあって、一番目は選択肢が２つ、２番目、３番目は選択肢が３つあると思って。
で、１行目、２行目は一番目の入力の選択肢をどちらを選ぶかを表している。
３，４，５行目は２番目の入力の選択肢のうちどれを選ぶかを表している。
６，７，８行目は３番目の入力の選択肢のうちどれを選ぶかを表している。
各列はひとつのテストケースを表している。
たとえば一行目は一番目の入力＝１、２番目の入力＝１、３番目の入力＝１
５行目は一番目の入力＝１、２番目の入力＝２、３番目の入力＝２といった感じ。
で、選択肢の組み合わせを網羅的に生成してほしい。出力は>>27のフォーマットで。
うまく説明できたかわからんがこんな感じです。
- 57 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 16:32:42 ]
- >>56
こんなんでいいかな、
www.uploda.org/uporg455626.cpp.html
>>27は1列ごとにテストケース1パターンを表してるようだけど、
それもフォーマット？
めんどいから、1行1ケース表示にしたけど。
つか、パズルじゃないだろ
- 58 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 16:35:53 ]
- #include <string>忘れてた
- 59 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 16:37:40 ]
- 修正
www.uploda.org/uporg455638.cpp.html
- 60 名前：27 mailto:sage [2006/07/23(日) 16:47:41 ]
- そうそう。そんな感じなんですが、何とか１列１テストケースになりませんかね。
そのほうが何かとありがたいんですが。
- 61 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 16:49:19 ]
- >>56
主語や目的語を省略しすぎなんだよ
自分だけが分かってて相手が分かってないときに説明するんだから
- 62 名前：27 mailto:sage [2006/07/23(日) 16:55:52 ]
- >>61
精進します。
- 63 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 17:03:17 ]
- ネズミが８方向に動けたら、つかまんなくなりそう。
どうなんだろ。
- 64 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 18:05:30 ]
- >>63
それじゃパズルとして綺麗じゃないような気がする（移動距離が長いものと短いものがあってイヤ）
どうせならヘックスでやってみるとおもしろいかもしれない。
- 65 名前：デフォルトの名無しさん [2006/07/23(日) 18:24:24 ]
- >>60
１列１テストケースにしたよ。
www.uploda.org/uporg455761.cpp.html
ところで、どうしてここで質問？質問スレ行くといいよ。
- 66 名前：27 mailto:sage [2006/07/23(日) 18:29:29 ]
- >>65
いや、考えようによってはパズルといえなくもないかなーと。
これからは注意します。
ありがとうございました。
- 67 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 18:31:13 ]
- あのな、パズルってのは（ｒｙ
- 68 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 18:34:46 ]
-
HEXのねずみ捕り面白そうだけど
ここで表現するの自体が難しそう
- 69 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 19:22:03 ]
- 3x3のマス目で行なうマスターマインド（値は重複しない1〜9）の解答を得る
アルゴリズムってできないでしょうか？
3手で正解を得られるようなんですが。
難しくてｻﾊﾟｰﾘわからん。
- 70 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 19:29:06 ]
- 最低限ルールぐらい書いてもらおうか
- 71 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 19:53:08 ]
- どんなルールか知らんが３ｘ３ならしらみつぶしで終わりそうな予感。
- 72 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 22:11:20 ]
- ○○○
○○○
○○○
１２３
４５６
７８９
場所 1
数字 9
- 73 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 22:14:37 ]
- ７８９
４５６
１２３
場所 1
数字 9
- 74 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 22:15:38 ]
- ９８７
６５４
３２１
場所 4
数字 9
- 75 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 22:17:46 ]
- ９７８
６４５
３１２
場所 8
数字 9
- 76 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 22:18:44 ]
- 糞スレ化している・・・
- 77 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 22:25:33 ]
-
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
HEXなってないかな・・・
- 78 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 23:38:46 ]
- 盤だけ表示できても駒が
- 79 名前：デフォルトの名無しさん mailto:sage [2006/07/23(日) 23:53:55 ]
- ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋
＋＋ ＋＋ ＋＋ ＋＋ ＋＋ ＋＋
どぞ
- 80 名前：デフォルトの名無しさん mailto:sage [2006/07/24(月) 07:13:27 ]
- 六角形の碁盤
game9.2ch.net/test/read.cgi/gamestones/1071768398/l50
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜ ｜ ｜ ｜ ｜ ｜○｜ ｜ ｜ ｜ ｜ ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜ ｜ ｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
- 81 名前：デフォルトの名無しさん mailto:sage [2006/07/24(月) 07:34:18 ]
- ＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜ ｜ ｜ ｜ ｜○｜ ｜ ｜ ｜ ｜ ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜ ｜ ｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
- 82 名前：デフォルトの名無しさん mailto:sage [2006/07/24(月) 13:34:38 ]
- ＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜ ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜ ｜ ｜ ｜ ｜○｜ ｜ ｜ ｜ ｜ ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜ ｜ ｜ ｜ ｜ ｜●｜ ｜ ｜ ｜ ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜ ｜ ｜ ｜ ｜ ｜ ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
- 83 名前：デフォルトの名無しさん mailto:sage [2006/07/24(月) 13:36:11 ]
- これ対称性を考えると意外とパターン少ないな
- 84 名前：デフォルトの名無しさん mailto:sage [2006/07/24(月) 17:49:24 ]
- ＨＥＸだとつかまんない予感。
- 85 名前：デフォルトの名無しさん [2006/07/25(火) 02:00:43 ]
- オセロのパーフェクト決着の最短推移と最長推移をそれぞれ一種類ずつ求めよ。
盤面の左下のマスを [0,0] とし、はじめ [3,3] に置いてある色のプレイヤーが先攻とする。
ゲームの推移の記法は [3,5] [4,6] ... とする。
・・・こういうのはパズルとは言わないかも
- 86 名前：デフォルトの名無しさん [2006/07/25(火) 02:08:54 ]
- >>5
こんなかんじか。
www.uploda.org/uporg457304.cpp.html
この問題って、始めの文字列と終わりの文字列も「ちょうど2文字だけ異なる」っていう条件を満たさなければならない？
多分可能だが、まだやっていない。
- 87 名前：デフォルトの名無しさん mailto:sage [2006/07/25(火) 03:06:56 ]
- 満たすべきだろうね
グレイコードから作る方法なら満たせるでしょう
- 88 名前：デフォルトの名無しさん [2006/07/25(火) 16:28:49 ]
- >>85
NP問題の予感
- 89 名前：デフォルトの名無しさん mailto:sage [2006/07/25(火) 18:05:54 ]
- ところでＨＥＸの座標ってどう表すの？
- 90 名前：デフォルトの名無しさん mailto:sage [2006/07/25(火) 18:08:35 ]
- >>88
むしろＰＳＰＡＣＥ問題の予感。
- 91 名前：デフォルトの名無しさん mailto:sage [2006/07/25(火) 18:17:48 ]
- >>89
普通の表の片方の斜めだけに進めるようにする。
■■□
■☆■
□■■
■：進めるマス
□：進めないマス
- 92 名前：デフォルトの名無しさん mailto:sage [2006/07/25(火) 18:19:40 ]
- --■■□
-■☆■
□■■
表示はこう
- 93 名前：90 mailto:sage [2006/07/25(火) 20:35:07 ]
- いや、俺の勘違い。やっぱＰＳＰＡＣＥじゃなくてＮＰかも。
- 94 名前：デフォルトの名無しさん mailto:sage [2006/07/25(火) 21:36:03 ]
- >>5の問題にグレイコードを応用するのは言うほど簡単じゃないとおも。
なかなか手ごわい。
- 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文字の時になんで始めと終わりが揃うのかフシギ
|
 |
