题目目录
- 题目1：全排列
- 题目2：三数排序
- 题目3：1+2+3+...+100 = ?
- 题目4 ：大整数相加
- 题目5：无零整数
题目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;
}
运行结果
运行环境
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;
}
运行结果
运行环境
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;
}
运行结果
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;
}
运行结果
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;
}
运行结果
题目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;
}
测试：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
假设a=‘123456789’ , b=‘11’
1 2 3 4 5 6 7 8 9
+ 1 1
---------------------
1 2 3 4 5 6 8 0 0
依次类推
我们发现
当进行两个数相加时
- 每次进行的步骤就是对应的数相加
- 如果有进位，还需要加上进位
- 最后我们只需要得到和的个位数以及产生的进位
简单的说
每次进行的步骤就是
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+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;
}
题目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;
}
参考 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;
}
涉及知识点
- to_string()
- find()
- string::npos
运行环境
Visual Studio Code