习题4-6 水仙花数

习题4-6 水仙花数 （20 分）

水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=1​3​​+5​3​​+3​3​​。 本题要求编写程序,计算所有N位水仙花数。

输入格式:

输入在一行中给出一个正整数N（3≤N≤7）。

输出格式:

按递增顺序输出所有N位水仙花数，每个数字占一行。

输入样例:

3

输出样例:

153
370
371
407

---

思路：依次取出数字的每一位（个位，十位，百位……）然后，不断进行次幂的相加求和

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int fun(int num, int N)
{
        int sum = 0;
	int n = num;//这里不能只能直接用num进行分解，要先把num的值保存下来。因为如果直接用num分解，则最后num的值为0，无法进行与sum值的比较
	while (n > 0)
	{
		int d = n % 10;
		sum = sum + pow(d,N);
		n /= 10;
	}
	if (sum == num)
	{
		return num;
	}
	else
	{
		return 0;
	}
}


int main()
{
        int num = 0;
	int N = 0;
	scanf("%d", &N);
	for (num = pow(10, N-1); num < pow(10, N); num++)
	{
		int ret = fun(num, N);
		if (ret != 0)
		{
			printf("%d\n", ret);

		}
	}
	system("pause");
	return 0;
}

测试结果：

最后一个测试用例超时，原因是pow函数调用次数过多。我们来分析一下：在main函数的for循环中，计算N位数的数字范围pow函数调用两次，然后进入fun函数，当num是N位数时，相应的，在计算次幂的加和时pow函数又调用N次。举个例子，如果是三位数，则数字的检测范围就是100-999，首先main函数中调用pow函数2次，然后对于每一个三位数，进入fun函数中，都调用3次，所以综合来看，检测100-999之间的数字是否是水仙花数，一共调用pow函数2+3*（999-100+1）=2702次。

 

改进方法：减少pow函数的调用次数。

因为每一位（个位、十位、百位……）的数字范围都是0-9，所以把0-9的次幂值都存入数组中，后面计算各个位的次幂加和时可以直接根据取下的各个位找到对应数组的值进行加和，避免了多次调用pow函数

改进后代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
static int p[10] = { 0 };
int narcissistic(int num)
{
	int sum = 0;
	int n = num;//这里不能只能直接用num进行分解，要先把num的值保存下来。因为如果直接用num分解，则最后num的值为0，无法进行与sum值的比较
	while (n > 0)
	{
		int d = n % 10;
		sum = sum +p[d];
		n /= 10;
	}
	if (sum == num)
	{
		return num;
	}
	else
	{
		return 0;
	}
}

//打印水仙花数
void Print(int m,int n)
{
	for (int num = m; num < n; num++)
	{
		int ret = narcissistic(num);
		if (ret != 0)
		{
			printf("%d\n", ret);

		}
	}
}

int main()
{
	int num = 0;
	int N = 0;
	scanf("%d", &N);
	//因为每一位的数字范围都是0-9，所以把0-9的次幂值都存入数组中，后面计算各个位的次幂加和时可以直接根据取下的各个位找到对应数组的值进行加和，避免了多次调用pow函数
	for (int i = 0; i < 10; i++)
	{
		p[i] = pow(i, N);
	}

	Print(pow(10, N - 1), pow(10, N));
	system("pause");
	return 0;
}

 测试结果：