2022-08-25 22:07 山东大学算法工程师发布于甘肃

关注

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

输入样例：

输出样例：

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

输入样例：

输出样例：

代码：

由观察可以得知，该矩阵只需要求出每一个位置距边界的最小值即可，可以化简为求上下左右四个坐标的最小值。

#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) = 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;
}

#算法##刷题#