2015年6月30日 星期二

繼承



在前兩篇的主程式中,透過 class myData object1 物件的 object1.add(d) 來加入資料,再呼叫 common_divisor(object1.data,object1.len) 來找出答案,由於 common_divisor 並不包含在 class myData 中,所以開發人員需要了解 class myData 的資料結構及 common_divisor 的參數型態才能把兩者搭配在一起,這樣會增加程式開發的複雜度,雖然把 common_divisor 放進 class myData 中可以改善這情況,但 class myData 偏向基礎資料類別,應該要讓很多不同的開發需求都能使用,如果把 common_divisor 函式加進去,那對於不需要"最大公因數"的應用來說這個函式就多餘了。

以繼承 class myData 來建立一個包含 common_divisor 的衍生類別 gcd,是可以不用重頭開發,又可避免在 class myData 添加多餘函式的方法。


C++的繼承機制有 private, protected, public 三種,不同的繼承方式會限制衍生類別對外公開父類別成員的機制,以下程式以 public 繼承來建立衍生類別 gcd:


#include <iostream>

class myData
{
//私有區段,只有class內部程式可存取
private:
   int _boundary; //陣列空間上限

//保護區段,只有class內部程式和繼承的class可存取
protected: 
   int len;  //資料總數 
   int *data; //用來存放所有輸入資料的記憶空間指標

//公用區段,class內外部程式均可存取
public:
   myData() //建構函式,當物件產生時會自動執行
   {
     len=0; //資料總數歸0
     _boundary=10; //邊界設為10 
     data=new int[_boundary]; //配置10個int記憶空間 
   }

   ~myData() //解構函式,當物件消滅時會自動執行
   {
     delete [] data; //釋放data記憶空間
   }

   void add(int d)
   {
     if (len>=_boundary-1) //資料滿了,增加記憶空間
     {
       int *newptr=new int[_boundary+10]; //動態配置比原來多10個int記憶空間
       for(int i=0; i<len; i++)
         newptr[i]=data[i]; //把舊資料複製到新的位置
       delete [] data; //釋放舊的記憶空間
       data=newptr; //資料指標指向新的位置
       _boundary+=10;
     }
     data[len++]=d; //把參數d放在最後的位置後再把資料長度+1
   }
};

class gcd : public myData //衍生類別 gcd 以 public 方式繼承 myData 
{
private:
   int common_divisor(int a, int b) //遞迴函式1
   {
     return (a%b==0) ? b : common_divisor(b,a%b); //交換位置輾轉相除
   }

   int common_divisor(int d[], int n) //遞迴函式2
   {
     if(n==1)
       return d[0];
     if(n==2)
       return common_divisor(d[0],d[1]); //呼叫遞迴函式1
     if(n>2)
       return common_divisor(common_divisor(d,n/2),
                         common_divisor(&d[n/2],n-n/2) ); //呼叫遞迴函式2 
     return 0; //n小於1才會發生
   }

public:
   int result() { return common_divisor(data, len); }
};

int main()
{
   int d;
   gcd mygcd;

   std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl;
   while ( std::cin >> d )
      mygcd.add(d);
   
   std::cout << "最大公因數=" << mygcd.result();
   return 0;
}

衍生類別 class gcd 對於父類別 class myData 是以 public 的方式繼承,有權存取父類別的 protected: 和 public: 區段,但無權存取父類別的 private: 區段;而在父類別 public: 區段中的資料或函式,以 public 方式繼承的衍生類別也會將其對外界公開,所以主程式只要宣告一個 gcd 物件 mygcd,即可以 mygcd.add() 叫用父類別的函式,最後再以 mygcd.result() 叫用 class gcd 的函式 result 得到結果。

由於外界已不必直接操作 class myData 中的 len 和 data,所以把它們搬到 
protected 區段以提高資料的安全性,同時也保留讓衍生類別可以存取的彈性。而置於 private 區段的資料或函式,仍然只有 class 本身有存取權限,繼承者或外部程式均無法存取。

public繼承
父類別衍生類別
publicpublic
protectedprotected
private無法存取

protected繼承
父類別衍生類別
publicprotected
protectedprotected
private無法存取

