第6章程序設(shè)計(jì)的問題求解基礎(chǔ)哈爾濱工業(yè)大學(xué)6.1問題求解策略算法設(shè)計(jì)的基本思路就是尋找解決問題的規(guī)律。指在數(shù)學(xué)思想支持下的解題思路、方式和方法。常用的問題求解策略枚舉、遞推、迭代、分治、遞歸6.2枚舉——從找回你的密碼談起窮舉法（Exhaustion），也稱枚舉法（Enumeration）列舉所有可能，逐一試探基本思想根據(jù)問題的部分已知條件預(yù)估解的范圍在此范圍內(nèi)對所有可能的情況進(jìn)行逐一驗(yàn)證若某個(gè)情況符合題目的全部條件，則該情況為本問題的一個(gè)解若全部情況的驗(yàn)證結(jié)果均不符合題目的全部條件，則說明該題無解直到找到滿足已知條件的解為止6.2枚舉——從找回你的密碼談起確定窮舉對象和窮舉范圍確定判定條件

符合答案的條件分支結(jié)構(gòu)實(shí)現(xiàn)

影響算法的時(shí)間復(fù)雜度循環(huán)結(jié)構(gòu)實(shí)現(xiàn)for(窮舉范圍){……

if(符合答案的條件)……}枚舉法求解問題的兩個(gè)基本要素【例6.1】百雞問題是我國古代數(shù)學(xué)名著《張丘建算經(jīng)》中的一個(gè)著名數(shù)學(xué)問題，它給出了由三個(gè)未知量的兩個(gè)方程組成的不定方程組的解。《張丘建算經(jīng)》為北魏張丘建所著，所載問題大部分為當(dāng)時(shí)社會(huì)生活中的實(shí)際問題，如有關(guān)測量、紡織、交換、納稅、冶煉、土木工程等，涉及面廣泛，其問題和解法均超出《九章算術(shù)》。百雞問題具體是這樣的：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何？其意為：公雞每只5元，母雞每只3元，小雞3只1元。請用窮舉法編程計(jì)算，若用100元買100只雞，則公雞、母雞和小雞各能買多少只。6.2枚舉——從找回你的密碼談起6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){intx,y,z;for(x=0;x<=100;x++){for(y=0;y<=100;y++){for(z=0;z<=100;z++){if(x+y+z==100&&5*x+3*y+z/3.0==100)printf("x=%d,y=%d,z=%d\n",x,y,z);}}}return0;}6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){intx,y,z;for(x=0;x<=20;x++){for(y=0;y<=33;y++){z=100-–x-y;if(5*x+3*y+z/3.0==100)printf("x=%d,y=%d,z=%d\n",x,y,z);}}return0;}【例6.3】韓信點(diǎn)兵問題。西漢開國功臣、軍事家韓信有一隊(duì)兵，他想知道有士兵多少人，便讓士兵排隊(duì)報(bào)數(shù)。按從1至5報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為1；按從1至6報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為5；按從1至7報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為4；最后再按從1至11報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為10。請問韓信至少有多少兵。確定問題的輸入和輸出輸入：無；輸出：士兵至少x人確定窮舉對象：士兵數(shù)x確定搜索范圍：x從1變化……確定判定條件：x被5、6、7、11整除余數(shù)為1、5、4、10x%5==1&&x%6==5&&x%7==4&&x%11==106.2枚舉——從找回你的密碼談起6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){intx;for(x=1;x<3000;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d\n",x);}}return0;}#include<stdio.h>intmain(void){intx;for(x=1;;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d\n",x);break;}}return0;}6.2枚舉——從找回你的密碼談起#include<stdio.h>#include<stdlib.h>intmain(void){intx;for(x=1;;x++){if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d\n",x);exit(0);}}return0;}#include<stdio.h>intmain(void){intx;intfind=0;//置找到標(biāo)志變量為假

