C++版 - HDUoj 2010 3阶的水仙花数 - 牛客网

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章，欲转载请先私信获博主允许，转载时请附上网址
http://blog.csdn.net/lzuacm。

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+33 $153=1^3+5^3+3^3$。
现在要求输出所有在m和n范围内的(三阶的)水仙花数。

扩展:
(n阶)水仙花数是指一个 n 位数 ( n≥3 )，它的每个位上的数字的 n 次幂之和等于它本身。
一个正整数abcd···被称为n阶的Armstrong数(水仙花数)当满足:
abcd⋯=an+bn+cn+dn+⋯ $abcd\cdots =a^n+b^n+c^n+d^n+\cdots$
（例如：3阶的水仙花数 33+73+03=370 $3^3+7^3+0^3=370$，4阶的水仙花数 1634=14+64+34+44 $1634=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