private繼承
父類別衍生類別
publicprivate
protectedprivate
private無法存取



2015年6月29日 星期一

Class template 類別樣版/模板



使用具有動態配置及記憶空間管理能力的 class 來存取資料,可以分擔主程式開發的工作,如上一篇 改善記憶體管理效能 裡的 class myData。但 myData 只處理 int 型態的資料,若要處理其他資料型態,例如來源資料是帶有小數點的浮點數,那又得另外撰寫一個 class myfloatData 來處理,不太理想。

針對這樣的問題,C++ 提供 Class template 的設計方法來解決,基本上就是把 class 宣告成類別樣板,以提高程式碼的可重覆使用性。Class template 基本語法:


template <class 變數型態名稱

class 類別名稱{ 
    // ........ 
    變數型態名稱 ........
};

以 Class template 方式改寫上一篇 class myData 如下


#include <iostream>


template <class dType>

class myData
{
//私有區段,只有class內部程式可存取
private:
   int _boundary; //陣列空間上限 

//公用區段,class內外部程式均可存取

public:
   int len;
   dType *data; //用來存放所有輸入資料的記憶空間指標
       
   //Member function
   myData() //建構函式,當物件產生時會自動執行
   {
     len=0; //資料長度歸0
     _boundary=10; //邊界設為10 
     data=new dType[_boundary]; //配置10個dType記憶空間 
   }

   ~myData() //解構函式,當物件消滅時會自動執行

   {
     delete [] data; //釋放data記憶空間
   }

   void add(dType d)

   {
     if (len>=_boundary-1) //資料滿了,增加記憶空間
     {
       dType *nptr=new dType[_boundary+10]; //配置10個dType記憶空間
       for(int i=0; i<len; i++)
         nptr[i]=data[i]; //把舊資料複製到新的位置
       delete [] data; //釋放舊的記憶空間
       data=nptr; //資料指標指向新的位置
       _boundary+=10;
     }
     data[len++]=d; //把參數d放在最後的位置後再把資料長度+1
   }
};

int common_divisor(int a, int b) //遞迴函式1

{
    return (a%b==0) ? b : common_divisor(b,a%b); //交換位置轉轉相除
}

int common_divisor(int d[], int n) //遞迴函式2

{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]); //呼叫遞迴函式1
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                           common_divisor(&d[n/2],n-n/2) ); //呼叫遞迴函式2 

   return 0; //n小於1才會發生

}

int main()

{
   int d;
   myData<int> object1;

   std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl;

   while ( std::cin >> d )
      object1.add(d);
   
   std::cout << "最大公因數=" << common_divisor(object1.data,object1.len);
   return 0;
}

跟原來的程式幾乎一樣,差別只是原來在 class 中寫死的 int,改為未知型態代名 dType。主程式中則以  myData<int> object1; 宣告來指定 dType 的實際型態 int。將來若需處理浮點數
資料,只要在程式裡宣告 myData<float> object2; 就可以使用了。

改善記憶體管理效能




上篇的動態配置記憶空間做法,每加入一筆資料就要重新產生新的空間,還要把舊資料 copy 過去,效率非常差。若是一開始就先配置一段大小適中的記憶空間,可以直接儲存每次輸入的資料,而在空間用完的時候才去配置新的空間,這樣就可以在執行效能和記憶體需求之間取得平衡。而每次配置的空間應該多大,需評估輸入資料產生的速度,資料輸入越快越多,就應配置更大的空間。

#include <iostream>

class myData
{
//私有區段,只有class內部程式可存取
private:
   //Data member
   int _boundary; //陣列空間上限 

//公用區段,class內外部程式均可存取
public:
   //Data member
   int len;
   int *data; //用來存放所有輸入資料的記憶空間指標
     
   //Member function
   myData() //建構函式,當物件產生時會自動執行
   {
     len=0; //資料長度歸0
     _boundary=10; //邊界設為10 
     data=new int[_boundary]; //配置10個int記憶空間 
   }

   ~myData() //解構函式,當物件消滅時會自動執行
   {
     delete [] data; //釋放data記憶空間
   }