for(x=1;!find;x++)//find為假時(shí)繼續(xù)循環(huán)

{

if(x%5==1&&x%6==5&&x%7==4&&x%11==10){printf("x=%d\n",x);find=1;//置找到標(biāo)志變量為真

}}

return0;}6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){ intx=0; intfind=0; do{ x++; find=(x%5==1&&x%6==5&&x%7==4&&x%11==10); }while(!find); printf("x=%d\n",x);return0;}#include<stdio.h>intmain(void){ intx=0;//因do-while循環(huán)中先對x加1，故這里x初始化為0

do{ x++; }while(!(x%5==1&&x%6==5&&x%7==4&&x%11==10)); printf("x=%d\n",x);return0;}【例6.4】還原算術(shù)表達(dá)式。請編寫一個(gè)程序求解以下算式中各字母所代表的數(shù)字的值，已知不同的字母代表不同的數(shù)字。先從鍵盤輸入小于1000的n值，如果n不小于1000，則重新輸入n值，然后輸出第一個(gè)滿足條件的解。6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){intx,y,z,n,find=0;do{printf("Inputn(n<1000):");scanf("%d",&n);}while(n>=1000);//若輸入的n不在合法范圍內(nèi)，則重新輸入

for(x=1;x<=9;++x){for(y=1;y<=9;++y){for(z=0;z<=9;++z){if(100*x+10*y+z+z+10*z+100*y==n&&x!=y&&y!=z&&x!=z){printf("X=%d,Y=%d,Z=%d\n",x,y,z);find=1;}}}}if(!find)printf("Notfound!");return0;}【例6.4】還原算術(shù)表達(dá)式。請編寫一個(gè)程序求解以下算式中各字母所代表的數(shù)字的值，已知不同的字母代表不同的數(shù)字。先從鍵盤輸入小于1000的n值，如果n不小于1000，則重新輸入n值，然后輸出第一個(gè)滿足條件的解。6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){

……

for(x=1;x<=9&&!find;++x){for(y=1;y<=9&&!find;++y){if(x==y)continue;//若y與x相等，就直接換下一個(gè)y再試

for(z=0;z<=9&&!find;++z){if(y==z||x==z)continue;//若z與x或y相等，就換下一個(gè)zif(100*x+10*y+z+z+10*z+100*y==n){printf("X=%d,Y=%d,Z=%d\n",x,y,z);find=1;}count++;}}}printf("Notfound!");return0;}【例6.4】還原算術(shù)表達(dá)式。請編寫一個(gè)程序求解以下算式中各字母所代表的數(shù)字的值，已知不同的字母代表不同的數(shù)字。先從鍵盤輸入小于1000的n值，如果n不小于1000，則重新輸入n值，然后輸出第一個(gè)滿足條件的解。6.2枚舉——從找回你的密碼談起#include<stdio.h>intmain(void){

……

for(x=1;x<=9;++x){for(y=1;y<=9;++y){if(x==y)continue;for(z=0;z<=9;++z){if(y==z||x==z)continue;count++;if(100*x+10*y+z+z+10*z+100*y==n){printf("X=%d,Y=%d,Z=%d\n",x,y,z);find=1;gotoEND;}}}}if(!find)printf("Notfound!");END:printf("count=%d\n",count);return0;}【例6.5】請編寫一個(gè)程序，計(jì)算并輸出1~n之間的所有素?cái)?shù)之和。6.2枚舉——從找回你的密碼談起intIsPrime(intm){inti;intsquareRoot=(int)sqrt(m);if(m<=1){return0;//負(fù)數(shù)、0和1都不是素?cái)?shù)

}

for(i=2;i<=squareRoot;++i){if(m%i==0){gotoEND;}}END:returni<=squareRoot?0:1;}intIsPrime(intm){inti;intsquareRoot=(int)sqrt(m);if(m<=1){return0;//負(fù)數(shù)、0和1都不是素?cái)?shù)

}

for(i=2;i<=squareRoot;++i){if(m%i==0){break;}}returni<=squareRoot?0:1;}【例6.5】請編寫一個(gè)程序，計(jì)算并輸出1~n之間的所有素?cái)?shù)之和。6.2枚舉——從找回你的密碼談起intIsPrime(intm){intflag=1;intsquareRoot=(int)sqrt(m);if(m<=1){flag=0;//負(fù)數(shù)、0和1都不是素?cái)?shù)

}

for(inti=2;i<=squareRoot&&flag;++i){if(m%i==0){flag=0;//若能被整除，則不是素?cái)?shù)

}}

returnflag;}#include<stdbool.h>boolIsPrime(intm){boolflag=true;intsquareRoot=(int)sqrt(m);if(m<=1){flag=false;//負(fù)數(shù)、0和1都不是素?cái)?shù)

}

