每日算法刷题Day4-完全数、分情况输出、平方矩阵、斐波那契数列匹配输出
每日算法刷题Day4-完全数、分情况输出、平方矩阵、斐波那契数列匹配输出
每日算法刷题Day4-完全数、分情况输出、平方矩阵、斐波那契数列匹配输出
⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。在众多刷题平台中我比较推荐“牛客”平台，它与其他平台相比有以下优点：
- 在线编程环境，可以省去配置环境的繁琐，直接上手刷题。
- 众多企业面试真题，更精准地解决面试算法问题。
- 有非常广泛的论坛与题解讨论基础，可谓是融合了力扣和脉脉的长处。
- 题库难易划分精准，即使小白也可以快速上手学习，同时也包含非常友好的入门题目，学练一体。
学习网站链接：牛客刷题网
开启刷题成长之旅吧！
本文目录
13. 完全数
一个整数，除了本身以外的其他所有约数的和如果等于该数，那么我们就称这个整数为完全数。
例如，6 就是一个完全数，因为它的除了本身以外的其他约数的和为 1+2+3=6
现在，给定你 N 个整数，请你依次判断这些数是否是完全数。
输入格式
第一行包含整数 N，表示共有 N 个测试用例。
接下来 N 行，每行包含一个需要你进行判断的整数 XX。
输出格式
每个测试用例输出一个结果，每个结果占一行。
如果测试数据是完全数，则输出 X is perfect，其中 X 是测试数据。
如果测试数据不是完全数，则输出 X is not perfect，其中 X 是测试数据。
数据范围
1≤N≤100 1≤X≤108
输入样例：
3
6
5
28输出样例：
6 is perfect
5 is not perfect
28 is perfect代码
这里我先采用了暴力求解的方法。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--){
int m,sum=0;
cin>>m;
for(int i=1;i<m;i++)
if(m%i==0)sum+=i;
if(sum==m)
cout<<m<<" is perfect"<<endl;
else cout<<m<<" is not perfect"<<endl;
}
return 0;
}结果报Time Limit Exceeded 超时，其实分析一下，确实数据量过大时会错误。
很明显外层n层for循环处理n行数，内层x层for循环处理这个数的约数判断，那么时间复杂度即
在这里就是
;由题中数据范围可知，最大测试数据时间可达10的8次方*100 那就是100亿了，肯定超时。
外循环无法优化，可以考虑内循环的简化。在这里我采用遍历的方式时间消耗大，由于约数一般是成对出现的，因此在判断完其中一个约数时，另一个约数也就可知了。这种约数的对称尽头一般在该数的平方。因此限制循环条件可以为根号下的该数，即sqrt 作为限制循环次数的条件。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin>>n;
while (n--)
{
int x;
long long sum=1;
cin>>x;
for (int i = 2; i <= sqrt(x);i++)
{
if (x % i == 0)
{
sum+=i;
sum+=x/i;
}
}
if (sum==x&&x!=1)//注意，1不是完全数，因为不能是其本身。
printf("%d is perfect\n",x);
else
printf("%d is not perfect\n",x);
}
return 0;
}当然除了sqrt以外，采用动态约束的思想也可以实现。
for (int i = 2; i <= x/i;i++)即随着i的不断变化，其对应的查找区间相应的缩小。
14. 分情况输出
当存在多种情况需要输出时，可以从一般的ifelse语句
if(C=='S')printf("%.1f",sum);
else printf("%.1f",sum/12);换为
printf("%.1lf",op=='S' ? s : s/12);15.平方矩阵
输入整数 N，输出一个 N 阶的回字形二维数组。
数组的最外层为 1，次外层为 2，以此类推。
输入格式
输入包含多行，每行包含一个整数 N。
当输入行为 N=0 时，表示输入结束，且该行无需作任何处理。
输出格式
对于每个输入整数 N，输出一个满足要求的 N 阶二维数组。
每个数组占 N 行，每行包含 N 个用空格隔开的整数。
每个数组输出完毕后，输出一个空行。
数据范围
0≤N≤100
输入样例：
1
2
3
4
5
0输出样例：
1
1 1
1 1
1 1 1
1 2 1
1 1 1
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1代码：
由观察可以得知，该矩阵只需要求出每一个位置距边界的最小值即可，可以化简为求上下左右四个坐标的最小值。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while (cin>>n&&n!=0)
{
for(int i = 1; i<=n;i++)
{
for(int j = 1;j<=n;j++){
int up = i,down = n-i+1,left = j,right = n-j+1;
cout <<min(min(up,down),min(left,right))<<" ";
}
cout<<endl;
}
cout<<endl;
}
return 0;
}原想法如下：
想要采用数组的方式，求得中心点然后采用麦哈顿距离求解。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m,a[101][101];
cin>>m;
a[m/2+1][m/2+1]=
for(int i = 1;i<=m;i++)
for(int j = 1;j<=m;j++)
{
a[m/2+1][m/2+1]=
}
return 0;
}但是这种方法在测试样例数值偶数的情况下不能很好地实现，因为中心点不确定。
16.斐波那契数列
输入整数 N，求出斐波那契数列中的第 N 项是多少。
斐波那契数列的第 0 项是 0，第 1 项是 1，从第 2 项开始的每一项都等于前两项之和。
输入格式
第一行包含整数 T，表示共有 T 个测试数据。
接下来 T 行，每行包含一个整数 N。
输出格式
每个测试数据输出一个结果，每个结果占一行，
结果格式为 Fib(N) = x，其中 N 为项数，x 为第 N 项的值。
数据范围
0≤N≤60
输入样例：
3
0
4
2输出样例：
Fib(0) = 0
Fib(4) = 3
Fib(2) = 1注意对于变量输入以及输出的处理。当然还要考虑数据过大时是否会产生溢出的问题。
#include <bits/stdc++.h>
using namespace std;
int t;
int main()
{
cin>>t;
while(t--)//变量输入
{
int n;
cin>>n;
long long a=0,b=1,c;
for(int i=0; i<=n; i++)
{
//匹配输出
if (i==n)printf("Fib(%d) = %lld\n",n,a);
c=a+b;
a=b;
b=c;
}
}
return 0;
}专题往期合集：每日算法题解
本专题练习题目、学习、面试、内推均在：牛客刷题网