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

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

因數

因數,又稱約數,是對於整數n,除m而"無餘數"的整數。
相對來說,稱n為該因數的倍數。
因數不限正負,可以用「因數倍數」或「倍數0 (mod 因數)」(參見同餘)來表達。
例如,(67=42)7是42的因數,寫作 742,亦是 420 (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; 
}