机试准备（洛谷）
作为一个输出过程，自己看看
还剩10天
题目描述
输入两个整数 �,�a,b，输出它们的和（∣�∣,∣�∣≤109∣a∣,∣b∣≤109）。
注意
- Pascal 使用
integer会爆掉哦！- 有负数哦！
- C/C++ 的 main 函数必须是
int类型，而且 C 最后要return 0。这不仅对洛谷其他题目有效，而且也是 NOIP/CSP/NOI 比赛的要求！
我的题解
#include <iostream>
using namespace std;//为了不加前缀名
int main() {
int a, b;
cin >> a >> b;
cout << a + b;
return 0;
}
#include <stdio.h>
int main() {
int a, b;
scanf("%d%d", a, b);
printf("%d", a + b);
return 0;
}
题目2
//c++
#include <iostream>
using namespace std;
//第一种方法就是讲元看成10
int main() {
int a, b;
cin >> a >> b;
cout << ((a * 10) + b )/( 19);
return 0;
}
//c
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int a,b;
scanf("%d %d", &a, &b);
printf("%d", (a * 10 + b)/ (19));
return 0;
}
题目描述（错了一次复习）
[P1422 小玉P1422 小玉家的电费 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)家的电费 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1422#submit)
我的题解
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int sum;
cin >> sum;
cout << fixed << setprecision(1);//保留小数点后一位
if (sum <= 150) cout << sum * 0.4463;
else if ( sum <=400) cout << 150 * 0.4463 + (sum - 150) * 0.4663;
else cout << 150 * 0.4463 + 250 * 0.4663 + (sum - 400) * 0.5663;
}
/C语言
//c
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int sum;
scanf("%d",&sum);
if (sum <= 150) printf("%.1f", sum * 0.4463) ;
else if (sum <= 400) printf("%.1f", 150 * 0.4463 + (sum - 150) * 0.4663) ;
else printf("%.1f", 150 * 0.4463 + 250 * 0.4663 + (sum - 400) * 0.5663) ;
}
思路
%用法
1 要输出float a=1.23234; 保留3位小数的写法为：
printf(“%.3f”,a);
2 输出double b=123.345232; 保留4为小数，写法为：
printf(“%.4lf”,b);
题目描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7MH08Cxo-1678635540235)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306000340152.png)]
我的题解
int main() {
int a, b, c;
for (a = 0; a <= 9; a++) {
for (b = 0; b <= 9; b++) {
for (c = 0; c <= 9; c++) {
if ((a * 100 + b * 10 + c) + (b * 100 + c * 10 + c) == 532)
printf("%d %d %d", a, b, c);
}
}
}
}
题目描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0gsuyK3Y-1678635540236)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306023408982.png)]
我的思路：
int main() {
int a, b, c, d,sum;
for (a = 0; a <= 9; ++a) {
for (b = 0; b < +9; ++b) {
for (c = 0; c <= 9; ++c) {
for (d = 0; d <= 9; ++d) {
sum = a * 1000 + b * 100 + c * 10 + d;
if (sum * 9 == (d * 1000 + c * 100 + b * 10 + a)) {
if(sum>=1000)
printf("%d\n", sum);
}
}
}
}
}
}
王道用的是求余！！值得学习%%%%
题目描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a8oj7vb2-1678635540236)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306030002374.png)]
我的题解：
int Reverse(int i) {
int k = i * i;
if (k < 10) {
return k;
}
if (10<k &&k< 100) {
int m = k % 10;//个位
int n = k/10;//十位
if (m == n) {
return k;
}
}
if (1000 > k&&k> 100) {
int a = k % 10;
int b = k / 100;
if (a == b) {
return k;
}
}
if (k > 1000&&k<10000) {
int a = k % 10;
int b = k / 10 % 10;//十位
int c = k / 100 % 10;//百位
int d = k / 1000;//千位
if ((a == d) && (b == c)) {
return k;
}
}
if (k > 10000 ) {
int a = k % 10;
int b = k / 10 % 10;//十位
int c = k / 100 % 10;//百位
int d = k / 1000%10;//千位
int e = k / 10000;
if ((a == e) && (b ==d)) {
return k;
}
}
return 0;
}
int main() {
//本质上还是求的是逆序数
//首先小于10肯定是
int i=0;
//再去找对称的数
while (i<= 256) {
if (Reverse(i) == i * i) {
printf("%d\n", i);
}
i++;
}
}
不得不说很久不巧写的方法比较笨==
还剩9天
模拟问题
题目描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OhQqXc7P-1678635540237)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306162133904.png)]
我的题解
int main() {
printf("请输入一个整数\n");
int n,h;
scanf("%d", &h);
int m = h,k;
int H = h + (h - 1) * 3;
for (h; h > 0; --h) {
n = H - m;
k = m;
for (n; n > 0; --n) {
printf(" ");
}
for (k; k >0;k-- ) {
printf("*");
}
m += 2;
printf("\n");
}
}
//第一行为h的话，那么高度为h，即最底部的长度应该是
//H=h+(h-1)*3;
王道解法
int main() {
int h;
while (scanf("%d", &h) != EOF) {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < 2 * h - 2 - 2 * i; ++j) {
printf(" ");
}
for (int j = 0; j < h + 2 * i; ++j) {
printf("*");
}
printf("\n");
}
}
}
使用二维数组去解决模拟问题
char arr[3000][1000];
int main() {
//用二维数组来模拟
//第一步：填空
int h;
while (scanf("%d", &h)!= EOF) {
for (int i = 0; i < h; i++) {
for (int j = 0; j < 3 * h - 2; j++) {
arr[i][j] = ' ';
}
}
//填充完空格开始放星星
int m = h - 1;
int k =0;
for (m; m >= 0; m--) {
for (int n=k ; n<= 3 * h - 2;++n) {
arr[m][n] = '*';
}
k += 2;
}
//打印
for (int i = 0; i < h; i++) {
for (int j = 0; j < 3 * h - 2; j++) {
printf("%c",arr[i][j]);
}
printf("\n");
}
}
}
c风格的字符串设计
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BV0REEMG-1678635540237)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172043262.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pGbPmDMc-1678635540238)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172233290.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NM3eLDF7-1678635540238)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172328511.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W5jrP8CU-1678635540238)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306172740950.png)]
题目描述（错题）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zmqRpElS-1678635540239)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306182210168.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ca2IIKZI-1678635540239)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230306193242901.png)]
我的题解
错了看了王道解法，记得在markji上去背
int main() {
int n;//外框长度
char inner, outter;
printf("请输入长度以及内外花色\n");
bool flag = true;
while (scanf("%d %c %c", &n, &inner, &outter) != EOF) {
if (flag == true) {
flag = false;
}
else
{
printf("\n");
}
char pattern[80][80] = { 0 };//方便最后以字符串的形式输出
int length = 1;//一开始的外框长度
int x, y;//坐标
char changchar = inner;
for (length = 1, x = n / 2, y = n / 2; length <= n; length = length + 2,--x,--y) {
//填满周围的正方形
for (int i = x, j = y; i < x + length; i++) {
pattern[i][j] = changchar;
}
//左上横线
for (int i = x, j = y; j < y + length; j++) {
pattern[i][j] = changchar;
}
//左下横线
for (int i = x + length - 1, j = y; j < y + length; j++) {
pattern[i][j] = changchar;
}
//右边竖线
for (int i = x, j = y + length - 1; i < x + length; ++i) {
pattern[i][j] = changchar;
}
//做个翻转符号
if (changchar == inner) {
changchar = outter;
}
else
{
changchar = inner;
}
}
//去四角
if (n != 1) {
pattern[0][0] = ' ';
pattern[n - 1][0] = ' ';
pattern[0][n - 1] = ' ';
pattern[n - 1][n - 1] = ' ';
}
//输出图形
for (int i = 0; i < n; i++) {
printf("%s\n", pattern[i]);
}
}
}
8天-排序
必须掌握的库函数-sort（）
//关键代码
//c++引入
//头文件
#include <algorithm>
using namespace std;
头文件cstdio
#include <cstdio>
/*
作用：<cstdio>是C语言标准库中的一个头文件，其全称为"C Standard Input and Output Library"。这个库提供了用于执行输入输出操作的函数。其中包括常用的输入函数scanf()、getchar()，以及输出函数printf()、putchar()等。这些函数可以让程序员在C语言中进行标准输入输出，从而读写文件、屏幕、键盘等设备。
在C语言中，<cstdio>可以用预处理指令“#include <cstdio>”来引入。一旦引入了这个头文件，就可以在程序中使用库提供的函数。
<cstdio>库函数的使用非常方便，而且效率高。因此，它是C语言程序员经常使用的一个标准库之一。由于C++是基于C语言的，所以在C++中也可以使用<cstdio>库中的函数。但是在C++中，建议使用iostream库进行输入输出操作，因为iostream库比<cstdio>更安全、更易于使用。
*/
using name space 作用解释
在C++中，using namespace std;是一个常用的语句，它的作用是告诉编译器使用std命名空间中的符号。std是C++标准库中许多类和函数所在的命名空间，如果不使用using namespace std语句，那么就需要使用std::来引用这些类和函数，例如std::cout、std::cin等。 使用using namespace std语句可以省略代码中的std::前缀，从而使代码更加简洁易读，但需要注意的是，这样做也会有一些潜在的问题，例如可能会引发命名冲突等问题。因此，一些C++编程规范建议尽可能不要在头文件中使用using namespace std;，而是在具体的源文件中使用。另外，也可以选择只使用需要的部分命名空间，例如using std::cout;只引入std命名空间中的cout符号，而不是整个std命名空间。 总之，using namespace std语句可以简化C++代码的编写，提高代码的可读性，但需要注意一些潜在的问题，并根据实际情况灵活使用。
sort用法实例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3LzETv0w-1678635540239)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312143313541.png)]
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n;//要输入的数字
while(scanf("%d",&n)!=EOF){
int arr[101];//要输入的数字
for (int i = 0; i < n; ++i){
//一次输入数字同时放入数组
scanf("%d",&arr[i]);
}
//对数组进行排序
sort(arr,arr+n);
//输出
for (int i = 0; i < n; ++i){
printf("%d",arr[i]);
}
}
}
注意点：
arr【i】和arr+i
其实表达意思是完全一样的
arr【i】表示的arr数组中第i号元素的具体值是多少
arr+i表达的意思是arr第i号元素的地址哦
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OJ6yrOLJ-1678635540240)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312144815703.png)]
注意end是尾巴后一个元素的位置
如何设计其排序的规则
默认的排序是升序排序
sort(start,end,compare)//加上一个参数即为compare参数[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8mkErHDS-1678635540240)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312145831814.png)]
using namespace std;
bool compare(int lhs,int rhs){
if(lhs>rhs){
return true;
}else{
return false;
}
//也可以写成 return lhs>rhs
//不发生交换时候返回真
}
int main(){
int arr[8];
for (int i = 0; i < 8; ++i) {
scanf("%d",arr+i);
}
sort(arr,arr+8,compare);
for (int i = 0; i < 8; ++i) {
printf("%d",arr[i]);
}
}
第一题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kx914wzC-1678635540240)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312181633384.png)]
我的题解
#include <cstdio>
#include <algorithm>
using namespace std;
bool comp(int i,int j){
//返回true不交换两个元素
/*第一种情况：左奇数右边偶数不交换*/
if(i%2==1&&j%2==0){
return true;
}else if(i%2==1&&j%2==1&&i>j){
//第二种就是判断奇数如果左边大右边小不交换
return true;
}else if(i%2==0&&j%2==0&&i<j){
//第三种情况判断偶数如果左边小右边大不交换
return true;
}else{
return false;
}
}
第二题
致命错误（第一次写的时候编译错误记录）
使用了变长数组（Variable Length Arrays，VLA），即使用了变量n来定义了一个可以放入n个学生对象的数组students。在C++11标准之前，这种定义数组的方式是不合法的，导致代码可移植性不好，编译器的实现也不稳定。因此，应该使用常量或者宏定义来定义数组的长度，例如使用 #define MAX_STUDENT_NUM 100 来定义数组的最大长度
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JqEMl4P6-1678635540241)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312192346582.png)]
我的题解
#include <cstdio>
#include <algorithm>
#define MAX_STUDENT_NUM 100
using namespace std;
struct Student{
int stuNum;
int stuGrade;
};
bool compare(Student lhs,Student rhs){
/*成绩从小到大,排序不变也就是true
* 若成绩相同，学号大小从小到大*/
if(lhs.stuGrade<rhs.stuGrade){
return true;
} else if (lhs.stuGrade==rhs.stuGrade&&lhs.stuNum<rhs.stuNum){
return true;
}else{
return false;
}
}
int main(){
Student students[MAX_STUDENT_NUM];//开辟一个可以放入是个学生对象的数组
//首先是输入n个整数来表示学生的个数
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&students[i].stuNum,&students[i].stuGrade);
}
//接下来排序
sort(students,students+n, compare);
for (int i = 0; i < n; ++i) {
printf("%d %d",students[i].stuNum,students[i].stuGrade);
printf("\n");//换行
}
}
第三题
重要技巧：
由于sort底层（快速排序）其实本身并不是稳定的故我们需要自己去设置一个变量，来令其稳定
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MkqaAkHy-1678635540241)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312194125321.png)]
我的题解
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_STUDENT_NUM 100
struct Student{
char name[100];
int score;//成绩
int seq;//保证其有序
};
//升序排序参数
bool upper(Student lhs,Student rhs){
if(lhs.score<rhs.score){
return true;
}else if (lhs.score==rhs.score&&lhs.seq>rhs.seq){
//相同成绩先录入在前
return true;
}else{
return false;
}
}
//降序排序参数
bool down(Student lhs,Student rhs){
if(lhs.score>rhs.score){
return true;
} else if (lhs.score==rhs.score&&lhs.seq>rhs.seq){
//相同成绩先录入在前
return true;} else{
return false;
}
}
int main(){
Student students[MAX_STUDENT_NUM];
int n,order;//排序人数和排序方法
while (scanf("%d%d",&n,&order)!=EOF){
//依次输入学生信息
int seq;
for (int i = 0; i < n; ++i) {
seq=0;
scanf("%s%d",&students[i].name,&students[i].score);
students[i].seq=seq;
seq++;
}
//开始分析是低到高还是告到底
if(order==1){
//升序的情况
sort(students,students+n, upper);
//输出值
printf("从高到低 成绩\n");
for (int i = 0; i < n; ++i) {
printf("%s %d\n",students[i].name,students[i].score);
}
}
//降序的情况
if(order==0){
sort(students,students+n, down);
printf("从低到高 成绩\n");
for (int i = 0; i < n; ++i) {
printf("%s %d\n",students[i].name,students[i].score);
}
}
}
}
第四题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Oto9TD2s-1678635540241)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312204056028.png)]
我的题解
#include <cstdio>
using namespace std;
int main(){
//首先是输入一个数n
int n;
int arr[201];
scanf("%d",&n);
for (int i = 0; i < n; ++i){
scanf("%d",&arr[i]);
}
int x;
scanf("%d",&x);
int i;
for ( i = 0; i < n; ++i){
if(arr[i]==x){
printf("%d\n",i);
break;
}
}
if(i==n){
//说明没有这个玩意
printf("-1\n");
}
}
遇到多个数据的时候最好的方式是排序+二分查找哦
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SssNUojp-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312204949484.png)]
容易出现的问题是
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n4u1q1No-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312205154151.png)]
用map解决查找问题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f13bdNmY-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312231325674.png)]
做题前瞻
常用方法名-find（）
在C++中，
std::map是一种关联式容器，它将键映射到值。我们可以使用map中的find方法来查找容器中是否存在某个指定的键。find函数的具体作用为：在map中查找键值等于指定键值的元素，如果能够找到，则返回指向该元素的迭代器；如果查找失败，则返回指向容器尾部的迭代器。函数的形式为：
c++ iterator map::find(const key_type& key); const_iterator map::find(const key_type& key) const;其中，key为要查找的键值，如果map中存在该键，则返回指向该元素的迭代器；否则返回指向容器尾部的迭代器。下面是一个使用
std::map::find函数的例子：
c++ #include <iostream> #include <map> int main() { std::map<std::string, int> m; m["Alice"] = 90; m["Bob"] = 80; m["Charlie"] = 70; auto it = m.find("Alice"); if (it != m.end()) { std::cout << "Alice's score is " << it->second << std::endl; } else { std::cout << "Alice is not found" << std::endl; } it = m.find("David"); if (it != m.end()) { std::cout << "David's score is " << it->second << std::endl; } else { std::cout << "David is not found" << std::endl; } return 0; }在这个例子中，我们定义了一个
std::map对象m，它将学生的姓名映射到他们的成绩。我们首先向m中添加了三个元素，然后使用find函数查找m中是否存在某个指定的键。第一个查找"Alice"，由于这个键存在于m中，因此find函数返回指向该元素的迭代器，并输出对应的成绩。第二个查找"David"，由于这个键不存在于m中，因此find函数返回指向容器尾部的迭代器，并输出一个提示信息。
find（）常常会和end（）配合使用
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sdGl6wcI-1678635540242)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230312233708280.png)]
#include <cstdio>
#include <map>
using namespace std;
int main(){
map<int,int> findIndex;
int m,n;
int arr[101];
while (scanf("%d",&n)!=EOF){
for (int i = 0; i < n; ++i){
scanf("%d",&arr[i]);
findIndex[arr[i]]=i;
//将数组元素作为建，数组元素下标作为值
}
scanf("%d",&m);
for (int i = 0; i < m; ++i){
int findnum;//带查找元素
scanf("%d",&findnum);
if(findIndex.find(findnum)!=findIndex.end()){
printf("NO\n");
} else{
printf("YES\n");
}
}
}
}
## 7天-字符串与线性数据结构
> 讨喜的写法：当输入或者是输出的时候呢用
>
> ```c
> scanf or printf
> ```
>
> 但是如果是运算时候分割等操作可以转化为cpp中的string
>
> 涉及的问题是如何互相转化
> 解决方法：
>
> 在C语言中，我们通常使用字符数组（char array）来存储和处理字符串。而在C++中，则提供了一个内置的字符串类型std::string。要将字符数组转换为std::string，可以使用std::string的构造函数，如下所示： ```c++ char cstr[] = "Hello, world!"; std::string cppstr(cstr); ```
>
> 要将std::string转换为字符数组，可以使用std::string的c_str()方法，它返回一个指向C风格字符串的指针，如下所示： ```c++ std::string cppstr = "Hello, world!"; const char* cstr = cppstr.c_str(); ```
>
> 需要注意的是，使用c_str()方法得到的指针指向一个常量字符数组，因此不能修改该数组的内容。如果需要修改字符串内容，则需要将其复制到一个非常量字符数组中。例如： ```c++ std::string cppstr = "Hello, world!"; char cstr[20]; std::strcpy(cstr, cppstr.c_str()); ```这个例子中，我们将std::string复制到了一个大小为20的字符数组中。需要确保目标数组足够大，否则可能会发生缓冲区溢出（buffer overflow）的错误。
>
> 
>
> 
### c++风格字符串的优点
> 
>
> 
>
> '
**同时string也包含有迭代器**
> 
#### string做一个连接的操作
**+**
#### 做一个删除的操作（erase）
> 数组最后一个换行符，肯定是`str.erase( str.size()-1);`
#### 做一个清空的操作（clear）
`str.clear()`:**会把该字符变成空字符串哦**
#### find操作
### 数组的缺点-确定之后无法扩容
### c++风格的动态数组-vector
#### 扩容-push_back()
#### 创建一个数组并在一开始赋值
#### 主要常用函数方法
#### 插入和删除方法
#### vector底层原理
### 相应习题
#### 第一题：
> 因子：数学中的因子指的是能够整除一个给定正整数的所有正整数。例如，6的因子有1、2、3和6。因子通常用于分解质因数的过程中，以及判断一个数是否为质数。一个正整数的因子总是包括1和本身，而其他因子可能会有更多个。
##### 我的题解
```c++
#include <vector>
#include <cstdio>
using namespace std;
int sum(int i){
//用于算因子之和
int sum=0;
for (int j = 1; j < i; ++j){
if(i%j==0){
sum+=j;
}
}
return sum;
}
int main(){
vector<int> Enum;//完数
vector<int> Gnum;//盈数
//要求是输出2-60之间所有的完数和盈数
for (int i = 2; i <= 60; ++i) {
if(i==sum(i)){
//相等的时候,放入容器中
Enum.push_back(i);
} else if(i<sum(i)){
//为盈数
Gnum.push_back(i);
}
}
//这时候放完了故输出
printf("E:");
for (int i = 0; i < Enum.size(); ++i) {
printf(" %d",Enum[i]);
}
printf("\n");
printf("G:");
for (int i = 0; i < Gnum.size(); ++i) {
printf(" %d",Gnum[i]);
}
}
受限制的线性表
队列
先进先出
c++库中已经依据队列的逻辑结构给予了相应的实现方法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uqYRvq6E-1678814571378)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314175732696.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wIrBLofF-1678814571379)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314175944438.png)]
如何模拟循环队列的效果：
先出再入
队列相关习题
第一题：约瑟夫环
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fbQQnk9z-1678814571379)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314190414080.png)]
我的题解：
#include <queue>
#include <cstdio>
using namespace std;
int main(){
int n,p,m;
while (true){
scanf("%d%d%d\n",&n,&p,&m);
//输入000出去
if(n==0&&p==0&&m==0) {
break;
}
/*这时候n表示有n个小孩，队头应该是编号p的小孩子
* m表示报数奥m的时候队头小孩子出队*/
//依次入队，队友为p
queue<int> Children;
for (int i = p,j=0; j < n; ++j){
//p--n--1--
Children.push(i);
if(i==n){
i=0;
}
i++;
}
//出循环说明队列已经初始化完成
//这时候开始依次出队
int i=0;
while(true){
//当不明确什么时候完成时定为无线循环，到点了break
//出队
i++;
int k=Children.front();//保持头部元素
Children.pop();//出队
if(i!=m){
//说明没到，再放入
Children.push(k);
}
if(i==m){
//说明到了，这时候输出其编号
i=0;
printf("%d,",k);
}
//如果只有一个元素了直接输出
if(Children.size()==1){
printf("%d",Children.front());
break;
}
}
}
}
第二题：猫狗收容所
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q6TAHX7K-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314200148645.png)]
我的题解
#include <queue>
#include <cstdio>
using namespace std;
struct Animal{
int num;//编号
int queue;//表示进入队列的顺序，因为队列的先后动作关乎于第一种收养方式
};
int main(){
//处理输入数据
int n;
scanf("%d",&n);
int m,t;
queue<Animal> DogQue;
queue<Animal> CatQue;
int queue=1;
for (int i = 0; i < n; ++i){
scanf("%d%d",&m,&t);//m表示是送动物进入/收养，t表示的是动物编号
if(m==1){
//这种情况说说明是要送入收养
if(t<0){
//送猫
Animal cat;
cat.queue=queue++;
cat.num=t;
CatQue.push(cat);
} else if(t>0){
//送狗
Animal dog;
dog.queue=queue++;
dog.num=t;
DogQue.push(dog);
} else{
continue;//直接进入下一次循环
}
}
else if(m==2){
//说明是要收养
if(t==1){
/*指定收养狗*/
if(!DogQue.empty()){
Animal g=DogQue.front();//队头元素
DogQue.pop();//不为空
printf("%d ",g.num);//输出其编号
} else{
continue;
}
}
else if(t==-1){
//收养猫
if(!CatQue.empty()){
Animal g=CatQue.front();//队头元素
CatQue.pop();//不为空
printf("%d ",g.num);//输出其编号
} else{//说明空了
continue;
}
}
else if(t==0){
//收养最早进入队列元素
//收养狗的情况
if(CatQue.empty()&&!DogQue.empty()||
(!CatQue.empty()&&!DogQue.empty()&&CatQue.front().queue>DogQue.front().num)){
printf("%d ",DogQue.front().num);
DogQue.pop();
} else if(CatQue.empty()&&DogQue.empty()){
continue;
} else{
//剩下的情况：猫不为空，狗空；猫狗不空但是猫编号小
printf("%d ",CatQue.front().num);
CatQue.pop();
}
}
}
}
}
栈
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AvMeK1HO-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314231006866.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-98Cl1GTf-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314231450870.png)]
相关习题
第一题：反转数字
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8w1COHeN-1678814571380)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314232613751.png)]
我的题解：
//反转数字输出
#include <cstdio>
#include <stack>
using namespace std;
int main(){
//数字范围很大故要用longlong型存储
long long num;
int n;//输入数字
scanf("%d",&n);
stack<long long>stack;
for (int i = 0; i < n; ++i){
scanf("%lld",&num);
stack.push(num);
}
//然后再出栈输出
while(!stack.empty()){
printf("%lld ",stack.top());
stack.pop();
}
printf("\n");
}
第二题：括号匹配
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0mHXzAsV-1678814571381)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315001034874.png)]
我的题解：
#include <cstdio>
#include <string>
#include <stack>
using namespace std;
int main(){
char str[200];//等待输入的字符
string string1;
while(fgets(str,199,stdin)!=NULL){
//读取一个词语-scanf+%s
//若是要读一行字用fgets配合上while可以实现不确定行数的多行输入
string1=str;//转化为c++风格的字符串
string1.pop_back();//去掉结尾的\n,因为fgets会读取多余的换行符
stack<unsigned > index;//存放下标
string string2;//存放结果字符串
for (int i = 0; i < string1.size(); ++i) {
if(string1[i]=='('){
index.push(i);
string2.push_back('$');//假装是匹配的知道遇到右括号
} else if(string1[i]==')'){
//第一种情况：栈中为空这时候无匹配项了
if(index.empty()){
string2.push_back('?');
} else{
//说明有左括号哦
string2.push_back(' ');
int k=index.top();
string2[k]=' ';
index.pop();
}
}else{
//其他字符直接当空格放入就行
string2.push_back(' ');
}
}
//这时候输出就好了
printf("%s\n%s",string1.c_str(),string2.c_str());
}
}
第三题：简单计算器（难）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YjWFEoWz-1678814571381)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315012038618.png)]
我的题解：
#include <stack>
#include <string>
#include <cstdio>
#include <map>
using namespace std;
int main(){
map<char,int> priority{
{'$',0},
{'+',1},{'-',1},
{'*',2},{'/',2}
};
char buf[300];
while(fgets(buf,300,stdin)!=NULL){
string expr=buf;
expr.pop_back();
if(expr=="0"){
break;
}
expr.push_back('$');
string num;//用来收集单独的0-9
stack<double> numstack;
stack<char> operstack;
for (unsigned i = 0; i <expr.size() ; ++i) {
if(expr[i]>='0'&&expr[i]<='9'){
/*在 ASCII 码表中，'0' ~ '9' 的字符编码分别为 48 ~ 57，
* 因此它们的大小关系是从小到大依次为'0' < '1' < '2' < ... < '9'，其中 '0' 最小，'9' 最大。 */
num.push_back(expr[i]);
}else if(expr[i]==' '){
if(num!=" "){
numstack.push(stod(num));
num=" ";
}
}
else{
//+ - / *
if(expr[i]=='$'){
//结尾
if(num!=" "){
numstack.push(stod(num));
num=" ";
}
}
while(!operstack.empty()&&priority[operstack.top()]>= priority[expr[i]]){
char oper=operstack.top();
operstack.pop();
double rhs=numstack.top();
numstack.pop();
double lhs=numstack.top();
numstack.pop();
switch (oper) {
case '+':
numstack.push(lhs+rhs);
break;
case '-':
numstack.push(lhs-rhs);
break;
case '/':
numstack.push(lhs/rhs);
break;
case '*':
numstack.push(lhs*rhs);
break;
}
}
operstack.push(expr[i]);
}
}
printf("%.2lf\n",numstack.top());
}
}
表达式的解析问题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F0OZ9wHG-1678814571381)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315002248526.png)]
表达式的数据结构设计
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lP12lOZu-1678814571382)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315002512582.png)]
读取字符串的操作！（很重要）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xu2kmjHf-1678814571382)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314233458670.png)]、
6天-函数调用的本质和递归的原理
函数调用的本质
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2X7PBx7I-1678881535184)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315150025181.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TvasZxeK-1678881535185)(D:\刷题图片\image-20230315150500425.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c4MGtlgT-1678881535185)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315150542624.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-42iZpAjy-1678881535186)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315151156157.png)]
金典理解方面的错误：并不是进入main函数操作系统才申请栈区的哦
在进入
main函数之前，程序会首先进行一些初始化操作，包括分配栈区等操作。具体来说，当操作系统启动一个进程时，会为这个进程分配一些虚拟内存空间，其中一部分用于存储栈区。 在进入main函数之前，操作系统会把一部分虚拟内存空间分配给栈区，然后在进入main函数时，程序会在这段栈区中为main函数的局部变量、参数等分配空间。当main函数结束时，程序会释放main函数所分配的栈空间，然后退出进程，操作系统会收回这些虚拟内存空间。 所以可以说，在进入main函数之前，程序已经分配了栈区，但这并不代表这个栈区一定很大，栈区的大小取决于操作系统的分配策略和硬件资源的限制。所以一直递归不出栈才会导致爆栈
第二点：栈区申请具体流程
在程序运行时，栈区是在进入函数时动态开辟的，也就是说，当函数被调用时，栈会自动分配一段地址空间，并且会在函数调用结束时释放。 栈区的大小是由操作系统根据需要来动态分配的，而不是由程序员手动定义的。当进程启动时，操作系统会为进程分配一定大小的栈空间。当函数调用时，程序将栈指针向下移动，以为当前调用函数预留一定大小的栈空间，栈大小的限制取决于操作系统对栈区的分配策略和硬件资源的限制。 在C语言中，栈的大小是可以通过修改编译器或链接器的设置来改变的，但是这样做并不是一个好的选择，并且一般来说，程序员也不需要手动去管理栈的大小。另外，如果在函数中定义了过多的局部变量、数组等数据，可能会导致栈区溢出，从而导致程序崩溃。
第三点：如何避免爆栈
要避免栈溢出（stack overflow），可以采取以下措施：
减少局部变量和递归调用的深度：在函数中声明的局部变量以及递归调用的深度都会占用栈空间，如果变量和调用层数过多，就容易导致栈溢出。
使用动态分配的内存：可以通过使用动态分配的内存（如
malloc、calloc等）来减少栈的使用量。动态分配的内存存放在堆区，不会影响栈空间的大小。增加栈空间的大小：可以通过修改编译器或链接器的设置来增加栈空间的大小，但是这种方法并不推荐，因为栈空间的大小是受到硬件资源限制的。
使用尾递归：尾递归是指函数调用自身，并且这个函数调用是出现在所返回的值上，而不是出现在表达式的中间。使用尾递归可以避免递归调用的深度过大，从而减少栈空间的使用量。
编写代码时，注意检查边界条件：例如，当使用数组或指针时，一定要确保不会访问到超出数组或指针范围的内存。这样即使出现了错误也不会导致栈溢出。 需要注意的是，栈溢出是一种非常危险的情况，可能会导致程序崩溃或者出现未定义的行为。因此，在编写代码时一定要格外小心，避免出现栈溢出的情况。
递归推导的要点
递归推导的基本方法是找到一个递推公式或者递归式来表示原问题，然后通过对公式或者式子的分析，得到问题的解。 具体的技巧包括：
- 找出递推公式或递归式，确定递归边界。对于递归问题，首先要确定递归关系，即原问题和子问题之间的关系。在找到递归关系之后，需要确定边界条件，即最小和最简单的问题的解，也就是递归问题的停止条件。
- 简化递归问题。对于复杂的递归问题，可以通过简化问题，缩小问题规模的方式来减少问题的复杂度，使得问题更易于处理。例如，可以考虑将原问题分解为若干个子问题，然后递归地解决这些子问题，最后合并子问题的结果得到原问题的解。
- 求解递归问题。在确定了递归关系和边界条件之后，就可以递归地求解问题了。在每一次递归调用中，首先需要判断是否满足递归边界，如果满足，则返回边界条件对应的结果；否则，继续递归解决子问题，并将子问题的结果合并，得到当前问题的解。
- 验证和优化递归算法。验证递归算法的正确性和优化递归算法的效率也是很重要的技巧。在验证递归算法时，可以使用数学归纳法或者反证法等方法。在优化递归算法时，可以考虑使用记忆化搜索或者动态规划等技术。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nfHjAne3-1678881535186)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315152618230.png)]
第一题：n的阶乘
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tmqS8w2f-1678881535187)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315160501949.png)]
我的题解:
#include <cstdio>
using namespace std;
int func(int i){
if(i==1){
return 1;
}
return i *func(i-1);
}
int main(){
//求n的阶乘
int n;
scanf("%d",&n);
printf("%d", func(n));
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Nx3YSWTP-1678881535187)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315160531961.png)]
\
第二题：汉诺塔问题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IhgN4yr4-1678881535187)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315162643525.png)]
我的题解：
//递归金典问题：汉诺塔问题
#include <cstdio>
using namespace std;
//指数级增长用longlong
int Hanuo(long long i){
//1.推导的是n和n-1的关系-》3*hanuo（n-1）+2
//2.算出口即n=1的时候——》2
if(i==1){
return 2;
}
else{
return 3*Hanuo(i-1)+2;
}
}
int main(){
int N;
while(scanf("%d",&N)!=EOF){
printf("%lld", Hanuo(N));
printf("\n");
}
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ibxxSLG3-1678881535188)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315163107236.png)]
从分而治之到递归的过程
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m07Su8BL-1678881535188)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315180947444.png)]
分而治之（Divide and Conquer）是一种将大问题分解成若干个小问题来解决的问题求解策略。
它通常包括三个步骤：分解问题、解决问题、合并问题的解。
在分解问题时，将问题分解为若干个规模较小、结构与原问题相似的子问题，然后对这些子问题进行递归求解。在解决问题时，利用递归求解子问题得到子问题的解。在合并问题的解时，将子问题的解合并为原问题的解。 而递归（Recursion）是一种在函数定义中使用函数自身的方法。当函数调用自身时，就形成了递归调用。
从分而治之到递归的过程主要体现在解决问题的步骤上。在分而治之中，利用递归求解子问题得到子问题的解后，需要将子问题的解合并为原问题的解。在这个过程中，往往需要编写额外的代码来实现合并。而在递归中，自然而然地得到了子问题的解，避免了额外的合并操作。
例如，对于快速排序算法，它是一种基于分而治之策略的排序算法。在分解问题时，将待排序序列分成两个子序列，然后分别递归地对子序列进行排序。在解决问题时，通过递归排序子序列得到子序列的有序序列，然后通过合并两个有序序列得到原问题的有序序列。而在递归中，每个子序列的有序性质都可以自然地得到，不需要额外的合并操作，使得算法更加简洁高效。 因此，从分而治之到递归的过程，是从手动实现合并操作到利用递归自然地得到子问题的解，使得算法更加简洁高效的过程。
典型例题：斐波那契数列
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gp7gjmR5-1678881535189)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315182058835.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FjaPEp0d-1678881535189)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315182412462.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ukR6LbxO-1678881535189)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315182502250.png)]
#include <cstdio>
int Func(int i){
if(i==1){
return 1;
} else if(i==0){
return 0;
} else{
return Func(i-1)+ Func(i-2);
}
}
int main(){
int n;
scanf("%d",&n);
printf("%d", Func(n));
}
典例二：二叉树习题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4oNJglFA-1678881535190)(C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230315194233641.png)]
首先，我们可以利用递归求解二叉树的节点总数。具体来说，我们可以定义一个函数
getNodeNum，它的输入是一个二叉树的根节点root，输出是该二叉树的节点总数。该函数的实现步骤如下： 1. 若root为空，返回0。 2. 否则，递归计算root节点的左子树和右子树的节点总数，再加上1（因为root节点也算一个节点），得到该二叉树的节点总数。 3. 返回上一层调用栈，将左右子树的节点总数相加，得到上一层的节点总数，并最终返回根节点的节点总数。其次，我们可以在后序遍历的过程中，对每个节点计算其子树的节点总数，并记录每个节点子树的节点总数是否等于给定的数m。具体来说，我们可以定义一个函数
getSubtreeWithNodeNum，它的输入是一个二叉树的根节点root、一个整数m和一个vector res，输出是所有节点子树的节点总数等于m的节点。该函数的实现步骤如下： 1. 若root为空，直接返回。 2. 否则，先递归遍历左子树和右子树。 3. 再计算当前节点root的左子树和右子树的节点总数leftNum和rightNum，再加上1，得到以root为根节点的子树的节点总数totalNum。 4. 若totalNum等于m，将root加入结果集res中。 5. 返回上一层调用栈。 最后，我们可以调用函数getSubtreeWithNodeNum，得到所有节点数为m的子树的根节点。
#include <cstdio>
using namespace std;
//确定完全二叉树怎么算
int getNodeNum(int m,int n){
//求的是结点编号为m的子树的结点总数
if(m>n){
return 0;
} else{
return 1+ getNodeNum(2*m,n)+ getNodeNum(2*m+1,n);
}
}
int main(){
//输入
int m,n;
while(scanf("%d%d",&m,&n)!=EOF){
if(m==0&&n==0){
break;
} else{
printf("%d\n", getNodeNum(m,n));
}
}
}
