每日算法刷题 Day4- 完全数、分情况输出、平方矩阵、斐波那契数列匹配输出

作者：timerring

2022 年 9 月 29 日
山东
本文字数：2308 字
阅读完需：约 8 分钟

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

13. 完全数

一个整数，除了本身以外的其他所有约数的和如果等于该数，那么我们就称这个整数为完全数。

例如，6 就是一个完全数，因为它的除了本身以外的其他约数的和为 1+2+3=6

现在，给定你 N 个整数，请你依次判断这些数是否是完全数。

输入格式

第一行包含整数 N，表示共有 N 个测试用例。

接下来 N 行，每行包含一个需要你进行判断的整数 XX。

输出格式

每个测试用例输出一个结果，每个结果占一行。

如果测试数据是完全数，则输出 X is perfect，其中 X 是测试数据。

如果测试数据不是完全数，则输出 X is not perfect，其中 X 是测试数据。

数据范围

1≤N≤1001≤X≤108

输入样例：

复制代码

输出样例：

6 is perfect5 is not perfect28 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 循环处理这个数的约数判断，那么时间复杂度即 $O (n^{2})$ 在这里就是 $O(nx)$;由题中数据范围可知，最大测试数据时间可达 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
1 11 1
1 1 11 2 11 1 1
1 1 1 11 2 2 11 2 2 11 1 1 1
1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 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

输入样例：

复制代码

输出样例：

Fib(0) = 0Fib(4) = 3Fib(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;}

复制代码

专题往期合集：每日算法题解

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/7d9f2b3bd9b839ceef08b0fc0】。未经作者许可，禁止转载。

timerring

关注

还未添加个人签名 2022.07.14 加入

还未添加个人简介

发布

暂无评论

创作场景

每日算法刷题 Day4- 完全数、分情况输出、平方矩阵、斐波那契数列匹配输出

13. 完全数

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

14. 分情况输出

15.平方矩阵

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码：

16.斐波那契数列

输入格式

输出格式

数据范围

输入样例：

输出样例：

timerring

评论