數(shù)獨(dú)實(shí)驗(yàn)報告范文(《數(shù)獨(dú)》教學(xué)反思范文)

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

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

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

一、 算法描述

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

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

算法1：簡單遞歸方法

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

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

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

設(shè)置三維數(shù)組poss[i][j][k]來存儲可能出現(xiàn)數(shù)字的信息。poss[i][j][0]記錄i行j列的格子可能出現(xiàn)數(shù)字的個數(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)行下一個遞歸。

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

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

三、時間效率分析

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

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

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

算法2：這種算法耗時長。

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

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

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

六、總結(jié)和反思

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

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

《數(shù)獨(dú)》教學(xué)反思范文

《數(shù)獨(dú)》教學(xué)反思范文

作為一位剛到崗的教師，課堂教學(xué)是我們的任務(wù)之一，借助教學(xué)反思我們可以拓展自己的教學(xué)方式，快來參考教學(xué)反思是怎么寫的吧！以下是小編為大家整理的《數(shù)獨(dú)》教學(xué)反思范文，供大家參考借鑒，希望可以幫助到有需要的朋友。

《數(shù)獨(dú)》教學(xué)反思1

數(shù)獨(dú)又叫九宮格，它是一種數(shù)字謎題，源自18世紀(jì)末的瑞士，后在美國發(fā)展、并在日本得以發(fā)揚(yáng)光大。中國是在2007年2月28日正式引入數(shù)獨(dú)。 2007年2月28日，北京晚報智力休閑數(shù)獨(dú)俱樂部（數(shù)獨(dú)聯(lián)盟sudokufederation前身）在新聞大廈舉行加入世界謎題聯(lián)合會的頒證儀式，這標(biāo)志著中國的數(shù)獨(dú)研究走向國際舞臺，與世界接軌，它將給數(shù)獨(dú)愛好者帶來更多與世界數(shù)獨(dú)愛好者們交流的機(jī)會。在活動前通過調(diào)查，我了解到同學(xué)們認(rèn)識數(shù)獨(dú)的并不多，可以說知之者甚少，親自動手做過數(shù)獨(dú)的同學(xué)們更是廖廖無幾，因?yàn)橹肋@種游戲全面考驗(yàn)做題者觀察能力和推理能力，雖然玩法簡單，但數(shù)字排列方式卻千變?nèi)f化，所以不少教育者認(rèn)為數(shù)獨(dú)是訓(xùn)練頭腦的絕佳方式。所以在本學(xué)期第一個活動主題的安排上我大膽地選用了數(shù)獨(dú)這一活動主題。

活動的導(dǎo)入是激趣導(dǎo)入，給出一個空的數(shù)獨(dú)格，讓學(xué)生們猜一猜這是什么？班級里50多名同學(xué)，每個班有3—5名同學(xué)能夠簡單說出這是數(shù)獨(dú)，有1—2名同學(xué)能講出數(shù)獨(dú)的游戲規(guī)則，并且親自做過數(shù)獨(dú)，導(dǎo)入的環(huán)節(jié)起到了激發(fā)興趣，調(diào)動積極性的作用，接著我在大屏幕上給出一道簡單的數(shù)獨(dú)題，有34個以上數(shù)字的數(shù)獨(dú)題屬于簡單的題，教師領(lǐng)著學(xué)生一起來填5—6個數(shù)字，讓學(xué)生掌握方法和規(guī)則，然后同學(xué)們再開始做題，可以獨(dú)自完成，也可以同學(xué)合作，在自己動手做的過程中，有基礎(chǔ)的同學(xué)在做題時比較占優(yōu)勢，能夠很快的在10分鐘左右正確而快速的完成，這些同學(xué)給他們留第2道繼續(xù)練習(xí)，占絕大多數(shù)的同學(xué)是初次接觸，他們做得慢一些，但也能在15分鐘左右完成，也有個別的初學(xué)的同學(xué)能在10分鐘左右準(zhǔn)確地完成，可見同學(xué)們的推理能力、判斷能力和觀察能力非常強(qiáng)。在活動結(jié)束之前，請做得快的同學(xué)談一談自己的方法，供大家分享和借鑒。并且布置同學(xué)們回家查閱數(shù)獨(dú)的方法和技巧。第二次活動時，先介紹查閱的資料，然后繼續(xù)進(jìn)行練習(xí)，可以單獨(dú)完成也可以合作完成。第三次活動的內(nèi)容是數(shù)獨(dú)賽一賽，一共是兩道題，用一節(jié)課的時間來完成，每個班都有十幾名同學(xué)做得又快又好，超過四分之三的同學(xué)能夠完成比賽題，通過比賽環(huán)節(jié)進(jìn)一步檢測對數(shù)獨(dú)知識掌握的程度如何，并且讓能力強(qiáng)的同學(xué)多與大家分享和互動。

