---
title: 基礎程式設計
tags: 資訊
---

# C++基本語法
* **英文大小寫視為不同**的文字
* **盡量不要在程式碼裡面寫中文**，有時候會出錯。
* 有些**特定單字不能使用**，因為**被設為常用函數**，如**max**
可以打成**maxx**
* 將程式碼**放入{ }中**，就會**由上到下執行**，一旦執行到**return 0 ;**，程式就會**立刻結束。**
* 如果程式碼**只有一行，分號；可以省略**
* 句子的結尾要有 **分號 ;** ，代表一件事結束 **endl** 代表 end line，結束一行(**換行**)
* 使用**Tab**鍵 程式碼可以**縮排** **Enter鍵** 可以**換行**
* 當程式**無法執行時，可以設定端點進行Debug除錯**
## 一、CH1 變數與運算子
1. ### d483 hello, world

#include <iostream>
using namespace std;
int main()
{
	cout << "hello, world";
	return 0;
}

3. ### ★ a001 哈囉
:::info
- 要加while() 進行重覆運算
:::

#include <iostream>
using namespace std;

int main()
{
    string s ;

    while(cin >> s)
    {
            cout << "hello, "<< s << endl;

    }
    return 0;
} 

3. ### a002 簡易加法
4. ### d489 伏林的三角地
5. ### ★ d827 買鉛筆

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        cout<< n/12*50+n%12*5<< endl;
    }
    return 0;
}

7. ### ★ d060 還要等多久啊？

#include <iostream>

using namespace std;

int main()
{
    int m;
    while(cin>> m)
    cout<< (m<=25? 25-m: 25-m+60)<< endl;
    return 0;

}

9. ### d485 我愛偶數
10. ### ★ d051 糟糕，我發燒了

#include <iomanip>
using namespace std;

int main()
{
    int f;
    while(cin>> f)
    {
       cout<< fixed << setprecision(3) <<(f-32)/1.8 << endl;


    }

    return 0;
}

12. ### ★ b004 繩子上吃草的牛

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
    double D,L,s,l;
    const double PI=2*acos(0);
    while(cin>> D>> L)
    {l=L/2;
    s=sqrt(L/2*L/2-D/2*D/2);
    printf("%.3f\n",PI*s*l);
        return 0;
    }
}

:::info
- printf .n控制小數點位數
:::
14. ### ★ d039 11044 - Searching for Nessy

### 作業
1. ### a861 1.Secure the Perimeter
:::info
- 2h+2w(*不能省略)，(h+w)*2
:::

#include <iostream>
using namespace std;

int main()
{
    int h,w;
    while(cin>>h>>w)
    cout<<(2*h+2*w)<<endl;
        return 0;
}

2. ### d226 10071 - Back to High School Physics
:::info
- v-t 圖算面積
:::

#include <iostream>
using namespace std;

int main()
{
    int v,t;
    while(cin>>v>>t)
    cout<<(v*t*2)<<endl;
        return 0;
}

3. ### d053 Big Chocolate
:::info
- 3x4巧克力需要11刀
- m-1+m*(n-1) (why?)
:::

#include <iostream>
using namespace std;

int main()
{
    int m,n;
    while(cin>>m>>n)
    cout<<(m-1+(n-1)*m)<<endl;
        return 0;
}

4. ### d277 矩陣對角線
:::info
- 3元運算子、%
對角線奇數可共用對角線交叉的花盆，偶數不共用
:::

#include <iostream>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        cout<<(n%2==1? n-1:n)<<endl;

    }
      return 0;
}

5. ### b681 1. 山洞探險
:::info
- 3元運算子
向北公式為2L-1，向南為2L
long long int
:::

#include <iostream>
using namespace std;

int main()
{
    int d,l;
    while(cin>>l)
    cout<<(l<0? -l*2:l*2-1)<<endl;
        return 0;
}

6. ### d127 二、牧場面積
:::info
- 接近正方型面積會最大
long long int
周長減掉兩個寬剩兩個長
:::

#include <iostream>
using namespace std;

long long int L;
int main()
{

    while(cin>>L)
    {
        cout <<(L/4)*((L-(L/4)*2)/2)  << endl;
    }
    return 0;
}

7. ### d461 班際籃球賽
:::info
- 場數差低於1場 所以要打至多
:::

#include <iostream>
using namespace std;

int n;
int main()
{

    while(cin>>n)
    {
        cout <<(n-1)<< endl;
    }
    return 0;
}

8. ### d096 00913 - Joana and the Odd Numbers
:::info
- long long int
有N個奇數為第(N+1)/2列
找出此列最後3個數字與第(N+1)/2列的關係
:::

cin >> t;
while(t>0)
{
    ....
    t--;
}
或
while(t--)
{
    ....
}

#include <iostream>

using namespace std;
long long int a,n;
int main()
{
        while()
        {
         
        cin>>n;
        if(n%2=1)
        (n+1)/2=a;
        cout << (9+6*a) <<endl;
        

        else()
        n/2=a;
        cout << (9+6*a) <<endl;
        }
    return 0;
}