for(inti=2;i<=squareRoot&&flag;++i){if(m%i==0){flag=false;//若能被整除，則不是素?cái)?shù)

}}

returnflag;}intmain(void){intn;scanf("%d",&n);printf("sum=%d\n",SumofPrime(n));return0;}【例6.6】德國人哥德巴赫在1742年提出了自己無法證明的兩個(gè)猜想：（1）每個(gè)大于2的偶數(shù)都是兩個(gè)素?cái)?shù)之和；（2）每個(gè)大于5的奇數(shù)都是三個(gè)素?cái)?shù)之和。1973年，我國數(shù)學(xué)家陳景潤攻克了數(shù)學(xué)界200多年懸而未決的世界級(jí)數(shù)學(xué)難題即“哥德巴赫猜想”中的“1＋2”，成為哥德巴赫猜想研究史上的里程碑。他的論文發(fā)表后立即在國際數(shù)學(xué)界引起了轟動(dòng)，被公認(rèn)為是對哥德巴赫猜想研究的重大貢獻(xiàn)。他的成果被國際數(shù)學(xué)界稱為“陳氏定理”，寫進(jìn)美、英、法、蘇、日等六國的許多數(shù)論書中。2009年，陳景潤被評為100位新中國成立以來感動(dòng)中國人物之一。現(xiàn)在，請你編寫一個(gè)程序來驗(yàn)證：任何一個(gè)大于或等于6但不超過2000000000的足夠大的偶數(shù)n總能表示為兩個(gè)素?cái)?shù)之和。例如，8=3+5，12=5+7等等。如果n符合“哥德巴赫猜想”，則輸出將n分解為兩個(gè)素?cái)?shù)之和的等式，否則輸出“n不符合哥德巴赫猜想！”的提示信息。他曾經(jīng)說過：時(shí)間是個(gè)常數(shù)，花掉一天等于浪費(fèi)24小時(shí)；學(xué)習(xí)要有三心：信心、決心、恒心；攀登科學(xué)高峰，就像登山運(yùn)動(dòng)員攀登珠穆朗瑪峰一樣，要克服無數(shù)艱難險(xiǎn)阻，懦夫和懶漢是不可能享受到勝利的喜悅和幸福的。6.2枚舉——從找回你的密碼談起【例6.5】請編寫一個(gè)程序，計(jì)算并輸出1~n之間的所有素?cái)?shù)之和。6.2枚舉——從找回你的密碼談起#include<stdio.h>#include<math.h>#include<stdbool.h>boolIsPrime(longm);boolGoldbach(longn);intmain(void){longn;intret;do{printf("Inputn:");ret=scanf("%ld",&n);if(ret!=1)while(getchar()!='\n');}while(ret!=1||n%2!=0||n<6||n>2000000000);if(!Goldbach(n)){printf("%ld不符合哥德巴赫猜想\n",n);}return0;}【例6.5】請編寫一個(gè)程序，計(jì)算并輸出1~n之間的所有素?cái)?shù)之和。6.2枚舉——從找回你的密碼談起boolGoldbach(longn){boolfind=false;for(longa=3;a<=n/2&&!find;a+=2){if(IsPrime(a)&&IsPrime(n-a)){printf("%ld=%ld+%ld",n,a,n-a);find=true;}}returnfind;}boolIsPrime(longm){boolflag=true;intsquareRoot=(int)sqrt(m);if(m<=1)flag=false;//負(fù)數(shù)、0和1都不是素?cái)?shù)

