求0~100000的“水仙花数”

求0~100000的“水仙花数”。

严格来说，三位自幂数才称为水仙花数。

但我们这里对其进行了变种，定义“水仙花数”为：一个n位数的每位的n次方相加，刚好等于它本身的数。

如：153 == 1^3 + 5^3 + 3^3

分析

这个题目的关键在于：

1. 如何知道这个数是几位数？
2. 如何判断这个数是否为“水仙花数”？

我们分成2个函数来解决：

1. 如何知道这个数是几位数？

1. 我们不断地进行n /= 10，当n == 0时，根据循环的次数，我们就可以得到n的位数。

2. 如何判断这个数是否为“水仙花数”？

1. 取极右法

1. 让n % 10，即可得到它的个位（极右）
2. 让n / 10，则可以让n使其它的个位
3. 然后让新的n再进入一次循环，最后就能得到它的每一位
4. 把每一位^位数的和与n相比，相等则为水仙花，代码如下

//取极右法
bool Is_lily_number(int n, int digit)
{
	int i = 0;
	int num = 0;
	int sum = 0;
	int same_n = n;

	for (i = 0; i < digit; i++)
	{
		//取出n的个位数
		num = pow(n % 10, digit);

		//去除n的个位数
		n /= 10;

		sum += num;
	}
	if (sum == same_n)
	{
		return true;
	}
	else
	{
		return false;
	}
}

1. 取极左法

1. 下图代码中使用的是这种方法，里面有详细注释。

整个代码如下

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int Count_digits(int n)
{
	int count = 0;

	while (n != 0)
	{
		n /= 10;
		count++;
	}
	return count;
}

bool Is_lily_number(int n, int digit)
{
	int i = 0;
	int sum = 0;
	int num = 0;
	int same_n = n;

	//求出每一位数，然后让每一位数的指数为digit（位数）
	for (i = 0; i < digit; i++)
	{
		//以数字“123”举例：
		//想取123的最左一位
		//则让123 /（10^（3-1））即可
		//所以我们这里设置为digit - i - 1
		num = n / pow(10, digit - i - 1);

		// 123的1已经取走，现在让23继续继续下一轮循环
		n %= (int)pow(10, digit - i - 1);

		//把每一位处理好的数相加
		sum += pow(num,digit);
	}
	if (sum == same_n)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main()
{
	int i = 0;
	int digit = 0;
	int count = 0;

	for (i = 1; i <= 100000; i++)
	{
		digit = Count_digits(i);
		if (Is_lily_number(i, digit))
		{
			printf("%d ", i);
			count++;
		}
	}
	printf("\n0~100000中，共有%d个水仙花数\n", count);

	return 0;
}