C++小例子【未更新完】

举报
海轰Pro 发表于 2021/08/05 22:39:24 2021/08/05
【摘要】 题目目录 题目1:全排列题目2:三数排序题目3:1+2+3+...+100 = ?题目4 :大整数相加题目5:无零整数 题目1:全排列 全排列 用1、2、3三个数字 可以组成多少个没有重复数字的三位数? 打印出所有的可能 解答 参考Demo - C++ #include <iostream> #include <vector...

题目1:全排列

全排列

用1、2、3三个数字

可以组成多少个没有重复数字的三位数?

打印出所有的可能

解答

参考Demo - C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> temp; // 临时保存已经选择的数

// backtracking:回溯
void backtracking(vector<vector<int> > &res, vector<bool> &isused, vector<int> &nums)
{ // 当temp数组的长度等于期望数组的长度时 return if (temp.size() == nums.size()) { res.push_back(temp); return; } // 遍历所有选择 for (int i = 0; i < nums.size(); ++i) { // 对没有选择过的元素再进行抉择:选择它|不选择它 if (isused[i]) { // 选择该元素 选择后标记该元素为已选择 同时进行下一元素的抉择 temp.push_back(nums[i]); isused[i] = false; backtracking(res, isused, nums); // 回复原来状态:未选择 同时从temp中pop出 isused[i] = true; temp.pop_back(); } }
}

// permute:返回nums数组构成的全排列
vector<vector<int> > permute(vector<int> &nums)
{ vector<vector<int> > res; vector<bool> isused(nums.size(), true); backtracking(res, isused, nums); return res;
}