for(inti=2;i<=squareRoot&&flag;++i){if(m%i==0)flag=false;//若能被整除，則不是素?cái)?shù)

}

returnflag;}6.4遞推——荷花定律和大自然中的秘密在一個(gè)荷花池里，第一天荷花開放的很少，第二天開放的數(shù)量是第一天的兩倍，之后的每一天，荷花都會(huì)以前一天兩倍的數(shù)量開放。如果到第30天，荷花就開滿了整個(gè)池塘，那么請問荷花是在第幾天開了半個(gè)池塘呢？向日葵的花盤中有2組對數(shù)螺線，一組順時(shí)針方向盤繞，另一組則逆時(shí)針方向盤繞，并且彼此相嵌。雖然不同的向日葵品種中，這些順逆螺旋的數(shù)目并不固定，但往往不會(huì)超出34和55、55和89、89和144這三組數(shù)字。除了向日葵，松果也符合這一奇妙的自然規(guī)律植物的花瓣、萼片、果實(shí)的數(shù)目以及其他方面的特征，都非常吻合一個(gè)奇特的數(shù)列，即Fibonacci數(shù)列：1，1，2，3，5，8，13，21，34，55，89......。這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都是前兩項(xiàng)之和6.4遞推——荷花定律和大自然中的秘密正向順推，就是從已知條件出發(fā)，向著所求問題前進(jìn)，最后與所求問題聯(lián)系起來例如，已知一個(gè)漢堡包12元，一個(gè)蛋撻比一個(gè)漢堡包貴5元，問買兩種各一個(gè)需多少元？首先根據(jù)已知條件可以推出一個(gè)蛋撻的價(jià)格是12+5=17元，然后可以推出買兩種各一個(gè)需17+12=29。反向逆推，即從所求問題出發(fā)，向著已知條件靠攏，最后與已知條件聯(lián)系起來。例如，小明來到一家早餐店，拿出一半錢吃早餐，又花了3.5元錢買飲料，還剩1元錢，問他原來帶了多少錢？這個(gè)問題適合使用反向逆推的方法，即從問題的結(jié)果出發(fā)，一步一步還原出答案。因?yàn)槲覀冎佬∶鳜F(xiàn)在有1元錢，他做的最后一件事是花3.5元買飲料，所以我們可以把3.5元和他的一元加起來，逆推出他買飲料之前有4.5元，根據(jù)已知條件，他花一半錢吃早餐還剩4.5元，那么他吃早餐一定花了4.5元，那么原來他就應(yīng)該有9元?？蛇f推求解的問題一般具有以下兩個(gè)特點(diǎn)：（1）問題可以劃分成多個(gè)狀態(tài)；（2）除初始狀態(tài)外，其它各個(gè)狀態(tài)都可以用固定的遞推關(guān)系式來表示。6.4.1正向順推實(shí)例11

2

3

5

8

......f1

f2f3

f1

f2f3

f1

f2f3

f1

f2f3

f3=f1+f2;f1=f2;f2=f3;11

2

3

5

8

......f1

f2

f1

f2

f1

f2

f1

