輾轉相除c語言
㈠ 什麼是c語言裡面的輾轉相除法
用輾轉相除法（即歐幾里得演算法）求兩個正整數的最大公約數。
解析：
設兩個數m,n，假設m>=n，用m除以n，求得余數q。若q為0，則m為最大公約數；若q不等於0，則進行如下迭代：
m=n,n=q,即原除數變為新的被除數，原余數變為新的除數重復演算法，直到余數為0為止。余數為0時的除數n，即為原始m、n的最大公約數。
迭代初值：m，n的原始值；
迭代過程：q=m%n;
m=n;
n=q;
迭代條件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因為：(q==2)!=0，重復演算法：
q=m%n(6%2==0)
m=n(m==2)余數為0時的除數n為最大公約數，n值賦給了m，所以輸出m的值
n=q(n==0)
因為：q==0 所以最大公約數為m的值
源程序：
#include<stdio.h>
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",&a,&b);
m=a;
n=b;
if(n>m)
{
int z;
z=m;m=n;n=z;//執行演算法前保證m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf("The greatest common divisor of");
printf("%d,%d is %d\n",a,b,m);
}
希望對你有所幫助!
㈡ C語言輾轉相除法問題
#include <stdio.h>
int fun(int a,int b) /* 2個數的公約數 */
{
int t;
while(b)
{
t = a%b;
a = b;
b = t;
}
return a;
}
int main()
{
int a[100];
int n;
int i;
int res;
scanf("%d",&n); /* 先輸入數的總數n */
if(n < 2)
{
printf("n不能小於2
");
return 0;
}
for(i=0;i<n;i++) /* 輸入n個數 */
scanf("%d",&a[i]);
res = fun(a[0],a[1]);
for(i=2;i<n;i++)
res = fun(res,a[i]);
printf("%d
",res);
return 0;
}
㈢ 輾轉相除法c語言
這是求最大公約數的，沒有問題啊，是不是你輸入出錯了，示例運行結果如下：
12,8
gcd=4
16,36
gcd=4
中間的逗號不能少的哦，否則就會出錯了，因為scanf("%d,%d",&a,&b);的%d,%d中間是有都逗號的呀。
㈣ c語言用輾轉相除法將一個十進制整數轉換成任意非十進制數（二、八、十六）
#include<stdio.h>
voidmain()
{
/*b[16]為數組，n—十進制數，m—進制類型，r—余數,i—循環變數,k—下標*/
intb[16],t,m,n,k,r,i;
printf("請輸入一個十進制整數:");/*輸入提示*/
scanf("%d",&n);
printf("請輸入一個要轉換的進制類型(2，8，16):");/*輸入提示*/
scanf("%d",&m);
t=n;/*用t暫存n*/
k=-1;/*k為數組下標,初值為-1*/
/*在兩條星線間填入代碼,用輾轉相除法將十進制數轉換為m進制數並存入數組b*/
/**********************************************************************/
if(m!=2&&m!=8&&m!=16)
{
printf("輸入的進制數不是2,8,16其中之一，默認使用2!!!!!!! ");
m=2;
}
while(n){
r=n%m;
n=n/m;
b[++k]=r;
}
/**********************************************************************/
/*輸出提示*/
printf("十進制整數%d轉換為%d進制數，結果=",t,m);
/*在兩條星線間填入代碼,從高位到低位輸出數組b（使用switch多分支語句）*/
/*********************************************************************/
for(i=k;i>=0;i--)
printf("%d",b[i]);
/*********************************************************************/
printf(" ");/*換行*/
}
㈤ c語言輾轉相除法
按照你的改了一下
#include<stdio.h>
intgcd(intx,inty)
{
inti;
intmax,min;
(x>y)?(max=x,min=y):(max=y,min=x);
if(i=max%min!=0)
do{
i=min;
min=max%min;
max=i;
}while(min!=0);
returnmax;
}
intmain()
{
inta,b;
scanf("%d%d",&a,&b);
printf("%d ",gcd(a,b));
return0;
}
再給你一個精簡版，二者實質是一樣的
#include<stdio.h>
intgcd(intx,inty)
{
if(y==0)returnx;
returngcd(y,x%y);
}
intmain()
{
inta,b;
scanf("%d%d",&a,&b);
printf("%d ",gcd(a,b));
return0;
}
㈥ 輾轉相除法求最大公約數c語言代碼
輾轉相除法是在在維基網路中的意思是：
在數學中，輾轉相除法，又稱歐幾里得演算法（英語：Euclidean algorithm），是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
兩個整數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。例如，252和105的最大公約數是21（ {\displaystyle 252=21\times 12;105=21\times 5} {\displaystyle 252=21\times 12;105=21\times 5}）；因為 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公約數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。這時，所剩下的還沒有變成零的數就是兩數的最大公約數。由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如 21 = 5 × 105 + (−2) × 252 。這個重要的結論叫做裴蜀定理。
在現代密碼學方面，它是RSA演算法（一種在電子商務中廣泛使用的公鑰加密演算法）的重要部分
簡單的來說輾轉相除法的原理就是：
先比較兩個數使第一個數為最大數a，第二個數為最小數b
使最大數%最小數得到余數a%b=temp
後將余數賦值給最小數a=temp再去除最大數b即b%a
一直往復直到余數不為0
㈦ 輾轉相除法c語言代碼
輾轉相除法用來求兩個數的最大公約數，代碼如下：
#include<stdio.h>
#include<stdlib.h>
intmain()
{
inta,b,r;
scanf("%d%d",&a,&b);
while(b!=0)//當其中一個數為0，另一個數就是兩數的最大公約數
{
r=a%b;
a=b;
b=r;
}
printf("GreatestCommonDivisor:%d ",a);
system("pause");
}
運行結果：
㈧ c語言求最大公約數輾轉相除法
int main(void)
{
printf("這是兩個整數求最大公約數的算式，請輸入兩個不相等的正整數，並按回車鍵確認：\n"); //操作提示
intm,n,r,i; //定義四個整形變數
scanf("%d %d",&m,&n); //輸入m和n的值
if(m<n) {i=m;m=n;n=i;} //如果m<n，借用變數i進行m和n的數值互換
while(m%n!=0) //m取模n 賦值給r
{r=a%b;m=n;n=r;} //余數不等於0，則n的值給m，r的值給n，再次進入循環
printf("它們的最大公約數是%d\n",n);
system("PAUSE");
return 0;
}
㈨ c語言中，用輾轉相除法計算兩個數的最大公約數的具體方法是怎樣的
#include <stdio.h>
int gcd(int a, int b) {
int r;
do {
r = a % b;
a = b;
b = r;
} while (r);
return a;
}
int main(void) {
int a, b;
printf("Input two integers: \n");
scanf("%d%d", &a, &b);
printf("The greatest common divisor is: %d\n", gcd(a, b));
return 0;
}
原理：
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余數，則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法是：
1. a ÷ b，令r為所得余數（0≤r<b）
若 r = 0，演算法結束；b 即為答案。
2. 互換：置 a←b，b←r，並返回第一步
㈩ C語言輾轉相除法
例如用輾轉相除法求a b 最大公約數（a b誰大誰小無所謂）：
int GCD( int a , int b )
{
int n=a%b;
whie(n != 0) //即： while(n)
{
a = b;
b = n;
n = a % b;
}
return b; //注意這里返回的是b 不是n
}