题目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
 

运行结果

运行环境

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