作者 主題: 求助─關於最大公因數問題〈C語言〉  (閱讀 16480 次)

0 會員 與 1 訪客 正在閱讀本文。

gary

  • 可愛的小學生
  • *
  • 文章數: 4
    • 檢視個人資料
請問各位大大,如果我想求3個未知數的最大公因數怎寫〈用函數寫〉,還有求N個未知數的最大公因數怎寫呢?〈是用C語言唷 不是C++〉

elleryq

  • 區域板主
  • 鑽研的研究生
  • *****
  • 文章數: 905
  • 性別: 男
    • 檢視個人資料
    • Thinking more...
求助─關於最大公因數問題〈C語言〉
« 回覆 #1 於: 2005-12-20 19:58 »
公因數可以用暴力法取得.
例如: 20, 用迴圈從 1 跑到 20, 每個都用 20 去除,可以除的盡(餘數是0)就是公因數.
然後把這些數字都記下來.

重複上面的方法三次,就可找出三個數的所有公因數,
接著取相同者,就是最大公因數...

整個方法都很暴力
但是一定可以交作業.
Plan your work, then work your plan.
我的首頁:http://blog.elleryq.idv.tw
351899by http://counter.li.org

gary

  • 可愛的小學生
  • *
  • 文章數: 4
    • 檢視個人資料
求助─關於最大公因數問題〈C語言〉
« 回覆 #2 於: 2005-12-20 20:05 »
我懂你的意思,但是我不知道運算式要怎麼寫內 ><

damon

  • 管理員
  • 俺是博士!
  • *****
  • 文章數: 4211
    • 檢視個人資料
    • http://blog.damon.tw/
求助─關於最大公因數問題〈C語言〉
« 回覆 #3 於: 2005-12-20 22:09 »
來這邊問作業只會有一種答案:請自己寫

gary

  • 可愛的小學生
  • *
  • 文章數: 4
    • 檢視個人資料
求助─關於最大公因數問題〈C語言〉
« 回覆 #4 於: 2005-12-20 23:29 »
呵!這不是作業,只是我自己去看題庫想不出來。
我知道求g.c.d有好幾種方法阿,輾轉相除,短除法,跟2樓大大所謂的暴力法,但是,我不知道他要怎寫。我想不出來運算式,我還有得學呢。><

日京三子

  • 全區板主
  • 俺是博士!
  • *****
  • 文章數: 8800
    • 檢視個人資料
    • http://www.24online.cjb.net
求助─關於最大公因數問題〈C語言〉
« 回覆 #5 於: 2005-12-21 08:16 »
那......... elleryq 的方法不失為一個簡單思考的方法,你應該嚐試看看。 :wink:
哈克不愛的多合一輸入平台----->新香草口味
過去的時間不斷流逝,抹去的眼淚已成追憶;
乾枯的雙手無力阻止,再會了我遠去的曾經。

twu2

  • 管理員
  • 俺是博士!
  • *****
  • 文章數: 5336
  • 性別: 男
    • 檢視個人資料
    • http://blog.teatime.com.tw/1
求助─關於最大公因數問題〈C語言〉
« 回覆 #6 於: 2005-12-21 08:20 »
引述: "gary"
我知道求g.c.d有好幾種方法阿,輾轉相除,短除法,跟2樓大大所謂的暴力法,但是,我不知道他要怎寫。我想不出來運算式,我還有得學呢。><


數學不好? 不會算? 那應該是去學數學吧.

手算會, 但不會改成程式? 那.... 找本演算法的書來看吧. 看到能了解為什麼書上的演算法會變成書上的那些範例程式. 看看別人是怎麼把邏輯轉成程式碼吧. 如果是你, 你會怎麼做... 學久了自然就懂了.

ricky

  • 實習板主
  • 鑽研的研究生
  • *****
  • 文章數: 669
    • 檢視個人資料
    • Ricky 碎碎唸
求助─關於最大公因數問題〈C語言〉
« 回覆 #7 於: 2005-12-21 09:10 »
三個數的最大公因數不會寫那就先簡化一下吧
先從兩個開始
就如同elleryq所說用暴力法(其實也沒那麼暴力啦)
要找a,b的最大公因數
1.找出a,b中最小的命名為n
   例如a<b,n=a or a>b,n=b
2.命令x=2到n開始去除a跟b,兩個都能同時整除的最大值就是a,b的最大公因數
    如果都找不到那就表示a,b互質嘍
