2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法.doc
《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法.doc》由會員分享,可在線閱讀,更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法.doc(3頁珍藏版)》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法 如果上期的“百錢買百雞”中雞的種類數(shù)是變化的,用枚舉法就無能為力了,這里介紹另一種算法——回溯法。 回溯基本思想 回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索法,它的基本思想是:在搜索過程中,當(dāng)探索到某一步時,發(fā)現(xiàn)原先的選擇達不到目標,就退回到上一步重新選擇。它主要用來解決一些要經(jīng)過許多步驟才能完成的,而每個步驟都有若干種可能的分支,為了完成這一過程,需要遵守某些規(guī)則,但這些規(guī)則又無法用數(shù)學(xué)公式來描述的一類問題。下面通過實例來了解回溯法的思想及其在計算機上實現(xiàn)的基本方法。 例1、從N個自然數(shù)(1,2,…,n)中選出r個數(shù)的所有組合。 算法分析:設(shè)這r個數(shù)為a1,a2,…ar,把它們從大到小排列,則滿足: (1) a1>a2>…>ar; (2) 其中第i位數(shù)(1<=i<=r)滿足ai>r-i; 我們按以上原則先確定第一個數(shù),再逐位生成所有的r個數(shù),如果當(dāng)前數(shù)符合要求,則添加下一個數(shù);否則返回到上一個數(shù),改變上一個數(shù)的值再判斷是否符合要求,如果符合要求,則繼續(xù)添加下一個數(shù),否則返回到上一個數(shù),改變上一個數(shù)的值……按此規(guī)則不斷循環(huán)搜索,直到找出r個數(shù)的組合,這種求解方法就是回溯法。 如果按以上方法生成了第i位數(shù)ai,下一步的的處理為: (1) 若ai>r-i且i=r,則輸出這r個數(shù)并改變ai的值:ai=ai-1; (2) 若ai>r-i且i≠r,則繼續(xù)生成下一位ai+1=ai-1; (3) 若ai<=r-i,則回溯到上一位,改變上一位數(shù)的值:ai-1=ai-1-1; 算法實現(xiàn)步驟: 第一步:輸入n,r的值,并初始化; i:=1;a[1]:=n; 第二步:若a[1]>r-1則重復(fù): 若a[i]>r-i,①若i=r,則輸出解,并且a[i]:=a[i]-1; ②若i<>r,則繼續(xù)生成下一位:a[i+1]:=a[i]-1; i:=i+1; 若 a[i]<=r-i,則回溯:i:=i-1; a[i]:=a[i]-1; 第三步:結(jié)束; 程序?qū)崿F(xiàn) var n,r,i,j:integer; a:array[1..10] of integer; begin readln(n,r);i:=1;a[1]:=n; repeat if a[i]>r-i then {符合條件 } if i=r then {輸出} begin for j:=1 to r do write(a[j]:3); writeln; a[i]:=a[i]-1; end else {繼續(xù)搜索} begin a[i+1]:=a[i]-1; i:=i+1;end else{回溯} begin i:=i-1; a[i]:=a[i]-1;end; until a[1]=r-1; end. 下面我們再通過另一個例子看看回溯在信息學(xué)奧賽中的應(yīng)用。 例2 數(shù)的劃分(noipxxtg) 問題描述 整數(shù)n分成k份,且每份不能為空,任意兩份不能相同(不考慮順序)。 例如:n=7,k=3,下面三種分法被認為是相同的。 1,1,5; 1,5,1; 5,1,1; 問有多少種不同的分法。 輸入:n,k (6- 1.請仔細閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法 2019 2020 年高 信息技術(shù) 全國青少年 奧林匹克 聯(lián)賽 教案 回溯
鏈接地址:http://m.italysoccerbets.com/p-2665655.html