   void add(int d)
   {
     if (len>=_boundary-1) //資料滿了,增加記憶空間
     {
       int *newptr=new int[_boundary+10]; //動態配置比原來多10個int記憶空間
       for(int i=0; i<len; i++)
         newptr[i]=data[i]; //把舊資料複製到新的位置
       delete [] data; //釋放舊的記憶空間
       data=newptr; //資料指標指向新的位置
       _boundary+=10;
     }
     data[len++]=d; //把參數d放在最後的位置後再把資料長度+1
   }
};

int common_divisor(int a, int b) //遞迴函式1
{
    return (a%b==0) ? b : common_divisor(b,a%b); //交換位置輾轉相除
}

int common_divisor(int d[], int n) //遞迴函式2
{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]); //呼叫遞迴函式1
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                           common_divisor(&d[n/2],n-n/2) ); //呼叫遞迴函式2 

   return 0; //n小於1才會發生
}

int main()
{
   int d;
   class myData object1;

   std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl;
   while ( std::cin >> d )
      object1.add(d);
   
   std::cout << "最大公因數=" << common_divisor(object1.data,object1.len);
   return 0;

}

2015年6月27日 星期六

class讓資料變聰明

Q : 輸入n個正整數,使用 class 設計求最大公因數程式



char bool int long float double 這些在 C 時期就已存在的基本資料型態,本身只是單純的資料沒有執行能力,不易用來開發物件導向程式。

C++ 剛誕生時,最初的名字稱為「C with Classes」,也就是具有 class 的 C 語言,這意味著 class 的加入,是 C++ 更上層樓成為物件導向程式語言的開端。

class 是一種自訂型態,其內容包含資料成員 (Data member) 和成員函式 (Member function) 兩大類。當 class 設計好之後,就可用來在程式中宣告並產生物件。由於 class 包含了資料和函式(Member function),所以物件本身就具有執行能力。

以下即改寫上一篇程式,用 class 來取代主程式中的 int 陣列與指標

#include <iostream>

class myData
{
//公用區段,class內外部程式均可存取
public:
   //Data member
   int len;
   int *data; //用來存放所有輸入資料的記憶空間指標

   //Member function
   myData() //建構函式,當物件產生時會自動執行
   {
       len=0; //資料長度歸0
       data=0; //資料指標歸0
   }

   ~myData() //解構函式,當物件消滅時會自動執行
   {
       if (data!=0)
         delete [] data; //釋放data記憶空間
   }

   void add(int d)
   {
     if (data!=0) //已經存在舊資料
     {
       int *newptr=new int[len+1]; //動態配置比原來多一個單位的記憶空間
         for(int i=0; i<len; i++)
             newptr[i]=data[i]; //把舊資料複製到新的位置
       delete [] data; //釋放舊的記憶空間
       data=newptr; //資料指標指向新的位置
     } else
       data=new int[1]; //沒有舊資料,直接動態配置記憶空間

     data[len]=d; //把參數d放在最後的位置
     len++; //資料長度+1
   }
};

int common_divisor(int a, int b) //遞迴函式1
{
   if(a%b==0) //如果a/b餘0,b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大,把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大,交換位置重新測試
}

int common_divisor(int d[], int n) //遞迴函式2
{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]);
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                                     common_divisor(&d[n/2],n-n/2) );

   return 0; //n小於1才會發生
}

int main()
{
   int d;
   class myData object1;

   std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl;
   while ( std::cin >> d )
      object1.add(d);

   std::cout << "最大公因數=" << common_divisor(object1.data, object1.len);
   return 0;
}

程式中設計了一個 class myData,它包含了 data、len 兩個資料成員,及建構函式、解構函式與 add 函式,之後於主程式中宣告了 myData 類別的 object1 物件,主程式不用再理會記憶體管理問題,只要以 object1.add(d); 去添加使用者輸入的數字即可,除了程式更簡易清晰,將來若想改善記憶體管理的效能,也只要修改 class myData 即可,後續維護的工作更容易。

2015年6月26日 星期五

動態配置記憶空間

Q : 輸入兩個正整數,以遞迴方式計算最大公因數並輸出



