每日算法刷题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; }#算法##刷题#