f1=f1+f2;f2=f2+f1;【例6.7】計(jì)算Fibonacci數(shù)列的前n項(xiàng)。6.4.1正向順推實(shí)例【例6.7】計(jì)算Fibonacci數(shù)列的前n項(xiàng)。#include<stdio.h>longFib(intn);intmain(void){inti;longn;printf("Inputn:");scanf("%ld",&n);for(i=1;i<=n;i++){printf("%4ld",Fib(i));}return0;}//函數(shù)功能：正向順推法計(jì)算并返回Fibonacci數(shù)列的第n項(xiàng)longFib(intn){inti;longf1=1,f2=1,f3=2;if(n==1){return1;}elseif(n==2){return1;}else{for(i=3;i<=n;i++)//每遞推一次計(jì)算一項(xiàng)

{

f3=f1+f2;f1=f2;f2=f3;}returnf3;}}6.4.1正向順推實(shí)例【例6.7】計(jì)算Fibonacci數(shù)列的前n項(xiàng)。#include<stdio.h>longFib(intn);intmain(void){inti;longn;printf("Inputn:");scanf("%ld",&n);for(i=1;i<=n;i++){printf("%4ld",Fib(i));}return0;}//函數(shù)功能：正向順推法計(jì)算并返回Fibonacci數(shù)列的第n項(xiàng)longFib(intn){inti;longf1=1,f2=1;if(n==1){return1;}elseif(n==2){return1;}else{for(i=1;i<(n+1)/2;i++)

{

f1=f1+f2;f2=f2+f1;}returnn%2!=0?f1:f2;}}6.4.2反向逆推實(shí)例【例6.8】猴子吃桃問題猴子第一天摘下若干個(gè)桃子，吃了一半，還不過癮，又多吃了一個(gè)。第二天早上又將剩下的桃子吃掉一半，并且又多吃了一個(gè)。以后每天早上都吃掉前一天剩下的一半零一個(gè)。到第10天早上再想吃時(shí)，發(fā)現(xiàn)只剩下一個(gè)桃子。問第一天共摘了多少桃子。每天剩下的桃子數(shù)比前一天的一半少一個(gè)每天剩下的桃子數(shù)加1之后，剛好是前一天的一半天數(shù)：

10

9

8

7

6

5

4

3

2

1

4

10

22

46

94

190

382

766

1534

6.4.2反向逆推實(shí)例#include<stdio.h>intMonkeyEatPeach(intdayn);intmain(void){intdays,total;printf("Inputdays:");scanf("%d",&days);total=MonkeyEatPeach(days);printf("x=%d\n",total);return0;}intMonkeyEatPeach(intday){intx=1;do{x=(x+1)*2;day--;}while(day>1);returnx;}intMonkeyEatPeach(intday){intx=1;while(day>1){x=(x+1)*2;day--;}returnx;}6.5遞歸——千里之行始于足下的啟示6.5.1遞歸的內(nèi)涵與數(shù)學(xué)基礎(chǔ)一種問題求解的策略假設(shè)你已經(jīng)走了999步，那么你再走一步即可邁出第1000步假設(shè)你已經(jīng)走了998步，那么你再走一步即可邁出第999步……直到你邁出第1步，遞歸結(jié)束walkwalk1“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”………….6.5.1遞歸的內(nèi)涵與數(shù)學(xué)基礎(chǔ)如果一個(gè)對象部分地由它自己組成或按它自己定義，則稱它是遞歸的（Recursive）遞歸（Recursion）函數(shù)/過程/子程序在運(yùn)行過程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象6.5.1遞歸的內(nèi)涵與數(shù)學(xué)基礎(chǔ)遞歸算法必須包含如下兩個(gè)部分：由其自身定義的與原始問題類似的更小規(guī)模的子問題，它使遞歸過程持續(xù)進(jìn)行，稱為一般條件（Generalcase）所描述問題的最簡單的情況，它是一個(gè)能控制遞歸過程結(jié)束的條件，稱為基本條件（Basecase）計(jì)算n!問題的一般條件可以用遞歸公式表示為：n!=n×(n-1)!（當(dāng)n>1時(shí)）計(jì)算n!問題的基本條件可以表示為：n!=1（當(dāng)n=1時(shí)）6.4.2遞歸函數(shù)的基本要素if(遞歸終止條件)//基本條件，也稱邊界條件，代表遞歸的出口return遞歸公式的初值;else//一般條件，表示遞推關(guān)系return遞歸函數(shù)調(diào)用返回的結(jié)果值;

