搁置
这是书籍的笔记, 这本书我选择记录我做的课后习题, 并改错.
第1章 引论
书本内容
这一章讲述的确确实实是引论, 方便为以后引申出算法, 时间复杂度, 递归等概念. 没有特别值得注意的地方.
练习
1.1
1.1 编写一个程序解决选择问题. 令k=N/2. 画出表格显示你的程序对于N为不同值的运行时间.
选择问题: 有N个数, 求出第k大的数是多少.
思路一:
- 当k=1时, 即是求最小值. 这种情况一次遍历即可得出结果, 拿一个位置存放当前最小值, 与遍历值对比.
- 当k=2时, 可以按照之前的思路, 设定一个2个空间的数组, 里面装着第一小和第二小的数据. 筛选标准是大于第一个, 同时小于第二个的话就存进去, 小于第一个直接替换第一个. 也是一次遍历.
- ….
- 依照这种思路, 只需要预先设定一个[N/2]大小的数组即可. 这当然是教程中列举的一种思路.
目前想不到教材列举的1秒的算法, 所以就把上面这个思路实现一下就行了.
实现:
1#include <stdio.h>
2#define MAX_NUMBER 1000
3
4int findKthMax(const int* array, int size, int k);
5void findPlace(int* replace, int k, int target);
6void initPlace(int* replace, int k);
7
8int main(void) {
9 int array[10] = {2,1,7,8,5,4,9,10,3,6};
10 const int* p = array;
11 printf("%d", findKthMax(p, 10, 10/2));
12 return 0;
13}
14
15int findKthMax(const int* array, int size, int k){
16 int replace[k];
17 initPlace(replace, k);
18 for (int i = 0; i < size; ++i) {
19 if (*(array + i) < replace[k-1]) {
20 findPlace(replace, k, *(array+i));
21 }
22 }
23
24 return replace[k-1];
25}
26
27void findPlace(int* replace, int k, int target){
28 for (int i = 0; i < k; ++i) {
29 if(target < *(replace+i)){
30 //挪动
31 for (int j = k-1; j > i; --j) {
32 *(replace+j) = *(replace+j-1);
33 }
34 *(replace+i) = target;
35 return;
36 }
37 }
38}
39
40void initPlace(int* replace, int k){
41 for (int i = 0; i < k; ++i) {
42 *(replace+i) = MAX_NUMBER;
43 }
44}
45
1.2
1.2 编写一个程序求解字谜游戏问题
输入是由一些字母和单词的二维数组组成的, 目标是要找出字谜中的单词, 这些单词可能是水平, 垂直或沿对角线以任何方向放置的.
思考: 准备一个单词本(字符串数组), 先从第一个字母开始找, 这样一个一个匹配, 匹配到第一个字符就尝试从任意方向上去找, 看看能不能继续匹配. 由于一般来说是单词本大, 题目范围相对小, 故由字谜开始寻找单词匹配.
实现: (大概就这样吧, 还可以封装一下, 算了)
1//
2// Created by bnaod1 on 2024/11/29.
3//
4
5#include "stdio.h"
6#include "stdlib.h"
7#include "string.h"
8
9void printStrInDict(char* str);
10void initStrAndPara(char* str, int* now_i, int* now_j, int* size);
11
12//谜题及字典
13const char word_puzzle[4][4] = {
14 't', 'h', 'i', 's',
15 'w', 'a', 't', 's',
16 'o', 'a', 'h', 'g',
17 'f', 'g', 'd', 't'
18};
19
20const char* dict[4] = {
21 "this",
22 "two",
23 "fat",
24 "that"
25};
26
27int main(int argc, char **argv){
28 for (int i = 0; i < 4; ++i) {
29 for (int j = 0; j < 4; ++j) {
30 //最后一个字母的位置
31 int now_j = j;
32 int now_i = i;
33 int k = 0; //str赋值下标
34 char* str = malloc(sizeof(char)*16);
35 memset(str, 0, sizeof(char)*16);
36 *str = word_puzzle[i][j];
37
38 //只寻找字母大于等于3个的单词
39 //1.上方
40 if (i > 1){
41 while(now_i >= 0){
42 *(str+k) = word_puzzle[now_i--][j];
43 k++;
44 }
45 printStrInDict(str);
46 }
47 //2.下方
48 k = 0;
49 now_i = i;
50 memset(str, 0, sizeof(char)*16);
51 if (i < 2){
52 while(now_i < 4){
53 *(str+k) = word_puzzle[now_i++][j];
54 k++;
55 }
56 printStrInDict(str);
57 }
58
59 //3. 左边
60
61
62
63 //最后释放内存
64 free(str);
65
66 }
67 }
68 return 0;
69}
70
71
72void printStrInDict(char* str){
73 for (int i = 0; i < 4; ++i) {
74 for (int j = 0; j < 4; ++j) {
75 //下一个字母不同就退出
76 if (*(str+j) != *(dict[i]+j)){
77 break;
78 }
79
80 //3个字母及以上的单词
81 if (j > 1){
82 printf("find pattern:");
83 for (int k = 0; k <= j; ++k) {
84 printf("%c", *(str+k));
85 }
86 printf("\n");
87 }
88 }
89 }
90}
91
1.3
1.3 只使用处理I/O的PrintDigit函数, 编写一个过程以输出任意实数(可以是负的)
教材中提供的PrintDigit函数:
1void PrintOut(unsigned int N){
2 if(N >= 10){
3 PrintOut(N / 10);
4 }
5 PrintOut(N % 10);
6}
说实话不太明白这道题什么意思, 所以着重实现后面的需求.
实现: (感觉有点敷衍了)
1//
2// Created by bnaod1 on 2024/11/30.
3//
4
5#include "stdio.h"
6
7void PrintDigit(long long num);
8long long abs_m(long long x);
9
10int main(){
11 PrintDigit(-100000000000000000);
12}
13
14void PrintDigit(long long num){
15 if (num < 0) printf("-");
16
17 num = abs_m(num);
18
19 printf("%lld", num);
20
21
22}
23
24
25
26long long abs_m(long long x){
27 if (x >= 0) {
28 return x;
29 } else {
30 return -x;
31 }
32}
33
1.4
1.4 #include filename读入文件filename将其插入到include语句处. 编写一个程序, 使它读入被include语句修饰的文件并且输出这个文件
在我的理解里, 这就是一个递归.
实现: (反正大概就这样了, 没有进行测试, 同时也没有处理<>的情况)
1//
2// Created by bnaod1 on 2024/11/30.
3//
4
5#include "stdio.h"
6#include "stdlib.h"
7#include "string.h"
8
9int main4(){
10
11}
12
13void read_file(char* file_name){
14 FILE* file = NULL;
15 char buff[255];
16 file = fopen(file_name, "r");
17
18 if (file == NULL){
19 perror("open file failed");
20 exit(1);
21 }
22
23 while (fgets(buff, 255, file) != NULL){
24 char pattern[] = "#include";
25 if (strstr(buff, pattern) != NULL){
26 //寻找文件名
27 char* include_file = malloc(sizeof(char)*16);
28 memset(include_file, 0, sizeof(char)*16);
29 int k = 0;
30 char* begin = strchr(buff, '"');
31 if (*begin != '"'){
32 *(include_file+k) = *(begin+k);
33 k++;
34 }
35
36 read_file(include_file);
37
38 free(include_file);
39 }
40
41 printf("%s", buff);
42 }
43}
1.8
$2^{100}(mod 5)$是多少.
2%5=2; 4%5=4; 8%5=3; 16%5=1; 32%5=2; 64%5=4; 128%5=3; …
余数结果只与个位数有关, 而2的次方的个位数是有规律的: 2, 4, 8, 6, 2, 4, 8, 6….
所以$2^{100}(mod 5) = 6$
第2章 算法分析
书本内容
概念:
- 大O: T(N)=O(f(N)), T的增长率小于等于f的增长率(上界)
- omega: T(N)=omega(f(N)), T的增长率大于等于f的增长率(下界)
- theta: T(N)=theta(f(N)), T的增长率等于f的增长率
- 小o: T(N)=o(f(N)), T的增长率小于f的增长率
法则:
- T1 + T2 = max(O(f), O(g))
- T1 * T2 = O(f * g)
- T是k次多项式, 则T(N) = theta(N^k)
- (logN)^k=O(N)
另外关于最大子序列的问题, 后面这两个算法是非常精彩的.
算法1: 分治, 从局部最优得到全局优, 而且局部优的情况是简单的.
1static int MaxSubSum( int A[], int Left, int Right)
2 {
3 int MaxLeftSum,MaxRightSum;
4 int MaxLeftBorderSum,MaxRightBorderSum;
5 int LeftBorderSum,RightBorderSum;
6 int Center,i;
7
8 if(Left == Right)
9 {
10 if(A[Left] > 0)
11 return A[Left];
12 else
13 return 0;
14 }
15
16 Center = (Left + Right)/2;
17 MaxLeftSum = MaxSubSum(A,Left,Center);
18 MaxRightSum = MaxSubSum(A,Center+1,Right);
19
20 MaxLeftBorderSum = 0;
21 LeftBorderSum = 0;
22 for(i = Center;i >= Left;i--)
23 {
24 LeftBorderSum += A[i];
25 if(LeftBorderSum > MaxLeftBorderSum)
26 MaxLeftBorderSum = LeftBorderSum;
27 }
28
29 MaxRightBorderSum = 0;
30 RightBorderSum = 0;
31 for(i = Center+1;i <= Right;i++)
32 {
33 RightBorderSum += A[i];
34 if(RightBorderSum > MaxRightBorderSum)
35 MaxRightBorderSum = RightBorderSum;
36 }
37
38 return Max(MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum);
39 }
算法分析: T(N) = 2*T(N/2) + O(N), 将T(N/2)继续减小可以得到最终结果T(N) = NlogN. 可以通过假设$N=2^k$简化推理.
算法2: 神奇的算法(这个算法真的是人想出来的?)
1int MaxSubSequence(const int A[], int N)
2 {
3 int ThisSum,MaxSum,j;
4
5 ThisSum = MaxSum =0;
6 for(j = 0;j < N;j++)
7 {
8 ThisSum += A[j];
9
10 if(ThisSum > MaxSum)
11 MaxSum = ThisSum;
12 else if(ThisSum < 0)
13 ThisSum = 0;
14 }
15 return MaxSum;
16 }
要点:
-
else if(ThisSum < 0).当ThisSum没有了增速的同时小于0了(这个子序列对最大序列的贡献为负), ThisSum立刻置为0, 开始重新寻找下一个子序列. -
当然由于初始化和重新赋值都为0, 算法自动排除掉开头为负数的存在
-
由于上面两点的存在, 保证了下一个可能的最大子序列一定不在前一个最大子序列中间开始.
练习
2.1
数学题, 就log几个麻烦点.
$\frac{2}{N} < 37 < \sqrt{N} < N < N\log_{}{N}<N\log_{}{N^2}<N\log_{}{\log_{}{N}}<N\log^2_{}{N}<N^{1.5}<N^2<N^2\log_{}{N}<n^3<2^{\frac{N}{2}}=2^N$
2.2
a
2.3
做不到.
2.4
洛必达+归纳法即可.
2.5
想不出.
2.9
$O(N)$, $O(logN)$
2.10
很久之前的印象，这个算法是中国人发现的，秦邵九貌似是。
c. $O(N)$
2.11
有序查找，就用二分法。所以是$O(logN)$
2.12
求最小子序列和
借用大神的算法：
1int MinSubSequence(const int A[], int N)
2 {
3 int ThisSum,MinSum,j;
4
5 ThisSum = MinSum =0;
6 for(j = 0;j < N;j++)
7 {
8 ThisSum += A[j];
9
10 if(ThisSum < MinSum)
11 MinSum = ThisSum;
12 else if(ThisSum > 0)
13 ThisSum = 0;
14 }
15 return MinSum;
16 }
求最小的正子序列和
还是借助一下大神的算法，稍微进行了修改：
1int MinPositiveSubSequence(const int A[], int N)
2 {
3 int ThisSum,MinPSum,j;
4
5 ThisSum = 0;
6 MinPSum = MAX_BOUND;
7 for(j = 0;j < N;j++)
8 {
9 ThisSum += A[j];
10
11 if(ThisSum < MinPSum && ThisSum > 0)
12 MinPSum = ThisSum;
13 else if(ThisSum > MinPSum || ThisSum < 0)
14 ThisSum = A[j];
15 }
16 return MinPSum;
17 }
求最大子序列乘积
考虑这样的序列：
1-2, 2 ,3, 6, 8, 9
2-2, -3, 6, 0, 3, 21, -1
30,0,0,0,0,1
这道题就不是那么简单了。当然暴力遍历我也会。
我觉得应该存两个值，一个是最大正值，还有一个是最大负值（它有可能成为最大正值）。当然遇到0了就重新找下一个序列。最后比较返回即可。还有一种特殊情况：全0.
测试了一下，基本是没问题的，也就不深究了。
1//
2// Created by bnaod1 on 2024/12/7.
3//
4#include "stdio.h"
5
6int MaxProdSubSequence(const int A[], int N);
7
8
9int main(){
10// const int A[] = {-2, 2 ,3, 6, 8, 9};
11// const int A[] = {-2, -3, 6, 0, 3, 21, -1};
12 const int A[] = {0,1,1,0,0,0};
13 int result = MaxProdSubSequence(A, 6);
14 printf("%d",result);
15 return 0;
16}
17
18
19int MaxProdSubSequence(const int A[], int N)
20{
21 int ThisProd,MaxProd,psbMaxProd,zeroflag,j;
22
23 ThisProd = psbMaxProd = MaxProd = 1;
24 zeroflag = 0;
25 for (j = 0;j < N;j++)
26 {
27 if (zeroflag == 0 && A[j] != 0){
28 zeroflag = 1;
29 }
30
31 ThisProd *= A[j];
32 psbMaxProd *= A[j];
33
34 //ThisProd只存放当下最大的
35 if (ThisProd < 0)
36 ThisProd = 1;
37 //psbMaxProd是从头到尾一直乘的，有可能很小，但是再遇到负数即可超越
38 else if (psbMaxProd > ThisProd)
39 ThisProd = psbMaxProd;
40 else if (ThisProd > MaxProd)
41 MaxProd = ThisProd;
42 //遇到0，表示前面这段子序列该结束了
43 else if (ThisProd == 0)
44 ThisProd = psbMaxProd = 1;
45 }
46
47 //全0
48 if (zeroflag == 0)
49 return 0;
50 else
51 return MaxProd;
52}
2.16
不用递归，写出快速求幂的程序
可以参考递归的写法，我们就正向写即可。
对于求解目标$X^N$，实际上是$X^N = X^{N/2} * X^{N/2} * X^{N % 2}$。正向求解最麻烦的是何时多乘个X，可以先计算出乘X的时机。我想二进制也可以做到。
1//
2// Created by bnaod1 on 2024/12/7.
3//
4#include "stdio.h"
5#include "stdlib.h"
6#include "stdbool.h"
7
8long int Pow(long int X, unsigned int N);
9
10int main(){
11 printf("%ld", Pow(2,5));
12 return 0;
13}
14
15long int Pow(long int X, unsigned int N){
16 int i = 0;
17 long int result = X;
18 unsigned int *prodX = NULL;
19 prodX = malloc(sizeof(unsigned int) * 32);
20
21 while (true){
22 if (N == 1)
23 break;
24 *(prodX+i) = N - (N/2)*2;
25 i++;
26 N = N / 2;
27 }
28
29 for (int j = i-1; j >= 0; --j) {
30 result = result * result;
31 if (*(prodX+j) == 1)
32 result *= X;
33 }
34
35
36 free(prodX);
37
38 return result;
39}
40
41
2.17
给出用于快速取幂运算中的乘法次数的精确计算。（提示可以考虑N的二进制表示）
其实N的二进制如果是1，那么就要多一次乘法；如果是0，乘法只有一次。当然需要排除掉最后一个1（最高位的1）。N的求二进制过程与我们快速求幂的过程一一对应，这也是我上一个题的写法。
举例来说，16的二进制为10000，则需要4次乘法（0000）；31的二进制为11111，则需要8次乘法（1111）；32的二进制为100000，则需要5次乘法（00000）。所以只需要取除最高位的二进制位即可。怎么取呢？首先将N与1进行位与运算，这样高位全被置为0，低位是什么就是什么，然后右移；一直重复直到N==0，这样我们有可能是多算了一个1。
为了练习二进制位运算相关运算，我还是写一下。
1//
2// Created by bnaod1 on 2024/12/9.
3//
4#include "stdio.h"
5int prod_count(unsigned int N);
6
7int main(){
8 printf("%d", prod_count(31));
9 return 0;
10}
11
12int prod_count(unsigned int N){
13 int res = 0;
14 while (N >> 1 != 0){
15 unsigned int sign = N & 1;
16
17 if (sign == 1)
18 res += 2;
19 else
20 res += 1;
21
22 N = N >> 1;
23 }
24
25 return res;
26}
27
2.19
a.当数组中只剩一个元素或者是空数组
b.N是奇数的话，将最后一个和前一个，最后一个和第一个比较
c.循环
d.
第3章 表、栈和队列
书本内容
-
ADT：抽象数据类型是一些操作的集合。
-
表ADT，数组实现，链表实现。这个是入门的东西，很经典，但知识量不大。
-
多项式ADT。和超大数+×有点类似。
-
基数排序。基数排序是由桶排序演化来的。
桶排序：N个整数，范围1到M；那么就准备M个桶，有个整数来了就将第N个桶增1；最后顺序输出桶的序号。复杂度$O(M+N)$。
如果10个数，范围是0~1000之内；那么我们选择10个桶（装位数），并进行3趟最低位优先的桶排序就可以排完了。前面各趟排序保证了几个数进入一个桶时，它们是顺序的。
基数排序就是多趟桶排序。桶的个数为数的位数表示个数，趟数为位数。时间复杂度$O(P(N+B))$，P是趟数，N是元素个数，B是桶数。
-
链表的游标实现