通過開展數(shù)獨(dú)活動，極大的調(diào)動了學(xué)生開動腦筋、進(jìn)行主動思考的良好習(xí)慣，他們的判斷能力和分析推理能力得到了有效的鍛煉和開發(fā)，并且拓展了視野，接受了新知識，學(xué)生們團(tuán)結(jié)協(xié)作，互動交流，讓數(shù)獨(dú)這一實(shí)踐活動深為同學(xué)們所喜愛。

活動過程中也有些許的不足，如有少部分學(xué)生跟不上，沒有完全理解，針對這一問題有效的解決方法是在導(dǎo)入過程中，應(yīng)該領(lǐng)著學(xué)生們多做一些練習(xí)，讓每一名同學(xué)都掌握游戲的方法和規(guī)則；活動過程應(yīng)該分層設(shè)計(jì)活動內(nèi)容，如有些同學(xué)能力特別強(qiáng)，他們做得又快又好，課堂準(zhǔn)備的數(shù)獨(dú)題遠(yuǎn)不能滿足他們的需要，針對這一問題解決的方法是在他們在完成了簡單的數(shù)獨(dú)題后，指導(dǎo)教師應(yīng)該給他們的是更難一些的題，這將有助于更好地提高和鍛煉，激發(fā)他們不斷挑戰(zhàn)的斗志和能力。第一次把數(shù)獨(dú)引入綜合實(shí)踐活動，在活動的開展過程中以及活動的實(shí)施中都還存在著許多不足和有待完善之處，我將在今后的數(shù)獨(dú)活動中繼續(xù)總結(jié)和探索，以期在以后的數(shù)獨(dú)活動中讓學(xué)生們獲得更多的體驗(yàn)和感受，在知識、情感、態(tài)度、能力等各方面都得到鍛煉和提高。

《數(shù)獨(dú)》教學(xué)反思2