那三個數呢
思考一下
假設a,b的最大公因數是p
那a,b,c的最大公因數不就是p,c的最大公因數
一步一步來先求a,b找出p
同樣的做法再來一次求p,c的最大公因數
我的symfony作品:YOMOpets 寵物誌
有興趣可以一起來討論symfony喔
我的部落格:http://ricky.ez2.us/

日京三子

  • 全區板主
  • 俺是博士!
  • *****
  • 文章數: 8800
    • 檢視個人資料
    • http://www.24online.cjb.net
求助─關於最大公因數問題〈C語言〉
« 回覆 #8 於: 2005-12-21 11:22 »
我不會C,我寫程式也很糟糕。在此獻上超笨拙的初學者型,「求兩個數字的最大公因數」php版程式:
引用
<?php
/*
// 尋求最大公因素
*/

//計算有多少因素
function CountMax($num,$arrayName)
{
   for ($i=2;$i<$num;$i++)
   {
      if(!($num % $i))
      {
         $arrayName[]=$i;
      }
   }
   return $arrayName;
}

// 取得兩者的公因數
function Get_Array($Array_A,$Array_B)
{
   for($i=0;$i<count($Array_A);$i++)
   {
      for($j=0;$j < count($Array_B);$j++)
      {
         // 如果有因數相同,就放入答案因素裡面去
         if($Array_A[$i] == $Array_B[$j])
         {
            $Anser[] = $Array_A[$i];
         }
      }
   }
   return $Anser;
}

// 設定兩個數字
$varA= 1210;
$varB= 36300;

//分別計算有多少因素
$Array_varA =CountMax($varA,$arrayA);
$Array_varB =CountMax($varB,$arrayB);


// 計算公因數
$AnserArray= Get_Array($Array_varA,$Array_varB);

// 顯示陣列中的最後一個,此為大公因數
echo $AnserArray[count($AnserArray)-1];
?>

輸出結果:
代碼: [選擇]
605
如果是三個數字,基本也相同,只是某幾個步驟多做幾次而已。 :wink:
哈克不愛的多合一輸入平台----->新香草口味
過去的時間不斷流逝,抹去的眼淚已成追憶;
乾枯的雙手無力阻止,再會了我遠去的曾經。

日京三子

  • 全區板主
  • 俺是博士!
  • *****
  • 文章數: 8800
    • 檢視個人資料
    • http://www.24online.cjb.net
求助─關於最大公因數問題〈C語言〉
« 回覆 #9 於: 2005-12-21 12:14 »
笨蛋作法,求三者最大公因數,PHP版:
引用
<?php
/*
// 尋求最大公因素
*/

//計算有多少因素
function CountMax($num,$arrayName)
{
   for ($i=2;$i<$num;$i++)
   {
      if(!($num % $i))
      {
         $arrayName[]=$i;
      }
   }
   return $arrayName;
}

// 取得兩者的公因數
function Get_Array($Array_A,$Array_B)
{
   for($i=0;$i<count($Array_A);$i++)
   {
      for($j=0;$j < count($Array_B);$j++)
      {
         // 如果有因數相同,就放入答案因素裡面去
         if($Array_A[$i] == $Array_B[$j])
         {
            $Anser[] = $Array_A[$i];
         }
      }
   }
   return $Anser;
}

// 設定三個數字
$varA= 1210;
$varB= 36300;
$varC= 65536;

//分別計算有多少因素
$Array_varA =CountMax($varA,$arrayA);
$Array_varB =CountMax($varB,$arrayB);
$Array_varC =CountMax($varC,$arrayC);

// 顯示出來做驗算
print_r($Array_varA);
print_r($Array_varB);
print_r($Array_varC);

// 計算公因數
$TempArray= Get_Array($Array_varA,$Array_varB);
$AnserArray= Get_Array($TempArray,$Array_varC);

