第12講函數(shù)舉例例1：求最大公約數(shù)要求：編寫計(jì)算最大公約數(shù)的函數(shù)，在主程序中，輸入兩個(gè)正整數(shù)，調(diào)用該函數(shù)并輸出最大公約數(shù)。解題思路：求最大公約數(shù)有多種方法，本講介紹兩種方法，分別是窮舉法和歐幾里得法（輾轉(zhuǎn)相除法）。例1：求最大公約數(shù)方法1：窮舉法思路：兩個(gè)整數(shù)a,b的最大公約數(shù)不能比兩者中小的那個(gè)大。先找出a,b中較小的那個(gè)數(shù)設(shè)為m，從m開(kāi)始嘗試看它是不是能被a,b整除，不能整除m就減1，再嘗試，第一個(gè)能被a,b整除的就是最大公約數(shù)。大家可以隨意找兩個(gè)整數(shù)，按這個(gè)方法推演一下。#include<stdio.h>intmain(){inta,b;scanf("%d%d",&a,&b);printf("%d",gcd(a,b));return0;}intgcd(inta,intb){intm;m=a<b?a:b;while(a%m!=0||b%m!=0)m--;returnm;}求最大公約數(shù)：窮舉法例1：求最大公約數(shù)方法2：歐幾里得法（輾轉(zhuǎn)相除法）思路：設(shè)r=amodb表示a除以b的余數(shù)，若r！=0，則將b作為新的a，r作為新的b，即gcd(a,b)=gcd(b,r),重復(fù)計(jì)算r=amodb，直到r=0為止，此時(shí)b為所求的最大公約數(shù)。大家可以隨意找兩個(gè)整數(shù)，按這個(gè)方法推演一下。intgcd(inta,intb){intr;while(r=a%b)//while((r=a%b)!=0){a=b;b=r;}returnb;}求最大公約數(shù)：歐幾里得法例2:判斷質(zhì)數(shù)要求：函數(shù)實(shí)現(xiàn)判斷一個(gè)數(shù)是不是質(zhì)數(shù)。主程序中輸入一個(gè)大于1的正整數(shù)，調(diào)用判斷質(zhì)數(shù)函數(shù)，并輸出結(jié)果。例2的完整程序#include<stdio.h>intmain(){intx,flag;scanf("%d",&x);if(x<=1){printf("非法輸入\n");return0;}flag=prime(x);if（flag==1）printf("%d是質(zhì)數(shù)\n",x);elseprintf(“%d不是質(zhì)數(shù)\n",x);return0;}intprime(intx){inti;for(i=2;i<x;i++)if(x%i==0)return0;return1;}例3:斐波那契（Fibonacci）數(shù)列要求：采用非遞歸函數(shù)的形式實(shí)現(xiàn)斐波那契數(shù)列。斐波那契（Fibonacci）數(shù)列：0,1,1,2,3,5,8,13…數(shù)列第1項(xiàng)值為0，第2項(xiàng)值為1，后面每項(xiàng)值是前面兩個(gè)值之和。斐波那契數(shù)列非遞歸實(shí)現(xiàn)函數(shù)Fib(n)計(jì)算出斐波那契數(shù)列的第n項(xiàng)的值。intFib(intn){intf;//f是f1和f2后面的值intf1=0;//f1表示第1項(xiàng)intf2=1;//f2表示第2項(xiàng)if(1==n)return0;if(2==n)return1;for(inti=3;i<=n;i++){f=f1+f2;f1=f2;//往后推，f1取代f2f2=f;//f2取代f}returnf;}例4:漢諾塔（Hanoi)問(wèn)題漢諾塔問(wèn)題是計(jì)算機(jī)科學(xué)中的經(jīng)典問(wèn)題，需要用遞歸的方法解決。古代有一個(gè)梵塔，塔內(nèi)有3個(gè)座A、B、C，開(kāi)始時(shí)Ａ座上有64個(gè)大小不等的盤子，大的在下，小的在上。有一個(gè)和尚想把這64個(gè)盤子從Ａ座移到Ｃ座，但規(guī)定每次只允許移動(dòng)一個(gè)盤，且在移動(dòng)過(guò)程中在3個(gè)座上都始終保持大盤在下，小盤在上。移動(dòng)過(guò)程中可以利用B座。要求編程輸出移動(dòng)盤子的步驟。ABC漢諾塔問(wèn)題解題思路可以這樣想：假如能有辦法將上面63個(gè)盤子從一個(gè)座移到另一座。那么，問(wèn)題就解決了。此時(shí)只需這樣做：(1)將63個(gè)盤子從A座移到B座(2)將1個(gè)盤子（最底下的、最大的盤子）從A座移到C座(3)再將63個(gè)盤子從B座移到C座63個(gè)盤子怎么從一個(gè)座移到另一座？假如能有辦法將上面62個(gè)盤子從一個(gè)座移到另一座。那么，問(wèn)題就解決了。62個(gè)盤子怎么移動(dòng)？如法炮制……1個(gè)盤子直接從一個(gè)座移到另一個(gè)座漢諾塔程序voidhanoi(intn,chara,charb,charc)//表示n個(gè)盤子，從a移到c，借助于b{if(n==1)move(a,c);else{hanoi(n-1,a,c,b);move(a,c