9. ### c776 106北二1.六邊形屋瓦
:::info
- 扣掉重覆的白色屋瓦。
:::

#include <iostream>

using namespace std;

int main()
{
int m,n,x ;
while (cin >> n>> m)
{
x= n*m*3+n*2+m*1;
cout << x <<endl;
}
return 0;

}

10. ### d549 矩形中的几何
:::info
- PA^2^ + PC^2^ = PB^2^ + PD^2^ (畢氏定理)
sqrt()，需 #include <cmath>
printf小數點，需 #include <cstdio>
PA、PB、PC變數形態用long long int或double
:::

    #include<iostream>
using namespace std;

int main()
{
int T,a,b,sum,f=0;
while(cin>>T)
{
for(int i=0;i<T;i++)
{f++;sum=0;
cin>>a>>b;
for(int n=a;n<=b ;n++)
	{
	if(n%2!=0)
	sum+=n;
	}
cout<<"Case "<<f<<':'<<' '<<sum<<endl;
}
}

}

## 二、CH2 條件判斷
1. ### ★ a012 10055 - Hashmat the Brave Warrior
2. ### ★ d058 BASIC 的 SGN 函數
3. ### ★ d065三人行必有我師

#include <iostream>

using namespace std;
int a,b, c;
int main()
{
    while(cin>> a >> b >> c)
    {
        if(a>b && a>c)
        {
            cout << a << endl;
        }

        else
        {
                if(b>c)
                {
                    cout<< b <<endl;
                }
                else
                {
                    cout<< c <<endl;
                }
        }
    }
    return 0;
}

:::info
- if條件是可以重複加入
:::
4. ### ★ a053 Sagit's 計分程式

#include <iostream>

using namespace std;
int a;
int main()
{
    while(cin>> a )
    {
        if(a>=0&&a<=10)
        cout << a*6 << endl;
        else if(a<20)
        cout<< 60+(a-10)*2 <<endl;
        else if(a<=40)
        cout<< 80+(a-20) <<endl;
        else
        cout<< 100 <<endl;
    }
    return 0;
}

5. ### a006 一元二次方程式
6. ### ★ d984 棄保效應

#include <iostream>

using namespace std;
unsigned int a, b, c;
int main()
{
    while(cin>> a >> b>> c )
    {
        // a>b>c b>a>c c>a>b
        if( a>b+c || b>a&&a>c&&a+c>b || c>a&&a>b&&a+b>c)
        cout << "A" << endl;
        // b>a>c a>b>c c>b>a
        else if(b>a+c || a>b&&b>c&&b+c>a  || c>b&&b>a&&b+a>c)
        cout<<  "B" <<endl;
        else
        cout<<  "C" <<endl;
    }
    return 0;
}

7. ### ★ a004 文文的求婚
:::info
- 閏年為可被4整除且不被100整除，或可被400整除
:::

#include <iostream>

using namespace std;
unsigned int a;
int main()
{
    while(cin>>a)
    {

        if( a%4==0&&a%100!=0 ||a%400==0)
        cout << "閏年\n";
        else
        cout<<  "平年\n";
    }
    return 0;
}

### 作業
1. ### d064 ㄑㄧˊ 數？
:::info
- 比較運算子
==(等於)
!=(不等於)
:::

    #include <iostream>

using namespace std;

int main()
{
    int a ;
    while(cin>> a)
    {
        if(a%2==1)
        {
        cout << "Odd" << endl;
        }
        else
        {
        cout << "Even" << endl;
        }
    }
    return 0;
}

2. ### d066 上學去吧！
:::info
- 巢狀if
亦可將時化為分
:::

#include <iostream>

using namespace std;

int main()
{
    int a , b;
    while(cin>> a >>b)
    {
        if(60*a+b>=450&&60*a+b<1020)
        {
        cout << "At School" << endl;
        }
        else
        {
        cout << "Off School" << endl;
        }
    }
    return 0;
}

3. ### d460 山六九之旅
:::info
- 多項選擇
:::

#include <iostream>

using namespace std;

int main()
{
    int a  ;
    while(cin>> a )
    {
        if(a<6)
        {
        cout << "0" << endl;
        }
        else if(a>=6&&a<12)
        {
        cout << "590" << endl;
        }
        else if(a>=12&&a<18)
        {
        cout << "790" << endl;
        }
        else if(a>=18&&a<60)
        {
        cout << "890" << endl;
        }
        else if(a>=60)
        {
        cout << "399" << endl;
        }
    }
    return 0;
}

4. ### a273 小朋友下樓梯

#include <iostream>

using namespace std;

int main()
{
    int a , b  ;
    while(cin>> a >>b )
    {
        if(a>0&&b>0&&a%b==0){
        cout << "Ok!" << endl;
        }
        else if(a>0&&b==0){
        cout << "Impossib1e!" << endl;
        }
        else if(a==0&&b>0){
        cout << "Ok!" << endl;
        }
        else if(a==0&&b==0)
        cout << "Ok!" << endl;
        else{
        cout << "Impossib1e!" << endl;
        }
    }
    return 0;
}

