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