机试准备(洛谷)
作为一个输出过程,自己看看
还剩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)的错误。
>
> ![image-20230314154655789](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314154655789.png)
>
> ![image-20230314154849943](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314154849943.png)
### c++风格字符串的优点
> ![image-20230314155009476](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155009476.png)
>
> ![image-20230314155112548](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155112548.png)
>
> ![image-20230314155227247](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155227247.png)'
**同时string也包含有迭代器**
> ![image-20230314155431537](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155431537.png)
#### string做一个连接的操作
**+**
![image-20230314155734052](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314155734052.png)
#### 做一个删除的操作(erase)
![image-20230314160015069](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314160015069.png)
> 数组最后一个换行符,肯定是`str.erase( str.size()-1);`
#### 做一个清空的操作(clear)
`str.clear()`:**会把该字符变成空字符串哦**
#### find操作
![image-20230314161018382](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314161018382.png)
![image-20230314161211834](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314161211834.png)
### 数组的缺点-确定之后无法扩容
![image-20230314162412634](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314162412634.png)
### c++风格的动态数组-vector
![image-20230314163738629](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314163738629.png)
#### 扩容-push_back()
![image-20230314164217532](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164217532.png)
#### 创建一个数组并在一开始赋值
![image-20230314164404391](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164404391.png)
#### 主要常用函数方法
![image-20230314164728303](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164728303.png)
![image-20230314164959562](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314164959562.png)
#### 插入和删除方法
![image-20230314165157382](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314165157382.png)
#### vector底层原理
![image-20230314174821515](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314174821515.png)
![image-20230314174947861](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314174947861.png)
### 相应习题
#### 第一题:
> 因子:数学中的因子指的是能够整除一个给定正整数的所有正整数。例如,6的因子有1、2、3和6。因子通常用于分解质因数的过程中,以及判断一个数是否为质数。一个正整数的因子总是包括1和本身,而其他因子可能会有更多个。
![image-20230314170125174](C:\Users\达芬奇\AppData\Roaming\Typora\typora-user-images\image-20230314170125174.png)
##### 我的题解
```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));
}
}
}