// 顯示陣列中的最後一個,此為大公因數
echo $AnserArray[count($AnserArray)-1];
?>
答案是,2。各數的因數分別是
代碼: [選擇]
Array
(
    [0] => 2
    [1] => 5
    [2] => 10
    [3] => 11
    [4] => 22
    [5] => 55
    [6] => 110
    [7] => 121
    [8] => 242
    [9] => 605
)
Array
(
    [0] => 2
    [1] => 3
    [2] => 4
    [3] => 5
    [4] => 6
    [5] => 10
    [6] => 11
    [7] => 12
    [8] => 15
    [9] => 20
    [10] => 22
    [11] => 25
    [12] => 30
    [13] => 33
    [14] => 44
    [15] => 50
    [16] => 55
    [17] => 60
    [18] => 66
    [19] => 75
    [20] => 100
    [21] => 110
    [22] => 121
    [23] => 132
    [24] => 150
    [25] => 165
    [26] => 220
    [27] => 242
    [28] => 275
    [29] => 300
    [30] => 330
    [31] => 363
    [32] => 484
    [33] => 550
    [34] => 605
    [35] => 660
    [36] => 726
    [37] => 825
    [38] => 1100
    [39] => 1210
    [40] => 1452
    [41] => 1650
    [42] => 1815
    [43] => 2420
    [44] => 3025
    [45] => 3300
    [46] => 3630
    [47] => 6050
    [48] => 7260
    [49] => 9075
    [50] => 12100
    [51] => 18150
)
Array
(
    [0] => 2
    [1] => 4
    [2] => 8
    [3] => 16
    [4] => 32
    [5] => 64
    [6] => 128
    [7] => 256
    [8] => 512
    [9] => 1024
    [10] => 2048
    [11] => 4096
    [12] => 8192
    [13] => 16384
    [14] => 32768
)
經過肉眼比對,果然最大的公因數為2,程式正確! ^O^  :lol:

還請不吝指教^^
哈克不愛的多合一輸入平台----->新香草口味
過去的時間不斷流逝,抹去的眼淚已成追憶;
乾枯的雙手無力阻止,再會了我遠去的曾經。

ricky

  • 實習板主
  • 鑽研的研究生
  • *****
  • 文章數: 669
    • 檢視個人資料
    • Ricky 碎碎唸
求助─關於最大公因數問題〈C語言〉
« 回覆 #10 於: 2005-12-21 13:47 »
那我也來發表一下吧
整個程式是用php寫的
利用輾轉相除法使用遞迴函數求取GCD(最大公因數)
輾轉相除法的演算過程就回去翻翻國小課本嘍
引用

<?php
 function GCD($a,$b)
 {
  if(($a%$b)==0) return $b; //如果整除(餘數為0) $b就是最大公因數
  return GCD($b,$a%$b);  //如果不為零則交換用$b去除$a除以$b的餘數
 }
 $a=10;
 $b=1230;
 $c=460;
 $GCD_a_b=GCD($a,$b);
 $GCD_all=GCD($GCD_a_b,$c);
 echo $GCD_all;
?>
我的symfony作品:YOMOpets 寵物誌
有興趣可以一起來討論symfony喔
我的部落格:http://ricky.ez2.us/

日京三子

  • 全區板主
  • 俺是博士!
  • *****
  • 文章數: 8800
    • 檢視個人資料
    • http://www.24online.cjb.net
求助─關於最大公因數問題〈C語言〉
« 回覆 #11 於: 2005-12-21 14:13 »
閒來無事,統計「計算時間」php版:
引用

<?php
/*
// 尋求最大公因素
*/

//時間統計
function getMicrotime(){
   $time = explode(' ',microtime());
   return $time[1]+$time[0];
}

//計算有多少因素
function CountMax($num)
{
//   $num=$num / 2 ; // 只要做一半就好
   for ($i=2;$i<$num /2;$i++)
   {
      if(!($num % $i))
      {
         $TempArray[]=$i;
      }
   }
   return $TempArray;
}

// 取得兩者的公因數
function Get_Array($Array_A,$Array_B)
{
   for($i=0;$i<count($Array_A);$i++)
   {
      for($j=0;$j < count($Array_B);$j++)
      {
         // 如果有因數相同,就放入答案因素裡面去
         if($Array_A[$i] == $Array_B[$j])
         {
            $Anser[] = $Array_A[$i];
         }
      }
   }
   return $Anser;
}

// 設定三個數字
$varA = 1210;
$varB = 36300;
$varC = 65536;

//分別計算有多少因素
$StartTime=getMicrotime();
$Array_varA =CountMax($varA);
$TimeA= getMicrotime() - $StartTime;

$StartTime=getMicrotime();
$Array_varB =CountMax($varB);
$TimeB= getMicrotime() - $StartTime;

$StartTime=getMicrotime();
$Array_varC =CountMax($varC);
$TimeC= getMicrotime() - $StartTime;
// 顯示出來做驗算
/*
print_r($Array_varA);
print_r($Array_varB);
print_r($Array_varC);
*/
echo    "處理第一個數字時間為 ".$TimeA."\n".
      "處理第二個數字時間為 ".$TimeB."\n".
      "處理第三個數字時間為 ".$TimeC."\n";

