---
# System prepended metadata

title: 期末報告

---

期末報告
===
# 程式設計(使用C++)
## EX_01：輸入三角形三邊長，以海龍公式求三角形面積。先輸出s看看是否正確。(整數除法、浮點數除法)(先乘除後加減)
### 預設:
```cpp=
#include <iostream>
.......              // 含入 cmath 標頭檔，才可使用sqrt

using namespace std;
int main()
{
    ........         // 宣告 a,b,c 三邊長變數為整數型態
    double s, area;

    ........         // 以cout輸出提示字串
    ........         // 以cin輸入邊長變數

    s = ........
    area = ........
    cout << "三角形面積為 " << area << endl; // a=5,b=6,c=7,area=14.6969
    
    return 0;
}
```
### Ex_1 Ans:
```cpp=

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a,b,c;
    double s,area;
    cout << "請輸入三角形的三邊長:" << endl;
    cin >> a >> b >> c;
    
    s=(double)(a+b+c)/2;
    area=sqrt(s*(s-a)*(s-b)*(s-c));
    cout << "三角形面積為" << area << endl;

    return 0;
}
```
* 1.整數運算會去掉小數 
* 2.乘號不能省

## Ex_2：承EX_01，先判斷三邊長是否可以構成三角形。如果可以，求三角形面積；如果不行，輸出錯誤。
* 每邊長要大於0，且任兩邊之和要大於第三邊。
### 預設:
```cpp=

int main()
{
    ........                                           // 宣告 a,b,c 三邊長變數為整數型態
    double s, area;

    cout << "請輸入三邊長：";
    cin >> a >> b >> c;

    if ( a > 0 && ........ && a + b > c && ........ )  // if else 後不用加分號
    {
        s = ........
        area = ........
        cout << "三角形面積為 " << area << endl;
    }
    else                                               // 不用加分號
    {
        cout << "不能構成三角形";    
    }
    
    return 0;
}
```
### Ex_2 Ans:
```cpp=

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a,b,c;
    double s,area;
    cout << "請輸入三角形的三邊長:" << endl;
    cin >> a >> b >> c;
    if( a>0 && b>0 && c>0 && a+b>c && a+c>b && b+c>a )
    {
        s=(double)(a+b+c)/2;
    area=sqrt(s*(s-a)*(s-b)*(s-c));
    cout << "三角形面積為" << area << endl;

    }
    else
    {
        cout << "不能構成三角形";
    }

    return 0;
}
```
* if和else後方不用打分號


## Ex_3:驗證登入帳號、密碼
```cpp=
int main()
{
    string user,pwd;

    cout << "請輸入帳號：";
    cin >> user;
    ........      // 讓使用者輸入密碼
    ........

    if (user=="admin" && ........)
    {
        cout << "Welcome";
    }
    else
    {
        ........  // 不等於!=
        {
            cout << "帳號錯誤";
        }
        ........
        {
            cout << "密碼錯誤";
        }
    }
    // Q：帳號、密碼都錯時會顯示？如何顯示帳號錯誤，密碼錯誤？

    return 0;
}    
```
### Ex_3 Ans
```cpp=
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    string user,pwd;

    cout << "請輸入帳號:";
    cin >> user;
    cout << "請輸入密碼:";
    cin >> pwd;
    if( user=="500207" && pwd=="030030" )
    {
        cout << "Welcome";
    }
    else
    {
        if(user!="500207" && pwd!="030030")
        {
            cout << "帳號及密碼錯誤";
        }
        else
        {
            if(user!="500207")
        {
            cout << "帳號錯誤";
        }
        if(pwd!="030030")
        {
            cout << "密碼錯誤";
        }
        }
    };
    return 0;
}
```


## Ex_5:印出 10 個 “hello”
```cpp=
int main()
{
    int i;                  // 區域變數 vs. 區塊變數 for (int i=1;i<=10;i++)    
    for (i=1;i<=10;i=i+1)   // 讓 i 從 1~10。for()後面不可加分號
    {                        
        cout << "hello ";
    }                       
    cout << i;              // Q：i 會顯示多少？
}

/*
i=i+1
i+=1
i++
*/
```



## Ex_6:聖誕樹
```cpp=
int main()
{
    int n;
    cout << "請輸入n：";
    cin >> n;

    for ........                      // 總共n列
    {
        for ........                  // 每列印星號之前先印「空白」
        {
            cout << " ";
        }

        for (int j=1;j<= .... ;j++)   // 星號的數量和列編號有關(1,3,5,7,9...)
        {
            cout << "*";
        }
        ........                      // 印完一列要換行
    }

    return 0;
}
```