// 主函数
int main()
{ // 初始化nums=[1,2,3] vector<int> nums; for (int i = 1; i <= 3; ++i) { nums.push_back(i); } // 结果返回值 vector<vector<int> > ans; ans = permute(nums); // 打印结果 for (int i = 0; i < ans.size(); ++i) { for (int j = 0; j < ans[i].size(); ++j) { cout << ans[i][j] << " "; } cout << endl; } return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

运行结果

运行环境

Visual Studio Code

题目2:三数排序

三数排序

输入三个整数a,b,c

请把这三个数由小到大输出

解答

参考Demo - C++

#include <iostream>
using namespace std;

// 主函数
int main()
{ cout<<"依次输入三个整数a、b、c:"; int num0,num1,num2; // 控制台输入三个数 cin>>num0>>num1>>num2; // 找出最小的数 放在num0 if(num0 > num1) { int t=num0; num0=num1; num1=t; } if(num0 > num2) { int t=num0; num0=num2; num2=t; } // 找出第二小的数 放在num1 if(num1 > num2) { int t=num1; num1=num2; num2=t; } // num2肯定就是最大的了 // 输出三个数 cout<<num0<<"<"<<num1<<"<"<<num2<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

运行结果

测试样例-1

测试样例-2

测试样例-3

运行环境

Visual Studio Code

题目3:1+2+3+…+100 = ?

计算 1+2+3+…+100 = ?

解答

Demo - 1 - C++

思路:循环,依次递加

#include <iostream>
using namespace std;

// 主函数
int main()
{ int sum=0; for(int i=1;i<=100;++i) { sum += i; } cout<<"1+2+3+..+100="<<+sum<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

运行结果

Demo - 2 - C++

思路:取巧,使用sizeof函数

    1+2+3+…+100

=((1+100)*100 )/2

=(101*100)/2

这里我们定义一个bool类型的二维数组a

100行,101列

也就是 a[100][101]

sizeof()函数的作用

返回一个对象或类型所占的内存字节数

bool类型在c++为长度为8bit,占1个字节

那么a[100][101]所占内存字节就是100*101

最后再除2即可

#include <iostream>
using namespace std;

// 主函数
int main()
{ bool a[100][101]; cout<<"1+2+3+...+100="<<(sizeof(a)>>1)<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

运行结果

Demo - 3 - C++

思路:递归

#include <iostream>
using namespace std;

// sum函数:求1+2+3...+n的和
int sum(int n) { return n == 0? 0:n+sum(n-1);
}
int main()
{ int ans=0; ans=sum(100); cout<<"1+2+3...+100="<<ans<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

运行结果

题目4 :大整数相加

用户依次输入两个正数 a、b

计算:a+b=?

解答

看到题目

求a+b

简单

return a+b!

#include <iostream>
using namespace std;

int main()
{ int a; int b; cout<<"输入第一个数:"; cin>>a; cout<<"输入第二个数:"; cin>>b; int ans=a+b; cout<<"a+b="<<ans<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

测试:2+3(通过)

测试:1111111111+1111111111(失败)

失败原因:

  • a、b都为int类型,a+b结果可能会造成溢出(超过int所能表示数的最大范围)

这时可能会想到

不用int类型,使用范围更大的long或者long long呢 ?

其实也是一样的

无论是long还是long long

都会有最大数,不小心都会产生溢出

比如计算:11111111111111111111123122222222222222222222222222222222222233333333333342343243243243242343+1

参考解答 - 1

思路:模拟

这里我们使用string类型存储数a、数b

假设a=‘123’ , b=‘12’

使用小学加法计算:

  1 2 3
+   1 2
---------
  1 3 5

  
 
  • 1
  • 2
  • 3
  • 4

假设a=‘123456789’ , b=‘11’

  1 2 3 4 5 6 7 8 9
+ 1 1
---------------------
  1 2 3 4 5 6 8 0 0

  
 
  • 1
  • 2
  • 3
  • 4

依次类推

我们发现

当进行两个数相加时

  • 每次进行的步骤就是对应的数相加
  • 如果有进位,还需要加上进位
  • 最后我们只需要得到和的个位数以及产生的进位

简单的说

每次进行的步骤就是

p+q+count

注:

  • count表示进位
  • p、q表示竖式中对应的元素

结合上述思路

得到一下代码:

#include <iostream>
using namespace std;


int main()
{ string a; string b; string ans; cout<<"输入第一个数:"; cin>>a; cout<<"输入第二个数:"; cin>>b; int count=0; int i=a.length()-1;//a的长度-1 int j=b.length()-1;//b的长度-1 // 对应数相加  while(i>=0 && j>=0) { ans += ((a[i]-'0'+b[j]-'0'+count)%10+'0'); count = (a[i]-'0'+b[j]-'0'+count)/10; --i; --j; } // 若a还未遍历完 while(i>=0) { ans += ((a[i]-'0'+count)%10+'0'); count = (a[i]-'0'+count)/10; --i; } // 若b还未遍历完 while (j>=0) { ans += ((b[j]-'0'+count)%10+'0'); count = (b[j]-'0'+count)/10; --j; } // 补1 (重要) if(count>0) { ans += '1'; } //翻转 reverse(ans.begin(),ans.end()); cout<<"a+b="<<ans<<endl; return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

运行结果

测试:1+9(通过)

测试:11111111111111111111+1111111111(通过)

疑问1

为什么最后需要进行reverse()?

假设a=‘123’ , b=‘1’

我们首先运算的是 3+1

再将其添加至ans

再算2+0

再算1+0

得到ans=421

而正确答案是:124

所以需要翻转

疑问2

为什么最后需要进行补1?

假设a=‘9’ , b=‘1’

如果只是按照对应位置数相加

那么答案就是:0

因为同时遍历完了a与b

但是最后还产生进位1

还需要进行一次运算

正确答案应该是:10

所以

如果a、b都遍历完后,进位不为0,那么还需要进行补1的操作

简化代码

#include <iostream>
using namespace std;


int main()
{ string a; string b; string ans; cout<<"输入第一个数:"; cin>>a; cout<<"输入第二个数:"; cin>>b; int count=0; int i=a.length()-1;//a的长度-1 int j=b.length()-1;//b的长度-1 while(i>=0 || j>=0 || count!=0) { int x= i>=0? a[i]-'0':0; int y= j>=0? b[j]-'0':0; ans += ((x+y+count)%10+'0'); count = (x+y+count)/10; --i; --j; } //翻转 reverse(ans.begin(),ans.end()); cout<<"a+b="<<ans<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

题目5:无零整数

无零整数的判断

要求:输入一个int类型的整数,判断是否为无零整数。

无零整数:数的十进制表示中不含0

示例:

  • 99、123、9872是无零整数
  • 10、101、2002不是

解答

参考 Demo 1

思路:对十进制表示的数的每一位进行判定,观察是否为0

#include <iostream>
using namespace std;


int main()
{ int num; cout<<"输入一个数:"; cin>>num; if(num == 0 ) { cout<<"这个数不是无零整数"<<endl; } while(num) { if(num%10 == 0) { cout<<"这个数不是无零整数"<<endl; return 0; } num = num/10; } cout<<"这个数是无零整数"<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

参考 Demo 2

思路:将int转化为string类型,借用find()函数查询是否含有0

#include <iostream>
using namespace std;


int main()
{ int num; cout<<"输入一个数:"; cin>>num; if(to_string(num).find('0') != string::npos) { cout<<"这个数不是无零整数"<<endl; return 0; } cout<<"这个数是无零整数"<<endl; return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

涉及知识点

  • to_string()
  • find()
  • string::npos

运行环境

Visual Studio Code

文章来源: haihong.blog.csdn.net,作者:海轰Pro,版权归原作者所有,如需转载,请联系作者。

原文链接:haihong.blog.csdn.net/article/details/115940288

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200