---
tags : 大一筆記
title: 程式設計
disqus: hackmd
---

# 程式設計
::: spoiler 文章目錄
[TOC]
:::

## 零. 期中考複習

### 0-1 C語言簡介

* 前身是B語言
* C++、Java、C# 皆為C演生出來的新語言
* 編譯式語言，比直譯式快
* 中階語言: (低階:適合電腦閱讀)+(高階:貼近人類語言習慣)
* 可攜性高

### 基礎架構

#include <stdio.h>
#include <stdlib.h>
int main(){
    
    system("pause");
    return 0;
}

### 跳脫字元

| Column 1 | Column 2 |
| -------- | -------- |
| \a | 響鈴 |
| \b | 調腿 |
| \f | 跳頁 |
| \n | 印出新的一行 |
| \r | 歸位的號碼 |
| \t | tab鑑 |
| \v | 垂直定位 |
| \\? | 印出問號 |
| \\' | 印出單引號 |
| \\" | 印出雙引號 |

### 變數型態

| Column 1 | Column 2 |
| -------- | -------- |
| char | 字元 |
| int | 整數 |
| long | 長整數 |
| short | 短整數 |
| float | 單精度浮點數 |
| double | 倍精度浮點數 |

### 易混淆or易忘的
1-1. a++ 會先執行整個敘述後，再將a 的值加1
1-2. ++a 則是先把a 的值加1後，再執行整個敘述

2.

num1>num2 ? larger=num1 : larger=num2;

3-1. **%10.3f**:字元寬度為10(包含小數點)，小數點後顯示3位數，不足的部份會由空白字元補上
3-2. **%-10.3f**: 加上負號-->像左對齊

4.

int a;
switch(a){
    case 1 ... 6:
        blahblahblah;
        break;
    case 7 ... 9:
        blahblahblah;
        break;
    default:
        break;
}

## 一. 程式輸入輸出與常用程式設計技巧

### 1-1 不固定長度的資料輸入

::: info
輸入一行英文，將非英文字母轉成空白字元，所有字母改為小寫，輸出每個單字，一行一個。
:::

| 函式或類別 |所需標頭檔|
| -------- | -------- |
| getline函式| #include<string> |
|stringstream類別 | #include<sstream>
|isalpha函式 | #include<cctype> |
|tolower函式 | #include<cctype> |

#include<iostream>
#include<string>
#include<sstream>
#include<cctype>

using namespace std;

int main(){
    string s,tmp;
    while(getline(cin,s)){
        for(int i=0; i<s.length(); i++){
            if(isalpha(s[i])){
                s[i]=tolower(s[i]);
            }else{
                s[i]=' ';
            }
        }
        stringstream ss;
        ss << s; //將s放入ss
               
        // 18~19 -> stringstream ss(s);

        while(ss>>tmp){
            //將ss輸入到字串tmp，並利用空白字元進行字串切割
    
            cout<<tmp<<endl;
        }
    }
    return 0;
}

### 1-2 C++純文字檔案輸入與輸出 (X)
> 太難了 我看不懂 先跳過

### 1-3 程式中定義常數

> 用#define 前置處理器

#define MAX 100
using namespace std;
int main(){
    int a[MAX];
    for(int i=0; i<MAX; i++){
        a[i]=i;
        cout<<a[i]<<" ";
    }
    return 0;
}

> 用const定義
>
> EX:
> 定義圓周率𝝅，使用acos(反餘弦函式)，輸入餘弦值-1.0， 反餘弦函式反查餘弦值-1.0的徑度，剛好是圓周率𝝅
>
>
> `const double PI = acos(-1.0);`
>
:::info
使用`#define MAX 100 `定義陣列大小與迴圈執行次數，使用`const double PI = acos(-1.0); `定義圓周率𝝅的值，顯示變數PI到螢幕
:::

| 函式或類別 |所需標頭檔|
| -------- | -------- |
| acos函式| #include<cmath> |
|setprecision 函式 | #include<iomanip> |

#include <iostream>
#include <cmath>
#include <iomanip>
#define MAX 100

using namespace std;

int main(){
    int a[MAX];
    const double PI = acos(-1.0);

    for(int i=0; i<MAX; i++){
        a[i]=i;
        cout<<a[i]<<" ";
    }
    cout<<endl;

    cout<<PI<<endl;
    cout<<setprecision(15)<<PI<<endl;    
    printf("%.15f",PI);

    return 0;
}

### 1-4 大量修改與比較資料(X)

:::danger
複習: 指標與位址 、 struct
:::

### 1-5 廣域與自動變數的差異(X)

### 1-6 位元運算(X)

## 二. 排序
### 2-1 氣泡排序(BubbleSort)

#include <iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int arr[n];
        for(int i=0; i<n; i++){
            cin>>arr[i];
        }
        for(int i=n-1; i>1; i--){
            for(int j=0;j<i; j++){
                if(arr[j]>arr[j+1]){
                    swap(arr[j],arr[j+1]);
                }
            }
        }
        for(int i=0; i<n; i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

### 2-2 插入排序(InsertionSort)

#include <iostream>
using namespace std;
int main(){
    int n;
    int insert;
    while(cin>>n){
        int arr[n];
        for(int i=0; i<n; i++){
            cin>>arr[i];
        }
        int j;
        for(int i=1; i<n; i++){
            insert = arr[i];
            for(j=i-1; j>=0; j--){
                if(insert < arr[j]){
                    arr[j+1]=arr[j];
                }
                else{
                    break;
                }
            }
            arr[j+1]=insert;
        }
        for(int i=0; i<n; i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

### 2-3 合併排序(MergeSort) (X)

>太難了先跳過

### 2-4 快速排序(QuickSort)(X)

>太難了先跳過

### 2-5 各種排序演算法的比較

| 演算法 | 氣泡排序 | 插入排序 | 合併排序 | 快速排序 |
| -------- | -------- | -------- |-------- | -------- |
| 平均演算法效率 |$O(n^2)$ | $O(n^2)$ |$O(nlog(n))$ | $O(nlog(n))$ |
| 最差情況演算法效率 | $O(n^2)$ | $O(n^2)$ |$O(nlog(n))$ | $O(n^2)$ |
| 記憶體空間使用量 | $O(1)$ | $O(1)$ |$O(n)$ | $O(log(n))$ |

### 2-6 利用STL進行排序

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int j, int k){
    return (j>k); //由大到小(預設是小到大)
}
int main(){
    int arr[4]={2, 4, 3, 1};
    sort(arr, arr+4);
    for(int i=0; i<4; i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

### 2-7 多鍵值排序(X)
> 跨謀啦 怎麼這麼難
:exploding_head:

## 三. 模擬

:::info
**淘汰遊戲**
輸入n和p，有n人參加遊戲，編號1~n，每p人淘汰一人，編號1開始不淘汰，超過n就接回1繼續。
輸出最後剩下的人。
:::

#include <iostream>
using namespace std;
int main(){
    
    return 0;    
}

## 四. 貪婪(Greedy)演算法
## 五. 暴力
## 六. 分而治之與二元搜尋
## 七. 動態規劃
## 八. 線性資料結構

## 九. 樹狀結構
## 十. 圖形資料結構與圖形走訪(DFS與BFS)
## 十一. 圖形最短路徑
## 十二. 常見圖形演算法