求最大公約數c語言演算法

Ⅰ C語言程序設計如何求最大公約數

具體操作步驟如下：

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

Ⅱ 如何用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、求最大公約數

對兩個正整數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;

}