目录
- 第一章 枚举
- 例题一 完美立方
- 例题二 生理周期
- 例题三 称硬币
- 例题四 熄灯问题
- 第二章 递归(一)
- 例题一 求阶乘
- 例题二 汉诺塔
- 例题三 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;
else
return 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 heavy
int main()
{
int t; //number of groups
cin >> t;
while(t--)
{
for(int i = 0; i < 3; i++) cin >> Left[i] >> Right[i] >> result[i]; //read three situatiionss in one group
for(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 points
return 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位为v
if (v)
c |= (1 << i);
else
c &= ~(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 function
for (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 term
char operation = cin.peek();
while (operation == '+' || operation == '-')
{
cin.get();
if (operation == '+')
{
result += term_value();
}
else if (operation == '-')
{
result -= term_value();
}
else
break;
operation = cin.peek();
}
return result;
}
int term_value()
{
int result = 1;
result = factor_value(); // the value of first term
char operation = cin.peek();
while (operation == '*' || operation == '/')
{
cin.get();
if (operation == '*')
{
result *= factor_value();
}
else if (operation == '/')
{
result /= factor_value();
}
else
break;
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-6
bool isZero(double x)
{
return fabs(x) <= EPS;
}
bool count24(double a[], int n)
{
if (n == 1)
{
if (isZero(a[0] - 24))
return true;
else
return 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;
else
cout << "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-6
using 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 array
void 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;
}
感觉int n和cin>>n可以放在一行里,因为完成的是一件事。
更多推荐
北大郭炜教授《程序与算法(二)算法基础》学习笔记
发布评论