上一篇 "換個方式看公因數" 的程式仍然有個問題,主程式 main() 以一個靜態陣列 int data[1000] 來存放使用者輸入的數字,若使用者輸入了超過 1000 個數字,程式就沒辦法處理。又或使用者只輸入 3 個數字,那麼 997 個多餘的空間就浪費了。要改善這個問題,就要使用動態空間配置。

char bool int long float double 都是 C++ 的基本資料型態,以他們宣告出來的變數即佔有對應的記憶空間,用來在程式中存放資料。int data[1000] 以靜態的方式宣告了名為 data 的陣列變數,共有 1000 個存放 int 資料的空間,靜態資料空間伴隨程式而存在,除非程式結束,否則空間不會釋放。

若改用指標的方式宣告,就能做到動態空間配置,例如

int* data;
.
.
data = new int[20];
.
.
delete [] data;

上面程式先宣告了一個名為 data 的 int 指標變數(尚未產生資料空間),直到中間以 new 指令才動態配置了 20 個 int 記憶空間,最後使用完畢以 delete 指令釋放記憶空間。而在程式中,以陣列的方式即可存取 data 的元素,例如 data[18]=100;

用上述的方法改寫上一篇的主程式 main() ,就能實現動態配置記憶空間,以避免輸入資料過多或空間浪費的問題,程式修改如下

#include <iostream>

int common_divisor(int a, int b) //遞迴函式1
{
   if(a%b==0) //如果a/b餘0,b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大,把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大,交換位置重新測試
}

int common_divisor(int d[], int n) //遞迴函式2
{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]);
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                                     common_divisor(&d[n/2],n-n/2) );

   return 0; //n小於1才會發生
}

int main()
{
   int d;
   int datacount=0;
   int *dataptr=0; //用來存放所有輸入資料的記憶空間指標

   std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl;
   while ( std::cin >> d )
   {
      if (dataptr!=0) //已經存在舊資料
      {
         int *newptr= new int[datacount+1]; //動態配置比原來多一個單位的記憶空間
         for(int i=0; i<datacount; i++)
                newptr[i]=dataptr[i]; //把舊資料複製到新的位置

         delete [] dataptr; //釋放舊的記憶空間
         dataptr=newptr; //資料指標指向新的位置
      } else
         dataptr=new int[datacount+1]; //沒有舊資料,直接動態配置記憶空間

        dataptr[datacount]=d; //把輸入的資料放進最後一個位置
        datacount++; //資料計數變數+1
    }
    std::cout << "最大公因數=" << common_divisor(dataptr, datacount);
    return 0;
}

基本資料型態本身不具備"主動"的方法,完全靠外在的程式碼去處理必要的程序,雖然看起來很傻沒有技巧,但總算仍可以完成任務~

2015年6月25日 星期四

換個方式看公因數

Q : 輸入兩個正整數,以遞迴方式計算最大公因數並輸出



在 "遞迴尋找公因數" 中,雖然使用了遞迴函式來尋找公因數,但其運算方式和使用for迴圈並無不同,執行效率也沒有提升,純粹只是為了要寫成遞迴的型式。

若有 a b 兩數的公因數是 7,表示 a 和 b 必為 7 的倍數,如 7*3=21 與 7*5=35,則兩數相減的差也必然是 7 的倍數,展開來看就很清楚:


35-21=(7*5)-(7*3)=7*(5-3)=14,7當然也是14(兩數相減)的因數


反覆利用兩數相減的差,取代原先大的數字來尋找公因數,可減少測試的次數(先前的方式是每次減1,遞減速度較慢),而遞迴函式即適合用來處理這類的運算,程式如下


#include <iostream>


int common_divisor(int a, int b)

{
   if(a%b==0) //如果a/b餘0,b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大,把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大,交換位置重新測試
}

int main()

{
    int a, b;

    std::cout << "請輸入2個正整數:";

    std::cin >> a >> b;
    std::cout << "最大公因數=" << common_divisor(a,b);
    return 0;
}

若要處理更多個數字,則可以搭配先前的方法來處理


#include <iostream>


int common_divisor(int a, int b) //遞迴函式1 

{
   if(a%b==0) //如果a/b餘0,b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大,把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大,交換位置重新測試
}

int common_divisor(int d[], int n) //遞迴函式2 

