數獨實(shí)驗報告范文(《數獨》教學(xué)反思范文)
數獨實(shí)驗報告范文
數獨實(shí)驗報告范文
Sudoku 數獨實(shí)驗報告
一、 算法描述
求解Sudoku讓人最容易想到的方法是窮舉每個(gè)方格可能的值，如果符合條件，則得到解，不符合條件則進(jìn)行回溯。通過(guò)遞歸的方法，顯然可以得到數獨的解。
我想到的簡(jiǎn)單的遞歸方法，是每一行從左到右，試驗每一個(gè)方格可能的數字，進(jìn)行遞歸。這種方法看似非常麻煩，實(shí)際上對于一般的數獨題，速度是非常快的，思想比較簡(jiǎn)單，寫(xiě)出來(lái)的代碼也非常簡(jiǎn)單、易懂。
算法1：簡(jiǎn)單遞歸方法
從第一個(gè)格開(kāi)始，從1到9試驗，是否滿(mǎn)足行、列、九宮格互不相同的條件。若滿(mǎn)足條件，則填入該數字，再試驗下一個(gè)格。當一個(gè)格子出現沒(méi)有數字能填的情況時(shí)，說(shuō)明已經(jīng)填的數字有誤，回溯，再進(jìn)行遞歸。
算法2：優(yōu)化的遞歸算法
先遍歷所有格子，統計每種格子可能出現數字的個(gè)數。每次挑選可能出現數字個(gè)數最少的格子來(lái)進(jìn)行遞歸。
設置三維數組poss[i][j][k]來(lái)存儲可能出現數字的信息。poss[i][j][0]記錄i行j列的格子可能出現數字的個(gè)數，poss[i][j][k](1<=k<=9) 若poss[i][j][k]=1，表示k可能在（i，j）格出現。若poss[i][j][k]=0，表示k不可能在（i，j）格中出現。每次找poss[i][j][0]最小的格子，來(lái)進(jìn)行下一個(gè)遞歸。
算法3：生成數獨棋盤(pán)的算法
我最開(kāi)始的想法是窮舉法，隨機生成滿(mǎn)足行各不相同的9行，再判斷9宮格、每列是否符合要求，符合條件時(shí)，隨機生成停止。然而，這種算法的當然時(shí)間復雜度顯然是過(guò)高。第99一步的隨機生成的次數是9*9/P9=9608。隨機生成一組棋盤(pán)耗時(shí)就非常大。后來(lái)，我從求解的個(gè)數的程序獲得啟發(fā)。算法二對于1000多組解的數獨棋盤(pán)，解起來(lái)也很快。隨機生成填9個(gè)方格，再用算法一的方法解出來(lái)，取第一組正確的解作為棋盤(pán)即可生成填好的棋盤(pán)。再把一定數量的格子的.數字隨機刪除，計算解的個(gè)數。如果解唯一，就得到了棋盤(pán)。
二、數據結構
這三種算法的數據結構不是非常復雜，只是普通的數組。
算法一：數組a[i][j]
算法二：數組a[i][j]和poss[i][j][k]
算法三：數組a[i][j]和poss[i][j][k]
三、時(shí)間效率分析
算法1：這種算法在tsinsen系統上只用了15ms得到全部答案。
雖然這種算法在tsinsen系統的測試中有很好的表現，但是我試了試在幾道骨灰級難度的題，發(fā)現這種算法可能會(huì )用到10秒以上的時(shí)間，并且測試數據不同，時(shí)間差異非常大。
我認為，這種算法的漏洞在于，如果開(kāi)始的格子可能出現的數字非常多，遞歸樹(shù)開(kāi)始的枝會(huì )非常多。并且，我們一般做數獨題，都會(huì )先挑可能出現數字個(gè)數最少的格子來(lái)填，充分利用了已知條件。然而，這種算法只按格子的行列順序來(lái)試驗，顯然非常傻。于是，我想出了第二種算法。
算法2：這種算法耗時(shí)長(cháng)。
非常令人失望的是，雖然它能在短時(shí)間內解出骨灰級題目，但是，和上一個(gè)算法相比，對于簡(jiǎn)單的題目，它比較耗時(shí)。在tsinsen系統中測試的時(shí)間是91ms。它的缺陷在于，每次遞歸都必須更新（i，j）格子所在的行、列、九宮格所有的元素。每次要求20個(gè)數的poss[i][j][]。回溯同樣要更新。并且求poss[i][j][]的函數時(shí)間復雜度是O（n）。每一步所耗時(shí)間比上一種算法多很多。但是，總的試驗的步數能顯著(zhù)減少。 所以，這種算法適用于數獨解題的動(dòng)畫(huà)演示和解極難題目。
四、程序結構
五、運行結果
六、總結和反思
后來(lái)老師提高了難度，要求程序能求出多解數獨題的解的個(gè)數。幾千個(gè)解的數據都能迅速得出答案，但是幾萬(wàn)個(gè)解的數據，需要很長(cháng)時(shí)間，更別提幾百萬(wàn)的數據。這兩種遞歸的算法都有問(wèn)題，優(yōu)化的空間也有限，需要更強大、高效的算法。
這次Project讓我不斷思考，改進(jìn)了最初的算法。編程是確實(shí)是一個(gè)克服困難、不斷改進(jìn)與超越的過(guò)程。總有新的數據擺在面前，把原來(lái)的算法打擊得很慘，激勵著(zhù)我們研究更加先進(jìn)的算法。
《數獨》教學(xué)反思范文
《數獨》教學(xué)反思范文
作為一位剛到崗的教師，課堂教學(xué)是我們的任務(wù)之一，借助教學(xué)反思我們可以拓展自己的教學(xué)方式，快來(lái)參考教學(xué)反思是怎么寫(xiě)的吧！以下是小編為大家整理的《數獨》教學(xué)反思范文，供大家參考借鑒，希望可以幫助到有需要的朋友。
《數獨》教學(xué)反思1
數獨又叫九宮格，它是一種數字謎題，源自18世紀末的瑞士，后在美國發(fā)展、并在日本得以發(fā)揚光大。中國是在2007年2月28日正式引入數獨。 2007年2月28日，北京晚報智力休閑數獨俱樂(lè )部（數獨聯(lián)盟sudokufederation前身）在新聞大廈舉行加入世界謎題聯(lián)合會(huì )的頒證儀式，這標志著(zhù)中國的數獨研究走向國際舞臺，與世界接軌，它將給數獨愛(ài)好者帶來(lái)更多與世界數獨愛(ài)好者們交流的機會(huì )。在活動(dòng)前通過(guò)調查，我了解到同學(xué)們認識數獨的并不多，可以說(shuō)知之者甚少，親自動(dòng)手做過(guò)數獨的同學(xué)們更是廖廖無(wú)幾，因為知道這種游戲全面考驗做題者觀(guān)察能力和推理能力，雖然玩法簡(jiǎn)單，但數字排列方式卻千變萬(wàn)化，所以不少教育者認為數獨是訓練頭腦的絕佳方式。所以在本學(xué)期第一個(gè)活動(dòng)主題的安排上我大膽地選用了數獨這一活動(dòng)主題。
活動(dòng)的導入是激趣導入，給出一個(gè)空的數獨格，讓學(xué)生們猜一猜這是什么？班級里50多名同學(xué)，每個(gè)班有3—5名同學(xué)能夠簡(jiǎn)單說(shuō)出這是數獨，有1—2名同學(xué)能講出數獨的游戲規則，并且親自做過(guò)數獨，導入的環(huán)節起到了激發(fā)興趣，調動(dòng)積極性的作用，接著(zhù)我在大屏幕上給出一道簡(jiǎn)單的數獨題，有34個(gè)以上數字的數獨題屬于簡(jiǎn)單的題，教師領(lǐng)著(zhù)學(xué)生一起來(lái)填5—6個(gè)數字，讓學(xué)生掌握方法和規則，然后同學(xué)們再開(kāi)始做題，可以獨自完成，也可以同學(xué)合作，在自己動(dòng)手做的過(guò)程中，有基礎的同學(xué)在做題時(shí)比較占優(yōu)勢，能夠很快的在10分鐘左右正確而快速的完成，這些同學(xué)給他們留第2道繼續練習，占絕大多數的同學(xué)是初次接觸，他們做得慢一些，但也能在15分鐘左右完成，也有個(gè)別的初學(xué)的同學(xué)能在10分鐘左右準確地完成，可見(jiàn)同學(xué)們的推理能力、判斷能力和觀(guān)察能力非常強。在活動(dòng)結束之前，請做得快的同學(xué)談一談自己的方法，供大家分享和借鑒。并且布置同學(xué)們回家查閱數獨的方法和技巧。第二次活動(dòng)時(shí)，先介紹查閱的資料，然后繼續進(jìn)行練習，可以單獨完成也可以合作完成。第三次活動(dòng)的內容是數獨賽一賽，一共是兩道題，用一節課的時(shí)間來(lái)完成，每個(gè)班都有十幾名同學(xué)做得又快又好，超過(guò)四分之三的同學(xué)能夠完成比賽題，通過(guò)比賽環(huán)節進(jìn)一步檢測對數獨知識掌握的程度如何，并且讓能力強的同學(xué)多與大家分享和互動(dòng)。
通過(guò)開(kāi)展數獨活動(dòng)，極大的調動(dòng)了學(xué)生開(kāi)動(dòng)腦筋、進(jìn)行主動(dòng)思考的良好習慣，他們的判斷能力和分析推理能力得到了有效的鍛煉和開(kāi)發(fā)，并且拓展了視野，接受了新知識，學(xué)生們團結協(xié)作，互動(dòng)交流，讓數獨這一實(shí)踐活動(dòng)深為同學(xué)們所喜愛(ài)。
活動(dòng)過(guò)程中也有些許的不足，如有少部分學(xué)生跟不上，沒(méi)有完全理解，針對這一問(wèn)題有效的解決方法是在導入過(guò)程中，應該領(lǐng)著(zhù)學(xué)生們多做一些練習，讓每一名同學(xué)都掌握游戲的方法和規則；活動(dòng)過(guò)程應該分層設計活動(dòng)內容，如有些同學(xué)能力特別強，他們做得又快又好，課堂準備的數獨題遠不能滿(mǎn)足他們的需要，針對這一問(wèn)題解決的方法是在他們在完成了簡(jiǎn)單的數獨題后，指導教師應該給他們的是更難一些的題，這將有助于更好地提高和鍛煉，激發(fā)他們不斷挑戰的斗志和能力。第一次把數獨引入綜合實(shí)踐活動(dòng)，在活動(dòng)的開(kāi)展過(guò)程中以及活動(dòng)的實(shí)施中都還存在著(zhù)許多不足和有待完善之處，我將在今后的數獨活動(dòng)中繼續總結和探索，以期在以后的數獨活動(dòng)中讓學(xué)生們獲得更多的體驗和感受，在知識、情感、態(tài)度、能力等各方面都得到鍛煉和提高。
《數獨》教學(xué)反思2
二年級的學(xué)生，自制能力差，最主要的還是要提起學(xué)生的學(xué)習興趣才能更好完成教學(xué)目標，數獨對于二年級的學(xué)生來(lái)說(shuō)還是比較難理解的，在上本節課前，我認真研讀教材，理解教材的`編寫(xiě)意圖。因此，在設計教學(xué)時(shí)，我從最簡(jiǎn)單的填數游戲開(kāi)始，讓學(xué)生理解數獨規則。接著(zhù)讓學(xué)生從簡(jiǎn)單的三宮格入手，降低整節課的難度，從而讓學(xué)生們放輕松，以最好的狀態(tài)進(jìn)入學(xué)習中。
一、以簡(jiǎn)單游戲開(kāi)始，激發(fā)學(xué)生的學(xué)習熱情。
在新授課前，我設計了簡(jiǎn)單的填數游戲，先讓學(xué)生理解行與列，孩子們玩得津津有味，但是只有游戲是不夠的，游戲后要有思考，從第一個(gè)游戲中，通過(guò)談話(huà)，捕捉課堂中及時(shí)生成教學(xué)問(wèn)題，以此開(kāi)展教學(xué)，同時(shí)，從學(xué)生已有的知識經(jīng)驗出發(fā)，調動(dòng)學(xué)生學(xué)習的積極性，讓親身經(jīng)歷知識的形成。學(xué)生們發(fā)現了要想填上類(lèi)似這樣的題的方法，需要至少知道三個(gè)數字。接著(zhù)填三宮格，先讓學(xué)生用語(yǔ)言描述一個(gè)數字在圖中的位置（第幾行，第幾列）。為學(xué)生填數時(shí)能用標準的語(yǔ)言敘述打好基礎。學(xué)生思考的結果是，要想填好數字，應該先找到字母所在的行或列，再進(jìn)行思考。學(xué)生們在不知不覺(jué)中自己發(fā)現了方法，也學(xué)會(huì )了用數學(xué)語(yǔ)言來(lái)表述自己的思考過(guò)程。學(xué)習的積極性被有效調動(dòng)起來(lái)。
二、以學(xué)生已有的知識經(jīng)驗為基礎，加強學(xué)生分析推理能力的發(fā)展。
在教學(xué)例2時(shí)，通過(guò)觀(guān)察、分析等活動(dòng)，讓學(xué)生在推理的過(guò)程中不斷嘗試、調整，學(xué)會(huì )按一定的方法進(jìn)行推理，進(jìn)一步體驗推理的作用。因此教學(xué)中我讓同桌兩人交流，說(shuō)說(shuō)先算A還是先算B,這樣想的理由是什么？在交流過(guò)程中，學(xué)生們明白了做這種題最重要的一條原則，就是先找到字母所在的行和列，然后看哪個(gè)給了三個(gè)數字，再寫(xiě)出字母所表示的數字。這樣層層深入，水到渠成，絲毫看不出老師教學(xué)的痕跡，完全是學(xué)生自己思考的結果，教師只是給予必要的指導，幫助孩子們學(xué)會(huì )用數學(xué)語(yǔ)言來(lái)表述自己的思考過(guò)程。在簡(jiǎn)單推理的過(guò)程中，培養了學(xué)生觀(guān)察、分析、推理和有條理地進(jìn)行數學(xué)表達的能力，學(xué)會(huì )有序地、全面地思考問(wèn)題。
總之，通過(guò)開(kāi)展數獨活動(dòng)，極大的調動(dòng)了學(xué)生開(kāi)動(dòng)腦筋、進(jìn)行主動(dòng)思考的良好習慣，他們的判斷能力和分析推理能力得到了有效的鍛煉和開(kāi)發(fā)，并且拓展了視野，接受了新知識，學(xué)生們團結協(xié)作，互動(dòng)交流，讓數獨這一實(shí)踐活動(dòng)深為同學(xué)們所喜愛(ài)。
活動(dòng)過(guò)程中也有些許的不足，在備課時(shí)，總覺(jué)得已經(jīng)想的很清楚了，但上課時(shí)總會(huì )覺(jué)得有些地方的跨度有些大，還有部分學(xué)生的思維跟不上，沒(méi)有完全理解。因此，我將在今后的數獨活動(dòng)中繼續總結和探索，以期在以后的數獨活動(dòng)中讓學(xué)生們獲得更多的體驗和感受，在知識、情感、態(tài)度、能力等各方面都得到鍛煉和提高。
《數獨》教學(xué)反思3
數獨安排在了本冊書(shū)的最后一個(gè)單元。數獨是一種邏輯性很強的游戲，學(xué)生必須時(shí)刻謹記同一個(gè)數字在同一行、列中只出現一次。
這種游戲只需要邏輯思維能力，與數字運算無(wú)關(guān)。雖然玩法簡(jiǎn)單，但數字排列方式卻千變萬(wàn)化，所以不少教育者認為數獨是鍛煉腦筋的好方法。當時(shí)我也是這樣給學(xué)生說(shuō)的，這部分內容這么難，時(shí)挺多出個(gè)，但是不能因為分值少我們就不學(xué)他，或是不認真學(xué)習解決此類(lèi)問(wèn)題的思考方法，因為通過(guò)學(xué)習這部分內容，能夠培養學(xué)生有順序地、全面思考問(wèn)題的能力，培養學(xué)生學(xué)習數學(xué)的樂(lè )趣。
記得剛出世例題時(shí)很多學(xué)生全愣在那里，不知從何開(kāi)始思考，只有王晨赫估計是家長(cháng)帶他提前預習了，所以我還什么都沒(méi)說(shuō)時(shí)他就急得想趕緊說(shuō)，結果讓他說(shuō)了我才發(fā)現，他是自己明白，不會(huì )系統的講解，同學(xué)們仍然一頭霧水。于是，我又帶領(lǐng)學(xué)生認真分析了題意，明確了每個(gè)數字在每行或每列只出現一次，然后帶領(lǐng)學(xué)生一起分析A那個(gè)空里應該填幾，很多學(xué)生這時(shí)已經(jīng)發(fā)現了答案，這是我讓幾個(gè)學(xué)生清晰的表述自己的想法，然后我把想法清晰的板書(shū)在黑板上，讓學(xué)生反復的說(shuō)，直到每個(gè)學(xué)生都會(huì )流利的表達自己的想法。然后讓學(xué)生按照剛才的方法自己思考B所在的空格里填幾，想完后同位兩個(gè)互相講想法，這時(shí)發(fā)現有幾個(gè)學(xué)生不會(huì )，于是我找了學(xué)生反復的教他們。
當學(xué)生順利地填完A和B的數字后，我就問(wèn)了學(xué)生這樣一個(gè)問(wèn)題，剛才我們?yōu)槭裁聪忍預，而沒(méi)有先填B呢？一些學(xué)生馬上反應說(shuō)：因為B所在的行和列數字信息不全，我給學(xué)生說(shuō)：這是因為A所在的行和列出現了3個(gè)不同的數字，我們就知道A是幾了，而B(niǎo)所在的行和列沒(méi)有出現3個(gè)不同的數字，也就是你們剛才說(shuō)的信息不全，以后再解答這種題目時(shí)，我們要先找哪一個(gè)數字呢？學(xué)生馬上答道：誰(shuí)所在的行和列出現了3個(gè)不同的數字就先找誰(shuí)。
通過(guò)一節課的學(xué)習，全班學(xué)生都學(xué)會(huì )了有順序地、全面地思考問(wèn)題，他們對這部分內容非常感興趣。