## Ex_6
```cpp=
#include <iostream>

using namespace std;

int main()
{
    int n,sum=1;
        for(int j=1;j<=2*i-1;j++)
        {
            cout << "*";
        }
        cout << endl;
    }
    for(int i=1;i<=n/2;i++)
    {
        for(int j=1;j<=2*n/3;j++)
        {
            cout << " ";
        }

        for(int j=1;j<=2*n/3;j++)
        {
            cout << "*";
        }
        cout << endl;
    }
    return 0;
}
```

## Ex_7:while 存錢買手機
```cpp=
int main()
{
    int i=1, ......... ;

    while ........
    {
        cout << "請輸入第 " << i << " 個月的存款： ";
        cin >> money;
        ........          // 把 money 加到 sum
        ........          // i+1
    }
    cout << "存了 " << .... << " 個月，總共 " << sum;

    return 0;
}
```

### Ex_7 Ans
```cpp=
#include <iostream>

using namespace std;

int main()
{
    int i=1,sum=0,money;

    while(sum<100000)
    {
        cout << "輸入第" << i << "個月的存款:";
        cin >> money;
        sum+=money;
        i++;
    }
    cout << "存了" << i-1 << "個月";
    return 0;

```
## Ex_8:小算盤開根號(以二分搜尋法實作)
```cpp=
int main()
{
    int n;
    bool sol=false;

    cin >> n;

    for ........         // 只需檢測到 n/2
    {
        if ........      // 如果i的平方等於n
        {
            cout << i;
            ........     // sol 設為 true，表示找到根
            ........     // 跳出迴圈
        }
    }

    if ........          // 沒有解，! -> not
    {
        cout << "只能求完全平方數的平方根！";
    }

    return 0;
}    

```



### Ex_8 Ans
```cpp=
#include <iostream>
#include <cstdio>

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-13);

    printf("經過了 %d 次運算，根號 %f 為 %.13f", cnt,n,a);

    return 0;
}

```

## Ex_9:小算盤開根號(以二分搜尋法實作)
```cpp=
int main()
{
    double n,lower,upper,mid;
    // Q2
 
    cin >> n;
    lower = 1;
    upper = n-1;
 
    while ........              // 上下界限的差 > 10^-13(數學寫法)，就繼續逼進
    {
        mid = ........          // mid 為上下界限的中間
        // Q2

        if ( mid*mid > n )      // 如果中間數的平方 > n，解在lower~mid間
            ........            // 將上限調為 mid
        else if ........        // 如果中間數的平方 < n，解在mid~upper間
            ........            // 將下限調為 mid
        else
            break;
    }
    printf("%.13f",mid);        // 需含入標頭檔 cstdio
    
    return 0;
}

Q1：2不行？
Q2：新增一個整數變數cnt，記錄總共做了幾次運算得解
printf("經過了 %d 次運算，根號 %f 為 %.13f", cnt,n,mid);
```
### EX_9 Ans
```cpp=
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n=5000000;

    for (int i=2;i<=n;i++)
    {
        bool prime=true;
        for (int j=2;j<sqrt(i);j++)
        {
            if (i%j==0)
            {
                prime==false;
                break;
            }
        }
        //if (prime)
            //cout << i << " ";
    }
    return 0;
}
```
## Ex_10 埃拉托斯特尼篩法(課本p3-5)，求1億以內的質數
```cpp=
int main()
{
    int n=100000000;
    bool isPrime[100000001];             // 區域變數只能到200萬左右，改為全域變數。   
    fill(isPrime,isPrime+n+1,1);         // 全部先設為1(true)，假設都是質數。需含入algorithm標頭檔
    isPrime[1]=false;                    // 1不為質數

    for (int i=2;i<=sqrt(n);i++)         // 檢查到<=√n即可
        if ........                      // 如果i是質數
            for ........                 // 如果i是質數，則篩掉它的倍數。(從i^2開始，每次+i)
                isPrime[....]=....;      // i的倍數不為質數

    for (int i=1;i<=n;i++)
        if (isPrime[i])
            cout << i << " ";
    return 0;
}
```

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

bool isPrime[100000001];
int main()
{
    int n=100;
    fill(isPrime,isPrime+n+1,1);
    isPrime[1]=false;

    for (int i=2;i<=sqrt(n);i++)
        if (isPrime[i])
            for(int j=i*i;j<=n;j+=i)
                isPrime[j]=false;
    for (int i=1;i<=n;i++)
        if (isPrime[i])
            cout << i << " ";
    return 0;
}
```
## Ex_11_1:大樂透電腦選號
```cpp=
int main()
{
    ........                     // 宣告一個大小6的num陣列
    srand(5);                    // 設定亂數種子。srand(time(NULL)); 需含入標頭檔 ctime

    for ........                 // 陣列的索引值由0開始，所以i初值要設為0
    {
        num[....] = rand()....;  // 隨機產生1~49間的數，需含入標頭檔 cstdlib
    }

    for ........                 // 印出陣列裏的亂數
    {
        cout << num[....] << " ";
    }

    return 0;
}
```


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

int dc(int b,int p,int m)
{
    if (p==1)
        return b%m;
    else
    {
        int half=dc(b,p/2,m);
        if (p%2==0)
            return half*half%m;
        else
            return half*half*b%m;
    }
}
int main()
{
    int b,p,m;
    while(cin >> b >> p >> m)
        cout << dc(b,p,m) << endl;
    return 0;
}
```

