1. <rp id="zsypk"></rp>

      2. 數(shù)獨(dú)實(shí)驗(yàn)報(bào)告

        時(shí)間:2020-10-10 18:57:21 報(bào)告 我要投稿

        數(shù)獨(dú)實(shí)驗(yàn)報(bào)告范文

          Sudoku 數(shù)獨(dú)實(shí)驗(yàn)報(bào)告

        數(shù)獨(dú)實(shí)驗(yàn)報(bào)告范文

          一、 算法描述

          求解Sudoku讓人最容易想到的方法是窮舉每個(gè)方格可能的值,如果符合條件,則得到解,不符合條件則進(jìn)行回溯。通過遞歸的方法,顯然可以得到數(shù)獨(dú)的解。

          我想到的簡(jiǎn)單的遞歸方法,是每一行從左到右,試驗(yàn)每一個(gè)方格可能的數(shù)字,進(jìn)行遞歸。這種方法看似非常麻煩,實(shí)際上對(duì)于一般的數(shù)獨(dú)題,速度是非?斓,思想比較簡(jiǎn)單,寫出來的代碼也非常簡(jiǎn)單、易懂。

          算法1:簡(jiǎn)單遞歸方法

          從第一個(gè)格開始,從1到9試驗(yàn),是否滿足行、列、九宮格互不相同的條件。若滿足條件,則填入該數(shù)字,再試驗(yàn)下一個(gè)格。當(dāng)一個(gè)格子出現(xiàn)沒有數(shù)字能填的情況時(shí),說明已經(jīng)填的數(shù)字有誤,回溯,再進(jìn)行遞歸。

          算法2:優(yōu)化的遞歸算法

          先遍歷所有格子,統(tǒng)計(jì)每種格子可能出現(xiàn)數(shù)字的個(gè)數(shù)。每次挑選可能出現(xiàn)數(shù)字個(gè)數(shù)最少的格子來進(jìn)行遞歸。

          設(shè)置三維數(shù)組poss[i][j][k]來存儲(chǔ)可能出現(xiàn)數(shù)字的信息。poss[i][j][0]記錄i行j列的格子可能出現(xiàn)數(shù)字的個(gè)數(shù),poss[i][j][k](1<=k<=9) 若poss[i][j][k]=1,表示k可能在(i,j)格出現(xiàn)。若poss[i][j][k]=0,表示k不可能在(i,j)格中出現(xiàn)。每次找poss[i][j][0]最小的格子,來進(jìn)行下一個(gè)遞歸。

          算法3:生成數(shù)獨(dú)棋盤的算法

          我最開始的想法是窮舉法,隨機(jī)生成滿足行各不相同的9行,再判斷9宮格、每列是否符合要求,符合條件時(shí),隨機(jī)生成停止。然而,這種算法的當(dāng)然時(shí)間復(fù)雜度顯然是過高。第99一步的隨機(jī)生成的次數(shù)是9*9/P9=9608。隨機(jī)生成一組棋盤耗時(shí)就非常大。后來,我從求解的個(gè)數(shù)的程序獲得啟發(fā)。算法二對(duì)于1000多組解的數(shù)獨(dú)棋盤,解起來也很快。隨機(jī)生成填9個(gè)方格,再用算法一的方法解出來,取第一組正確的解作為棋盤即可生成填好的棋盤。再把一定數(shù)量的格子的數(shù)字隨機(jī)刪除,計(jì)算解的個(gè)數(shù)。如果解唯一,就得到了棋盤。

          二、數(shù)據(jù)結(jié)構(gòu)

          這三種算法的數(shù)據(jù)結(jié)構(gòu)不是非常復(fù)雜,只是普通的數(shù)組。

          算法一:數(shù)組a[i][j]

          算法二:數(shù)組a[i][j]和poss[i][j][k]

          算法三:數(shù)組a[i][j]和poss[i][j][k]

          三、時(shí)間效率分析

          算法1:這種算法在tsinsen系統(tǒng)上只用了15ms得到全部答案。

          雖然這種算法在tsinsen系統(tǒng)的測(cè)試中有很好的表現(xiàn),但是我試了試在幾道骨灰級(jí)難度的題,發(fā)現(xiàn)這種算法可能會(huì)用到10秒以上的時(shí)間,并且測(cè)試數(shù)據(jù)不同,時(shí)間差異非常大。

          我認(rèn)為,這種算法的漏洞在于,如果開始的格子可能出現(xiàn)的數(shù)字非常多,遞歸樹開始的枝會(huì)非常多。并且,我們一般做數(shù)獨(dú)題,都會(huì)先挑可能出現(xiàn)數(shù)字個(gè)數(shù)最少的格子來填,充分利用了已知條件。然而,這種算法只按格子的行列順序來試驗(yàn),顯然非常傻。于是,我想出了第二種算法。

          算法2:這種算法耗時(shí)長(zhǎng)。

          非常令人失望的是,雖然它能在短時(shí)間內(nèi)解出骨灰級(jí)題目,但是,和上一個(gè)算法相比,對(duì)于簡(jiǎn)單的題目,它比較耗時(shí)。在tsinsen系統(tǒng)中測(cè)試的時(shí)間是91ms。它的缺陷在于,每次遞歸都必須更新(i,j)格子所在的行、列、九宮格所有的元素。每次要求20個(gè)數(shù)的.poss[i][j][];厮萃瑯右隆2⑶仪髉oss[i][j][]的函數(shù)時(shí)間復(fù)雜度是O(n)。每一步所耗時(shí)間比上一種算法多很多。但是,總的試驗(yàn)的步數(shù)能顯著減少。 所以,這種算法適用于數(shù)獨(dú)解題的動(dòng)畫演示和解極難題目。

          四、程序結(jié)構(gòu)

          五、運(yùn)行結(jié)果

          六、總結(jié)和反思

          后來老師提高了難度,要求程序能求出多解數(shù)獨(dú)題的解的個(gè)數(shù)。幾千個(gè)解的數(shù)據(jù)都能迅速得出答案,但是幾萬個(gè)解的數(shù)據(jù),需要很長(zhǎng)時(shí)間,更別提幾百萬的數(shù)據(jù)。這兩種遞歸的算法都有問題,優(yōu)化的空間也有限,需要更強(qiáng)大、高效的算法。

          這次Project讓我不斷思考,改進(jìn)了最初的算法。編程是確實(shí)是一個(gè)克服困難、不斷改進(jìn)與超越的過程?傆行碌臄(shù)據(jù)擺在面前,把原來的算法打擊得很慘,激勵(lì)著我們研究更加先進(jìn)的算法。

        【數(shù)獨(dú)實(shí)驗(yàn)報(bào)告范文】相關(guān)文章:

        實(shí)驗(yàn)報(bào)告范文01-20

        實(shí)驗(yàn)報(bào)告范文(15篇)01-20

        實(shí)驗(yàn)報(bào)告范文15篇01-20

        實(shí)驗(yàn)報(bào)告范文(集錦15篇)01-20

        倉(cāng)儲(chǔ)實(shí)踐實(shí)驗(yàn)報(bào)告01-13

        《血染的實(shí)驗(yàn)報(bào)告》讀后感01-20

        民間文學(xué)課題實(shí)驗(yàn)報(bào)告01-20

        整十?dāng)?shù)加減整十?dāng)?shù)評(píng)課稿01-18

        《血染的實(shí)驗(yàn)報(bào)告》讀后感3篇01-20

        獨(dú)店中學(xué)開學(xué)典禮校長(zhǎng)講話稿01-07

        99热这里只有精品国产7_欧美色欲色综合色欲久久_中文字幕无码精品亚洲资源网久久_91热久久免费频精品无码
          1. <rp id="zsypk"></rp>