// 計算公因數
$TempArray = Get_Array($Array_varA,$Array_varB);
$AnserArray = Get_Array($TempArray,$Array_varC);

// 顯示陣列中的最後一個,此為大公因數
if ($AnserArray[count($AnserArray)-1])
{
   echo "公因數為 ".$AnserArray[count($AnserArray)-1]."\n";
}else{
   echo "沒有這三者, "."\t".$varA.
   "\t".$varB.
   "\t".$varC." 的公因數"."\n";
}
?>
輸出結果為:
引用
處理第一個數字時間為 0.022422075271606
處理第二個數字時間為 0.72452116012573
處理第三個數字時間為 1.3270049095154
公因數為 2



這麼多個示範,發問題的 gary 同學,想必應該知道怎麼做了吧 ^O^  :wink:
哈克不愛的多合一輸入平台----->新香草口味
過去的時間不斷流逝,抹去的眼淚已成追憶;
乾枯的雙手無力阻止,再會了我遠去的曾經。

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
求助─關於最大公因數問題〈C語言〉
« 回覆 #12 於: 2005-12-21 14:23 »
shell 版
代碼: [選擇]

$ cat gcd3.sh
#!/bin/sh
gcd_x=$1
gcd_y=$2
gcd_z=$3
get_gcd() {
        gcd_b=$1
        gcd_r=$2
        while [ $gcd_r -ne 0 ]; do
                gcd_a=$gcd_b
                gcd_b=$gcd_r
                gcd_r=$(( $gcd_a % $gcd_b ))
        done
        echo "$gcd_b"
}
gcd_xy=`get_gcd $gcd_x $gcd_y`
gcd_xyz=`get_gcd $gcd_z $gcd_xy`
echo "gcd=$gcd_xyz"
$ ./gcd3.sh 1210 36300 65536
gcd=2

日京三子

  • 全區板主
  • 俺是博士!
  • *****
  • 文章數: 8800
    • 檢視個人資料
    • http://www.24online.cjb.net
求助─關於最大公因數問題〈C語言〉
« 回覆 #13 於: 2005-12-21 14:27 »
引述: "ricky"
那我也來發表一下吧
整個程式是用php寫的
利用輾轉相除法使用遞迴函數求取GCD(最大公因數)
輾轉相除法的演算過程就回去翻翻國小課本嘍
超級好辦法! :wink:

讓小弟佩服,真是好辦法!
哈克不愛的多合一輸入平台----->新香草口味
過去的時間不斷流逝,抹去的眼淚已成追憶;
乾枯的雙手無力阻止,再會了我遠去的曾經。

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
求助─關於最大公因數問題〈C語言〉
« 回覆 #14 於: 2005-12-21 14:42 »
引述: "thyme"
shell 版
代碼: [選擇]

$ cat gcd3.sh
#!/bin/sh
gcd_x=$1
gcd_y=$2
gcd_z=$3
get_gcd() {
        gcd_b=$1
        gcd_r=$2
        while [ $gcd_r -ne 0 ]; do
                gcd_a=$gcd_b
                gcd_b=$gcd_r
                gcd_r=$(( $gcd_a % $gcd_b ))
        done
        echo "$gcd_b"
}
gcd_xy=`get_gcd $gcd_x $gcd_y`
gcd_xyz=`get_gcd $gcd_z $gcd_xy`
echo "gcd=$gcd_xyz"
$ ./gcd3.sh 1210 36300 65536
gcd=2


老jou說看不太懂 @_@
上面大概只有 $(( $gcd_a % $gcd_b )) 比較不常用,
其他都很普通,
$(( )) 就是 bash 做數學運算的的方法
echo $(( 1 + 2 )) 會得到3
% 就是 mod ,算餘數
b=$(( 20 % 6 ))
echo $b
會得到餘數 2

日京三子

  • 全區板主
  • 俺是博士!
  • *****
  • 文章數: 8800
    • 檢視個人資料
    • http://www.24online.cjb.net
求助─關於最大公因數問題〈C語言〉
« 回覆 #15 於: 2005-12-21 14:53 »
引述: "thyme"

老jou說看不太懂 @_@
上面大概只有 $(( $gcd_a % $gcd_b )) 比較不常用,
其他都很普通,
$(( )) 就是 bash 做數學運算的的方法
echo $(( 1 + 2 )) 會得到3
% 就是 mod ,算餘數
b=$(( 20 % 6 ))
echo $b
會得到餘數 2

