資源簡(jiǎn)介

(共16張PPT)
05 循環(huán)分支運(yùn)用
程序設(shè)計(jì)基礎(chǔ)
學(xué)習(xí)目標(biāo)
循環(huán)分支綜合運(yùn)用
0 1
窮舉法應(yīng)用
0 2
如果兩個(gè)數(shù)都能夠被一個(gè)數(shù)整除，則這個(gè)數(shù)就是兩個(gè)數(shù)的公約數(shù)。
如，8 和 4 都可以被2整除，2就是 8 和 4的公約數(shù)。
公約數(shù)中最大的稱為最大公約數(shù)。
如 8 和 4 都可以被2或4整除，2和4都是8 和 4的公約數(shù)。其中4最大，4就是8 和 4的最大公約數(shù)。
最大公約數(shù) 5-1
編程求204和85的最大公約數(shù)，有兩種辦法可以解決這個(gè)問(wèn)題
應(yīng)用窮舉法。窮舉法也叫枚舉法或列舉法。這種方法的主要思想是：在要解決的問(wèn)題是由有限種情況組成時(shí)，把所有的情況一一列舉出來(lái)，再對(duì)其一一進(jìn)行判斷和解決。
依次判斷從1到85之間的數(shù)字，是否能夠同時(shí)整除204和85
答案應(yīng)該是17
最大公約數(shù) 5-2
最大公約數(shù) 5-3
應(yīng)用輾轉(zhuǎn)相減法。
輾轉(zhuǎn)相減法的原理：兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的差的最大公約數(shù)。
例如，252和105的最大公約數(shù)是21（252 = 21 × 12；105 = 21 × 5）；因?yàn)?52 105 = 147，所以147和105的最大公約數(shù)也是21。在這個(gè)過(guò)程中，較大的數(shù)縮小了，所以繼續(xù)進(jìn)行同樣的計(jì)算可以不斷縮小這兩個(gè)數(shù)直至其中一個(gè)變成零。這時(shí)，所剩下的還沒(méi)有變成零的數(shù)就是兩數(shù)的最大公約數(shù)。
最大公約數(shù) 5-4
你認(rèn)為兩種算法，哪一種比較好？為什么？
最大公約數(shù) 5-5
如果兩個(gè)數(shù)都可以整除一個(gè)數(shù)，則這個(gè)數(shù)就是那兩個(gè)數(shù)的公倍數(shù)。
如 6和8都可以整除48，48就是6和8的公倍數(shù)。公倍數(shù)中最小的稱為最小公倍數(shù)。如 48、24都是6和8的公倍數(shù)，24是公倍數(shù)中最小的，是6和8的最小公倍數(shù)。
編程求204和85的最小公倍數(shù)。（答案應(yīng)該是1020）
一種辦法是窮舉法，自己嘗試編程序
最小公倍數(shù) 3-1
也可以借助最大公約數(shù)求最小公倍數(shù)，步驟： 　　
一、利用輾除法或其它方法求得最大公約數(shù)； 　　
二、 最小公倍數(shù)等于兩數(shù)之積除以最大公約數(shù)。 　　
舉例：12和8的最大公約數(shù)為4 　　
12×8/4=24 　　兩數(shù)的最小公倍數(shù)是24
最小公倍數(shù) 3-2
你認(rèn)為兩種算法，哪一種比較好？為什么？
最小公倍數(shù) 3-3
素?cái)?shù)，又叫質(zhì)數(shù)，是除了1和它本身之外再不能被其他數(shù)整除的自然數(shù)。
由于找不到一個(gè)通項(xiàng)公式來(lái)表示所有的素?cái)?shù)，所以對(duì)于數(shù)學(xué)家來(lái)說(shuō)，素?cái)?shù)一直是一個(gè)未解之謎。
求素?cái)?shù)的方法有很多種，最簡(jiǎn)單的方法是根據(jù)素?cái)?shù)的定義來(lái)求。對(duì)于一個(gè)自然數(shù)N，用大于1小于N的各個(gè)自然數(shù)都去除一下N，如果都除不盡，則N為素?cái)?shù)，否則N為合數(shù)。但是，如果用素?cái)?shù)定義的方法來(lái)編制計(jì)算機(jī)程序，它的效率一定是非常低的，其中有許多地方都值得改進(jìn)。
求素?cái)?shù) 5-1
利用素?cái)?shù)定義，編程求50個(gè)素?cái)?shù)
試著改進(jìn)算法，提高效率
求素?cái)?shù) 5-2
求素?cái)?shù) 5-3
改進(jìn)建議：
第一，對(duì)于一個(gè)自然數(shù)N，只要能被一個(gè)非1非自身的數(shù)整除，它就肯定不是素?cái)?shù)，所以不必再用其他的數(shù)去除。
第二，對(duì)于N來(lái)說(shuō)，只需用小于N的素?cái)?shù)去除就可以了。例如，如果N能被15整除，實(shí)際上就能被3和5整除，如果N不能被3和5整除，那么N也決不會(huì)被15整除。
第三，對(duì)于N來(lái)說(shuō)，不必用從2到N一1的所有素?cái)?shù)去除，只需用小于等于√N(yùn)(根號(hào)N)的所有素?cái)?shù)去除就可以了。
求素?cái)?shù) 4-3
求素?cái)?shù) 4-4
循環(huán)分支綜合運(yùn)用
最大公約數(shù)
最小公倍數(shù)
求素?cái)?shù)
窮舉法應(yīng)用
總結(jié)

展開(kāi)更多......

收起↑