第一章枚举
- 例题一完美立方
- 例题二生理周期
- 例题三称硬币
- 例题四熄灯问题
第二章递归（一）
- 例题一求阶乘
- 例题二汉诺塔
- 例题三 n皇后问题
- 例题四逆波兰表达式
补充笔记（from theCherno)
第三章递归（二）
- 例题一求表达式的值
- 例题二爬台阶
- 例题三算24
第四章二分算法
- 例题一求方程的根
- 例题二找出一对数字
- 例题三疯牛
第五章分治
- 归并排序
- 快速排序
第六章动态规划
- 数字三角形

学会程序和算法，走遍天下都不怕！

——郭炜

第一章枚举

枚举是一种基于逐个尝试答案的一种问题求解策略。

例题一完美立方

题目：形如a3= b3 + c3 + d3的等式被称为完美立方等式。例如123= 63 + 83 + 103 。编写一个程序，对任给的正整数N(N≤100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 +c3 + d3，其中a,b,c,d 大于 1, 小于等于N，且b<=c<=d。

我写的：

#include <iostream>
#include <cmath>using namespace std;bool test(int a,int b,int c,int d);int main()
{cout << "please enter number N" << endl;int N;cin >> N;int a, b, c, d;for(a=1;a<=N;a++){for(b=1;b<=N;b++){for(c=b;c<=N;c++){for(d=c;d<=N;d++){if(test(a,b,c,d)){printf("Cube = %d, Triple = (%d,%d,%d)\n", a,b,c,d);}else{continue;}}}}}
}bool test(int a,int b,int c,int d)
{if(pow(a,3) == pow(b,3)+pow(c,3)+pow(d,3)){return 1;}else{return 0;}
}

标答：

#include <iostream>
#include <cstdio>using namespace std;int main()
{int N;scanf("%d", &N);for (int a = 2; a <= N; ++a)for (int b = 2; b < a; ++b)for (int c = b; c < a; ++c)for (int d = c; d < a; ++d)if (a * a * a == b * b * b + c * c * c + d * d * d)printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);return 0;
}

原来是不需要打这么多大括号的
但是没理解为什么a b c 都要小于a
有的地方用C语言风格输出稍微便捷些
VScode里面可以右键格式化代码

例题二生理周期

题目：人有体力、情商、智商的高峰日子，它们分别每隔23天、 28天和33天出现一次。对于每个人，我们想知道何时三个高峰落在同一天。给定三个高峰出现的日子p,e和i（不一定是第一次高峰出现的日子） ,再给定另一个指定的日子d，你的任务是输出日子d之后，下一次三个高峰落在同一天的日子（用距离d的天数表示）。例如：给定日子为10，下次出现三个高峰同一天的日子是12，则输出2。

我写的：

#include <iostream>using namespace std;bool test(int t, int j, int ini);int main()
{cout << "please enter p e i and d " << endl;int p, e, i, d;cin >> p >> e >> i >> d;int j;for(j=d+1;;j++){if(test(23,j,p) && test(28,j,e) && test(33,j,i)){cout << "The next triple peak occurs in " << j-d << " days" << endl;break;}else{continue;}}
}bool test(int t, int j, int ini)
{if((j-ini)%t == 0)return 1;elsereturn 0;
}

标答：

#include <iostream>
#include <cstdio>using namespace std;int main()
{int p, e, i, d;while (cin >> p >> e >> i >> d && p != -1){int k;for (k = d + 1; (k - p) % 23; ++k);for (; (k - e) % 28; k += 23);for (; (k - i) % 33; k += 23 * 28);cout << "the next triple peak occurs in " << k - d << " days." << endl;}return 0;
}

例题三称硬币

题目：有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同，但不知道假币比真币轻还是重。现在，用一架天平称了这些币三次，告诉你称的结果，请你找出假币并且确定假币是轻是重（数据保证一定能找出来）

标答：