二年級的學(xué)生，自制能力差，最主要的還是要提起學(xué)生的學(xué)習(xí)興趣才能更好完成教學(xué)目標(biāo)，數(shù)獨(dú)對于二年級的學(xué)生來說還是比較難理解的，在上本節(jié)課前，我認(rèn)真研讀教材，理解教材的`編寫意圖。因此，在設(shè)計(jì)教學(xué)時，我從最簡單的填數(shù)游戲開始，讓學(xué)生理解數(shù)獨(dú)規(guī)則。接著讓學(xué)生從簡單的三宮格入手，降低整節(jié)課的難度，從而讓學(xué)生們放輕松，以最好的狀態(tài)進(jìn)入學(xué)習(xí)中。

一、以簡單游戲開始，激發(fā)學(xué)生的學(xué)習(xí)熱情。

在新授課前，我設(shè)計(jì)了簡單的填數(shù)游戲，先讓學(xué)生理解行與列，孩子們玩得津津有味，但是只有游戲是不夠的，游戲后要有思考，從第一個游戲中，通過談話，捕捉課堂中及時生成教學(xué)問題，以此開展教學(xué)，同時，從學(xué)生已有的知識經(jīng)驗(yàn)出發(fā)，調(diào)動學(xué)生學(xué)習(xí)的積極性，讓親身經(jīng)歷知識的形成。學(xué)生們發(fā)現(xiàn)了要想填上類似這樣的題的方法，需要至少知道三個數(shù)字。接著填三宮格，先讓學(xué)生用語言描述一個數(shù)字在圖中的位置（第幾行，第幾列）。為學(xué)生填數(shù)時能用標(biāo)準(zhǔn)的語言敘述打好基礎(chǔ)。學(xué)生思考的結(jié)果是，要想填好數(shù)字，應(yīng)該先找到字母所在的行或列，再進(jìn)行思考。學(xué)生們在不知不覺中自己發(fā)現(xiàn)了方法，也學(xué)會了用數(shù)學(xué)語言來表述自己的思考過程。學(xué)習(xí)的積極性被有效調(diào)動起來。

二、以學(xué)生已有的知識經(jīng)驗(yàn)為基礎(chǔ)，加強(qiáng)學(xué)生分析推理能力的發(fā)展。

在教學(xué)例2時，通過觀察、分析等活動，讓學(xué)生在推理的過程中不斷嘗試、調(diào)整，學(xué)會按一定的方法進(jìn)行推理，進(jìn)一步體驗(yàn)推理的作用。因此教學(xué)中我讓同桌兩人交流，說說先算A還是先算B,這樣想的理由是什么？在交流過程中，學(xué)生們明白了做這種題最重要的一條原則，就是先找到字母所在的行和列，然后看哪個給了三個數(shù)字，再寫出字母所表示的數(shù)字。這樣層層深入，水到渠成，絲毫看不出老師教學(xué)的痕跡，完全是學(xué)生自己思考的結(jié)果，教師只是給予必要的指導(dǎo)，幫助孩子們學(xué)會用數(shù)學(xué)語言來表述自己的思考過程。在簡單推理的過程中，培養(yǎng)了學(xué)生觀察、分析、推理和有條理地進(jìn)行數(shù)學(xué)表達(dá)的能力，學(xué)會有序地、全面地思考問題。

總之，通過開展數(shù)獨(dú)活動，極大的調(diào)動了學(xué)生開動腦筋、進(jìn)行主動思考的良好習(xí)慣，他們的判斷能力和分析推理能力得到了有效的鍛煉和開發(fā)，并且拓展了視野，接受了新知識，學(xué)生們團(tuán)結(jié)協(xié)作，互動交流，讓數(shù)獨(dú)這一實(shí)踐活動深為同學(xué)們所喜愛。

活動過程中也有些許的不足，在備課時，總覺得已經(jīng)想的很清楚了，但上課時總會覺得有些地方的跨度有些大，還有部分學(xué)生的思維跟不上，沒有完全理解。因此，我將在今后的數(shù)獨(dú)活動中繼續(xù)總結(jié)和探索，以期在以后的數(shù)獨(dú)活動中讓學(xué)生們獲得更多的體驗(yàn)和感受，在知識、情感、態(tài)度、能力等各方面都得到鍛煉和提高。

《數(shù)獨(dú)》教學(xué)反思3

數(shù)獨(dú)安排在了本冊書的最后一個單元。數(shù)獨(dú)是一種邏輯性很強(qiáng)的游戲，學(xué)生必須時刻謹(jǐn)記同一個數(shù)字在同一行、列中只出現(xiàn)一次。

這種游戲只需要邏輯思維能力，與數(shù)字運(yùn)算無關(guān)。雖然玩法簡單，但數(shù)字排列方式卻千變?nèi)f化，所以不少教育者認(rèn)為數(shù)獨(dú)是鍛煉腦筋的好方法。當(dāng)時我也是這樣給學(xué)生說的，這部分內(nèi)容這么難，時挺多出個，但是不能因?yàn)榉种瞪傥覀兙筒粚W(xué)他，或是不認(rèn)真學(xué)習(xí)解決此類問題的思考方法，因?yàn)橥ㄟ^學(xué)習(xí)這部分內(nèi)容，能夠培養(yǎng)學(xué)生有順序地、全面思考問題的能力，培養(yǎng)學(xué)生學(xué)習(xí)數(shù)學(xué)的樂趣。

記得剛出世例題時很多學(xué)生全愣在那里，不知從何開始思考，只有王晨赫估計(jì)是家長帶他提前預(yù)習(xí)了，所以我還什么都沒說時他就急得想趕緊說，結(jié)果讓他說了我才發(fā)現(xiàn)，他是自己明白，不會系統(tǒng)的講解，同學(xué)們?nèi)匀灰活^霧水。于是，我又帶領(lǐng)學(xué)生認(rèn)真分析了題意，明確了每個數(shù)字在每行或每列只出現(xiàn)一次，然后帶領(lǐng)學(xué)生一起分析A那個空里應(yīng)該填幾，很多學(xué)生這時已經(jīng)發(fā)現(xiàn)了答案，這是我讓幾個學(xué)生清晰的表述自己的想法，然后我把想法清晰的板書在黑板上，讓學(xué)生反復(fù)的說，直到每個學(xué)生都會流利的表達(dá)自己的想法。然后讓學(xué)生按照剛才的方法自己思考B所在的空格里填幾，想完后同位兩個互相講想法，這時發(fā)現(xiàn)有幾個學(xué)生不會，于是我找了學(xué)生反復(fù)的教他們。

當(dāng)學(xué)生順利地填完A和B的數(shù)字后，我就問了學(xué)生這樣一個問題，剛才我們?yōu)槭裁聪忍預(yù)，而沒有先填B呢？一些學(xué)生馬上反應(yīng)說：因?yàn)锽所在的行和列數(shù)字信息不全，我給學(xué)生說：這是因?yàn)锳所在的行和列出現(xiàn)了3個不同的數(shù)字，我們就知道A是幾了，而B所在的行和列沒有出現(xiàn)3個不同的數(shù)字，也就是你們剛才說的信息不全，以后再解答這種題目時，我們要先找哪一個數(shù)字呢？學(xué)生馬上答道：誰所在的行和列出現(xiàn)了3個不同的數(shù)字就先找誰。

通過一節(jié)課的學(xué)習(xí)，全班學(xué)生都學(xué)會了有順序地、全面地思考問題，他們對這部分內(nèi)容非常感興趣。