老大!

單獨「指令」是看得懂,但是搞不懂你那部份是在做甚麼啊 QQ

例如:
代碼: [選擇]
get_gcd() {
        gcd_b=$1
        gcd_r=$2
        while [ $gcd_r -ne 0 ]; do
                gcd_a=$gcd_b
                gcd_b=$gcd_r
                gcd_r=$(( $gcd_a % $gcd_b ))
        done
        echo "$gcd_b"
}

我知道,gcd_b=$1 <-- 這串是用來定義說,第一個由指令列傳入的變數,就讓他叫做gcd_b但,你後面接著這個迴圈:
代碼: [選擇]
       while [ $gcd_r -ne 0 ]; do
                gcd_a=$gcd_b
                gcd_b=$gcd_r
                gcd_r=$(( $gcd_a % $gcd_b ))
        done
就看不懂這是在幹什麼了@@

還請抽空指點一下,謝謝 :cry:
哈克不愛的多合一輸入平台----->新香草口味
過去的時間不斷流逝,抹去的眼淚已成追憶;
乾枯的雙手無力阻止,再會了我遠去的曾經。

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
求助─關於最大公因數問題〈C語言〉
« 回覆 #16 於: 2005-12-21 16:47 »
#!/bin/sh
# 輾轉相除法:把除數當成被除數,把餘數當除數,一直到餘數為零,此時除數即為我們所
要的。
# 1. input x, y
# 2. x / y = z ....r
# 3. x = y; y = r
# 4. x / y = z ....r
# 5. ....直到 r 為零

# 在命令列,傳入的第一個參數為 $1,第二個為 $2,以此類推
gcd_x=$1
gcd_y=$2
gcd_z=$3

# xxx() {  } 形式的就是宣告副程式
get_gcd() {
    # 副程式也可以看成一個sehll程式, 傳入的第一個參數為 $1,以此類推
    gcd_b=$1
    gcd_r=$2
    # 正常是將第一個參數給 gcd_a, 第二個給 gcd_b
    # 為了減少一個判斷餘數是否為零的動作,就直接這麼設定

    # 只要餘數不為零,就繼續做迴圈
    # $gcd_r 最好寫成 "$gcd_r" ,才不會在 gcd_r 為空的時出錯
    # 開始做輾轉相除
    while [ "$gcd_r" -ne 0 ]; do
        # 把上一次相除的除數設成被除數
        gcd_a=$gcd_b
        # 把上一次相除的餘數設成除數
        gcd_b=$gcd_r
        # % 就是取得餘數的運算
        # $(( )) 是shell做數學運算的表示法
        # gcd_r 是求出的餘數
        gcd_r=$(( $gcd_a % $gcd_b ))
    done
    echo "$gcd_b"
}
# 先算 x y 的公因數
# 由於用 xxx=`yyy `的方式執行,在副程式內 echo 出來的字串,都會放在 xxx 變數裡
gcd_xy=`get_gcd $gcd_x $gcd_y`
# 再和 z 算公因數
gcd_xyz=`get_gcd $gcd_z $gcd_xy`
# 印出結果
echo "gcd=$gcd_xyz"

gary

  • 可愛的小學生
  • *
  • 文章數: 4
    • 檢視個人資料
求助─關於最大公因數問題〈C語言〉
« 回覆 #17 於: 2005-12-21 18:49 »
謝謝各位囉,我知道我要用什麼方法了,先將X,Y做輾轉相除,在用FUNCTION來來寫的gcd2(gcd(X,Y),Z)。至於n個數的話,就用陣列將每數值儲存,以此類推就求出來了。
不過我還有用非陣列式寫法來寫n個數的最大公因數。

代碼: [選擇]
#include<stdio.h>
 int GCD(int x,int y)
{
 if(x%y==0)
 return y;
 return GCD(y,x%y);
}
main()
{
 int i,num,a,b;
 printf("Please input the numbers of you want:");
 scanf("%d",&num);
 printf("Please input a number:");
 if(num>=1)
 scanf("%d",&a);
 for(i=2;i<=num;i++)
 {
 printf("Please input a number:");
 scanf("%d",&b); a=GCD(a,b);
 }
printf("The G.C.D is%d\n",a);
}

謝謝各位囉。 ^^
至於國小數學課本已經丟了,呵呵‧‧‧我也想當國小生耶,但是我媽不准 ><