每日算法刷题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循环处理这个数的约数判断,那么时间复杂度即每日算法刷题Day4-完全数、分情况输出、平方矩阵、斐波那契数列匹配输出在这里就是每日算法刷题Day4-完全数、分情况输出、平方矩阵、斐波那契数列匹配输出;由题中数据范围可知,最大测试数据时间可达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 perfectn",x);
else
printf("%d is not perfectn",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) = %lldn",n,a);
c=a+b;
a=b;
b=c;
}
}
return 0;
}
发表评论

相关文章