2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法.doc

《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法.doc（3頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 回溯法 如果上期的“百錢買百雞”中雞的種類數(shù)是變化的，用枚舉法就無能為力了，這里介紹另一種算法——回溯法。 回溯基本思想 回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索法，它的基本思想是：在搜索過程中，當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先的選擇達(dá)不到目標(biāo)，就退回到上一步重新選擇。它主要用來解決一些要經(jīng)過許多步驟才能完成的，而每個(gè)步驟都有若干種可能的分支，為了完成這一過程，需要遵守某些規(guī)則，但這些規(guī)則又無法用數(shù)學(xué)公式來描述的一類問題。下面通過實(shí)例來了解回溯法的思想及其在計(jì)算機(jī)上實(shí)現(xiàn)的基本方法。 例1、從N個(gè)自然數(shù)(1,2,…,n)中選出r個(gè)數(shù)的所有組合。 算法分析：設(shè)這r個(gè)數(shù)為a1,a2,…ar,把它們從大到小排列，則滿足： （1） a1>a2>…>ar; （2） 其中第i位數(shù)(1<=i<=r)滿足ai>r-i; 我們按以上原則先確定第一個(gè)數(shù)，再逐位生成所有的r個(gè)數(shù)，如果當(dāng)前數(shù)符合要求，則添加下一個(gè)數(shù);否則返回到上一個(gè)數(shù)，改變上一個(gè)數(shù)的值再判斷是否符合要求，如果符合要求，則繼續(xù)添加下一個(gè)數(shù)，否則返回到上一個(gè)數(shù)，改變上一個(gè)數(shù)的值……按此規(guī)則不斷循環(huán)搜索，直到找出r個(gè)數(shù)的組合，這種求解方法就是回溯法。 如果按以上方法生成了第i位數(shù)ai，下一步的的處理為： （1） 若ai>r-i且i=r，則輸出這r個(gè)數(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; 算法實(shí)現(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. 下面我們再通過另一個(gè)例子看看回溯在信息學(xué)奧賽中的應(yīng)用。 例2 數(shù)的劃分（noipxxtg） 問題描述 整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。 例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。 1，1，5; 1，5，1; 5，1，1; 問有多少種不同的分法。 輸入：n，k (6=ai,則添加下一個(gè)元素ai+1； （3） 如果i=a[i]則繼續(xù)搜索； ②若sum=a[i] then {判斷是否回溯} begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{繼續(xù)搜} else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯} end; until a[1]>nk; writeln(t); end. 回溯法是通過嘗試和糾正錯(cuò)誤來尋找答案，是一種通用解題法，在NOIP中有許多涉及搜索問題的題目都可以用回溯法來求解。