零的执行人 发表于 2020-1-24 17:50:58

C语言题求助

水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=1的3次方+5的3次方+3的3次方。 本题要求编写程序,计算所有N位水仙花数。
输入格式: 输入在一行中给出一个正整数N（3≤N≤7）。
输出格式: 按递增顺序输出所有N位水仙花数，每个数字占一行。
输入样例:
3
输出样例:
153
370
371
407
#include <stdio.h>
#include <math.h>

int main()
{
        int i,n;int a;
        scanf("%d",&n);
        int p=pow(10,(n-1));
        int q=pow(10,n);
        for(i=p;i<=q;i++){
                int t=i;
                int k=0,s=0;
                while(t>0){
                        a=t%10;
                        t=t/10;
                        s=s+pow(a,n);
                        k++;
                        }
                if(s==i)printf("%d\n",i);
        }       
        return 0;

}


测试点问题： 当n取最大值7时，结果正确但是运行超时，题目要求如下： 时间限制: 2500 ms 内存限制: 64 MB 代码长度限制: 16 KB
请问各位大神怎么减小时间复杂度啊？

零的执行人 发表于 2020-1-24 18:15:44

#include <stdio.h>
#include <math.h>
int b;
int main()
{
    int i,n;int a;
    scanf("%d",&n);
    for(i=0;i<=9;i++)b=pow(i,n);
    int p=pow(10,(n-1));
    int q=pow(10,n);
    for(i=p;i<=q;i++){
      int t=i;
      int k=0,s=0;
      while(t>0){
            a=t%10;
            t=t/10;
            s=s+b];
            k++;
            }
      if(s==i)printf("%d\n",i);
    }   
    return 0;
}

chxchxkkk 发表于 2020-1-28 17:53:21

本帖最后由 chxchxkkk 于 2020-1-28 17:57 编辑

水仙花数
页: [1]
查看完整版本: C语言题求助