【例6.9】分別用迭代和遞歸兩種方法計(jì)算正整數(shù)n的階乘即n!。326.4.2遞歸函數(shù)的基本要素#include<stdio.h>unsignedintFact(unsignedintn);intmain(void){unsignedintn;printf("Inputn:");scanf("%u",&n);printf("%u!=%u\n",n,Fact(n));return0;}//函數(shù)功能：用迭代法計(jì)算n的階乘并返回unsignedintFact(unsignedintn){unsignedinti,p=1; for(i=2;i<=n;i++) { p=p*i; }returnp;}#include<stdio.h>unsignedintFact(unsignedintn);intmain(void){unsignedintn;printf("Inputn:");scanf("%u",&n);printf("%u!=%u\n",n,Fact(n));return0;}//函數(shù)功能：用遞歸法計(jì)算n的階乘并返回unsignedintFact(unsignedintn){if(n==1||n==0)//基本條件

{

return1;}else//一般條件

{

returnn*Fact(n-1);//遞歸調(diào)用

}}#include<stdio.h>intMonkeyEatPeach(intdays);intmain(){ intx,days;printf("Inputdays:"); scanf("%d",&days); x=MonkeyEatPeach(days); printf("x=%d\n",x); return0;}intMonkeyEatPeach(intdays)//由第days天推出第days-1天{if(days==1)//遞歸結(jié)束條件

return1;//遞歸初值else return2*(MonkeyEatPeach(days-1)+1);//遞推式}6.4.2遞歸函數(shù)的基本要素【例6.10】采用遞歸法編寫求解例6.8的猴子吃桃問題的程序代碼6.5.3遞歸的執(zhí)行過程遞歸算法的執(zhí)行過程一般可分為兩個(gè)階段：遞推階段（也稱遞歸前進(jìn)階段）把一個(gè)較復(fù)雜的問題逐步分解為與原始問題類似的更小規(guī)模的子問題，逐步簡化直至最終轉(zhuǎn)化為一個(gè)最簡單的問題，可以直接求解并終止遞歸回歸階段（也稱遞歸返回階段）當(dāng)獲得最簡單情況的解后，逐級(jí)返回，依次得到稍復(fù)雜問題的解。6.5.3遞歸的執(zhí)行過程棧操作“后進(jìn)先出”的特點(diǎn)使其能夠精確地滿足函數(shù)調(diào)用和返回的順序，因此特別適合于保存與函數(shù)調(diào)用相關(guān)的信息。保存這些信息的?？臻g，稱為活躍記錄或者棧幀。棧幀中主要存儲(chǔ)輸入?yún)?shù)、計(jì)算表達(dá)式時(shí)用到的臨時(shí)變量的值、函數(shù)調(diào)用時(shí)保存的狀態(tài)信息（如返回地址）等6.5.4遞歸與迭代的關(guān)系遞歸的本質(zhì)不斷地把規(guī)模較大的問題分解成與原來問題相同但規(guī)模較小的同類子問題，直到這個(gè)小的問題能夠直接使用簡單的方法解決為止子問題與原問題的區(qū)別只是問題的規(guī)模不同而已遞歸和迭代的關(guān)系迭代顯式地使用重復(fù)結(jié)構(gòu)，而遞歸使用選擇結(jié)構(gòu)，通過重復(fù)函數(shù)調(diào)用實(shí)現(xiàn)重復(fù)結(jié)構(gòu)迭代和遞歸都涉及終止測試，迭代在循環(huán)測試條件為假時(shí)終止循環(huán)，遞歸則在遇到基本條件時(shí)終止遞歸。迭代不斷修改循環(huán)計(jì)數(shù)變量，直到它使循環(huán)條件為假時(shí)為止。遞歸則不斷產(chǎn)生最初問題的簡化版本，直到簡化為遞歸的基本條件。6.5.4遞歸與迭代的關(guān)系【例6.11】最大公約數(shù)問題。兩個(gè)正整數(shù)的最大公約數(shù)（GreatestCommonDivisor，GCD）是能夠整除這兩個(gè)整數(shù)的最大整數(shù)。從鍵盤任意輸入兩個(gè)正整數(shù)a和b，請分別采用枚舉法、歐幾里德算法（輾轉(zhuǎn)相除法）以及更相減損術(shù)三種不同的方法編程計(jì)算并輸出兩個(gè)正整數(shù)a和b的最大公約數(shù)。（1）窮舉法