#include <iostream>
#include <cstring>using namespace std;char Left[3][7];    //coins on the left, 3 results in total, one string can contain 7 chars
char Right[3][7];
char result[3][7];bool IsFake(char c, bool light); //define a function, to test a coin is whether light or heavyint main()
{int t; //number of groupscin >> t;while(t--){for(int i = 0; i < 3; i++) cin >> Left[i] >> Right[i] >> result[i]; //read three situatiionss in one groupfor(char c = 'A'; c <= 'L'; c++){if( IsFake(c, true) ){cout << c << " is the counterfeit coin and it is light.\n";break;}else if( IsFake(c, false) ){cout << c << " is the counterfeit coin and it is heavy.\n";break;}}}return 0;
}bool IsFake(char c, bool light) 
{for(int i = 0; i < 3; i++) //for the three situations in one group{char *pLeft, *pRight;if(light){pLeft = Left[i];pRight = Right[i];}else                  //if the fake coin is heavy, we swap the left and right{pLeft = Right[i];pRight = Left[i];}switch(result[i][0]) //use the first letter of up even down to switch between cases{case 'u':if(strchr(pRight,c) == NULL) //check if char c is in the string at which pRight pointsreturn false;break;case 'e':if(strchr(pLeft,c) || strchr(pRight,c))return false;break;case 'd':if(strchr(pLeft,c) == NULL)return false;break;    }}return true;
}

记住这几个写法
while(t–)
for(int i = 0; i < 3; i++)
for(char c = ‘A’; c <= ‘L’; c++)
case ‘u’:

chatGPT, 利用枚举和结构体：

#include <iostream>
#include <cstring>using namespace std;enum Result {UP, EVEN, DOWN};struct Group {char Left[7];char Right[7];Result result;
};bool IsFake(char c, bool light, Group g[3]);int main()
{int t;cin >> t;while(t--){Group g[3];for(int i = 0; i < 3; i++){cin >> g[i].Left >> g[i].Right;string res;cin >> res;if(res == "up") g[i].result = UP;else if(res == "even") g[i].result = EVEN;else g[i].result = DOWN;}for(char c = 'A'; c <= 'L'; c++){if(IsFake(c, true, g)){cout << c << " is the counterfeit coin and it is light.\n";break;}else if(IsFake(c, false, g)){cout << c << " is the counterfeit coin and it is heavy.\n";break;}}}return 0;
}bool IsFake(char c, bool light, Group g[3])
{for(int i = 0; i < 3; i++){char *pLeft, *pRight;if(light){pLeft = g[i].Left;pRight = g[i].Right;}else{pLeft = g[i].Right;pRight = g[i].Left;}switch(g[i].result){case UP:if(strchr(pRight,c) == NULL)return false;break;case EVEN:if(strchr(pLeft,c) || strchr(pRight,c))return false;break;case DOWN:if(strchr(pLeft,c) == NULL)return false;break;}}return true;
}

例题四熄灯问题

贴一个位运算错误代码：

int main()
{int i = 1;i << 3; cout << i;
}

这里没有改变变量i的值
应修改为：

int main()
{int i;i = 1;i = i << 3;cout << i;
}

给 i 赋上 1 经过位运算之后的值
标答：

#include <memory>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int GetBit(char c, int i)
{// 取c的第i位return (c >> i) & 1;
}
void SetBit(char &c, int i, int v)
{// 设置c的第i位为vif (v)c |= (1 << i);elsec &= ~(1 << i);
}
void Flip(char &c, int i)
{// 将c的第i位为取反c ^= (1 << i);
}
void OutputResult(int t, char result[]) // 输出结果
{cout << "PUZZLE #" << t << endl;for (int i = 0; i < 5; ++i){for (int j = 0; j < 6; ++j){cout << GetBit(result[i], j);if (j < 5)cout << " ";}cout << endl;}
}
int main()
{char oriLights[5]; // 最初灯矩阵，一个比特表示一盏灯char lights[5];    // 不停变化的灯矩阵char result[5];    // 结果开关矩阵char switchs;      // 某一行的开关状态int T;cin >> T;for (int t = 1; t <= T; ++t){memset(oriLights, 0, sizeof(oriLights));for (int i = 0; i < 5; i++){ // 读入最初灯状态for (int j = 0; j < 6; j++){int s;cin >> s;SetBit(oriLights[i], j, s);}}for (int n = 0; n < 64; ++n){ // 遍历首行开关的64种状态memcpy(lights, oriLights, sizeof(oriLights));switchs = n; // 第i行的开关状态for (int i = 0; i < 5; ++i){result[i] = switchs; // 第i行的开关方案for (int j = 0; j < 6; ++j){if (GetBit(switchs, j)){if (j > 0)Flip(lights[i], j - 1); // 改左灯Flip(lights[i], j);         // 改开关位置的灯if (j < 5)Flip(lights[i], j + 1); // 改右灯}}if (i < 4)lights[i + 1] ^= switchs; // 改下一行的灯switchs = lights[i];          // 第i+1行开关方案和第i行灯情况同}if (lights[4] == 0){OutputResult(t, result);break;}} // for( int n = 0; n < 64; n ++ )}return 0;
}

