---
# System prepended metadata

title: 基礎程式設計
tags: [資訊概論]

---

###### tags: `資訊概論`
# 基礎程式設計
 ## 一、基本語法
1. ### 變數型態
    | 常用型態 | 意義 | 範圍 |
    |:-------|:---------- |:-------|
    | int    | 整數                            |-2147483648~2147483647||
    | long long int  | 長整數      |-2^63^ ~ 2^63^-1||
    | float  | 單精度浮點數(小數) |±1.5x10^−45^ ~ ±3.4x10^38^|
    | double | 雙精度浮點數(小數) |±5.0×10^−324^ ~ ±1.7×10^308^|
    | char   | 字元      | 'A'|
    | string | 字串      | "Hello"|
    | bool   | 布林      | true、false|
EX_01：輸入三角形三邊長，以海龍公式求三角形面積。

```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    
    int a,b,c;
    long double s;
    cout<<"Please input triangle's side length"<<endl;
    cin>>a>>b>>c;
    
    s=(double)(a+b+c)/2;
    s=s*(s-a)*(s-b)*(s-c);
    s=sqrt(s);
    cout<<s<<endl;
    
    return 0;
}
```

## 二、運算子
1. ### 算數運算子
    | 算數運算子 | 意義 | 備註|
    |:-------- |:------ |:-------|
    | +        | 加    | |
    | -        | 減    | |
    | *        | 乘    | |
    | /        | 除    | |
    | %        | 取餘數 | |
    | ++       | 遞增    | i++ 即 i=i+1|
    | \-\-     | 遞減    | i\-\- 即 i=i-1|
    ``` javascript=
    int a=1,b;
    b=a++;
    b=++a;
    cout << a << " " << b;
    ``` 
    
2. ### 關係運算子
    | 關係運算子 | 意義 | 備註|
    |:-------- |:------ |:-------|
    | ==       | 等於    | =是指派，==是判斷是否相等     |
    | !=       | 不等於  |
    | >	       | 大於    |
    | >=       | 大於等於 |
    | <	       | 小於    |
    | <=	   | 小於等於 |

3. ### 邏輯運算子
    | 邏輯運算子 | 意義 | 備註|
    |:-------- |:------ |:-------|
    | &&       | and  |
    | \|\|     | or   |
    | !        | not  |


## 三、迴圈

    1. #### if 條件式語法
``` javascript
if(條件)
{
    條件「成立」時的程式碼
}
```

2. #### if~else 語法：
``` javascript
if(條件)
{
    條件「成立」時的程式碼
}
else
{
    條件「不成立」時的程式碼
}
```
3. #### 巢狀 if 語法
``` javascript
if(條件1)
{
    if(條件2)
    {
        條件1「成立」，且條件2「成立」時的程式碼
    }
    else
    {
        條件1「成立」，且條件2「不成立」時的程式碼
    }
}
else
{
    條件1「不成立」時程式碼
}
```
4. #### 多重選擇 if~else if~else 語法
``` javascript
if(條件1)
{
    條件1「成立」時程式碼區塊
}
else if(條件2)
{
    條件1「不成立」，且條件2「成立」時的程式碼
}
else if(條件3)
{
    條件1、2「不成立」，且條件3「成立」時的程式碼
}
....
else
{
    上述條件都「不成立」時的程式碼
}
```
:::info
EX_02：承EX_01，先判斷三邊長是否可以構成三角形。如果可以，求三角形面積；如果不行，輸出錯誤。