{
   if(n==2)
     return common_divisor(d[0],d[1]); //只剩兩個數字,交給遞迴函式1找公因數 
   else if(n>2)
     //提出第一個數字,第二個數字由遞迴函式2處理,再交給遞迴函式1找公因數
     return common_divisor(d[0], common_divisor(&d[1], n-1));

   return 0; //n小於2才會發生 
}

int main()

{
    int data[1000], datacount=0; //假設輸入數字最多1000個

    std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl; 

    while ( std::cin >> data[datacount] )
        datacount++;
  
    std::cout << "最大公因數=" << common_divisor(data, datacount);
    return 0;
}

最後,使用二分法來改寫遞迴函式2,可以讓程式的執行效率更好

int common_divisor(int d[], int n) //遞迴函式2
{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]);
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                                        common_divisor(&d[n/2],n-n/2) );

   return 0; //n小於1才會發生
}

2015年6月24日 星期三

遞迴尋找公因數

Q : 輸入幾個正整數,以遞迴方式計算最大公因數並輸出



在 "求最大公因數" 中,求公因數的函式裡有一個 for 迴圈

把這段改為遞迴就行了




#include <iostream>

int common_divisor(int a, int b, int c, int x) //
遞迴函式
{
if(a%x==0 && b%x==0 && c%x==0) //終止條件,找到公因數 
return x;

x--;
if (x>a) x=a;
if (x>b) x=b;
if (x>c) x=c;

return common_divisor(a,b,c,x); //測試下一個 
}

int common_divisor(int a, int b, int c)

{
return common_divisor(a,b,c,a); //先假設a是公因數,去呼叫遞迴函式
}

int main()

{
  int a, b, c;

  std::cout << "請輸入3正整數:";

  std::cin >> a >> b >> c;
  std::cout << "最大公因數=" << common_divisor(a,b,c);
  return 0;
}

這個程式中有兩個同名函式 common_divisor,這是 C++ 允許的,因為兩個函式接受參數的數量不同,所以編譯器會依呼叫者所傳遞的參數數量(和型態),去對應正確的函式。在 main 裡的 std::cout << "最大公因數=" << common_divisor(a,b,c); 因只傳了 a,b,c 三個參數,所以會呼叫非遞迴的 int common_divisor(int a, int b, int c),再透過這個函式呼叫真正的遞迴函式 int common_divisor(int a, int b, int c, int x) 去尋找答案。

上面的程式裡有個明顯的問題,由於最大公因數 x 必小於或等於 a b c,為了避免多餘的運算,所以在遞迴函式中有 x>a x>b x>c 的判斷,以快速縮小 x 的起始值來提升運算的效率,但 x>a x>b x>c 的判斷只需在開始時執行一次就可以了,不用在每次遞減的過程中重複進行無效比對,程式修改如下:

int common_divisor(int a, int b, int c, int x) //遞迴函式
{
if(a%x==0 && b%x==0 && c%x==0) //終止條件,找到公因數 
return x;

return common_divisor(a,b,c,x-1); //遞減測試下一個 
}

int common_divisor(int a, int b, int c)

{
  int x=a;
if (x>b) x=b;
if (x>c) x=c;
return common_divisor(a,b,c,x); //先假設a b c中最小的是公因數,去呼叫遞迴函式
}

使用陣列

Q : 輸入幾個正整數存放於陣列,計算最大公因數並輸出



1. 陣列就是一串性質相同的變數,存放於連續的 memory 位址
2. 當同性質的資料變多,應該用陣列來取代 a b c 這種獨立變數
3. 陣列 arr[n] 有 n 個元素,存放於 arr[0] ~ arr[n-1]
4. 處理陣列資料,通常會使用迴圈

本題和 "求最大公因數" 相同,但要用陣列來存放輸入資料,程式如下

#include <iostream>

