算法基礎課件

1、一個籠子里有雞和兔，現(xiàn)在只知道里面一共有35個頭，94個腳，雞和兔各有多少只？試設計一個求解的算法，并用自然語言描述出來.1.分析問題設所求的雞數(shù)是x，兔數(shù)是y，已知籠子里的頭數(shù)是a,腳數(shù)是b，依題意得到如下的方程組：計算機解決問題的第一步x+y=a2x+4y=b 解方程組得：x=2a-b/2 y=b/2-a2.設計算法用自然語言描述算法輸入a和b的值；求x=2a-b/2；求y=b/2-a；輸出x和y的值；結束。計算機解決問題的第二步優(yōu)點：通俗易懂 缺點：語句較長，不 便翻譯成機器語言用流程圖描述算法ab?a=5,b=7,流程圖輸出結果應為？流程圖的基本符號圖形符號符號名稱說明流線起始、終止框

2、表示算法的開始或結束開始框：一流入線結束框：一流出線輸入、輸出框框中標明輸入、輸出的內容只有一流入線和一流出線處理框框中標明進行什么處理只有一流入線和一流出線判定框框中標明判定條件并在框外標明判定后的兩種結果的流向一流入線兩流出線（Y和N）但同時只能一流出線起作用流線表示從某一框到另一框的流向連接圈表示算法流向出口或入口連接點一條流線雞兔同籠問題流程圖開始輸入a,b的值求x=2a-b/2求y=b/2-a輸出x,y的值結束輸入a和b的值；求x=2a-b/2；求y=b/2-a；輸出x和y的值；結束。對照自然語言描述的算法畫流程圖，你可以嗎程序三種基本控制結構（重要）用偽代碼描述算法 輸入a和b的值

