算法合集之染色法和構(gòu)造法在棋盤上的應(yīng)用用(編輯修改稿)
2024-11-12 20:32 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 藍(lán)色： 21個(gè) 白色： 22個(gè) 黑色： 21個(gè) ? 覆蓋類問(wèn)題其實(shí)是一個(gè)難度較大的課題 ， 這里只討論了一些簡(jiǎn)單的情況 ， 以說(shuō)明染色法與構(gòu)造法的應(yīng)用 ? 需要補(bǔ)充的是 ， 染色法的種類形形色色 、 五花八門 。 考慮到可推廣性和易操作性 ， 本文只著重研究了 “ 間隔染色法 ” （ 即自然染色法的推廣 ） 23 小結(jié) 3 馬的遍歷 ? 馬行走規(guī)則 ? 從 2*3的矩形一個(gè)角按對(duì)角線跳到另一個(gè)角上 ? 馬的遍歷 ? 從一個(gè)格出發(fā)按跳馬規(guī)則不重復(fù)地走遍所有格 ? 棋盤中馬的遍歷問(wèn)題分兩類 ? (1) 馬的哈密爾頓鏈 ? (2) 馬的哈密爾頓圈 32 馬的哈氏鏈 ? 通常有三種方法 ? １ 貪心法 —— 每一步跳向度最小的點(diǎn) （ 度數(shù)指可一步到達(dá)且未經(jīng)過(guò)的點(diǎn)的個(gè)數(shù) ） ? ２ 分治法 —— 將棋盤分成幾個(gè)小棋盤 ， 分別找哈氏鏈 ，再接起來(lái) ? ３ 鑲邊法 —— 先在一個(gè)小棋盤中找到哈氏鏈 ， 然后在棋盤四周鑲邊 ， 已產(chǎn)生大棋盤的哈氏鏈 。 ? 按上述方法不難得到下面結(jié)論： ? n*n棋盤存在哈氏鏈的充要條件是 n3。 32 馬的哈氏圈 ? 例 4 求 n*n棋盤的哈氏圈 ? 分析 ： ? 將棋盤自然染色 ， 考察無(wú)解情況 。 ? 馬無(wú)論怎么走 ， 都必須按黑格－白格－黑格－白格 ．．．．．． 如此循環(huán) 。 由于要回到起點(diǎn) （ 起點(diǎn)與終點(diǎn)同色 ） ， 途經(jīng)兩種顏色的格子數(shù)必相等 ， 可知 n為奇數(shù)時(shí)無(wú)解 。 ? 因?yàn)榇笮∠拗?， n6時(shí)也無(wú)解 馬 馬 馬 馬 馬 馬 馬 馬 馬 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1