伊のspace～芳香精油＊美容保養＊程式設計

民國100年經濟部事業招考題目

因數

因數，又稱約數，是對於整數n，除m而"無餘數"的整數。
相對來說，稱n為該因數的倍數。
因數不限正負，可以用「因數|倍數」或「倍數≡0 (mod 因數)」（參見同餘）來表達。
例如，(6×7=42)7是42的因數，寫作 7|42，亦是 42≡0 (mod 7)。
亦稱“因子”。一整數被另一整數整除，後者即是前者的因數，如1,2,4都為8的因數。

舉例：
18的因數：1,2,3,6,9,18
24的因數：1,2,3,4,6,8,12,24

公因數

在數學中，公約數，亦稱“公因數”。如果一個數同時是幾個數的約數，稱這個數為它們的“公約數”；公約數中最大的稱為最大公約數(最大公因數)。

舉例：
18跟24的公因數：1,2,3,6
18跟24的最大公因數：6，最大公因數 數學表示法：(18,24)=6

互質

兩個正整數只有一個公因數1時，它們的關係叫做互質。
舉例：
4的因數：1,2,4
9的因數：1,3,9
則4和9互質，(4,9)=1。

最大公因數的求法

1.短除法

(24,36,42)=2*3=6

2.標準分解式法


3.輾轉相除法


舉例：x=42,y=75 求x,y最大公因數
1. 以較大的數(75)為被除數，較小的數(42)為除數，75 / 42 = 1 餘 33
2. 前一步驟的除數為被除數，餘數為除數，42 / 33 = 1 餘 9
3. 33 / 9 = 3 餘 6
4. 9 / 6 = 1 餘 3
5. 6 / 3 = 2 餘 0，除數 3 即可為最大公因數

由以上敘述可得遞迴function：(了解原理後，寫出程式就不是問題)

遞迴的寫法：

int gcd(int x,int y) {
    if (y == 0)  /* 餘 0，除數 x 即為最大公因數 */
        return x;
    else
        return gcd(y, x % y);  /* 前一步驟的除數為被除數，餘數為除數 */
}

#include "stdafx.h"
#include < stdio.h >
#include < cstdlib >

int gcd(int x,int y);

int _tmain(int argc, _TCHAR* argv[])
{
    int xin=42,yin=75;
    int x,y;
    if (xin < yin) {
        x=yin;
        y=xin;
    } else {
        x=xin;
        y=yin;
    }
    printf("GCD=%d \n", gcd(x,y) );
    system("pause");
	return 0;
}
int gcd(int x,int y) {
    if (y == 0)  /* 餘 0，除數 x 即為最大公因數 */
        return x;
    else
        return gcd(y, x % y);  /* 前一步驟的除數為被除數，餘數為除數 */
}

迴圈的寫法：

int gcd2(int x,int y) {
    int temp;
    while(y != 0) {	/* 餘 0，除數 x 即為最大公因數 */
        temp=x % y;
        x=y;		/* 前一步驟的除數為被除數 */
        y=temp;	    /* 餘數為除數 */
    }
    return x;
}

#include "stdafx.h"
#include < stdio.h >
#include < cstdlib >

int gcd2(int x,int y);

int _tmain(int argc, _TCHAR* argv[])
{
    int xin=42,yin=75;
    int x,y;
    if (xin < yin) {
        x=yin;
        y=xin;
    } else {
        x=xin;
        y=yin;
    }
    printf("GCD=%d \n", gcd2(x,y) );
    system("pause");
	return 0;
}
int gcd2(int x,int y) {
    int temp;
    while(y != 0) {	/* 餘 0，除數 x 即為最大公因數 */
        temp=x % y;
        x=y;		/* 前一步驟的除數為被除數 */
        y=temp;	    /* 餘數為除數 */
    }
    return x;
}

C++實做遞迴

#include < iostream > 
using namespace std; 

int gcd(int, int); 

int main() { 
    int m = 0;
    int n = 0; 

    cout << "輸入兩數："; 
    cin >> m >> n; 

    cout << "GCD: " 
         << gcd(m, n) << endl; 

    return 0; 
} 

int gcd(int m, int n) { 
    if(n == 0) 
        return m; 
    else 
        return gcd(n, m % n); 
}

C++實做迴圈

#include < iostream > 
using namespace std; 

int gcd(int, int); 

int main() { 
    int m = 0;
    int n = 0; 

    cout << "輸入兩數："; 
    cin >> m >> n; 

    cout << "GCD: " 
         << gcd(m, n) << endl; 

    return 0; 
} 

int gcd(int m, int n) { 
    int r = 0; 

    while(n != 0) { 
        r = m % n; 
        m = n; 
        n = r; 
    } 

    return m; 
}