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

1、2019-2020 年高中信息技術(shù)全國青少年奧林匹克聯(lián)賽教案回溯法如果上期的“百錢買百雞”中雞的種類數(shù)是變化的，用枚舉法就無能為力了，這里介紹 另一種算法一一回溯法?；厮莼舅枷牖厮莘ㄊ且环N既帶有系統(tǒng)性又帶有跳躍性的搜索法，它的基本思想是：在搜索過程中， 當探索到某一步時，發(fā)現(xiàn)原先的選擇達不到目標，就退回到上一步重新選擇。它主要用來解決一些要經(jīng)過許多步驟才能完成的，而每個步驟都有若干種可能的分支，為了完成這一過程， 需要遵守某些規(guī)則，但這些規(guī)則又無法用數(shù)學公式來描述的一類問題。下面通過實例來了解回溯法的思想及其在計算機上實現(xiàn)的基本方法。例1、從N個自然數(shù)(1,2,n)中選出r個數(shù)的所有組合。算

2、法分析：設這r個數(shù)為ai,a2,ar,把它們從大到小排列，則滿足：(1)aia2ar；(2)其中第i位數(shù)(1=ir-i;我們按以上原則先確定第一個數(shù)，再逐位生成所有的r個數(shù)，如果當前數(shù)符合要求，則添加下一個數(shù)；否則返回到上一個數(shù)，改變上一個數(shù)的值再判斷是否符合要求，如果符合要 求，則繼續(xù)添加下一個數(shù)，否則返回到上一個數(shù)，改變上一個數(shù)的值按此規(guī)則不斷循環(huán)搜索，直到找出r個數(shù)的組合，這種求解方法就是回溯法。如果按以上方法生成了第i位數(shù)a,下一步的的處理為：(1)若air-i且i=r，則輸出這r個數(shù)并改變ai的值:ai=ai-1;(2)若air-i且i豐r，則繼續(xù)生成下一位ai+1=a -1;(3)

3、若air-1則重復：若air-i，若i=r，則輸出解，并且ai:=ai-1;若ir，則繼續(xù)生成下一位:ai+1:=ai-1; i:=i+1;若air-i then 符合條件if i=r then 輸出beginfor j:=1 to r do write(aj:3);write In;ai:=ai-1;endelse 繼續(xù)搜索begi n ai+1:=ai-1; i:=i+1;e ndelse回溯beg in i:=i-1; ai:=ai-1;e nd;un til a1=r-1;en d.F面我們再通過另一個例子看看回溯在信息學奧賽中的應用。例2數(shù)的劃分(noipxxtg)問題描述 整數(shù)n分

4、成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7,k=3，下面三種分法被認為是相同的。1，1，5; 1，5，1; 5，1，1;問有多少種不同的分法。輸入：n，k(6n=200，2=k=6)輸出：一個整數(shù)，即不同的分法。樣例輸入：7 3輸出：4 四種分法為：1,1,5; 1,2,4; 1,3,3; 2,2,3;算法分析：此題可以用回溯法求解，設自然數(shù)n拆分為ai,a2,ak,必須滿足以下兩個條件：(1)n=ai+a2+ak；(2)ai=a2=ak(避免重復計算)；現(xiàn)假設己求得的拆分數(shù)為ai,a2,ai,且都滿足以上兩個條件，設sum=n-ai-a2-ai,我們根據(jù)不同的情形進

5、行處理：(1)如果i=k,則得到一個解，則計數(shù)器t加1，并回溯到上一步，改變ai-1的值；(2)如果i=ai,則添加下一個元素ai+1；(3)如果ik且sumai,則說明達不到目標，回溯到上一步，改變ai-1的值； 算法實現(xiàn)步驟如下：第一步：輸入自然數(shù)n,k并初始化；t:=0; i:=1;ai:=1; sum:=n-1; nk:=n div k;第二步：如果a1=ai則繼續(xù)搜索；若sum=ai then 判斷是否回溯 begininc(i);ai:=ai-1;sum:=sum-ai;endelse begin dec(i); inc(ai); sum:=sum+ai+1-1; end; end

6、;un til a1 nk; writel n( t);en d.回溯法是通過嘗試和糾正錯誤來尋找答案，是一種通用解題法，在NOIP中有許多涉及回溯繼續(xù)搜回溯搜索問題的題目都可以用回溯法來求解。2019-2020 年高中信息技術(shù)全國青少年奧林匹克聯(lián)賽教案多精度數(shù)值處理課題：多精度數(shù)值的處理目標：知識目標：多精度值的加、減、乘、除 能力目標：多精度值的處理，優(yōu)化！ 重點：多精度的加、減、乘 難點：進位與借位處理 板書示意：1） 輸入兩個正整數(shù)，求它們的和2） 輸入兩個正整數(shù)，求它們的差3） 輸入兩個正整數(shù)，求它們的積4）輸入兩個正整數(shù)，求它們的商 授課過程: 所謂多精度值處理，就是在對給定的數(shù)據(jù)

7、范圍， 用語言本身提供的數(shù)據(jù)類型無法直接進行處 理（主要指加減乘除運算），而需要采用特殊的處理辦法進行?？纯聪旅娴睦?。例1從鍵盤讀入兩個正整數(shù)，求它們的和。分析：從鍵盤讀入兩個數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知 道，在pascal語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當兩個被加數(shù)據(jù)大時，上述算 法顯然不能求出精確解， 因此我們需要尋求另外一種方法。在讀小學時，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個整數(shù)相加的算法。8 5 6A3A2A1+ 2 5 5+B3B2B11 1 1 1C4C3C2C1圖1圖2如果我們用數(shù)組A、B分別存儲加數(shù)和被加數(shù)，用數(shù)組

8、C存儲結(jié)果。則上例有A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,兩數(shù)相加如圖2所示。由上圖可以看出：Ci:= Ai+Bi;if Ci10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end;因此，算法描述如下：procedureadd(a,b;var c); a,b,c都為數(shù)組，a存儲被加數(shù)，b存儲加數(shù)，c存儲結(jié)果var i,x:integer; begini:=1endend;通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設計如下：program exam1; constmax=200;v

9、ara,b,c:array1.max of 0.9; n:string;lena,lenb,lenc,i,x:integer;beginwrite(Input augend:); readln(n);lena:=length(n); 加數(shù)放入a數(shù)組 for i:=1 to lena do alena-i+1:=ord(ni)-ord(0);write(Input addend:); readln(n);lenb:=length(n); 被加數(shù)放入b數(shù)組 for i:=1 to lenb do blenb-i+1:=ord(ni)-ord(0);i:=1;writelnend.例2高精度減法。w

10、hile (i0) or(i=bx := ai + bi + x div 10; ci := x mod 10;i := i + 1 數(shù)組的長度) do begin第i位相加并加上次的進位存儲第i位的值位置指針變量while (i=lena) or(i=10 then begin lenc:=i;ci:=1end else lenc:=i-1;for i:=lenc downto 1 do write(ci); 兩數(shù)相加，然后加前次進位保存第i位的值處理最高進位輸出結(jié)果從鍵盤讀入兩個正整數(shù)，求它們的差。分析：類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數(shù)必須比 減數(shù)大，同時需

11、要處理借位。因此，可以寫出如下關系式if aibi then begin ai+1:=ai+1-1;ai:=ai+10 endci:=ai-bi類似，高精度減法的參考程序：program exam2;constmax=200;vara,b,c:array1.max of 0.9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite(Input minuend:); readln(n1);write(Input subtrahend:); readln(n2);處理被減數(shù)和減數(shù)if (length(n1)length(n2) or (lengt

12、h(n1)=length(n2) and (n1n2) then beginn:=n1;n1:=n2;n2:=n;write(-) n11) do dec(lenc); for i:=lencdownto 1 do write(ci);writelnend.例3高精度乘法。 從鍵盤讀入兩個正整數(shù)，求它們的積。分析：類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位 進乘法運算時，必須進行錯位相加，如圖3,圖4。8 5 6A3A2Aii:=1;while (i=lena) or(i1) do dec(le nc);for i:=le nc dow nto 1 do write

13、(ci);writelnen d.例4高精度除法。從鍵盤讀入兩個正整數(shù)，求它們的商（做整除）新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有 移位處理。當然,分析： 做除法時，每一次上商的值都在09,每次求得的余數(shù)連接以后的若干位得到為了程序簡潔,可以避免高精度乘法,用09次循環(huán)減法取代得到商的值。這里,我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果,采取的方法是按位相除法。參考程序：program exam4;constmax=200;vara,c:array1.max of 0.9;x,b:longint;n1,n2:string;lena:integer;code,i,j:integer;beginwrite(Input dividend:); readln(n1);write(Input divisor:); readln(n2);lena:=length(n1);for i:=1 to lena do ai := ord(n1i) - ord(0);val(n2,b,code);按位相除x:=0;for i:=1 to lena do beginci:=(x*10+ai) div b;x:=(x*10+ai) mod b;end;顯示商j:=1;while (cj=0) and