项目场景：

PTA习题4-6 水仙花数

问题描述：

在程序测试时，输入最大位数（7位）被告知运行超时
此为第一版代码

#include<stdio.h>
#include<math.h>
int main()
{
    int n,x,y,i,j,sum=0;
    scanf("%d",&n);
    for(i=pow(10,n-1);i<pow(10,n);i++,sum=0)
		{
			j=i;
        	for(x=1;x<=n;x++)
			{
        		y=j%10;
                sum+=pow(y,n);    
                j/=10;       
			}
            if(i==sum)        
			{	
                printf("%d\n",i);
			}	 	        
		}
    return 0;    
}
        }

原因分析：

1.pow函数返回的是float,程序有很大隐患

2.每次循环都会计算一次pow(10,n),费时

解决方案：

1.i的上下限均为固定值，不妨直接求出来每次用而不是每次都求一次

2.设一个新的函数，用时直接调度函数即可

3.设一个新的数组，用来存放0~9的N次幂，需要时直接从数组里取用即可，更方便

我的第一个版本没有考虑到i的最大最小是固定的，还是运行时有些慢

#include<stdio.h>
#include<math.h>
int sxh(int a,int b);
int main()
{
    int n,x,y,i,j,sum=0;
    scanf("%d",&n);
    for(i=sxh(10,n-1);i<sxh(10,n);i++,sum=0)
		{
			j=i;
        	for(x=1;x<=n;x++)
			{
        		y=j%10;
                sum+=sxh(y,n);    
                j/=10;       
			}
            if(i==sum)        
			{	
                printf("%d\n",i);
			}	 	        
		}
    return 0;    
}

int sxh(int a,int b)
{
	int i,res=1;
	for(i=1;i<=b;i++){
		res*=a;
	}
	return (res);
}

DWR帮忙改的版本

#include<stdio.h>
#include<string.h>

int main()
{
    const int N = 10;
    int n, i, min, max, sum, now, cnt = 0;
    int a[N];//设置数组存放，随取随用
    scanf("%d", &n);
    for(i = 0; i < N; i++)
        a[i] = qmi(i, n);
    
    min = qmi(10, n - 1), max = qmi(10, n);
    
    for(i = now = min, sum = 0; i < max; i++, now = i, sum = 0)
    {
        while(now)//now不为0时
        {
            sum += a[now % 10];
            now /= 10;
        }
        if(sum == i)
        {
            cnt++;
            printf("%d\n", i);
        }
    }
    return 0;
}

int qmi(int x, int k)//快速幂，运算更简便
{
    int res = 1, pow = x;
    while(k)
    {
        if(k & 1)//转为二进制进行运算，同位为1得1，其余均为零 
            res *= pow;
        pow *= pow;
        k >>= 1;//二进制数组向右移一位
    }
    return res;
}

项目场景：

PTA习题4-6 水仙花数

问题描述：

在程序测试时，输入最大位数（7位）被告知运行超时
此为第一版代码

#include<stdio.h>
#include<math.h>
int main()
{
    int n,x,y,i,j,sum=0;
    scanf("%d",&n);
    for(i=pow(10,n-1);i<pow(10,n);i++,sum=0)
		{
			j=i;
        	for(x=1;x<=n;x++)
			{
        		y=j%10;
                sum+=pow(y,n);    
                j/=10;       
			}
            if(i==sum)        
			{	
                printf("%d\n",i);
			}	 	        
		}
    return 0;    
}
        }

原因分析：

1.pow函数返回的是float,程序有很大隐患

2.每次循环都会计算一次pow(10,n),费时

解决方案：

1.i的上下限均为固定值，不妨直接求出来每次用而不是每次都求一次

2.设一个新的函数，用时直接调度函数即可

3.设一个新的数组，用来存放0~9的N次幂，需要时直接从数组里取用即可，更方便

我的第一个版本没有考虑到i的最大最小是固定的，还是运行时有些慢

#include<stdio.h>
#include<math.h>
int sxh(int a,int b);
int main()
{
    int n,x,y,i,j,sum=0;
    scanf("%d",&n);
    for(i=sxh(10,n-1);i<sxh(10,n);i++,sum=0)
		{
			j=i;
        	for(x=1;x<=n;x++)
			{
        		y=j%10;
                sum+=sxh(y,n);    
                j/=10;       
			}
            if(i==sum)        
			{	
                printf("%d\n",i);
			}	 	        
		}
    return 0;    
}

int sxh(int a,int b)
{
	int i,res=1;
	for(i=1;i<=b;i++){
		res*=a;
	}
	return (res);
}

DWR帮忙改的版本

#include<stdio.h>
#include<string.h>

int main()
{
    const int N = 10;
    int n, i, min, max, sum, now, cnt = 0;
    int a[N];//设置数组存放，随取随用
    scanf("%d", &n);
    for(i = 0; i < N; i++)
        a[i] = qmi(i, n);
    
    min = qmi(10, n - 1), max = qmi(10, n);
    
    for(i = now = min, sum = 0; i < max; i++, now = i, sum = 0)
    {
        while(now)//now不为0时
        {
            sum += a[now % 10];
            now /= 10;
        }
        if(sum == i)
        {
            cnt++;
            printf("%d\n", i);
        }
    }
    return 0;
}

int qmi(int x, int k)//快速幂，运算更简便
{
    int res = 1, pow = x;
    while(k)
    {
        if(k & 1)//转为二进制进行运算，同位为1得1，其余均为零 
            res *= pow;
        pow *= pow;
        k >>= 1;//二进制数组向右移一位
    }
    return res;
}