算法基礎(chǔ)課件

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

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

3、；求x=2a-b/2；求y=b/2-a；輸出x和y的值；結(jié)束。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.編寫程序計(jì)算機(jī)解決問題的第三步利用Python語言編程程序4.調(diào)試運(yùn)行程序如果程序語法有錯(cuò)誤，程序運(yùn)行時(shí)計(jì)算機(jī)會給出提示信息，人們可根據(jù)提示修改程序，直到無錯(cuò)；我們還需要對結(jié)果進(jìn)行驗(yàn)證，因?yàn)檫壿嬪e(cuò)誤或計(jì)算方法錯(cuò)誤計(jì)算機(jī)無法檢查。所以若出現(xiàn)后一種情況，可能需要返回前幾步進(jìn)一步修改

4、，直到滿意。計(jì)算機(jī)解決問題的第四步分析問題設(shè)計(jì)算法編寫程序調(diào)試運(yùn)行程序1234計(jì)算機(jī)解決問題的過程算法的概念描述算法的方法計(jì)算機(jī)解決問題的步驟算法的特征01020403在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。有窮性、確定性、數(shù)據(jù)輸入、數(shù)據(jù)輸出、可行性、自然語言流程圖偽代碼重點(diǎn)讀懂流程圖，三種基本結(jié)構(gòu)分析問題設(shè)計(jì)算法編寫程序調(diào)試運(yùn)行程序 有1、2、3、4個(gè)數(shù)字，能組成多少個(gè)互不相同且無重復(fù)數(shù)字的三位數(shù)？都是多少？ 程序分析：可填在百位、十位、個(gè)位的數(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)一個(gè)整數(shù)，它加上100后是一個(gè)完全平方數(shù)，再加上268又是一個(gè)完全平方數(shù)，請問該數(shù)是多少？程序分析：在10萬以內(nèi)判斷，先將該數(shù)加上100后再開方，再將該數(shù)加上268后再開方，如果開方后的結(jié)果滿足如下條件，即是結(jié)果。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輸入三個(gè)整數(shù)x,y,z，請把這三個(gè)數(shù)由小到大輸出。程序分析：我們想辦法把最小的數(shù)放到x上，先將x與y進(jìn)行比較，如果xy則將x與y的值進(jìn)行交換，然后再用x與z進(jìn)行比較，如果xz則將x與z的值進(jìn)行交換，這樣能使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個(gè)月起每個(gè)月都生一對兔子，小兔子長到第三個(gè)月后每個(gè)月又生一對兔子，假如兔子都不死，問每個(gè)月的兔子總數(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之間有多少個(gè)素?cái)?shù)，并輸出所有素?cái)?shù)。程序分

9、析：判斷素?cái)?shù)的方法：用一個(gè)數(shù)分別去除2到sqrt(這個(gè)數(shù))，如果能被整除，則表明此數(shù)不是素?cái)?shù)，反之是素?cái)?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ù)”是指一個(gè)三位數(shù)，其各位數(shù)字立方和等于該數(shù)本身。例如：153是一個(gè)“水仙花數(shù)”，因?yàn)?53=1的三次方5的三次方3的三次方。程序分析：利用for循環(huán)控制100-999個(gè)數(shù)，每個(gè)數(shù)分解出個(gè)位，十位，百位。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,將一個(gè)正整數(shù)分解質(zhì)因數(shù)。例如：輸入90,打印出90=2*3*3*5。程序分析：對n進(jìn)行分解質(zhì)因數(shù)，應(yīng)先找到

11、一個(gè)最小的質(zhì)數(shù)k，然后按下述步驟完成：(1)如果這個(gè)質(zhì)數(shù)恰等于n，則說明分解質(zhì)因數(shù)的過程已經(jīng)結(jié)束，打印出即可。(2)如果nk，但n能被k整除，則應(yīng)打印出k的值，并用n除以k的商,作為新的正整數(shù)你n,重復(fù)執(zhí)行第一步。(3)如果n不能被k整除，則用k+1作為k的值,重復(fù)執(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輸入兩個(gè)正整數(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是一個(gè)數(shù)字。例如2+22+222+2222+22222(此時(shí)共有5個(gè)數(shù)相加)，幾個(gè)數(shù)相加

13、有鍵盤控制。程序分析：關(guān)鍵是計(jì)算出每一項(xiàng)的值。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一個(gè)數(shù)如果恰好等于它的因子之和，這個(gè)數(shù)就稱為“完數(shù)”。例如6=123.編程找出1000以內(nèi)的所有完數(shù)。程序分析：因子就是所有可以整除這個(gè)數(shù)的數(shù),不包括這個(gè)數(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猴子吃桃問題：猴子第一天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不癮，又多吃了一個(gè)，第二天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上想再吃時(shí)，見只剩下一個(gè)桃子了。求第一天共摘了多少。程序分析：采取逆向思維的方法，從后往前推斷。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兩個(gè)乒乓球隊(duì)進(jìn)行比賽，各出三人。甲隊(duì)為a,b,c三人，乙隊(duì)為x,y,z三人。已抽簽決定比賽名單。有人向隊(duì)員打聽比賽的名單。a說他不和x比，c說他不和x,z比，請編程序找出三隊(duì)賽手的名單。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有一分?jǐn)?shù)序列：2/1，3/2，5/3，8/5，13/8，21/13.求出這個(gè)數(shù)列的前20項(xiàng)之和。程序分析：請抓住分子與分母的變化規(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!