3、；求x=2a-b/2；求y=b/2-a；輸出x和y的值；結束。x=2a-b/2y=b/2-aprint x,yInput a,ba=int(input(請輸入頭數(shù):)b=int(input(請輸入腳數(shù):)x=int(2*a-b/2)y=int(b/2-a)print (雞的數(shù)量為,x)print ( 兔的數(shù)量為,y)3.編寫程序計算機解決問題的第三步利用Python語言編程程序4.調試運行程序如果程序語法有錯誤，程序運行時計算機會給出提示信息，人們可根據(jù)提示修改程序，直到無錯；我們還需要對結果進行驗證，因為邏輯錯誤或計算方法錯誤計算機無法檢查。所以若出現(xiàn)后一種情況，可能需要返回前幾步進一步修改

4、，直到滿意。計算機解決問題的第四步分析問題設計算法編寫程序調試運行程序1234計算機解決問題的過程算法的概念描述算法的方法計算機解決問題的步驟算法的特征01020403在有限步驟內求解某一問題所使用的一組定義明確的規(guī)則。有窮性、確定性、數(shù)據(jù)輸入、數(shù)據(jù)輸出、可行性、自然語言流程圖偽代碼重點讀懂流程圖，三種基本結構分析問題設計算法編寫程序調試運行程序 有1、2、3、4個數(shù)字，能組成多少個互不相同且無重復數(shù)字的三位數(shù)？都是多少？ 程序分析：可填在百位、十位、個位的數(shù)字都是1、2、3、4。組成所有的排列后再去掉不滿足條件的排列。if _name_ = _main_: s = (1,2,3,4) for

5、 a in s: for b in s: for c in s: if a != b and b != c and c != a: print %d%d%d %(a,b,c)一個整數(shù)，它加上100后是一個完全平方數(shù)，再加上268又是一個完全平方數(shù)，請問該數(shù)是多少？程序分析：在10萬以內判斷，先將該數(shù)加上100后再開方，再將該數(shù)加上268后再開方，如果開方后的結果滿足如下條件，即是結果。from math import sqrtif _name_ = _main_: i = 1 while i = 2: if year %400 = 0 or (year % 4 = 0 and year % 1

6、00 != 0): sum += 1 print it is the %dth day of the year. % sum輸入三個整數(shù)x,y,z，請把這三個數(shù)由小到大輸出。程序分析：我們想辦法把最小的數(shù)放到x上，先將x與y進行比較，如果xy則將x與y的值進行交換，然后再用x與z進行比較，如果xz則將x與z的值進行交換，這樣能使x最小。if _name_ = _main_: a,b,c = input(),input(),input() if a b: a,b = b,a if a c: a,c = c,a if b c: b,c = c,b print small to big: %d,%d

7、,%d %(a,b,c)輸出9*9口訣。程序分析：分行與列考慮，共9行9列，i控制行，j控制列。if _name_ = _main_: for i in range(1,10): for j in range(1,10): print %d*%d = %-3d %(i,j,i*j), print 輸出國際象棋棋盤。程序分析：用i控制行，j來控制列，根據(jù)i+j的和的變化來控制輸出黑方格，還是白方格。if _name_ = _main_: for i in range(8): for j in range(8): if (i + j) % 2 = 0: print %c%219,else: pri

8、nt a, print古典問題：有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數(shù)為多少？程序分析： 兔子的規(guī)律為數(shù)列1,1,2,3,5,8,13,21.if _name_ = _main_: f1,f2 = 1,1 print 1: %d %f1 print 2: %d %f2 for i in range(3,21,2): f1 = f1 + f2 print %d: %d %(i,f1) f2 = f1 + f2 print %d: %d %(i+1,f2)判斷101-200之間有多少個素數(shù)，并輸出所有素數(shù)。程序分

9、析：判斷素數(shù)的方法：用一個數(shù)分別去除2到sqrt(這個數(shù))，如果能被整除，則表明此數(shù)不是素數(shù)，反之是素數(shù)。from math import sqrtif _name_ = _main_: count = 0 flag = 1 for a in range(101,201): s = int(sqrt(a) for i in range(2,s+1): if a % i = 0: flag = 0 break if flag = 1: count += 1 print a else: flag = 1 print the total num is %d %count打印出所有的“水仙花數(shù)”，所謂

10、“水仙花數(shù)”是指一個三位數(shù)，其各位數(shù)字立方和等于該數(shù)本身。例如：153是一個“水仙花數(shù)”，因為153=1的三次方5的三次方3的三次方。程序分析：利用for循環(huán)控制100-999個數(shù)，每個數(shù)分解出個位，十位，百位。if _name_ = _main_: print water flower number is :, for a in range(100,1000): x,y,z = a/100,a/10%10,a%10 if x*3 + y*3 + z*3 = a: print %d,%a,將一個正整數(shù)分解質因數(shù)。例如：輸入90,打印出90=2*3*3*5。程序分析：對n進行分解質因數(shù)，應先找到

11、一個最小的質數(shù)k，然后按下述步驟完成：(1)如果這個質數(shù)恰等于n，則說明分解質因數(shù)的過程已經(jīng)結束，打印出即可。(2)如果nk，但n能被k整除，則應打印出k的值，并用n除以k的商,作為新的正整數(shù)你n,重復執(zhí)行第一步。(3)如果n不能被k整除，則用k+1作為k的值,重復執(zhí)行第一步。if _name_ = _main_: n = input(please enter a number:) print %d = %n, for k in range(2,n+1): while n != k: if n % k = 0: n = n/k print %d * %k, else: break print

12、n輸入兩個正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)。程序分析：利用輾除法。if _name_ = _main_: print please enter two numbers: s = input(),input() s.sort() a,b = s0,s1 while b != 0: t = a % b a = b b = t print common divisor:%d%a print common multiple:%d%int(s0*s1/a)求s=a+aa+aaa+aaaa+aa.a的值，其中a是一個數(shù)字。例如2+22+222+2222+22222(此時共有5個數(shù)相加)，幾個數(shù)相加

13、有鍵盤控制。程序分析：關鍵是計算出每一項的值。if _name_ = _main_: print please enter a and n: a,n = input(),input() sum = a if n 1: b = a for i in range(2,n+1): b = a + b*10 print b sum += b print a+aa+aaa+. = %ld %sum一個數(shù)如果恰好等于它的因子之和，這個數(shù)就稱為“完數(shù)”。例如6=123.編程找出1000以內的所有完數(shù)。程序分析：因子就是所有可以整除這個數(shù)的數(shù),不包括這個數(shù)自身。if _name_ = _main_: for

14、n1 in range(3,1001): sum = 1 n = n1 for k in range(2,n+1): while n != k: if n % k = 0: n = n/k sum += k else: break sum += n if sum = n1: print sum猴子吃桃問題：猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個，第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第10天早上想再吃時，見只剩下一個桃子了。求第一天共摘了多少。程序分析：采取逆向思維的方法，從后往前推斷。if _name_ = _mai

15、n_: s1 = 1 for day in range(10,1,-1): s2 = (s1+1)*2 s1 = s2 print the total number is %d %s1兩個乒乓球隊進行比賽，各出三人。甲隊為a,b,c三人，乙隊為x,y,z三人。已抽簽決定比賽名單。有人向隊員打聽比賽的名單。a說他不和x比，c說他不和x,z比，請編程序找出三隊賽手的名單。if _name_ = _main_: for x in a,b,c: if x != a and x != c: print x:%s%x for z in a,b,c: if z != x and z != c: print z:%s%z for y in a,b,c: if y != x and y != z: print y:%s%y有一分數(shù)序列：2/1，3/2，5/3，8/5，13/8，21/13.求出這個數(shù)列的前20項之和。程序分析：請抓住分子與分母的變化規(guī)律。if _name_ = _main_: a,b,s = 2,1,0 for n in range(1,21): s += a/b a = a+b b = a-b print sum = %.3f %s求1+2!+3!