算法学习专栏——C++需要知道的一些基础知识例题
一、天数转换（简单–）
读取对应于一个人的年龄（以天为单位）的整数值，并转化为年，月和日表示方式输出，年、月、日分别对应 ano(s), mes(es), dia(s)。
注意：为了方便计算，假设全年 365天，每月 30 天。 数据保证，不会出现 12个月和几天的情况，例如 360,363 或 364。
输入格式
输入一个整数 N。
输出格式
参照输出样例，输出转换后的天数表达。
数据范围
$$
1≤ N ≤1000000
$$
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstdio>
#include < cstring>
using namespace std;
int main()
{
int N;
cin >> N;
int arr[3] = {365,30,1};
string ans[3] = {" ano(s)"," mes(es)"," dia(s)"};
for (int i = 0; i < 3; i++)
{
int n;
n = N / arr[i];
N -= n*arr[i];
printf("%d%s\n",n,ans[i].c_str());
}
}
二、简单排序（简单–）
读取三个整数并按升序对它们进行排序。
输入格式
共一行，包含三个整数。
输出格式
首先，将三个整数按升序顺序输出，每行输出一个整数。
然后，输出一个空行。
紧接着，将三个整数按原输入顺序输出，每行输出一个整数。
数据范围
$$
−100≤输入整数≤100
$$
输入整数各不相同。
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
include< bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d,e,f;
cin >> a >> b >> c;
d = min(a,min(b,c));
e = max(a,max(b,c));
f = a + b + c - d - e;
cout << d << endl;
cout << f << endl;
cout << e << endl;
cout << endl;
cout << a << endl;
cout << b << endl;
cout << c << endl;
}
三、约数（简单–）
输入一个整数 N，按照从小到大的顺序输出它的全部约数。
输入格式
一个整数 N。
输出格式
输出全部约数，每个约数占一行。
数据范围
$$
1≤N≤1000
$$
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案1.0（请自己先思考一下再参考）
#include < iostream>
#include < cmath>
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
int N;
cin >> N;
for (int i = 1; i <= N; i++)
{
if (N % i == 0) cout << i << endl;
}
return 0;
}
四、乘法表（简单–）
输入一个整数 N，输出 N 的乘法表，如下：
1 | |
输入格式
一个整数 N。
输出格式
输出 N的乘法表，具体形式参照输出样例。
数据范围
$$
1<N<1000
$$
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstdio>
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= 10; i++) printf("%d x %d = %d\n",i,n,i*n);
return 0;
}
五、完全数（简单+）
一个整数，除了本身以外的其他所有约数的和如果等于该数，那么我们就称这个整数为完全数。
例如，6 就是一个完全数，因为它的除了本身以外的其他约数的和为 1+2+3=6。
现在，给定你 N 个整数，请你依次判断这些数是否是完全数。
输入格式
第一行包含整数 N，表示共有 N 个测试用例。
接下来 N行，每行包含一个需要你进行判断的整数 X。
输出格式
每个测试用例输出一个结果，每个结果占一行。
如果测试数据是完全数，则输出 X is perfect，其中 X 是测试数据。
如果测试数据不是完全数，则输出 X is not perfect，其中 X 是测试数据。
数据范围
$$
\begin{flalign}
&1≤N≤100\
&1≤X≤10^8&
\end{flalign}
$$
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
using namespace std;
int n,m;
int main()
{
int n,x;
cin >> n;
while (n -- )
{
int sum = 0;
cin >> x;
for (int i = 1; i * i < x; i++)
// 注意这里的i * i < x理解，比如给你一个数16,约数有1,2,4，8,16,你会发现这些约数都是两两组合的，那么我们在判断出2为约数的时候，我们也就可以判断8为约数，如此以来我们就不需要循环到16了，那我们思考一下，是不是很容易就知道我们只需要循环到一个数的平方根的位置就可以了呀，比如16这个数就只需要循环到4就可以将所有的约数求出来了。
if (x % i == 0)
{
sum += i;
if (x / i != i && x / i < x) sum += x / i;
}
if (sum == x) cout << x << " is perfect" << endl;
else cout << x << " is not perfect" << endl;
}
return 0;
}
六、平方矩阵 II（简单–）
输入整数 N，输出一个 N 阶的二维数组。
数组的形式参照样例。
输入格式
输入包含多行，每行包含一个整数 N。
当输入行为 N=0 时，表示输入结束，且该行无需作任何处理。
输出格式
对于每个输入整数 N，输出一个满足要求的 N 阶二维数组。
每个数组占 N 行，每行包含 N 个用空格隔开的整数。
每个数组输出完毕后，输出一个空行。
数据范围
$$
0≤N≤1000
$$
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cmath>
using namespace std;
int main () {
int n;
while (cin >> n,n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << abs(i - j) + 1 << ' ';
}
cout << '\n';
}
cout << '\n';
}
return 0;
}
七、平方矩阵（简单+）
输入整数 N，输出一个 N 阶的二维数组 M。
这个 N 阶二维数组满足 M[i] [j]=2^i+j^
具体形式可参考样例。
输入格式
输入包含多行，每行包含一个整数 N。
当输入行为 N=0时，表示输入结束，且该行无需作任何处理。
输出格式
对于每个输入整数 N，输出一个满足要求的 N 阶二维数组。
每个数组占 N 行，每行包含 N 个用空格隔开的整数。
每个数组输出完毕后，输出一个空行。
数据范围
$$
0≤N≤15
$$
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < bits/stdc++.h>
using namespace std;
int main()
{
int n,x=0;
while (cin >> x,x)
{
for (int i = 0; i < x; i++)
{
for (int j = 0; j < x; j++) cout << int(pow(2,i + j)) << " ";
cout << endl;
}
cout << endl;
}
return 0;
}
八、 蛇形矩阵（中等–）
输入两个整数 n和 m，输出一个 n行 m列的矩阵，将数字 1 到 n×m 按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入格式
输入共一行，包含两个整数 n和 m。
输出格式
输出满足要求的矩阵。
矩阵占 n行，每行包含 m个空格隔开的整数。
数据范围
$$
1≤n,m≤100
$$
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstdio>
using namespace std;
int res[105][105];
int main()
{
int n,m;
cin >> n >> m;
int d1[4] = {0,1,0,-1};
// +1表示向右走一格，-1表示向左走一格，0表示左右方向上不动
int d2[4] = {1,0,-1,0};
// +1表示向下走一格，-1表示向上走一格，0表示上下方向上不动
for(int i = 0, j = 0, d = 0,k = 1; k <= n * m; k ++)
{
res[i][j] = k;
int a = i + d1[d],b = j + d2[d];
if (a < 0 || a >= n || b < 0 || b >= m || res[a][b])
// 当下一个格子查出界限 || 下个格子已经填充过数字：我们就更改方向
{
d = (d + 1) % 4;
a = i + d1[d];
b = j + d2[d];
}
i = a;
j = b;
}
for (int i = 0; i < n; i++)
{
for (int j = 0;j < m; j++) cout << res[i][j] << " ";
cout << endl;
}
return 0;
}
九、忽略大小写比较字符串大小（简单+）
一般我们用 strcmp 可比较两个字符串的大小，比较方法为对两个字符串从前往后逐个字符相比较（按 ASCII 码值大小比较），直到出现不同的字符或遇到 \0 为止。
如果全部字符都相同，则认为相同；如果出现不相同的字符，则以第一个不相同的字符的比较结果为准；如果两字符串长度不同，但所有相同位置的字符均相同，则认为较长字符串更大。
在有些时候，我们比较字符串的大小时，希望忽略字母的大小，例如 Hello 和 hello 在忽略字母大小写时是相等的。
请写一个程序，实现对两个字符串进行忽略字母大小写的大小比较。
输入格式
输入为两行，每行一个字符串，共两个字符串。
注意字符串中仅可能包含大小写字母和空格。
输出格式
如果第一个字符串比第二个字符串小，输出一个字符 <。
如果第一个字符串比第二个字符串大，输出一个字符 >。
如果两个字符串相等，输出一个字符 =。
数据范围
每个字符串的长度范围 [1,80][1,80]。
输入样例1：
1 | |
输出样例1：
1 | |
输入样例2：
1 | |
输出样例2：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstdio>
#include < cstring>
using namespace std;
int main()
{
char a[100],b[100];
fgets(a,100,stdin);
// 你只用记住有这种写法就可以了，它是gets()函数的替代品
fgets(b,100,stdin);
if (a[strlen(a) - 1] == '\n') a[strlen(a) - 1] = 0;
if (b[strlen(b) - 1] == '\n') b[strlen(b) - 1] = 0;
for (int i = 0; a[i]; i++)
{
if (a[i] >= 'A' && a[i] <= 'Z') a[i] += 32;
}
for (int i = 0; b[i]; i++)
{
if (b[i] >= 'A' && b[i] <= 'Z') b[i] += 32;
}
if (strcmp(a,b) == 0) cout << "=";
else if (strcmp(a,b) > 0) cout << ">";
else cout << "<";
return 0;
}
十、最长单词（简单）
一个以 . 结尾的简单英文句子，单词之间用单个空格分隔，没有缩写形式和其它特殊形式，求句子中的最长单词。
输入格式
输入一行字符串，表示这个简单英文句子，长度不超过 500500。
输出格式
该句子中最长的单词。如果多于一个，则输出第一个。
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstdio>
using namespace std;
int main()
{
string s,str;
while (cin >> s)
{
if (s.back() == '.') s.pop_back();
if (s.size() > str.size()) str = s;
}
cout << str;
return 0;
}
十一、字符串中最长的连续出现的字符（简单）
求一个字符串中最长的连续出现的字符，输出该字符及其出现次数，字符串中无空白字符（空格、回车和 tab），如果这样的字符不止一个，则输出第一个。
输入格式
第一行输入整数 N，表示测试数据的组数。
每组数据占一行，包含一个不含空白字符的字符串，字符串长度不超过 200200。
输出格式
共一行，输出最长的连续出现的字符及其出现次数，中间用空格隔开。
输入样例：
1 | |
输出样例：
1 | |
思路
方法千千万，大家可以尝试使用< map > 、max函数或者min函数或者思路实现。下面只介绍一种写法，空间复杂度较低。
代码
答案（请自己先思考一下再参考）
#include < iostream>
using namespace std;
int main()
{
int n,c = 0;
char b;
string a;
cin >> n;
while(n--)
{
int c = 0;
cin >> a;
for (int i = 0; i < a.size() - 1;)
{
int j = 0;
while(a[i] == a[i + j]) j++;
if (c < j)
{
c = j;
b = a[i];
}
i += j;
}
cout << b << ' ' << c << endl;
}
return 0;
}
十二、倒排单词（简单）
编写程序，读入一行英文(只包含字母和空格，单词间以单个空格分隔)，将所有单词的顺序倒排并输出，依然以单个空格分隔。
输入格式
输入为一个字符串（字符串长度至多为 100）。
输出格式
输出为按要求排序后的字符串。
输入样例：
1 | |
输出样例：
1 | |
思路
略
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < sstream>
using namespace std;
int main() {
int len = 0;
string a[110];
string s;
string ss;
getline(cin, s);
stringstream ssin;
ssin << s;
while (ssin >> ss) {
a[len++] = ss;
}
for (int i = len - 1;i >= 0; i--) {
cout << a[i] << ' ';
}
return 0;
}
十三、最长公共字符串后缀（简单+）
给出若干个字符串，输出这些字符串的最长公共后缀。
输入格式
由不超过 5 组输入组成。
每组输入的第一行是一个整数 N。
N 为 0 时表示输入结束，否则后面会继续有 N 行输入，每行是一个字符串（字符串内不含空白符）。
每个字符串的长度不超过 200。
输出格式
每组数据输出一行结果，为 N 个字符串的最长公共后缀（可能为空）。
数据范围
$$
1≤N≤200
$$
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
using namespace std;
const int N = 200;
string s[N];
int main()
{
int n;
while(cin >> n, n)
{
int len = 300;
for (int i = 0; i < n; i++)
{
cin >> s[i];
if (len > s[i].size()) len = s[i].size();
}
while(len)
{
bool success = true;
for (int i = 1; i < n; i++)
{
bool same = true;
for (int j = 1; j <= len; j++)
{
if (s[0][s[0].size() - j] != s[i][s[i].size() - j])
{
same = false;
break;
}
}
if (!same)
{
success = false;
break;
}
}
if (success) break;
len --;
}
cout << s[0].substr(s[0].size() - len) << endl;
}
return 0;
}
十四、最大公约数（简单）
输入两个整数 a 和 b，请你编写一个函数，int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。
输入格式
共一行，包含两个整数 a 和 b。
输出格式
共一行，包含一个整数，表示 a 和 b 的最大公约数。
数据范围
$$
1≤a,b≤1000
$$
输入样例：
1 | |
输出样例：
1 | |
思路
这道题目基本属于一种求公约数的数学思路，你必须知道如何最为官方化地求两个数的最大公约数才可以，比如16 12：
16 12 => 12 16 % 12 => 12 4 => 4 12 % 4 => 4 0这个时候我们就知道4就是这两个数的最大公约数；
16 24 => 24 16 % 24 => 24 16 => 16 24 % 16 => 16 8 => 8 16 % 8 => 8 0这个时候就知道8是这两个数的最大公约数；
这就显而易见这里面的原理了吧。我们现在的任务就是要将这种思路通过代码的方式写出来。
代码
答案（请自己先思考一下再参考）
#include < iostream>
using namespace std;
int gcd(int a,int b) {
if (b != 0) {
return gcd(b, a % b);
} else {
return a;
}
}
int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a, b);
return 0;
}
十五、递归求阶乘（简单）
请使用递归的方式求 n 的阶乘。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示 n 的阶乘的值。
数据范围
$$
1≤n≤10
$$
输入样例：
1 | |
输出样例：
1 | |
思路
不太好说，如果实在不懂就直接问本人吧。
代码
答案（请自己先思考一下再参考）
#include < iostream>
using namespace std;
const int N = 11;
int n;
int fac(int n) {
if (n >= 1) return n * fac(n - 1);
else return 1;
}
int main()
{
int n;
cin >> n;
cout << fac(n);
return 0;
}
十五、递归求斐波那契数列（简单）
请使用递归的方式求斐波那契数列的第 n 项，下标从1开始。
斐波那契数列：1,1,2,3,5… 这个数列从第 3 项开始，每一项都等于前两项之和
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示斐波那契数列的第 n 项。
数据范围
$$
1≤n≤30
$$
输入样例：
1 | |
输出样例：
1 | |
思路
和十四题几乎是一个套路，本题作为练习题
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstring>
#include < algorithm>
using namespace std;
int fib(int x)
{
int a = 1,b = 1,c;
if (x == 1) return a;
else if (x == 2) return b;
x -= 2;
while (x --)
{
c = a + b;
a = b;
b = c;
}
return c;
}
int main()
{
int x;
cin >> x;
cout << fib(x);
return 0;
}
十六、数组去重（简单-）
给定一个长度为 n 的数组 a，请你编写一个函数：
1 | |
输入格式
第一行包含一个整数 n。
第二行包含 n 个整数，表示数组 a。
输出格式
共一行，包含一个整数表示数组中不同数的个数。
数据范围
$$
\begin{flalign}
&1≤n≤1000\
&1≤ai≤1000&
\end{flalign}
$$
输入样例：
1 | |
输出样例：
1 | |
思路
思路说少有4种，这道题目大家请以思考多方法解题为主。
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < cstring>
#include < algorithm>
using namespace std;
int get_unique_count(int arr[],int n)
{
int ans = 0;
sort(arr,arr + n);
for (int i = 0; i < n - 1; i ++ ) if (arr[i] < arr[i + 1]) ans += 1;
return ans;
}
int main()
{
int n;
cin >> n;
int arr[1010];
for (int i = 0; i < n; i ++ ) cin >> arr[i];
cout << get_unique_count(arr,n) + 1;
return 0;
}
十七、三元组排序（简单+）
给定 N 个三元组 (x,y,z)，其中 x 是整数，y 是浮点数，z 是字符串。
请你按照 x 从小到大的顺序将这些三元组打印出来。
数据保证不同三元组的 x 值互不相同。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个整数 x，一个浮点数 y，一个字符串 z，表示一个三元组，三者之间用空格隔开。
输出格式
共 N 行，按照 x 从小到大的顺序，每行输出一个三元组。
注意，所有输入和输出的浮点数 y 均保留两位小数。
数据范围
$$
\begin{flalign}
&1≤N≤10000\
&1≤x,y≤10^5&
\end{flalign}
$$
字符串总长度不超过 105。
输入样例：
1 | |
输出样例：
1 | |
思路
用pair实现，想尝试其他办法也行，但是基本都是pair最为方便，如果你不会使用pair，我就建议直接看代码吧，看代码如何使用pair
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < algorithm>
#include < vector>
using namespace std;
typedef pair< double, string> PDS;
const int N = 1e4 + 10;
int n;
vector< pair< int, PDS>> ans;
int a;
double b;
string c;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
ans.push_back({a,{b,c}});
}
sort(ans.begin(), ans.end()); // 默认是比较第一个数的大小来排序，且按照从小到大的顺序，更多细节之后遇到再进行讲解
for (auto i:ans) {
cout << i.first << " " << i.second.first << " " << i.second.second.c_str()<< '\n';
}
return 0;
}