intGcd(inta,intb){ inti,t; if(a<=0||b<=0) return-1; t=a<b?a:b;

for(i=t;i>0;i--) { if(a%i==0&&b%i==0) returni; } return1;}

6.5.4遞歸與迭代的關(guān)系（2）歐幾里德算法（輾轉(zhuǎn)相除法）

對正整數(shù)a和b，連續(xù)進(jìn)行求余運(yùn)算

r=a%b直到余數(shù)r為0為止

此時(shí)非0的除數(shù)，即為所求

若r≠0，則b作為新的a，r作為新的b即Gcd(a,b)=Gcd(b,r)重復(fù)a%b運(yùn)算，直到r=0時(shí)為止。

intGcd(inta,intb){ intr; if(a<=0||b<=0) { return-1; }

do{ r=a%b; a=b; b=r; }while(r!=0);

returna;}

6.5.4遞歸與迭代的關(guān)系輾轉(zhuǎn)相除法的遞歸實(shí)現(xiàn)

intGcd(inta,intb){ if(a<=0||b<=0) { return-1; }intr=a%b;

if(r==0)returnb;elsereturnGcd(b,r);}

6.5.4遞歸與迭代的關(guān)系（3）更相減損術(shù)（《九章算術(shù)》）——遞歸方法性質(zhì)1如果a>b，則Gcd(a,b)=Gcd(a-b,b)性質(zhì)2如果b>a，則Gcd(a,b)=Gcd(a,b-a)性質(zhì)3如果a=b，則Gcd(a,b)=a=b

intGcd(inta,intb){if(a<=0||b<=0)return-1;

if(a==b)returna;elseif(a>b)returnGcd(a-b,b);elsereturnGcd(a,b-a);}《九章算術(shù)》是我國古代的數(shù)學(xué)專著，值得我們后人為之驕傲和自豪的是，作為一部世界數(shù)學(xué)名著，《九章算術(shù)》早在隋唐時(shí)期即已傳入朝鮮、日本。它已被譯成日、俄、德、法等多種文字版本?！毒耪滤阈g(shù)》是算經(jīng)十書中最重要的一種，該書系統(tǒng)地總結(jié)了戰(zhàn)國、秦、漢時(shí)期的數(shù)學(xué)成就，是當(dāng)時(shí)世界上最簡練有效的應(yīng)用數(shù)學(xué)，它的出現(xiàn)標(biāo)志中國古代數(shù)學(xué)形成了完整的體系。更相減損術(shù)就是《九章算術(shù)》中記載的一種求最大公約數(shù)的方法，其主要思想是

6.5.4遞歸與迭代的關(guān)系更相減損術(shù)——迭代方法

intGcd(inta,intb){ if(a<=0||b<=0) { return-1; }

while(a!=b)

{ if(a>b) { a=a-b; } elseif(b>a) {

b=b-a; } }

returna;}6.5.4遞歸與迭代的關(guān)系【例6.12】利用如下遞歸公式，用遞歸法編程計(jì)算并輸出Fibonacci數(shù)列的前n項(xiàng)。longFib(intn){if(n==1)//基本條件

{return1;}elseif(