```cpp=
#include <iostream>
#include <cmath>
using namespace std;
void Function(long double a, long double b, long double c)
{
    long double s;
    s=(a+b+c)/2;
    s=s*(s-a)*(s-b)*(s-c);
    s=sqrt(s);
    cout<<s<<endl;
}
int main()
{
    
    long double a,b,c,max,min,mid;
    cin>>a>>b>>c;
    
    if((a+b>c) && (a+c>b) && (b+c>a))
        Function(a,b,c);
    else
        cout<<"error";
    return 0;
}
```
:::
:::info 
EX_03：驗證登入帳號、密碼。
```cpp=
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int main() 
{
    string acc,pwd;
    cout<< "Please input account :"<< endl;
    cin>> acc;
    cout<< "Please input password :"<< endl;
    cin>> pwd;
    
    if(acc == "aaa" && pwd == "111")
    {
        cout<< "Welcome";
    }
    else if(acc == "aaa" && pwd != "111")
    {
        cout<< "password error";
    }
    else if(acc != "aaa" && pwd == "111")
    {
        cout<< "account error";
    }
    else
    {
        cout<< "account and password error";
    }
}
:::

:::info
EX_04：將成績轉換成等級制
80以上 A，70 ~ 80 B，60 ~ 70 C，60以下 D，其它「錯誤」
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main() 
{
    int grd;
    cin>>grd;
    if(grd>100 || grd<0)
    {
        cout<< "error";
    }
    else if(grd > 79)
    {
        cout<< "A";
    }
    else if(grd > 69)
    {
        cout<< "B";
    }
    else if(grd > 59)
    {
        cout<< "C";
    }
    else
    {
        cout<< "D";
    }
}
```
:::
## 四、迴圈
1. ### for 迴圈語法
``` javascript
for(變數初值;條件判斷;改變量)
{
    程式碼
}
```
2. ### 巢狀迴圈語法
``` javascript
for(變數1初值;條件1判斷;改變量)
{
    for(變數2初值;條件2判斷;改變量)
    {
        程式碼
    }
}
```
3. ### while 迴圈語法
``` javascript
while(條件判斷)    // 條件為「真」的時候繼續執行
{
    程式碼
}
```
4. ### do..while 迴圈語法
``` javascript
do
{
    程式碼
}while(條件判斷);  // 條件為「真」的時候繼續執行
```
:mega: do while()後要如分號！
:::info
EX_05：計算1+2+...+n。
```cpp=
#include <iostream>
using namespace std;
int main()
{
    int n,sum=0;            

    cout << "請輸入n：";
    cin >> n;

    for(int i=1; i<n; i++)        
    {
        sum+=i;            
    }                   
    cout << sum;

    return 0;
}
```
:::
:::info
EX_06：印出金字塔形狀。
```cpp=
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cout<<"  ";
		for(int j = 1; j <= n-i; j++)
			cout<<" ";
		for(int k = 1 ;k <= 2*i-1; k++)
			cout<<"*";
		cout<<endl;		
	}
   return 0;
}
```
EX_06 (Bonus)：3層聖誕樹。
```cpp=
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cout<<"  ";
		for(int j = 1; j <= n-i; j++)
			cout<<" ";
		for(int k = 1 ;k <= 2*i-1; k++)
			cout<<"*";
		cout<<endl;		
	}
	for(int i = 1; i <= n; i++)
	{
		cout<<" ";
		for(int j = 1; j <= n-i; j++)
			cout<<" ";
		for(int k = 1 ;k <= 2*i+2; k++)
			cout<<"*";
		cout<<endl;		
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n-i; j++)
			cout<<" ";
		for(int k = 1 ;k <= 2*i+4; k++)
			cout<<"*";
		cout<<endl;		
	}
	
	for(int i = 1; i <= n/2; i++)
	{
		for(int j = 1; j <= (2*n+3)/3; j++)
			cout<<" ";
		for(int k = 1 ;k <= (2*n+3)/3; k++)
			cout<<"*";
		cout<<endl;		
	}
   return 0;
}
```
:::
:::info
EX_07：while 存錢買手機。
```cpp=
#include <iostream>
using namespace std;
int main()
{
	int  i=1,sum=0,money;
	while(sum<36000)
	{
		cout<< "請輸出第" << i << "個月的存款";
		cin>> money;
		sum+=money;
		i++;
	}
	cout<< "存了" << i-1 << "個月，總共"<< sum; 
}
```
:::
:::info 
EX_08：小算盤開根號。
```cpp=
#include <iostream>
using namespace std;
int main ()
{
	int n,i;
	bool sol = false;
	cin>> n;
	
	for(i = 1; i <= n; i++)
	{
		if(i*i == n)
		{
			cout<< i << endl;
			sol=true;		
			break;
		}		
	}	
	 
	 if(!sol)
		 cout<< "Cannot find any solution" << endl;
	return 0;
}
```
:::
:::info
EX_09：小算盤開根號(以二分搜尋法實作)。

