1、高一必修1教科版信息技術(shù)第四單元非數(shù)值計算之遞歸程序基礎(chǔ)知識回顧1、學(xué)習(xí)了分支語句和循環(huán)語句；2、學(xué)習(xí)了python函數(shù)的定義與調(diào)用。1、掌握遞歸算法的概念；2、用遞歸編寫“漢諾塔”游戲程序，解決實際問題。本課目標for i in range(2,n+1): s=s*ireturn s#調(diào)用factorial函數(shù)total=factorial(4) print(total)python函數(shù)的定義與調(diào)用的例子：求n!=1*2*.*(n-1)*n def factorial(n):s=1factorial(n)=n!=1*2*.*(n-1)*n factorial(n-1)=(n-1)!=1*2*

2、.*(n-1)factorial(n)=factorial(n-1)*nfactorial(4)=factorial(3)*4=factorial(2)*3*4 =factorial(1)*2*3*4求4！的執(zhí)行過程factorial(4)調(diào)用返回逐層回歸遞推調(diào)用def factorial(n): if n=1:return 1; else:return n*factorial(n-1) print(factorial(4)=24*factorial(3)3*factorial(2)2*factorial(1)1=6=24def factorial(n): if n=1:return 1; e

3、lse:return n*factorial(n-1) print(factorial(4)像上面的程序段中，直接或間接地調(diào)用自身的方法稱為遞歸?？梢詫⑦f歸簡單類比為具有相似性重復(fù)的事物。遞歸程序遞歸程序遞歸是計算科學(xué)領(lǐng)域中一種重要的計算思維模式，它既是一種抽象表達的手段，也是一種問題求解的重要方法。從上面遞歸的定義可以得出：遞推關(guān)系是遞歸的重要組成，而邊界條件是遞歸的另一個要素，它保證遞歸能在有限次的計算后得出結(jié)果，而不會產(chǎn)生無限循環(huán)。遞歸的基本思想是將規(guī)模較大的問題層層轉(zhuǎn)化為規(guī)模較小的同類問題求解。1(n 1)求n的階乘的遞歸定義為：factorial(n) n * factorial(n

4、 1)玩轉(zhuǎn)“漢諾塔”游戲ACB如圖所示，木板上有A、B、C三根桿，A桿上有若干木盤，規(guī)定每次移動一個木盤，且小的木盤只能疊在大的木盤上面。請設(shè)計算法，用盡可能少的次數(shù)把所有木盤從A桿全部移到C桿上。1、求出最少移動次數(shù)；2、輸出將木盤從A桿移動到C桿的每一步移動的過程。分析“漢諾塔”游戲要使移動次數(shù)盡可能少，必須排除無效移動。不妨以3個木盤為例，如圖。一次只能移動一個木盤，大盤不能放在小盤上。ABC同學(xué)們可以嘗試著將黃色和藍色小木盤移到B或C，最后紅色木盤一定是從A移到C。因此移動一定按照下面的方式，次數(shù)才是最少的。1、黃色從A-C2、藍色從A-B3、黃色從C-B4、紅色從A-C5、黃色從B-

5、A6、藍色從B-C7、黃色從A-C分析“漢諾塔”游戲ABC遞歸是將規(guī)模較大的問題層層轉(zhuǎn)化為規(guī)模較小的同類問題求解。我們可以這樣看待移動問題：第1步：將上面兩個木盤借助C從A-B；第2步：將紅色木盤從A-C；第3步：將上面兩個木盤借助A從B-C。 設(shè)f(3)表示將3個木盤從A借助B移動到C最少的移動次數(shù)，則第1步移動次數(shù)是f(2)，第2步移動次數(shù)是1，第3步移動次數(shù)也是f(2),且有f(3)=2f(2)+1。 擴展到f(n)即是：f(n)=2f(n-1)+1,邊界是f(1)=1?？梢岳盟鼈兙帉懬笠苿哟螖?shù)的遞歸程序?！皾h諾塔”游戲遞歸程序一：#定義函數(shù)def move(n): if n=1:re

6、turn 1 else:return 2*move(n-1)+1#主程序n = int(input(請輸入木盤的個數(shù)：) print(move(n)當(dāng)程序運行時我們輸入n的值請輸入木盤的個數(shù)：11請輸入木盤的個數(shù)：2 3請輸入木盤的個數(shù)：3 7分析“漢諾塔”游戲二怎么樣將移動的過程每一步都寫出來？ 由于將n個木盤從A桿移動到C桿，需要借助中間的B桿，只要超過一個木盤，在移動過程中，總會存在起始桿、過渡桿及目標桿的問題，因此，定義函數(shù)時，用到了4個參數(shù)：hanoi(n,s,m,t),其中：n表示移動的盤子的數(shù)量，s表示盤子的起始桿，m表示中間過渡桿，t表示目標桿。ABCABCABC分析“漢諾塔”

7、游戲ABCABCABChanoi(n,s,m,t)(n1)hanoi(n-1,s,t,m)hanoi(n-1,m,s,t)第n個從s移到t“漢諾塔”游戲遞歸程序二ABCABCABC#定義函數(shù)def move(n,s,m,t): if n=1:print(s,-,t) else:move(n-1,s,t,m)print(s,-,t)move(n-1,m,s,t)#主程序n = int(input(請輸入木盤的個數(shù)：) move(n,a,b,c)請輸入木盤的個數(shù)：3 a - ca - bc - ba - cb - ab - ca - c課堂總結(jié)一、遞歸直接或間接地調(diào)用自身的方法稱為遞歸。二、編寫遞

8、歸程序時：要分析清楚遞歸定義，明確邊界條件和遞推關(guān)系式。玩轉(zhuǎn)“漢諾塔”游戲#定義函數(shù)def move(n,s,m,t): if n=1:print(s,-,t) else:move(n-1,s,t,m)print(s,-,t)move(n-1,m,s,t)#主程序n = int(input(請輸入木盤的個數(shù)：) move(n,a,b,c)請輸入木盤的個數(shù)：3 a - ca - bc - ba - cb - ab - ca - c？玩轉(zhuǎn)“漢諾塔”游戲的程序執(zhí)行過程move(3,a,b,c)調(diào)用move(2,a,c,b)print(a,-,c)move(2,b,a,c)move(1,a,b,c)print(a,-,b)move(1,c,a,b)def move(n,s,m,t): if n=1:print(s,-,t) else:move(n-1,s,t,m)print(s,-,t)move(n-1,m,s,t) move(3,a,b,c)move(1,b,c,a)print(b,-,c)move(1,a,b,c)輸出：a-c輸出：a-b輸出：c-b輸出：a-c輸出：b-a輸出：b-c輸出：a-c課后作業(yè)：下面是“漢諾塔”游戲中求最少移