c中最大公約數的演算法

『壹』 如何用C語言求兩個數的最大公約數的三種演算法

1、相減法

#include<stdio.h>

int main()

{

int a,b;

int c=0;//計數器

while(1)//循環判斷的作用

{

printf("輸入兩個數字求最大公約數:");

scanf("%d%d",&a,&b);

while(a!=b)

{

if(a>b)

a=a-b;

else

b=b-a;

c++;

}

printf("最大公約數是:%d ",a);

printf("%d ",c);

}

return 0;

}

運行效果：

2、輾轉相除法：

#include<stdio.h>

int a,b,temp;

int Division(){

printf("請輸入兩個數(a,b)： ");

scanf("%d,%d",&a,&b);

if(a<b){

temp=a;

a=b;

b=temp;

}

while(a%b!=0){

temp=a%b;

a=b;

b=temp;

}

printf("最大公約數為：%d ",b);

return 0;

}

3、窮舉法

#include<stdio.h>

int main()

{

int a,b,c;

int d=0;//計數器

while(1)

{

printf("輸入兩個數字求最大公約數:");

scanf("%d%d",&a,&b);

c=(a>b)?b:a;//三目運算符

while(a%c!=0||b%c!=0)

{

c--;

d++;

}

printf("最大公約數是:%d ",c);

printf("%d ",d);

}

return 0;

}

『貳』 c語言求最大公約數

1、新建一個C語言源程序，這里使用Visual C++6.0的軟體：

『叄』 c語言如何求最小公倍數和最大公約數

解題步驟：

1、求最大公約數

對兩個正整數a,b如果能在區間[a,0]或[b,0]內能找到一個整數temp能同時被a和b所整除，則temp即為最大公約數。

2、求最小公倍數

對兩個正整數a,b,如果若干個a之和或b之和能被b所整除或能被a所整除，則該和數即為所求的最小公倍數。

//窮舉法求兩數的最大公約數

int divisor(int a,int b)

{

int temp;//定義義整型變數

temp=(a>b)?b:a;//采種條件運算表達式求出兩個數中的最小值

while(temp>0){

if(a%temp==0&&b%temp==0)//只要找到一個數能同時被a,b所整除，則中止循環

break;

temp--;//如不滿足if條件則變數自減，直到能被a,b所整除

}

return temp;//返回滿足條件的數到主調函數處

}

//窮舉法求兩數的最小公倍數

int multiple(int a,int b)

{

int p,q,temp;

p=(a>b)?a:b;//求兩個數中的最大值

q=(a>b)?b:a;//求兩個數中的最小值

temp=p;//最大值賦給p為變數自增作準備

while(1){//利用循環語句來求滿足條件的數值

if(p%q==0)

break;//只要找到變數的和數能被a或b所整除，則中止循環

p+=temp;//如果條件不滿足則變數自身相加

}

return p;

}

(3)c中最大公約數的演算法擴展閱讀：

用窮舉法解題時，就是按照某種方式列舉問題答案的過程。針對問題的數據類型而言，常用的列舉方法一有如下三種：

（1）順序列舉是指答案范圍內的各種情況很容易與自然數對應甚至就是自然數，可以按自然數的變化順序去列舉。

（2）排列列舉有時答案的數據形式是一組數的排列，列舉出所有答案所在范圍內的排列，為排列列舉。

（3）組合列舉當答案的數據形式為一些元素的組合時，往往需要用組合列舉。組合是無序的。

例子如下：在公元五世紀我國數學家張丘建在其《算經》一書中提出了「百雞問題」：

「雞翁一值錢5，雞母一值錢3，雞雛三值錢1。百錢買百雞，問雞翁、母、雛各幾何？」這個數學問題的數學方程可列出如下：

Cock+Hen+Chick=100

Cock*5+Hen*3+Chick/3=100

顯然這是個不定方程，適用於窮舉法求解。依次取Cock值域中的一個值，然後求其他兩個數，滿足條件就是解。

該問題的C語言程序演算法如下：

int Cock,Hen,Chick;/*定義公雞，母雞，雞雛三個變數*/

Cock=0;

while(Cock<=19)/*公雞最多不可能大於19*/

{Hen=0;

whlie(Hen<=33)/*母雞最多不可能大於33*/

{Chick=100-Cock-Hen;

if(Cock*15+Hen*9+Chick==300)/*為了方便，將數量放大三倍比較*/

printf(" 公雞=%d 母雞=%d 雛雞=%d",Cock,Hen,Chick);

Hen=Hen+1;

}

Cock=Cock+1;

}

『肆』 C語言程序設計如何求最大公約數

最大公約數演算法：

(1)輾轉相除法

兩整數a和b：

① a%b得余數c

② 若c=0，則b即為兩數的最大公約數，結束

③ 若c≠0，則a=b，b=c，再回去執行①

(2)相減法

兩整數a和b：

① 若a>b，則a=a-b

② 若a<b，則b=b-a

③ 若a=b，則a（或b）即為兩數的最大公約數，結束

④ 若a≠b，則再回去執行①

(3)窮舉法：

① i= a b中的派者老小數

② 若a，b能同時被i整除，塵升則i即為最大公約嫌和數，結束

③ i--，再回去執行②

『伍』 求最大公約數c語言

c語言求最大公約數有輾轉相除法、更相減損術、窮舉法三種。

最大公約數：

最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號。

早在公元前300年左右，歐幾里得就在他的著作《幾何原本》中給出了高緩好卜效的解法——輾轉相除法。輾轉相除法使用到的原理很聰明也很簡單，假設用f（x，y）表示x，y的最大公約數，取k=x/y，b=x%y，則x=ky+b，如果一個數能夠同擾穗時整除x和y，則必能同時整除b和y。

而能夠同時整除b和y的數也必能同時整除x和y，即x和y的公約數與b和y的公約數是相同的，其最大公約數也是相同的，則有f（x，y）=f（y，x%y）（y>0），如此便可把原問題轉化為求兩個更小數的最大公約數，直到其中一個數為0，剩下的另外一個數就是兩者最大的公約數。