P.S.
1. [科學記號表示法](http://notepad.yehyeh.net/Content/CPP/CH01/03DataType/1.php)
2. [printf](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)
```cpp=
#include <iostream>
#include <stdio.h>
using namespace std;
int main ()
{
	double lower,upper,mid,n;
	int cnt = 0;
	cin>>n;
	lower = 0;
	upper = n;
	
	while(upper - lower > 1e-13)
	{
		mid = (lower + upper)/2;
		cnt++;
		if(mid*mid > n)
			upper = mid;
		else if(mid*mid < n)
			lower = mid;
		else
			break;	
	}
	printf("經過了 %d 次運算，根號 %f 為 %.13f", cnt,n,mid);
	return 0;
}
:::
:::info
EX_10：小算盤開根號([以牛頓法實作](http://mathcenter.ck.tp.edu.tw/Resources/Ctrl/ePaper/ePaperOpenFileX.ashx?autoKey=55))。
```cpp=
#include <iostream>
#include <stdio.h>
using namespace std;
int main ()
{
	double a,n;
	int cnt = 0;
	cin>>n;
	a=n;
	
	do
	{
		a=(a*a+n)/(2*a);
		cnt++;
	}while((a*a-n) > 1e-15);
	printf("經過了 %d 次運算，根號 %f 為 %.15f", cnt,n,a);
	return 0;
}
```
:::
:::info
練習(轉換數字)
```cpp=
#include <iostream>
using namespace std;
int main()
{
    int n, m;
    while (cin >>n)
    {
        m = 0;
        while(true)
        {
            m *= 10;
            m += n%10;         
            n /=10;
            if (n==0)
            {
                break;
            }
        }
        cout << m << endl;
    }
}
```

:::

## 五、陣列
### 一維陣列、二維陣列語法
``` javascript
int arr[5];                      // 宣告一個大小為5的int陣列
arr[0]=80;                       // 陣列的索引值由0開始
arr[5]=90;                       // 索引值0~4
int arr[5] =  { 1, 3, 5, 7, 9 }; // 宣告陣列時設定初值
int arr[5] =  { 1 };             // arr[0]初值1，其餘預設為0
int arr[] = { 1, 3, 5, 7, 9 };   // 陣列大小依初值自動計算

int arr2D[4][2];                 // 宣告二維陣列(多維陣列)
int arr2D[4][2] = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
```
:::info
EX_11：大樂透電腦選號。
```cpp=
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
int main()
{
    int num[6]; 
	int t;    
	int mark[50]={0};               
    srand(5);                    

    for(int i=0; i<6; i++)       
    {
        do
        {
            t = rand()%49+1;    
        } 
		while(mark[t]==1);    
        num[i] = t;              
        mark[t] = 1; 
    }

    for(int i=0; i<6; i++) 
    {
        cout << num[i] << " ";
    }

    return 0;
}
```
:::
:::info
EX_12：求學測總級分 平均 名次。
Hint：類似bubble sort的寫法。若此位同學的總分<p位同學，名次為p+1。
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main ()
{
	int score[4][8] = {{12,13,15,10,12,0,0,0},{15,13,15,15,14,0,0,0},{14,14,12,15,13,0,0,0},{11,10,12,12,10,0,0,0}};
	for(int i=0; i<4; i++)                     
    {
        int sum=0;                      
        for(int j=0; j<5; j++)                  
        {
            sum += score[i][j];
        }
        score[i][5] = sum;
        score[i][6] = sum/5;
    }

	for(int i=0; i<4; i++)             // 對第i個人求名次
	{
    	int p=0;             // 計算成績大於第i個人的人數
   		for(int j=0; j<4; j++)         // 從頭比較每個人的總分
    	{
        	if (score[i][5] < score[j][5])
        	{
            	p++;
        	}
    	}
    	score[i][7] = p+1;          // 記錄第i個人的名次
	}
	
	cout << "座號\t國文\t英文\t數學\t自然\t社會\t總分\t平均\t名次\n";    
	for (int i=0;i<4;i++)               
    {
        cout<< i+1<<"\t";                      
        for (int j=0;j<8;j++)
        {
            cout << score[i][j] << "\t";
        }
        cout << endl;
    }

    return 0;
}
	
```
:::
## 六、函式
1. ### 自定函式宣告語法
``` javascript
回傳值的型態 函式名稱(變數型態 參數1，變數型態 參數2，...)
{
    程式碼
    return 回傳值或運算式;
}
```
:::info
EX_13 高中運動會 
      以輾轉相除法求兩數的最大公因數(寫成函式)，並用之來求4數的最大公因數。
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int gcd(int a,int b)
{
    int r;
    do
    {
        r = a % b;        // r 為 a 除以 b 的餘數
        a = b;          // 下一次的 a 為 ?
        b = r;          // 下一次的 b 為 ?
    } while (r>0); // 當 ? 不為 0 時繼續做

    return a;             // 回傳 a,b 的最大公因數，a? b? r?
                          // g=gcd(12,16) 函式除錯(Step into)
}

int main()
{
    int a=400, b=200, c=150, d=625, g;
    
    g = gcd(a, b);        // g 為 a,b 的最大公因數
    g = gcd(g, c);              // g 再和 c 求最大公因數
    g = gcd(g, d);             // g 再和 d 求最大公因數

    cout << g;
    
    return 0;    
}
	

```
:::

:::info
EX_14 (Bonus)：寫一函式可以計算n!，並以之求 $C(n,k)=\frac{n!}{(n-k)! * k!}$，例如C(4,2)=6。
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int f(int a)
{	
	int sum=1;
	int i;
    for(i=1; i<=a; i++)
    {
    	sum*=i;
	}
	return sum;
}

int main()
{
    int n,k;
    cin>> n >> k ;
	int t=n-k;
    cout <<f(n)/(f(t)*f(k));
    
    return 0;    
}
```
:::
:::info
EX_15：求費式數列第n項。

[費式數列遞迴式](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)

``` cpp=
#include <iostream>
using namespace std;

int f(int n)
{
    if(n==0)
        return 0;
    else if(n==1)
        return 1;
    else
        return f(n-1)+f(n-2);
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}
```
:::
:::info
EX_16：以遞迴改寫 EX_13 高中運動會中的gcd函式。
```cpp=
#include <iostream>
using namespace std;

int gcd(int a,int b)
{
    int r;
    do
    {
        r=a%b;
        a=b;
        b=r;
    }while(r>0);
    return a;
}
int main()
{
    int a=400, b=200, c=150, d=625, g;

    g = gcd(a, b);
    g = gcd(g, c);
    g = gcd(g, d);

    cout << g;

    return 0;
}
```

:::
:::info
EX_17：以遞迴函式計算 n 層香檳塔，總共有幾個杯子。
遞迴式 : f(n)=1　,if n==1
　　　　f(n)=？ ,if n>1

![](https://i.imgur.com/uniXdVh.jpg =100x)


```cpp=
#include <iostream>
using namespace std;
int f(int n)
{
    if(n>1)
		return (1+n)*n/2;
	else if(n == 1)
		return 1; 
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);
   
    return 0;    
}```
:::
:::info
EX_17 (Bonus)：計算 n 層「三角錐形」香檳塔，總共有幾個杯子。
( 第1層1個、2->3、3->6、4->10、5->15、第n層->？個杯子 )
[2017的世界紀錄總共杯子數量為50116](https://kknews.cc/zh-tw/food/3j4y43y.html)，疊了幾層？(6x)

![](https://i.imgur.com/Faj13v9.png =200x)
```cpp=
#include <iostream>
using namespace std;
long long int f(int n)
{
    if(n>1)
		return f(n-1)+n*(n+1)/2;
	else if(n == 1)
		return 1; 
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);
   
    return 0;    
}
```
:::





