[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
705(4): デフォルトの名無しさん [sage] 2023/05/28(日) 09:45:16.03 ID:wyI6c4Ev(1) AAS
お題 ナイトツアー
5×5の狭いチェスボードのどこかにナイトのコマを置きそこからナイトの可能な動きでコマを動かします
ただし同じマスは2回通れません
このとき全マス25マスを全て通る手順の数を数え上げて下さい
しかし実際全部数えるのは流石に無駄なので対称性を利用して
♯{A1→B3}×8
+ ♯{A3→B5}×8 + ♯{A3→C4}×8
+ ♯{B2→C4}×8
+ ♯{C3→D5}×8
はよいとします
例
♯{A1→B3} = 152
--ナイトの動き--
桂馬の動きと同じ、水平方向の移動量+垂直方向の移動量 = 3となる移動(もちろん盤の中)
706: デフォルトの名無しさん [sage] 2023/05/28(日) 11:22:07.87 ID:p5Vu/cFc(1) AAS
>>705
訂正
> --ナイトの動き--
水平方向の移動量+垂直方向の移動量 = 3となる移動で水平、垂直な移動はなし(もちろん盤の中)
707(1): デフォルトの名無しさん [] 2023/05/28(日) 23:12:57.01 ID:eCmMTKII(1) AAS
>>705
対称性を考慮するのは面倒なので全部数え上げる。Rで書いたら5秒以内に到底終わらなかったので、
ideone.com/y5Dwy7
C++に移植した。盤面表示はideoneでは途中で切れてしまうので非表示にした（関数moveの
コメント部分をコメントでなくせば表示される）。
ideone.com/6Muw9F
対称性を考慮すれば、手順数は1728 / 8 = 216通りになる。
709: デフォルトの名無しさん [] 2023/05/29(月) 01:46:57.43 ID:F8hmnix6(1) AAS
>>705
Kotlin
馬鹿正直に再帰で全パターンやっているだけ。
途中経過は出力しない。既に置かれたマスは1bitで記録されるようにして 5 * 5 = 25 bit で Int (32bit) に収まるのでそれを利用している。
恐らく Boolean の配列を使って書くとそこまで最適化されなさそうなのでこうした。
外部ﾘﾝｸ:paiza.io
結果は同じ 1728 になったので多分これで合っていると思う。
710: デフォルトの名無しさん [] 2023/05/29(月) 23:38:05.56 ID:5zRv7Ftx(1) AAS
>>705
>>707にちょっと付け加えたら対称性を考慮して数え上げることができた。
外部ﾘﾝｸ:ideone.com (R)
外部ﾘﾝｸ:ideone.com (C++)
Rでは5秒以内に終わらなかった。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.045s