C++版 - HDUoj 2010 3阶的水仙花数 - 牛客网
C++版 - HDUoj 2010 3阶的水仙花数 - 牛客网
C++版 - HDUoj 2010 3阶的水仙花数 - 牛客网
时间限制：1秒 空间限制：32768K 热度指数：1005
在线提交(牛客网仅支持C++或Java): https://www.nowcoder.com/questionTerminal/dc943274e8254a9eb074298fb2084703 或 http://acm.hdu.edu.cn/submit.php?pid=2010
题目描述
春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的： (三阶的)“水仙花数”是指一个三位数，它的各位数字的立方和等于其本身，比如：153=13+53+33153=13+53+33153=1^3+5^3+3^3。 现在要求输出所有在m和n范围内的(三阶的)水仙花数。
扩展: (n阶)水仙花数是指一个 n 位数 ( n≥3 )，它的每个位上的数字的 n 次幂之和等于它本身。 一个正整数abcd···被称为n阶的Armstrong数(水仙花数)当满足: abcd⋯=an+bn+cn+dn+⋯abcd⋯=an+bn+cn+dn+⋯abcd \cdots = a^n + b^n + c^n + d^n + \cdots （例如：3阶的水仙花数 33+73+03=37033+73+03=3703^3 + 7^3 + 0^3 = 370，4阶的水仙花数 1634=14+64+34+441634=14+64+34+441634 = 1^4 + 6^4 + 3^4 + 4^4 等等）。
输入描述:
输入数据有多组，每组占一行，包括两个整数m和n（100 <= m <= n <= 999）。输出描述: 对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开;
如果给定的范围内不存在水仙花数，则输出no;
每个测试实例的输出占一行。
示例1 输入
100 120
300 380输出
no
370 371示例2 (区间上限n恰好是一个水仙花数) 输入
2 407
150 370输出
153 370 371 407
153 370思路:
暴力法，暂无更优解法。看到有人用鸡贼的方法，直接枚举100~999之间的4个水仙花数，方法并不general，该方法对于n阶的水仙花数就无能为力了，不推荐~
相关数学解释:
Narcissistic number - Wikipedia https://en.wikipedia.org/wiki/Narcissistic_number
Armstrong Number - OEIS https://oeis.org/A005188
已AC代码:
#include <iostream>
using namespace std;
int GetSum(int n)
{
int sum = 0;
while (n != 0)
{
int lastDigit = n % 10;
sum += lastDigit * lastDigit*lastDigit;
n /= 10;
}
return sum;
}
int main() {
int m, n;
while (cin >> m >> n)
{
bool hasArmstrongNum = false; //水仙花数又叫Armstrong数，故用此变量名
int count = 0;
for (int i = m; i <= n; i++) // 注意: 循环控制条件需要=，否则wrong answer.
{
int sum = 0;
sum = GetSum(i);
if (sum == i)
{
hasArmstrongNum = true;
if (count != 0)
cout << " "; // 除了第一个水仙花数，其他水仙花数前面需要加空格
cout << i;
count++;
}
}
if (hasArmstrongNum)
cout << endl;
else
cout << "no" << endl;
}
return 0;
}最初的版本:
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
void PrintArmstrongNums(int m, int n)
{
vector<int> vect;
int count = 0;
for (size_t i = m; i <= n; i++)
{
int sum = GetSum(i);
if (i == sum)
{
vect.push_back(i);
count++;
}
}
if (count > 0)
{
cout << vect[0];
for (size_t i = 1; i < count; i++)
cout << " " << vect[i];
cout << endl;
}
if (count == 0)
cout << "no" << endl;
}
int GetSum(int n)
{
int sum = 0;
while (n != 0)
{
int lastDigit = n % 10;
sum += lastDigit * lastDigit*lastDigit;
n /= 10;
}
return sum;
}
};
int main()
{
Solution sol;
int a, b;
while (cin >> a >> b)
{
sol.PrintArmstrongNums(a, b);
}
return 0;
}ps: 关于高阶的水仙花数(Armstrong数)，可参考下面Java实现的各类算法： ArmstrongNumbers: Efficient Armstrong Number generation in Java https://github.com/shamily/ArmstrongNumbers
腾讯云开发者