5. ### b186 97七區資訊學科1(改編)
:::info
- 取餅乾/10，蛋糕/2中小的數即是贈送的盒數
:::

#include <iostream>

using namespace std;

int main()
{
int a , b ,c;
    while(cin>> a >> b >> c)
    {
        if(a/10>c/2){

        cout <<a<<" "<<"個餅乾，"<<b+(c/2)<<" "<<"盒巧克力，"<<c<<" "<<"個蛋糕。"<<endl;
        }
        else if(a/10==c/2){
        cout <<a<<" "<<"個餅乾，"<<b+(a/10)<<" "<<"盒巧克力，"<<c<<" "<<"個蛋糕。"<<endl;
        }

        else {
        cout <<a<<" "<<"個餅乾，"<<b+(a/10)<<" "<<"盒巧克力，"<<c<<" "<<"個蛋糕。"<<endl;
        }

    }
    return 0;
}

6. ### a005 Eva 的回家作業
:::info
- 判斷等差或等比數列，求第5項
while(t\-\-)
:::

#include <iostream>

using namespace std;

int main()
{
int t, a , b ,c , d ,e;
cin>>t;
    while(t--)
    {   cin>> a>> b >> c >> d >> e;
        if(c-b==b-a){

        cout <<a<<b<<c<<d<<d+b-a<<endl;
        }
        else if(c/b==b/a){
        cout <<a<<b<<c<<d<<d*(b/a)<<endl;
        }




    }
    return 0;
}

7. ### d057 11494 - Queen
:::info 垂直、水平、或對角線1步可到，其它2步可到
- abs()可求絕對值，需 #include <cstdlib>
if(x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0) break;
或 if(!x1 && !y1 && !x2 && !y2) break; 讓輸入0 0 0 0時結束。
:::

#include <iostream>
#include <cstdlib>
#include <math.h>
using namespace std;

int main()
{
    int a, b , c , d ,e ,k;
    while(cin>>a>>b>>c>>d)
    {
        if(abs(a-c)==abs(b-d))
        {
            pow(a-c,2)+pow(b-d,2)=e;
            sqrt(e)=k;
        }
        else if(a-c==0)
        {
            abs(b-d)=k;
        }
        else if(b-d==0)
        {
            abs(a-c)=k;
        }
        else
            abs(a-c)+abs(b-d)=k;
        cout<< k << endl;
    }

    return 0;
}

