计算导论与程序设计基础复习指北

观前提示

本文中所有的代码都不保证可靠性，仅为一个便于理解的例子，如出现问题，本人概不负责，也请大家指正。

简介

本文简单的梳理了计导中的知识。

计算机程序设计语言

定义: 用于书写计算机程序的语言，用于表达和描述要加工的数据以及求解问题的步骤和过程。是根据预先定义的规则（语法）、由一个有限字母表上的字符构成的字符串的总体。

计算模型

图灵机
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
}

数组定义

一维数组
1
type arrayName[arraysize];

多维数组

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

指针定义
1
type *var-name;
type 是var-name所指向的类型

2. 输入输出

输入
1
2
3
int scanf(const char *format, ...);
char *gets(char *s);
char getchar(void);
scanf()是格式化输入,
gets()能读入一整行的字符,
getcchar()能读入单独的一个字符
输出
1
2
3
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
1
2
3
4
5
if (...) {

} else {

}
可以没有else 有多个嵌套

switch

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

循环

while
1
2
3
4
while(condition)
{

}

for

1
2
3

for ( init; condition; increment ) {

}

do…while
1
2
3
4
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;

一个结构体可以简单的理解为将多个变量组合成了一个变量。
在定义结构体之后，我们相当于构造了一种新的变量类型。
我们可以用这种变量类型来定义变量。
访问结构体中的变量需要使用 . 运算符。

指针

指向变量的指针
指针变量存储了另一个变量的地址。
比如
1
2
int a;
int *p = &a;
这样 p 变量中就储存了 a 的地址。
我们访问一个变量
可以直接通过变量名访问
也可以通过它的地址来间接访问它的值。

指向指针的指针
我们知道指针也是一种变量
所以我们也可以定义一个指向指针的指针，形如 int **p。
我们这样理解，p 指向了另一个指针，而那一个指针指向的是一个变量。
我们可以直接将一个指针解引用后的值当做一个完整的变量。
也就是说我们可以将 *p 当做一个整体来理解，它在一定意义上与它指向的变量的变量名等价。

指向函数的指针
1
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, 我们要交换他们

1
2
3

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题，当代码量达到一定水平之后，量变就会引发质变，会让大家对编程有一个全新的理解。