第二章递归（一）

例题一求阶乘

#include <iostream>int get_factorial(int n)
{int factorial;if(n == 0){factorial = 1;}else{factorial = n * get_factorial(n-1);}return factorial;
}int main()
{int n;std::cin >> n;std::cout << get_factorial(n); 
}

例题二汉诺塔

我写的：

#include <iostream>using namespace std;void move_method(int n, char start, char transit, char destination)
{if (n == 2){cout << start << "->" << transit << endl;cout << start << "->" << destination << endl;cout << transit << "->" << destination << endl;}else if (n > 2){move_method(n - 1, start, destination, transit);cout << start << "->" << destination << endl;move_method(n - 1, transit, start, destination);}
}int main()
{int n;cin >> n;move_method(n, 'A', 'B', 'C');
}

例题三 n皇后问题

标答：

#include <iostream>
#include <cmath>using namespace std;void nQueens(int k);int queenPosition[100]; // queen's position fron line0 to line(n-1), assume n <= 100
int N;int main()
{cin >> N;nQueens(0); // start from line0
}void nQueens(int k) // put a queen in linek
{if (k == N) // if N queens (line0 to line N-1) are well positioned{for (int i = 0; i < N; i++) // for every line{cout << queenPosition[i] + 1 << " "; // print the results}cout << endl;}// below is the actually working functionfor (int i = 0; i < N; i++) // for every position in linek{int j = 0;for (j = 0; j < k; j++) // for all the positioned queens{if (queenPosition[j] == i || abs(queenPosition[j] - i) == abs(k - j)) // if conlicting{break; // stop trying, jump out the inner loop and try the next position in linek}}if (j == k){queenPosition[k] = i;nQueens(k + 1); // to deal with next line}}
}

例题四逆波兰表达式

标答：

#include <iostream>
#include <cstdio>
#include <cstdlib>using namespace std;double exp()
{// 读入一个逆波兰表达式，并计算其值char s[20];cin >> s;switch (s[0]){case '+':return exp() + exp();case '-':return exp() - exp();case '*':return exp() * exp();case '/':return exp() / exp();default:return atof(s);break;}
}
int main()
{printf("%lf", exp());return 0;
}

补充笔记（from theCherno)

break 和 continue 都是对于循环而言的
一个是跳出这个循环，一个是之间进入下一轮循环
for 里面的东西可以很灵活。循环变量初始、新一轮循环开始条件、每个循环最后对循环变量做出的调整，分别填上就好。

第三章递归（二）

例题一求表达式的值

我的答案：

#include <iostream>using namespace std;int expression_value();
int term_value();
int factor_value();int main()
{cout << expression_value() << endl;return 0;
}int expression_value()
{int result = 0;result = term_value(); // the value of first termchar operation = cin.peek();while (operation == '+' || operation == '-'){cin.get();if (operation == '+'){result += term_value();}else if (operation == '-'){result -= term_value();}elsebreak;operation = cin.peek();}return result;
}int term_value()
{int result = 1;result = factor_value(); // the value of first termchar operation = cin.peek();while (operation == '*' || operation == '/'){cin.get();if (operation == '*'){result *= factor_value();}else if (operation == '/'){result /= factor_value();}elsebreak;operation = cin.peek();}return result;
}int factor_value()
{int result = 0;char element = cin.peek();if (element == '('){cin.get();result = expression_value();cin.get();}else{int digit;cin >> digit;result = result * 10 + digit;}return result;
}

呜呜呜chatGPT帮了我好多我好爱
记得魔法上网挂米国

提一句：
cin.get()可以取走一个字符，从输入流里拿走最左边的字符。
cin.peek()可以读到最左边的字符但不用把它拿走
在这里插入图片描述

例题二爬台阶

我的答案：

