C語言求余運算

C語言求余運算

【例題】輸入兩個正整數m和m.輸出這兩個數的最大公約數和最小公倍數。

我先寫了一個求最大公約數，有了最大公約數才求得到最小公倍數。但是我先把求公約數的程序寫出來之後，運行起來有問題。

程序如下。

#include<stdio.h>
void main()
{
 int m,n,k;
 scanf("%d,%d",&m,&n);
 if(m>=n)
  k=n-1;
 else
  k=m-1;
 for(;k!=0;k--)
 {
  if(m%k==0&&n%k==0)
   printf("%d",k);
  break;
 }
 printf("\n");
}
//求m和n的最大公約數，我想的是。將最小的那個數賦給k，然後k-1，是為了防止兩個相同的數被自身整除。執行for語言，當m和n能同時被k整除的時候，輸出k的值，然後執行break結束for循環，如果不能被整除再繼續k--。
//現在這個程序有兩個問題：
//（1）這個break的位置好像放錯了，輸入結果後，程序不會顯示任何結果。
//（2）取掉之後，可以運行出結果。但是結果是錯誤的結果。
//（3）因為有 k-1 但是，輸入兩個相同的數之後，結果更是錯得離譜。
//希望大家幫我指導一下這3個問題。

最佳回答：

(1)break的位置沒錯，

（2）k=n-1;這步操作是不必要的。

 

但關鍵問題是，你的這種算法是片面的，不能求出所有數的最大公約數。

應用輾轉相除法，

舉例如下，可自行編程練習。

 

輾轉相除法．

  當兩個數都較大時，采用輾轉相除法比較方便．其方法是：

  以小數除大數，如果能整除，那麼小數就是所求的最大公約數．否則就用余數來除剛才的除數；再用這新除法的余數去除剛才的余數．依此類推，直到一個除法能夠整除，這時作為除數的數就是所求的最大公約數．

  例如：求4453和5767的最大公約數時，可作如下除法．

  5767÷4453＝1余1314

  4453÷1314＝3余511

  1314÷511＝2余292

  511÷292＝1余219

  292÷219＝1余73

  219÷73＝3

  於是得知，5767和4453的最大公約數是73．

  輾轉相除法適用比較廣，比短除法要好得多，它能保證求出任意兩個數的最大公約數．

追問：

但是在輸入一個數之後，用循環如何判定除幾次？

比如你上面說的這種方法

292÷219＝1余73

  219÷73＝3
73也是約數

3也是約數

如何選定73?

追問：

而且用這種方法在賦於變量時是否也會出錯？設5767為m，4453為n。變量為k

k=m%n

k=n%k

k=k%k?到第三步的時候變量是否會出問題？

回答：

int m=292;

int n=219;

int r ;

while(r!=0){

r=m%n;

if(r!=0){

m=n;

n=r;

}

}

printf("%d",n);

 

主要部分是這樣的，如果你調試出後，可把完整的發出來，供有同問人的借鑒。

追問：

謝謝，程序解決了問題。這種方法我也想過，但是有一點沒弄明白。

當

292÷219＝1余73

  219÷73＝3

當進行到292/219，r同樣滿足while條件

如果再進行下行，r就等於3。

r同樣滿足條件

如果再進行下行73%3，值為1，當值為1同樣滿足條件

然後現進行3%1。這時r=0,滿足條件，循環不是才停止嗎？

因為上面的while和if的條件都是當r!=0時才進行的循環。

望指導。。。

回答：

m%n在C語言,java等大多數語言裡是表示取模，即取整數相除的余數。

r=m%n,r得到的不是m/n的商，而是m/n的余數

 

如

r=219%73

219/73=3是整除，余數為0，r不會等於3，而是等於0

到此循環結束，

m=n;

n=r;

的操作不會再執行。

 

上一次循環結束時的n值就是最大公約數

追問：

我思維混亂了點。一會又取余，一會又變成了除。

非常感謝你無私的指導。