NekoMio

NekoMio

telegram
github

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

观前提示#

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

简介#

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

计算机程序设计语言#

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

计算模型#

  1. 图灵机
    1. 组成
      1. 一个无限长的纸带
      2. 一个读写头
      3. 内部状态
      4. 一个程序,用于对这个盒子进行控制
    2. 原理
      1. 根据程序的命令以及它的内部状态进行磁带的读写、移动 ,直至得到最后的结果。
  2. 自动机 (有限状态自动机)
    1. 组成
      1. 一个有限状态控制器
      2. 一个读头
      3. 一条写有字符的输入带
    2. 工作原理
      1. 读头在输入带上从左向右移动,每当读头从带上读到一个字符时,便引起控制器状态的改变,同时读头右移一个符号的位置
    3. 状态转移图
      1. 点:表示一种状态
      2. 边:表示一种转移关系

C 语言 (划重点)#

语法#

1. 定义#

  1. 变量定义
    C 中常见的变量有以下几种
int a;
long long b;
char c;
float b;
double e;
  1. 函数定义
return_type function_name( parameter list )
{
   body of the function
}
  1. 数组定义

    1. 一维数组
    type arrayName[arraysize];
    
    1. 多维数组
    type arrayName[arraysize1][..]..[..][arraysizen];
    
  2. 指针定义

type *var-name;

type 是 var-name 所指向的类型

2. 输入输出#

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

scanf()是格式化输入,
gets()能读入一整行的字符,
getcchar()能读入单独的一个字符

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

与上面类似
printf() 是格式化输出,
puts() 可以输出一个字符串,
putchar() 可以输出一个单独的字符

  1. 格式化符号
字符描述
d有符号十进制数值 int
u十进制 unsigned int
fdouble 型输出 10 进制定点表示
schar 数组字符串
cunsigned char

修饰符

字符描述
l对于整数类型,表示一个 long 尺寸的整型参数。 对于浮点类型,表示一个 double 尺寸的整型参数。
ll对于整数类型,表示一个 long long 尺寸的整型参数。

更多内容参考printf format string

流程控制#

  1. 判断语句

    1. if
    if (...) {
    
    } else {
    
    }
    

    可以没有 else 有多个嵌套

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

    1. while
    while(condition)
    {
    
    }
    
    1. for
    for ( init; condition; increment ) {
    
    }
    
    1. do...while
    do
    {
    
    }while( condition );
    

运算符#

  1. 算术运算符 +-*/%
  2. 关系运算符 ==,!=,>,<,>=,<=
  3. 逻辑运算符 &&,||,!

结构体#

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. 指向变量的指针
    指针变量存储了另一个变量的地址。
    比如
int a;
int *p = &a;

这样 p 变量中就储存了 a 的地址。
我们访问一个变量
可以直接通过变量名访问
也可以通过它的地址来间接访问它的值。

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

  2. 指向函数的指针

return_type (*function_name)( parameter list );

请注意第一个括号不能省略, 否则将会变成返回一个指针的函数
函数指针可以指向一个函数,其中 parameter list 中的参数名称可以省略,但不能省略参数名称。类似于函数声明。

  1. 指向结构体的指针
    指向结构体的指针与指向变量的指针类似。
    问题在于 . 运算符的优先级高于 *运算符的优先级,所以我们要去元素的话 (*a).b 一定要加括号。
    这样很麻烦,所以我们有一种新的运算符 ->, 则 (*a).b 等价于 a->b 这样更加简洁易懂。

函数传参与返回值#

  1. 传参为按值传递,在函数内函数的参数不会影响原来的值。
  2. 如果想要修改原来的值,那么我们要传入的值一定是要修改的值的地址。
  3. 将数组作为函数参数时,只可以省略第一维的大小,而且其他维的大小在传参的时候都要对应,而且传入数组时,数组内的元素可以被修改。
  4. 函数无法返回一个数组。

字符串#

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

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。