算法及算法的描述方法

1、西安電子科技大學(xué)計(jì)算機(jī)學(xué)院西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 張淑平張淑平Computer Science & Engineering, Xidian University, China - School of Computer Science & Engineering, Xidian University, China 2 - School of Computer Science & Engineering, Xidian University, China 3 素?cái)?shù)的定義：一個(gè)大于素?cái)?shù)的定義：一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有的整數(shù)，如果它的正因數(shù)只有1和它和它本身，就

2、叫做素?cái)?shù)，否那么就叫合數(shù)。本身，就叫做素?cái)?shù)，否那么就叫合數(shù)。 - School of Computer Science & Engineering, Xidian University, China 4 YNK 2K不能整除不能整除n?K K+1輸出輸出n是素?cái)?shù)是素?cái)?shù) 輸入輸入n的值的值開始開始結(jié)束結(jié)束YNK等于等于n?輸出輸出n不是素?cái)?shù)不是素?cái)?shù) - School of Computer Science & Engineering, Xidian University, China 5 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法( (歐幾里得算法歐幾里得算法) )：給定兩個(gè)正整數(shù)給定兩個(gè)正整數(shù)m m

3、和和n n，求它們的最大公約數(shù)，求它們的最大公約數(shù)( (公因子公因子) )。步驟步驟1:1:【求余數(shù)】以【求余數(shù)】以n n除除m m并令并令r r為所得余數(shù)為所得余數(shù)(0r(0rn)n)步驟步驟2:2:【余數(shù)為【余數(shù)為0?0?】假設(shè)】假設(shè)r=0r=0，算法結(jié)束；，算法結(jié)束；n n即為答案即為答案步驟步驟3:3:【互換】置【互換】置mnmn， nrnr，轉(zhuǎn)向步驟，轉(zhuǎn)向步驟1 1。 - School of Computer Science & Engineering, Xidian University, China 6 YNrm被被n除的余數(shù)除的余數(shù)r不等于不等于0?n r輸出輸出n的值

4、的值輸入正整數(shù)輸入正整數(shù)m和和n開始開始結(jié)束結(jié)束m n結(jié)構(gòu)不好！結(jié)構(gòu)不好！ - School of Computer Science & Engineering, Xidian University, China 7 - School of Computer Science & Engineering, Xidian University, China 8 - School of Computer Science & Engineering, Xidian University, China 9 AB順序結(jié)構(gòu)順序結(jié)構(gòu)abpAB成立成立不成立不成立ab選擇結(jié)構(gòu)選擇結(jié)構(gòu)1p

5、A成立成立不成立不成立ab選擇結(jié)構(gòu)選擇結(jié)構(gòu)2 - School of Computer Science & Engineering, Xidian University, China 10 pA成立成立不成立不成立ab循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)2pA成立成立不成立不成立ab循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)1 - School of Computer Science & Engineering, Xidian University, China 11 AB死循環(huán)死循環(huán)apAB成立成立不成立不成立ab - School of Computer Science & Engineering, Xidia

6、n University, China 12 YNI 1S 0Ib then max a else max b 例如：例如： if (k mod 4 = 0) and (k mod 100 0) or (k mod 100 = 0) and (k mod 400 = 0) then print “k is a leap year. else print “k is not a leap year. - School of Computer Science & Engineering, Xidian University, China 30 YNIb do a a - b while I

7、=100 do S S + I; I I + 1; - School of Computer Science & Engineering, Xidian University, China 31 算法算法1：計(jì)算：計(jì)算1+2+100BEGIN S 0; I 1; while (I 100) do S S + I; I I + 1; print S；ENDYNI 1S 0I=100?S S+I輸出輸出S的值的值開始開始結(jié)束結(jié)束I I+1 - School of Computer Science & Engineering, Xidian University, China 32

8、YNr不等于不等于0?輸出輸出n的值的值輸入正整數(shù)輸入正整數(shù)m和和n開始開始結(jié)束結(jié)束m n; n rrm被被n除的余數(shù)除的余數(shù)rm被被n除的余數(shù)除的余數(shù)算法算法2：輾轉(zhuǎn)相除法求最大公約數(shù)：輾轉(zhuǎn)相除法求最大公約數(shù)BEGIN input m,n; /*輸入正整數(shù)輸入正整數(shù)m和和n*/ rm mod n; /*求求m被被n除的余數(shù)除的余數(shù)*/ while (r0) do m n; n r; rm mod n; print n； /*輸出最大公約數(shù)輸出最大公約數(shù)*/END - School of Computer Science & Engineering, Xidian University

9、, China 33 算法算法3：輾轉(zhuǎn)相除法求最大公約數(shù)：輾轉(zhuǎn)相除法求最大公約數(shù)BEGIN input m,n; /*輸入正整數(shù)輸入正整數(shù)m和和n*/ do rm mod n; m n; n r; while r0; print m； /*輸出最大公約數(shù)輸出最大公約數(shù)*/ENDYNr不等于不等于0?輸出輸出m的值的值輸入正整數(shù)輸入正整數(shù)m和和n開始開始結(jié)束結(jié)束rm被被n除的余數(shù)除的余數(shù)m n; n r - School of Computer Science & Engineering, Xidian University, China 34 Y N K 2K不能整除不能整除n?K K+1輸出輸出n是素?cái)?shù)是素?cái)?shù) 輸入輸入n的值的值開始開始結(jié)束結(jié)束YNK等于等于n?算法算法2：素性判別：素性判別BEGIN input n; /*輸入正整數(shù)輸入正整數(shù)n*/ k2; while (n mod k 0) do k k+1; if (k=n) then print “n是素?cái)?shù)是素?cái)?shù) else print “n不是素?cái)?shù)不是素?cái)?shù) END輸出輸出n不是素?cái)?shù)不是素?cái)?shù) - School of Computer Science & Engineering, Xidian University, China