計算導論とプログラム設計の基礎の復習ガイド

觀前提示#

本文中所有的代碼都不保證可靠性，僅為一個便於理解的例子，如出現問題，本人概不負責，也請大家指正。

簡介#

本文簡單地梳理了計導中的知識。

計算機程式設計語言#

定義：用於書寫計算機程式的語言，用於表達和描述要加工的數據以及求解問題的步驟和過程。是根據預先定義的規則（語法）、由一個有限字母表上的字符構成的字符串的總體。

計算模型#

圖靈機
1. 組成
  1. 一個無限長的紙帶
  2. 一個讀寫頭
  3. 內部狀態
  4. 一個程序，用於對這個盒子進行控制
2. 原理
  1. 根據程序的命令以及它的內部狀態進行磁帶的讀寫、移動，直至得到最後的結果。
自動機 (有限狀態自動機)
1. 組成
  1. 一個有限狀態控制器
  2. 一個讀頭
  3. 一條寫有字符的輸入帶
2. 工作原理
  1. 讀頭在輸入帶上從左向右移動，每當讀頭從帶上讀到一個字符時，便引起控制器狀態的改變，同時讀頭右移一個符號的位置
3. 狀態轉移圖
  1. 點：表示一種狀態
  2. 邊：表示一種轉移關係

C 語言（劃重點）#

語法#

1. 定義#

變量定義
C 中常見的變量有以下幾種

int a;
long long b;
char c;
float b;
double e;

函數定義

return_type function_name( parameter list )
{
   body of the function
}

數組定義

一維數組

type arrayName[arraysize];

多維數組

type arrayName[arraysize1][..]..[..][arraysizen];

指針定義

type *var-name;

type 是 var-name 所指向的類型

2. 輸入輸出#

輸入

int scanf(const char *format, ...);
char *gets(char *s);
char getchar(void);

scanf()是格式化輸入，
gets()能讀入一整行的字符，
getcchar()能讀入單獨的一個字符

輸出

int printf(const char *format, ...);
int puts(const char *s);
int putchar(int c);

與上面類似
printf() 是格式化輸出，
puts() 可以輸出一個字符串，
putchar() 可以輸出一個單獨的字符

格式化符號

字符	描述
`d`	有符號十進制數值 int
`u`	十進制 unsigned int
`f`	double 型輸出 10 進制定點表示
`s`	char 數組字符串
`c`	unsigned char

修飾符

字符	描述
`l`	對於整數類型，表示一個 long 尺寸的整型參數。對於浮點類型，表示一個 double 尺寸的整型參數。
`ll`	對於整數類型，表示一個 long long 尺寸的整型參數。

更多內容參考printf format string

流程控制#

判斷語句

if (...) {

} else {

}

可以沒有 else 有多個嵌套

switch

switch(...) {
    case ..:
        do some thing
        break;
    case ..:
        do some thing
        break;
    /* case的數量是任意的*/
    default: /* 可選的 */
        do some thing
}

循環

while

while(condition)
{

}

for ( init; condition; increment ) {

}

do...while

do
{

}while( condition );

運算符#

算術運算符 +-*/%
關係運算符 ==,!=,>,<,>=,<=
邏輯運算符 &&,||,!

結構體#

struct struct_name {
    type val_name_1;
    ...
    type val_name_n;
} s1;

struct struct_name s2;

typedef struct {
    type val_name_1;
    ...
    type val_name_n;
}struct_name; 

truct_name s1, s2;

一個結構體可以簡單的理解為將多個變量組合成了一個變量。
在定義結構體之後，我們相當於構造了一種新的變量類型。
我們可以用這種變量類型來定義變量。
訪問結構體中的變量需要使用 . 運算符。

指針#

指向變量的指針
指針變量存儲了另一個變量的地址。
比如

int a;
int *p = &a;

這樣 p 變量中就儲存了 a 的地址。
我們訪問一個變量
可以直接通過變量名訪問
也可以通過它的地址來間接訪問它的值。

指向指針的指針
我們知道指針也是一種變量
所以我們也可以定義一個指向指針的指針，形如 int **p。
我們這樣理解，p 指向了另一個指針，而那一個指針指向的是一個變量。
我們可以直接將一個指針解引用後的值當做一個完整的變量。
也就是說我們可以將 *p 當做一個整體來理解，它在一定意義上與它指向的變量的變量名等價。
指向函數的指針

return_type (*function_name)( parameter list );

請注意第一個括號不能省略，否則將會變成返回一個指針的函數
函數指針可以指向一個函數，其中 parameter list 中的參數名稱可以省略，但不能省略參數名稱。類似於函數聲明。

指向結構體的指針
指向結構體的指針與指向變量的指針類似。
問題在於 . 運算符的優先級高於 *運算符的優先級，所以我們要去元素的話 (*a).b 一定要加括號。
這樣很麻煩，所以我們有一種新的運算符 ->，則 (*a).b 等價於 a->b 這樣更加簡潔易懂。

函數傳參與返回值#

傳參為按值傳遞，在函數內函數的參數不會影響原來的值。
如果想要修改原來的值，那麼我們要傳入的值一定是要修改的值的地址。
將數組作為函數參數時，只可以省略第一維的大小，而且其他維的大小在傳參的時候都要對應，而且傳入數組時，數組內的元素可以被修改。
函數無法返回一個數組。

字符串#

在 C 語言中字符串就是字符數組。
字符串的結尾是'\0'，對應 ASCII 碼為 0
在 string.h 庫中有不少關於字符串的常用函數如 strlen (), strcpy ()。
我這裡不再展開，大家可以再網上查閱相關內容。

算法#

1. 交換兩個變量的值#

假設我們有兩個變量 a 和 b, 我們要交換他們

int temp = a;
a = b;
b = temp;

2. 排序算法#

我們主要學習一下冒泡排序
冒泡排序第 k 次循環將第 k 大（第 k 小）的數字移動到第 k 前（第 k 後）
然後在n-1輪之後就能獲得一個排好序的數組

我們設 a[i] 是需要排序的數組。

for (int i = 1; i < n; i++) {
    for (int j = 1; j <= n - i; j++) {
        if (a[j] > a[j + 1]) {
            int temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp;
        }
    }
}

3. 二分查找#

我們先考慮最簡單的二分法
假設我們有一個長度為 n 已經從小到大排序好的數組 a[i]。
我們想知道一個數 $x$ 是否在 a[i] 中出現。
這時我們可以通過二分來找這個數

int l = 0, r = n, ans = n + 1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] == x) {
        ans = mid;
        break;
    }
    if (a[mid] < x) l = mid + 1;
    else (a[mid] > x) r = mid - 1;
}

最後求出的 ans 就是 $x$ 的位置，如果沒有找到的話 ans 就是 n + 1

另一種二分為二分答案。
二分答案是指，我們對一個問題答案的值進行二分。
通過邏輯判斷得出我們真正的答案是比我們分出的值大還是小，從而修改 l,r 的值。
二分答案的條件是我們問題的答案具有單調性，
比如說，a 如果可行，那麼比 a 大的一定不可行， a 如果不可行，比 a 小的一定不可行。
這樣我們就可以進行二分了。

寫在最後#

由於篇幅有限，我很多內容不能寫得很詳細，也省略了一部分內容，很多內容還是要依靠大家自己複習。
希望大家能認真複習，祝願大家在期末中取得好成績。

計導成績更多的來自於平時的積累，要多打代碼，多刷 OJ 題，當代碼量達到一定水平之後，量變就會引發質變，會讓大家對編程有一個全新的理解。