#include <iostream>using namespace std;int get_combinatioins(int N);int main()
{cout << "please enter the number of steps" << endl;int N = cin.get();get_combinatioins(N);return 0;
}int get_combinatioins(int N)
{int combinations;if (N == 1)combinations = 1;else if (N == 2)combinations = 2;else if (N > 2)combinations = get_combinatioins(N - 1) + get_combinatioins(N - 2);return combinations;
}

例题三算24

fabs是求浮点数的绝对值，abs是求整数的绝对值
函数原型（记住这个名词）为int abs (int x)和float fabs (float x)

按F11可以切换全屏和非全屏模式

抄写标答呜呜：

#include "iostream"
#include "cmath"using namespace std;double a[5];
#define EPS 1e-6bool isZero(double x)
{return fabs(x) <= EPS;
}bool count24(double a[], int n)
{if (n == 1){if (isZero(a[0] - 24))return true;elsereturn false;}double b[5];for (int i = 0; i < n - 1; i++){for (int j = i+1; j < n; j++) // double loops to enumerate combinations of two numbers{int m = 0;for (int k = 0; k < n; k++){if (k != i && k != j)b[m++] = a[k];}b[m] = a[i] + a[j];if (count24(b, m + 1))return true;b[m] = a[i] - a[j];if (count24(b, m + 1))return true;b[m] = a[j] - a[i];if (count24(b, m + 1))return true;b[m] = a[i] * a[j];if (count24(b, m + 1))return true;if (!isZero(a[j])){b[m] = a[i] / a[j];if (count24(b, m + 1))return true;}if (!isZero(a[i])){b[m] = a[j] / a[i];if (count24(b, m + 1))return true;}}}return false;
}int main()
{while (true){for (int i = 0; i < 4; i++)cin >> a[i];if (isZero(a[0]))break;if (count24(a, 4))cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

笔记：

vscode 里面想比较两个代码文件，可以在左边的项目栏里ctrl选中两个要比较的文件，右键选择compare selected
判断整数相等直接==，判断浮点数相等只好用差值小于机器精度。表现在代码里可以宏定义一个esp，即machine epsilon为1e-6, 这边的 $\epsilon$ 有点像淑芬的思维哈哈。然后定义一个判断是否趋于零的函数isZero。需要判断的时候调用这个函数就好了。
想要循环进行一个操作，但是判断循环条件比较复杂，不想放到while后面的括号里，可以while(true), 然后在终止条件里break;出去就行了。

第四章二分算法

二分算法要求是一个有序的数列
可使用sort进行排序，时间复杂度是nlogn

例题一求方程的根

#include <iostream>
#include <cmath>
#include <iomanip>#define epsilon 1e-6using namespace std;double get_solution();int main()
{cout << fixed << setprecision(8) << get_solution() << endl;
}double get_solution()
{double left = 0, right = 100;double solution = (left + right) / 2;double function_value = pow(solution, 3) - 5 * pow(solution, 2) + 10 * solution - 80;while (fabs(function_value - 0) > epsilon){if (function_value > 0)right = solution;else if (function_value < 0)left = solution;solution = (left + right) / 2;function_value = pow(solution, 3) - 5 * pow(solution, 2) + 10 * solution - 80;}return solution;
}

cout << fixed << setprecision(8) << get_solution() << endl;这句是chaatGPT告诉我这么输出的。只要记住有这个办法，具体语法到时候搜就好了。
记住浮点数的绝对值要用fabs，abs没有用。

例题二找出一对数字

一次性找出文所有的当前选中的单词: Ctrl + Shift + L
一小段试验代码：check向函数传值的方式：

#include <iostream>using namespace std;const int MAX_N = 100000;void get_numbers(int &n, int *arr);int main()
{int n;int arr[MAX_N];get_numbers(n, arr);for (int i = 0; i < n; i++){cout << arr[i];}
}void get_numbers(int &n, int *arr)
{cin >> n;for (int i = 0; i < n; i++){cin >> arr[i];}
}

在这里插入图片描述
在自己定义的函数里面，用 n 或 N 甚至 number 都无所谓。只要在参数列表那边加了&，就可以修改实参的值。如·：

void get_numbers(int &number, int *arr)
{cout << "enter n:" << endl;cin >> number;cout << "enter the n numbers:" << endl;for (int i = 0; i < n; i++){cin >> arr[i];}
}

还有就是定义数组的时候要指定其大小

我的答案：

#include <iostream>
#include <algorithm>using namespace std;const int MAX_N = 100000;void get_numbers(int &n, int *arr);
void find_the_pair(int *arr, int &n, int &m);int main()
{cout << "enter m: " << endl;int m;cin >> m;int n;int arr[MAX_N];get_numbers(n, arr);sort(arr, arr + n);find_the_pair(arr, n, m);
}void get_numbers(int &n, int *arr)
{cout << "enter n:" << endl;cin >> n;cout << "enter the n numbers:" << endl;for (int i = 0; i < n; i++){cin >> arr[i];}
}void find_the_pair(int *arr, int &n, int &m)
{int i = 0, j = n - 1;int small = arr[i];int big = arr[j];int sum;while (true){sum = small + big;bool keeptrying = true;if (sum < m){i++;small = arr[i];continue;}else if (sum > m){j--;big = arr[j];continue;}else if (sum == m){cout << small << " " << big << endl;break;}}
}

例题三疯牛

当输入数据很多的时候scanf效率会更高些
shift+字母键可以打出大写
格式化代码可以 Ctrl + Shift + I
总看到的gdb是 GNU symbolic debugger的意思
还有啊，数组直接在main函数里面定义成全局变量就好了，每个函数都可以去操作，不要引用来引用去。
麻了，debug失败。先不贴码了

第五章分治

归并排序

复杂度nlogn
"临摹宋帖“：

#include <iostream>
using namespace std;int a[10] = {13, 27, 19, 3, 8, 12, 2, 8, 30, 89};
int b[10]; // to have a storage to store the sorted arrayvoid MergeSort(int a[], int start, int end, int tmp[]);int main()
{int size = sizeof(a) / sizeof(int);MergeSort(a, 0, size - 1, b);for (int i = 0; i < size; i++){cout << a[i] << ",";}cout << endl;return 0;
}void Merge(int a[], int start, int middle, int end, int tmp[])
{int pointerb = 0;int pointer1 = start, pointer2 = middle + 1;while (pointer1 <= middle && pointer2 <= end){if (a[pointer1] < a[pointer2]){tmp[pointerb++] = a[pointer1++];}else{tmp[pointerb++] = a[pointer2++];}}while (pointer1 <= middle)tmp[pointerb++] = a[pointer1++];while (pointer2 <= end)tmp[pointerb++] = a[pointer2++];for (int i = 0; i < end - start + 1; ++i)a[start + i] = tmp[i];
}void MergeSort(int a[], int start, int end, int tmp[])
{if (start < end){int middle = start + (end - start) / 2;MergeSort(a, start, middle, tmp);MergeSort(a, middle + 1, end, tmp);Merge(a, start, middle, end, tmp);}
}

可以选中所有变量名，给这个变量重命名。（快捷键：选中加F2）
divide and conquer; recursion;

快速排序

#include <iostream>
using namespace std;
int main()
{int a[3] = {1, 2, 3};int i = 0;cout << a[i++] << endl;cout << i;
}
//output 1 
//1

#include <iostream>
using namespace std;
int main()
{int a[3] = {1, 2, 3};int i = 0;cout << a[++i] << endl;cout << i;
}
//output 2 
//1

#include <iostream>
using namespace std;
int main()
{int a[3] = {1, 2, 3};int i = 1;a[i--] = 6;cout << a[0] << " " << a[1] << endl;cout << i;
}
//output 1 6
0

// 关于IDE(clion):
// 我滴超人稚晖君使用的IDE是clion, 追星追星
// shift + alt + <或> 可以改变字体大小
// 右下角输入法改成ENG可以防止中文及其标点的输入
//关于数组：

int length = sizeof(a)/sizeof(a[0])

for(int i = 0; i < length; i++)

第六章动态规划

数字三角形

#include <iostream>
#include <algorithm>
using namespace std;const int MAXN = 105;int N;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];int main() {cin >> N;for (int i = 1; i <= N; i++) {for (int j = 1; j <= i; j++) {cin >> triangle[i][j];}}// 初始化最后一行的 dp 值for (int j = 1; j <= N; j++) {dp[N][j] = triangle[N][j];}// 自底向上进行动态规划for (int i = N-1; i >= 1; i--) {for (int j = 1; j <= i; j++) {dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];}}// 最终的答案即为 dp[1][1]cout << dp[1][1] << endl;return 0;
}