int common_divisor(int d[], int n)
{
   int i, min, x;

   for(min=d[0], i=1; i<n; i++) //假設min是d[0],搜尋索引從1開始 
   {
      if (d[i]<min)
         min=d[i]; //找出d[i]中最小的值做為測試起始值
   }

   for(x=min; x>0; x--) //因要找出符合條件中最大的,所以迴圈從大到小遞減
   {
      bool match=true; //先假設所有 d[i] 可以被 x 整除
      for(i=0; i<n; i++)
      {
         if(d[i]%x!=0)  //任一項 d[i] 不能整除就跳出i迴圈,測試下一個x 
         {
            match=false;
            break;
         }
      }
      if (match) //完全符合,此 x 即為最大公因數,回傳主程式
        return x;
    }
    return 0; //不可能
}

int main()
{
    int data[1000], datacount=0; //假設輸入數字最多1000個

    std::cout << "請輸入n個正整數,輸入完成請按 Ctrl-Z" << std::endl; 
    while ( std::cin >> data[datacount] )
datacount++;

    std::cout << "最大公因數=" << common_divisor(data, datacount);
    return 0;
}

第一個遞迴

Q : 計算 x 的 y 次方值



x 的 y 次方值,就是 x 不斷連乘,總共乘以 y 次的結果
例如 5 的 3 次方就是 5 x 5 x 5 = 125

幾乎不必思考,直接以迴圈撰寫程式

long power(int x, int y)
{
   long r=1;
   while( y-- > 0 ) //用 r 來存放 x 累乘結果,共累乘 y 次
      r=r*x;
   return r;
}

次方值在計算複利、年金時經常會用到,但 C++ 內建的數學運算只有五種
加 + 減 - 乘 * 除 / 餘 %
所以次方這類的計算,就要用函式來處理。但上面的 power 函式沒用遞迴...

遞迴(Recursion)也是函式,透過不斷呼叫自己來運算結果
設計遞迴函式要注意幾點 :
1. 相同的運算方式 (若運算過程沒有規律,就難以用同一段程式來處理)
2. 遞迴參數調整 (參數若不改變,就難以到達終止條件)
3. 終止條件 (透過自我呼叫時不斷改變的參數,最後要符合終止條件)


1.x 的 y 次方值,就是 x 不斷乘以 x ,總共乘以 y 次的結果
2.次方函式有兩個參數 power( x, y )
3.若計算 5 的 2 次方,主程式呼叫 power( 5, 2 )


step a. power 收到後,呼叫自己計算 5 * power ( 5 , 1 )
step b. power 收到後,呼叫自己計算 5 * power ( 5 , 0 )
step c. power 收到後,達終止條件,傳回 power ( 5 , 0 ) = 1
step b. 收到返回值 1,傳回 5 * power ( 5 , 0 ) = 5 * 1 = 5
step a. 收到返回值 5,傳回 5 * power ( 5 , 1 ) = 5 * 5 = 25

主程式收到結果 25

同樣是思考次方的計算,遞迴要多點想像力,直接看程式會比較清楚

long power(int x, int y)
{
   long r;
   if(y<1) //終止條件,x 的 0 次方等於 1,回傳並結束
     return 1;
   r = x * power(x, y-1); //提一個 x 出來,如 8^5 = 8 * (8^4)
   return r;
}


2015年6月23日 星期二

從小學題目開始 - 求最大公因數

Q : 輸入幾個正整數,計算最大公因數並輸出



1. 公因數x,就是一組數字的共同因數,這組數字除以x都餘0
2. 公因數x,絕對不可能大於這組數字中最小的數字
3. 最大公因數,就是符合上述條件的n個x中,數值最大的

經過以上的思考,就可以用迴圈循序測試法寫出程式了

#include <iostream>

int common_divisor(int a, int b, int c)
{
  int min=a;

  if (b<min)  //找出 a b c 中最小的值做為測試起始值,避免多餘的測試
    min=b;
  if (c<min)
    min=c;

  for(int x=min; x>0; x--) //因要找出符合條件的最大值所以由大往小比對
  {
    if(a%x==0 && b%x==0 && c%x==0) //測試a b c 除以x是否都餘0
       return x; //完全比對符合則回傳x,即a b c的最大公因數
  }
  return 0; //不可能
}

int main()
{
  int a, b, c;

  std::cout << "請輸入3正整數:";
  std::cin >> a >> b >> c;
  std::cout << "最大公因數=" << common_divisor(a,b,c);
  return 0;
}