8. ### d095 00579 - ClockHands
:::info
- 分別計算時針與分針相對於12點的角度再相減
fabs()可求浮點數的絕對值，需 #include <cmath>``` javascript
char colon; //設一個字元變數，把冒號讀掉
while( cin >> h >> colon >> m && !(h == 0 && m == 0) )```
:::

9. ### c461 apcs 邏輯運算子(Logic Operators)
:::info
- 位元運算子&(AND)、|(OR)、(^)XOR
將a、b以位元運算子運算後和c比較
:::

10. ### d502 第三題：產品包裝
:::info
- 裝3\*3\*3產品和2\*2\*2產品剩下的空間，用來裝1\*1\*1的產品，可讓需要的包裝箱最少。

一個3\*3\*3產品裝在箱子裏，會剩37個1\*1\*1的空間。
2\*2\*2產品裝在箱子裏，會剩64-8*(b%8)個1\*1\*1的空間。
小心n或k等於0的情形
:::
## 三、CH3 重複結構
1. ### ★ d490 我也愛偶數

#include <iostream>

using namespace std;
int main()
{
    int a,b;
    while(cin>> a>> b)
    {
        int sum=0;
        for(int i=a;i<=b;i++)
        {
            if(i%2==0)
            {
                sum=sum+i;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

2. ### ★ d074 電腦教室

#include <iostream>

using namespace std;
int main()
{
    int n;
    while(cin>> n)
    {
        int maxx=-1,p;
        for(int i=0;i<n;i++)
        {
            cin >> p;
            if(p>maxx)
            {
                maxx=p;
            }
        }
        cout << maxx << endl;
    }
    return 0;
}

4. ### ★ a215 明明愛數數
:::info
- do_while迴圈
:::

 #include <iostream>

using namespace std;
int main()
{
    int m,n;
    while(cin>> n >> m)
    {
        int sum=0,cnt=0;
        do
        {
            sum+=n;
            cnt++;
            n++;
        }
        while(sum<=m);
        cout << cnt << endl;
    }
    return 0;
}

7. ### ★ a024 最大公因數(GCD)
:::info
- 暴力法(i++ v.s. i\-\-)
* [時間複雜度1](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AB%87%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95%E5%92%8C%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-b1f6908e4b80)、[時間複雜度2](https://jason-chen-1992.weebly.com/home/time-space-complexity)
- [輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm) (a=bq+r，則gcd(a, b) = gcd(b, r))
- 除錯練習
:::

#include <iostream>

using namespace std;
int main()
{
    int n,m;
    while(cin>> n >> m)
    {
        for(int i=min(n,m);i>=1;i--)
        {
            if(n%i==0&&m%i==0)
            {
            cout<< i <<endl;
            break;
            }
        }

    }
    return 0;
}

#include <iostream>

using namespace std;
int main()
{
    int a,b;
    while(cin>> a >> b)
    {
     int r;
     do{
     r=a%b;
     a=b;
     b=r;
     } while(r>0);
     cout << a << endl;


    }
    return 0;
}

8. ### ★ a149 乘乘樂
:::info
- 運算子優先順序 sum=sum*(n%10)
- 複合指定運算子
:::

#include <iostream>

using namespace std;
int main()
{
    int t;
    cin>> t;
    while(t--)
    {
     int a,sum=1;
     cin>>a;
     do
     {
        sum*=a%10;
        a/=10;
     }while(a>0);
     cout << sum << endl;


    }
    return 0;
}

10. ### ★ c418 Bert的三角形 (1)

#include <iostream>

using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        for (int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                cout<< "*" ;
            }
            cout<<endl;
        }


    }
    return 0;
}

11. ### ★c419 Bert的三角形 (2)
:::info
- 巢狀迴圈(內外圈變數不能重複)
:::

#include <iostream>

using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        for (int i=1;i<=n;i++)
        {
            for(int j=1;j<=n-i;j++)
            {
                cout<< "_" ;
            }
            for(int j=1;j<=i;j++)
            {
                cout<< "*" ;
            }
            cout<<endl;
        }


    }
    return 0;
}

---
### 作業

1. ### d498 我不說髒話
:::info
- for迴圈
:::

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        for( int i=1; i<=n; i++ )
        {
            cout << "I don't say swear words!" << endl;
        }
    }
       return 0;
}

2. ### c022 10783 - Odd Sum
:::info
- 累加
:::

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int T,a,b,f=0,sum;

while(cin>>T)
    {
    for(int i=0;i<T;i++)
    {
    f++;
    sum=0;
    cin>>a>>b;
        for(int n=a;n<=b;n++)
        {
        if(n%2!=0)
        sum+=n;
        }
    cout<<"Case "<<f<<':'<<' '<<sum<<endl;
    }

    return 0;
    }
}

3. ### d010 盈數、虧數和完全數
:::info
- 將因數累加
:::

#include <iostream>

using namespace std;

int main()
{
    int N,sum=0;
    while(cin >> N )
    {
        for(int i=1;i<N;i++)
        {
            if(N%i==0)
            {
                sum+=i;
            }
        }
        if(sum>N)
        {
            cout << "盈數" << endl;
        }
        else if (sum==N)
        {
            cout << "完全數" << endl;
        }
        else if (sum<N)
        {
            cout << "虧數" << endl;
        }
        sum=0;
    }
    return 0;
}

4. ### c299 1. 連號或不連號
:::info
- 輸入數列時，找出其最大和最小值
最大-最小+1==n，表示這個數列是連續的
:::

5. ### d186 11461 - Square Numbers
:::info
- 完全平方數的判定
:::
6. ### a248 新手訓練 ~ 陣列應用
:::info
- 不斷的將a/b的餘數*10之後再除以b
:::

#include<iostream>
using namespace std;
 
int main()
{
        int a,b,N;
        while(cin>>a>>b>>N)
        {
                cout<<a/b<<'.';
                a%=b;
                for(int i=N;i>0;i--)
                {
                        a*=10;
                        cout<<a/b;
                        a%=b;
                }
                cout<<endl;
        }      
        return 0;
}

7. ### a038 數字翻轉
:::info
- while
不斷取個位數加入翻轉數字
:::

#include<iostream>
using namespace std;

int main()
{
	int e;
	while( cin >> e )
	{
		int abcde = 0;
		while( e )
		{
			abcde *= 10;
			abcde += e % 10;
			e /= 10;
		}
		cout << abcde << endl;
	}
	return 0;
}

8. ### a536 11689 - Soda Surpler
:::info
- 每次換的汽水又可再變成空瓶子拿去換
可以換的汽水數量=所有空瓶數/c
手上空瓶=所有空瓶數/c+所有空瓶數%c
:::

9. ### d189 11150 - Cola
:::info
- 不論開始有幾瓶，最後的剩餘狀況都只1瓶或2瓶
:::

10. ### d122 Oh! My Zero!!
:::info
- 0的數量為2和5因數個數的較小值，對n!來說2的因數個數一定會比5多
:::

11. ### c420 Bert的三角形 (3)
:::info
- 巢狀迴圈
:::

12. ### c013 00488-Triangle Wave
:::info
- 巢狀迴圈
下半部 for(k=A-1;k>0;k\-\-)
:::

13. ### b003 運算式 + - 符號設定問題
:::info
- 1+2....+n=sum，如果減一個數字m，sum會減2*m
如果k-sum為偶數，則可從1~n找出數字減掉
[解題心得](https://home.gamer.com.tw/creationDetail.php?sn=4156133)
:::
<br />

## 四、CH4 陣列

1. ### ★ d212 東東爬階梯
:::info
- 一維陣列
- DP
- 費式數列
:::

#include <iostream>
using namespace std;

int main()
{
    int n;
    unsigned long long int f[100]={1,1}; //unsigned lon long int只能到f[92]

    for(int i=2;i<100;i++)
        f[i]=f[i-1]+f[i-2];

    while(cin >> n)
        cout << f[n] << endl;

    return 0;
}

2. ### ★ c067 Box of Bricks
:::info
- 一維陣列
:::

#include <iostream>
using namespace std;

int main()
{
    int n,Set=1;
    while(cin >> n && n>0)
    {
        int h[n],sum=0,ave,mov=0;
		
        for (int i=0;i<n;i++)
        {
            cin >> h[i];
            sum+=h[i];
        }
		
        ave=sum/n;
		
        for (int i=0;i<n;i++)
        {
            if(h[i]>ave)
            {
                mov+=(h[i]-ave);
            }
        }

        cout << "Set #" << Set++ << endl << "The minimum number of moves is " << mov << "." << endl << endl;
    }
    return 0;
}

3. ### a693 吞食天地

:::info
- 每次都重算會TLE
- S[-1]陣列除錯
:::

#include <iostream>
#include <stdio.h>
int main()
int n,m;

int main()
{
    
    while(cin>>n>>m)//輸入有幾筆測資 M行N個數字
    {

        int l,r;
        int food[n+1]={0};

        
        for(int i =1;i<=n;i++)
        {
            cin>>food[i];
            food[i]+=food[i-1];//求總飽和度
        }

        //長的飽和度減掉短的飽和度就是所求飽和差
        while(m--)
        {
            cin>>l>>r;
            cout<<food[r]-food[l-1]<<endl;
        }
    }
    return 0;
}

4. ### a020 身份證檢驗
:::info
- 以陣列將英文代號轉為數字
還有錯
:::

#include<iostream>
using namespace std;



int main()
{
    int n;
    while(cin>>n)//輸入有幾筆測資 M行N個數字
    {
        int m,sum,x=8,f[n];
        m=f[0]-55;
        while()
        {
            cin>>f[i];
            f[n]=f[i]+1;
            f[n]=f[i]*x;
            sum+=f[i];
            x=x-1;
        }


        cout<< ((m/10)+sum)%10==0?"real":"fake"<<endl;
    }
    return 0;
}

5. ### b139 NOIP2005 2.校门外的树

6. ### ★ a104 排序
:::info
- [思考排序的演算法](https://zh.wikipedia.org/wiki/十三張)
- [insertion sort1](https://kopu.chat/2017/06/22/插入排序insertion-sort/)
- [insertion sort2](http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php)
- [insertion sort3](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)
- [bubble sort](https://pjchender.blogspot.com/2017/09/bubble-sort.html)
:::

#include <iostream>
using namespace std;
unsigned int a, b, c;
int main()
{
    int n,;
    while(cin >> n )
    {
        int s[n];
        for (int i=0;i<n;i++)
        {
            cin >> s[i];
            
        }
        for(int i=1;i<n;i++)
        {
            int
        }
        
        for(int i=0;i<n;i++)
        {
           cout << s[i] <<" ";
        }
        cout<< endl;
    }

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin>>n)//測試筆數
    {
        int s[n]; //設置一個陣列
        for(int i=0;i<n;i++)

                cin>>s[i];//將數字讀入陣列


        for(int i=1;i<n;i++)
        {
            int key=s[i],j=i-1;//將要其中一個數字拉出來 向左和每個位置的數字做比較
            while(s[j]>key&&j>=0)//當前一個數字大於key時執行 但比較時不能超出自己的陣列
            {
                s[j+1]=s[j];//不能用到i j和j+1位置數字對調 j+1=i
                j--;//j再往左移動一格作比較
            }
            s[j+1]=key;//
        }
        for(int i=0;i<n;i++)
        cout<<s[i]<< " ";//輸出陣列
        cout<<endl;

    }
    return 0;
}

7. ### ★ d452 二、直線最小距離和
:::info
- 排序後求中位數，中位數與數組各數的距離和最小
- swap()
- 其它排序演算法實作
* [exchange sort](http://it-easy.tw/sorting-algorithm/)
* [selection sort1](https://openhome.cc/Gossip/AlgorithmGossip/SelectionInsertionBubble.htm)
* [selection sort2](https://kopu.chat/2017/06/20/選擇排序-selection-sort/)
:::

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int t,n;
    cin>>t;
    while(t--)//測試筆數

    {
        cin>>n;
        int s[n],sum=0; //設置一個陣列
        for(int i=0;i<n;i++)

                cin>>s[i];//將數字讀入陣列


            for(int i=1;i<n-1;i++)//因為要向右比較 所以最後一個不能向右比
            {
                int minIdx=i;//假設第一個位置的數字是最小值 這裡讀取的是位置
                for(int j=i+1;j<n;j++)
                {
                    if(s[j]<s[minIdx])//右邊的數字小於預設最小值
                        minIdx=j;//最小值換成右邊的數字
                }
                swap(s[minIdx],s[i]);//翻轉數字 最小值要到陣列的第一個位置所以s[minIdx]和s[0]互換
            }
        for(int i=0;i<n;i++)
            sum+=abs(s[n/2]-s[i]);//距離絕對值
        cout<<sum<< endl;

    }
    return 0;
}

8. ### ★ d153 六、智力测验
:::info
- 時間複雜度O(n^2^)的排序法會TLE
- (n-1)+(n-2)+….+1=n(n-1)/2=n2/2-n/2，當n很大時，如1百萬時，500,000,000,000-500,000=499,999,500,000(n/2可以忽略)
- 其它排序演算法觀念
* [merge sort](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
* [quick sort1](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php)
* [quick sort2](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR)
- 排序演算法比較
* [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
* [Comparison Sorting Algorithms](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
:::

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n,t;
    cin>>t;
    while(t--)
    {
            cin>>n;
            int s[n];
            for (int i=0;i<n;i++)

                cin >> s[i];//讀入陣列

                        
            sort(s,s+n);//不用演算過程的話可以用sort()
            cout<<(n%2==1?s[n/2]:s[n/2-1])<<endl;//奇數可以直接取中數,偶數取兩數小的
    }
    return 0;
}

9. ### d478 共同的數 - 簡易版
:::info
- 依序比較兩數列
- C++ IO加速

        ios::sync_with_stdio(false);
        cin.tie(0);

:::

10. ### ★ a694 吞食天地二
:::info
- 二維陣列
:::
11. ### a015 矩陣的翻轉
:::info
- 二維陣列
:::

12. ### d596 1. 猜九宮格裡的地雷
:::info
- 因為只有9個格子，且每個格子只有4個相鄰格子，
所以以二維陣列記錄每個格子其相鄰格子的編號最簡單
- 以一維陣列記錄格子編號是否有地雷(bool)
- 「與地雷相鄰格子」的4個鄰居都可能是地雷
- 「與地雷不相鄰格子」的4個鄰居都不是地雷
:::
### 作業

1. ### b138: NOIP2005 1.陶陶摘苹果

2. ### b127: 會議中心（Room）
:::info
費式數列
:::

3. ### a034: 二進位制轉換
:::info
- 餘數輸出由下而上倒序寫 for(int j=i-1;j>=0;j\-\-)
:::
4. ### d097: 10038 - Jolly Jumpers
- 宣告一個記錄差的陣列d(初值為0)，若兩數的差為3，則d[3]=1
- 輸入結束後，如果d[1~n-1]有0，則不是jolly jumper

5. ### d563: 等值首尾和
:::info
- 以迴圈讓prefix由前往後加，suffix由後往前加
- 如果prefix(前段和)==suffix(後段和)則答案加1，同時往前、後各加一個元素
- 如果prefix<suffix，則prefix往後加一個元素
- 如果prefix>suffix，則suffix往前加一個元素
:::
6. ### a040: 阿姆斯壯數
:::info
- pow(x,y)計算xy，需含入 cmath 標頭檔
- 以迴圈和%求n位數整數的個位、十位…，放入陣列，並計算n
- 再以迴圈將所有位數的n次方加起來，判斷是否等於此整數
:::
7. ### d123: 11063 - B2-Sequence
:::info
- 宣告一個記錄兩數和是否存在的陣列s(初值為0)
- 以兩數和當成index，如果不存在，則s[兩數和]=1
:::
8. ### d424: 00105 - The Skyline Problem
:::info
- 使用陣列紀錄每個x軸座標上的最高高度
- 輸出時注意邊界
:::
9. ### c435: MAX ! MAX ! MAX !
:::info
- 爆力解會TLE
- 往後掃描時不斷記錄最大範圍答案和最大值(一層迴圈完成)
:::
10. ### d481: 矩陣乘法
:::info
- 二維陣列
:::
11. ### a417: 螺旋矩陣
:::info
- 二維陣列
- memset將陣列歸零，memset(a,0,sizeof(a)); 需含入 cstring 標頭檔
- 逆時針即順時針的轉置矩陣
:::
12. ### b965: 第 2 題 矩陣轉換
:::info - 二維陣列
- 旋轉座標轉換
A (0,0) -> (0,2)
B (1,0) -> (0,1)
C (2,0) -> (0,0)
D (0,1) -> (1,2)
E (1,1) -> (1,1)
F (2,1) -> (1,0)
- 旋轉後的r，等於轉換前的c。
- 旋轉後的c，等於r數量(3)-r-1。
:::
13. ### a291: nAnB problem
:::info
- 使用陣列紀錄是否比較過
- 使用 scanf 和 printf 才不會TLE
:::

<br/>
## 五、CH5 字元陣列、字串

1. ### ★ a149: 乘乘樂
:::info
- 改寫為以字元陣列方式讀入
- 字串結束符號 '\0'
:::

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int T;	
    cin >> T;

    while(T--)
    {
        int product=1;
        char n[11];
		
        cin >> n;
        for (int i=0;i<strlen(n);i++)
            product*=(int)n[i]-48;
			
        cout << product << endl;
    }
    return 0;
}

2. ### a009: 解碼器

3. ### ★ d124: 3的倍数
:::info
- 3的倍數判別法：各個數字和為3的倍數
:::
4. ### a054: 電話客服中心
:::info
- 注意100000000答案為KLY
:::
[演算法筆記-字串](https://archive.is/u1lQL)

5. ### ★ a782: 4. Redundant Acronym Syndrome Syndrome
:::info
- 不能使用cin >> s
- cin.getline(s,1000)
- toupper()將字元變大寫
- strcmp()比較兩字串是否相等
- 陣列的名字代表陣列開始的位址，s=="END"的寫法，即使s為"END"也不會相等
:::

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    string line;
    while(getline(cin,line)&& line!="END")//讀入字串,在line=END時停止
    {
        int last;
        cout << (char)toupper(line[0]);//將第一個字母變成大寫,而且將scii code換成字母
        for(int i=1;i<line.size();i++)//從第二個字母開始搜索
        {
            if(line[i]==' ')//如果搜尋到空白,將後面一格變成大寫
            {
                cout << (char)toupper(line[i+1]);
                last=i+1;//紀錄大寫字母位置
            }
        }
        cout << " ";
        for(int i=last;i<line.size();i++)
            cout <<line[i];//將最後一個大寫字母到結束印出來
        cout << endl;
    }
    return 0;
}

6. ### ★ a011: 00494 - Kindergarten Counting Game
:::info
- 不能只算空的數量，字母的前一個是非字母即一個字
- 不能使用cin >> s
- cin.getline(s,1000)
- isalpha()
:::
7. ### d614: 簡易加法運算
:::info
- 讀入測試筆數T後，需以getline(cin,str)將T後的換行字元讀掉，或cin.ignore()
- 以cin.getline()或getline(cin,str)，讀入一行
- isdigit()判斷字元是否為數字
- 如果是數字，減48(0的ascii)得到數值，加前一個數字*10
- 如果不是數字，答案加上目前已經造出來的數字。
:::
8. ### ★ a022: 迴文
:::info
- string類別
- getline(cin,str)
- str.length()
- i\-\-
- str.clear()
- 將字串反轉後比較是否相等
:::
9. ### c290: APCS 2017-0304-1秘密差
:::info - string類別
- str.length()
- abs()可求絕對值，需含入 cstdlib 標頭檔
:::
10. ### ★ a130: 12015 - Google is Feeling Lucky
:::info
- 找最大值
- struct
- printf()，需含入 cstdio 標頭檔
:::

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    struct rec//結構類似陣列 可以將不同屬性同時放在一起 還可以分開比較
    {
        string name;
        int v;
    }web[10];
    //=struct rec web[10]
    int t,cs=1;
    cin>>t;
    while(t--)//測試筆數
    {
        int maxx=-1;
        for(int i=0;i<10;i++)
        {
            cin>>web[i].name>>web[i].v;//將屬性輸入結構
            if(web[i].v>maxx)//判斷點擊數大小
            maxx=web[i].v;//將最大值找出來
        }
        printf("Case #%d:\n",cs++);//測試筆數印出
        for(int i=0;i<10;i++)
        {
            if(web[i].v==maxx)
                cout<<web[i].name<<endl;//點擊數最多網址印出
        }
    }
    return 0;
}

---
### 作業

1. ### b428: 凱薩加密

2. ### a065: 提款卡密碼
:::info
- abs()可求絕對值，需含入 cstdlib 標頭檔
:::
3. ### d235: Q10929:You can say 11
:::info
- 11的倍數判別法：奇數位數字和與偶數位數字和相差為11的倍數
:::
4. ### a224: 明明愛明明
:::info
- 統計每個字母出現的次數
- 迴文的條件為：只有一個字母出現的次數是奇數或全部都是偶數
- 每筆測資統計的陣列要歸零
- isalpha()判斷字元是否為英文字母
- toupper()將字元變大寫
:::
5. ### a865: 5. Greek Numerals
:::info
- 將26個字母對應的值儲存為陣列
- #、$、3為多的字母
:::
6. ### d275: 11586 - Train Tracks
:::info
- 只要M和F數量一樣且軌道一個以上即可
- cin.ignore()
:::
7. ### c459: 2. 自戀數
:::info
- 可將N以字元陣列讀入
- strlen(N)計算其長度
- 數字字元-'0'求其數值
- pow(a,b)計算a^b^，需含入 cmath 標頭檔
- 根據進位制求出數值大小及每位數字的d次方合，比較是否相等
:::
8. ### d103: NOIP 2008 1.ISBN号码
:::info
- 數字字元-'0'求得其數值
- 計算識別碼，如果等於最後一個數字，或餘10且最後一個字元為'X'，則為正確
:::
9. ### d086: 態度之重要的證明
:::info
- toupper()將字元變大寫或tolower()將字元變小寫
- A的ASCII值為65，a的ASCII值為97
:::
10. ### a275: 字串變變變
:::info
- 使用陣列儲存兩字串各別字母出現的次數(以字母的ascii為陣列索引)
- 如果各別字母出現次數一樣，表示可經由調整順序後，讓兩字串一樣
:::
11. ### d267: 11577 - Letter Frequency
:::info
- cin.ignore()把數字後的換行字元讀掉
- isalpha()判斷字元是否為英文字母
- tolower()將字元變大寫
- 以字母的ascii為陣列索引記錄出現次數，迴圈找出頻率最高的次數，迴圈印出頻率最高的字母
:::
12. ### d671: 11716 - Digital Fortress
:::info
- cin.ignore()把數字後的換行字元讀掉
:::
13. ### c462: apcs 交錯字串 (Alternating Strings)
:::info
- 找出每一個連續大(小)寫片段的長度並將其記錄在陣列
:::

<br />

## 六、CH6 函式

1. ### ★ d171: 飛蛾撲火(二)
:::info
- 內建函式：pow、log10、floor
- logN^M^ = M*logN
:::

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n,m;
    while ( cin >> n >> m) {
        cout <<floor( log10(pow(n,m)) + 1 )<< endl;
    }
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n,m;
    while ( cin >> n >> m) {
        cout <<floor( m*(log10(n))+ 1 )<< endl;//logNM = M*logN 次方算開會超時 用數學定理處理
    }
    return 0;
}

2. ### ★ c039: 00100 - The 3n + 1 problem
:::info
- 自訂函式(先練習寫pow(n,m))
- 內建函式：swap、max、min
:::

#include <iostream>
#include <cmath>
using namespace std;
int cl(int n)
    {
        int cnt=1;
        while(n!=1)
        {
            if(n%2==1)
                n=n*3+1;
            else
                n/=2;
            cnt++;
            return cnt;
        }
    }

#include <iostream>
using namespace std;

int cl(int n)
{
    int i=1;

    while (n!=1)
    {
        if (n%2==1)
            n=3*n+1;
        else
            n=n/2;
        i++;
    }

    return i;
}

int main()
{
    int a,b,c,d;
    while(cin >> a >> b)
    {
        int ans=0;
        c=a;
        d=b;
        if(a>b)
            swap(a,b);
        
        for(int i=a;i<=b;i++) // for(int i=min(a,b);i<=max(a,b);i++)
            ans=max(ans,cl(i));
        cout << c << " " << d << " " << ans <<endl;
    }
    return 0;
}

#include <iostream>
using namespace std;

int cl(int n)//將重複的運算寫成函數庫
{
    int i=1;

    while (n!=1)
    {
        if (n%2==1)
            n=3*n+1;
        else
            n=n/2;
        i++;
    }

    return i;
}

int main()
{
    int a,b;
    while(cin >> a >> b)
    {
        int ans=0;
        for(int i=min(a,b);i<=max(a,b);i++) // 將起點和終點先經過比較確定
        
            ans=max(ans,cl(i));
        cout << a << " " << a << " " << ans <<endl;
    }
    return 0;
}

3. ### ★ c294: APCS-2016-1029-1三角形辨別
:::info
- 自定交換函式swap(傳參考呼叫)(除錯Step into)
- 使用swap讓a,b,c依小->大排序(c為最長邊)
:::
4. ### a121: 質數又來囉
:::info
- 1不是質數
:::
5. ### ★ b112: 5.高中運動會
:::info
- 多個數的最大公因數
:::
6. ### ★ a216: 數數愛明明
:::info
- 遞迴(先印出費式數列)
- long long int
- TLE(遞迴求一般項)
:::
7. ### ★ a227: 三龍杯 -> 河內之塔
:::info
- 遞迴
- scanf()、printf() 需含入 cstdio 標頭檔
- [河內塔|樂和遊戲](http://www.novelgames.com/zh-HK/tower/)
- [河內塔程式參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php)
:::
8. ### d269: 11579 - Triangle Trouble
:::info
- 排序後找連續3個邊，可構成最大三角形
- [更快的排序演算法 quick sort1](https://kopu.chat/2017/08/03/快速排序-quick-sort/)
- [quick sort2](http://www.algolist.net/Algorithms/Sorting/Quicksort)
:::
---
### 作業

1. ### d658: 11636 - Hello World!
:::info
- 以log2()求N為2的幾次方
- 以ceil()無條件進位
:::
2. ### d237: 質數合
:::info
- 以質數函式測試是否需加此數
- 不可直接輸出142913828922
:::
3. ### d117: 10924 - Prime Words
:::info
- 以質數函式測試字母值總合
:::
4. ### a623: Combination
:::info
- 將n!寫成函式，在主程式呼叫3次
:::
5. ### c002: 10696 - f91
:::info
- 遞迴
:::
6. ### d255: 11417 - GCD
:::info
- 將gcd寫成函式
:::
7. ### d693: 最小公倍數
:::info
- n個數的公倍數可以從兩兩連續求公倍數得到
- long long int
- 以遞迴求gcd
:::
8. ### c813: 11332 - Summing Digits
:::info
- 將f(x)寫成函式，不斷呼叫了式，直到n為個位數
:::
9. ### c015: 10018 - Reverse and Add
:::info
- 將數字反轉寫成函式
- 迴文的檢查為數字反轉後和原數字相等即是
:::
10. ### a263: 日期差幾天
:::info
- 判斷閏年可寫成函式
- 可算出總天數再相減
:::