## Ex_11_2:大樂透電腦選號(解決數字重覆的問題)
```cpp=
int main()
{
    int num[6];                 // 宣告一個大小6的num陣列
    int mark[50]={0};           // 標記陣列的初值=0。50個空間，陣列索引值為0~49
    int t;
    srand(5);                   // 設定亂數種子。srand(time(NULL)); 需含入標頭檔 ctime

    for (int i=0;i<6;i++)       // 陣列的索引值由0開始，所以i初值為0
    {
        do
        {
            t = rand()%49+1;    // 隨機產生1~49間的數，暫放於t
        } while ........        // 如果mark陣列第t個位子為1，代表亂數重覆，再產生另一個亂數
        ........                // 將產生的不重覆亂數記錄在num陣列
        ........                // 將mark陣列第t個位子的值設為1，表示產生過t這個數字
    }

    for (int i=0;i<6;i++)       // 印出陣列裏的亂數
    {
        cout << num[i] << " ";
    }

    return 0;
}


Q1：產生亂數後，檢查此數字是否重覆，如果重覆再產生一次，下列程式碼想法有何漏洞？
    for(int i=0;i<6;i++)
    {
        t=rand()%49+1;
        for (int j=0;j<i;j++)
            if (t==num[j])
                t=rand()%49+1;
        num[i]=t;
    }
    
Q2：t=rand()%5+1會發生什麼狀況？(陣列除錯練習)    
```



### Ex_11_2 Ans
```cpp=
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
    int num[6],t;
    int mark[50]={0};
    srand(time(NULL));

    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<5;i++)
        {
            for(int j=0;j<5-i;j++)
            {
                if(num[j]>num[j+1])
                {
                    t=num[j];
                    num[j]=num[j+1];
                    num[j+1]=t;
                }
            }
        }

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

```

## Ex_12:求學測總級分和平均
```cpp=
int main()
{
    int score[4][7] = {{12,13,15,10,12,0,0},{15,13,15,15,14,0,0},{14,14,12,15,13,0,0},{11,10,12,12,10,0,0}},sum=0;

    for ........                      // 4個人，列
    {
        ........                      // 計算每人總分之前，sum 要先歸0
        for ........                  // 5科，欄
        {
            sum += score[....][....];
        }
        score[....][5] = sum;
        score[....][....] = sum/5;
    }

    cout << "座號\t國文\t英文\t數學\t自然\t社會\t總分\t平均\n";
    for (int i=0;i<4;i++)               
    {
        ........                      // 先印出座號
        for (int j=0;j<....;j++)
        {
            cout << score[i][j] << "\t";
        }
        cout << endl;
    }

    return 0;
}
```



### Ex_12 Ans

```cpp=
#include <iostream>

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++)
    {
        int p=0;

        for(int j=0;j<4;j++)
        {
            if(score[i][5] < score[j][5])p++;
        }
        score[i][7]=p+1;
    }

    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;
}
```


## EX_13：ZeroJudge b112: 5. 高中運動會。
#### 以輾轉相除法求兩數的最大公因數(寫成函式)，並用之來求4數的最大公因數
```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;
}
```

### Ex_13 Ans
```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;
}
```









## 演算法
### EX_06_2：ZeroJudge c129: 00572 - Oil Deposits
```cpp=
#include <iostream>

using namespace std;

int visited[100][100]={0};
char mp[100][100];
int r,c;

void dfs(int i,int j)
{
    if(i<0 || i>=r || j<0 || j>=c || visited[i][j]==1 || mp[i][j]=='*')
       return;
    visited[i][j]=1;

    dfs(i-1,j-1);
    dfs(i-1,j);
    dfs(i-1,j+1);
    dfs(i,j-1);
    dfs(i,j+1);
    dfs(i+1,j-1);
    dfs(i+1,j);
    dfs(i+1,j+1);
}

int main()
{
    while(cin >> r >> c && r!=0 && c!=0)
    {
        int cnt=0;

        for(int i=0;i<r;i++)
            for(int j=0;j<c;j++)
                {
                    cin >> mp[i][j];
                    visited[i][j]=0;
                }


        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(mp[i][j]=='@' && visited[i][j]==0)
                {
                    dfs(i,j);
                    cnt++;
                }
            }
        }

        cout << cnt << endl;
    }
    return 0;
}
```
* ???????????????????????