注册 登录
编程论坛 → C++教室

c++校园竞赛题

欣飞飞 发布于 2013-10-08 21:50， 851 次点击
给定一个正数，然后将其每一位数字进行平方求和后形成下一个数，循环往复，直到生成的数在前面已经出现为止，变换结束。
例：给定44,2个4的平方和变成32,3的平方加2的平方等于13,1的平方加3的平方等于10，然后就是1，下面任然是1，序列变换结束，课简单描述成：44->32->13->10->1->1.
再例如给定2，其变换序列为2->4->16->37->58->89->->145->42->20->4。
我们规定，给定正整数n，若最后的变换终止于数值1，则称n为“快乐数”，否则就不是。
现在的任务，给定正整数N，请你计算区间【1··N】之间有多少个“快乐数”


INPUT
测试数据有多组，首先输入测试的组数T（0<T<=20）然后是T组测试数据，每组测试输入一个正整数N（1<=N<=5,000,000)
OUTPUT
对于每组测试，请你计算区间【1··N】之间有多少个“快乐数”
9 回复
#2
Sicgl2013-10-08 23:55
思路很明显啊...为什么不试试?
#3
blueskiner2013-10-09 09:10
。。。动不动就求作业。。求答案。。
#4
3037709572013-10-09 09:19
竞赛题你还拿来求助，那还竞赛个P呀。
#5
yuccn2013-10-09 09:54
写上“总统竞选题” 也没有用的
#6
欣飞飞2013-10-09 10:30
竞赛好了，我还是不会所以来求助的啊！！
#7
rjsp2013-10-09 11:01
以下是引用欣飞飞在2013-10-9 10:30:41的发言：

竞赛好了，我还是不会所以来求助的啊！！

我做了一下，主要是要考虑执行效率
程序代码：
#include <vector>

// 返回 1-1,1-2,1-3,……,1-N 之内有多少个快乐数
std::vector<unsigned> foo( unsigned N )
{
    std::vector<char> a( 5000001, 0 ); // 0表示未决，1表示正在判断，2表示非快乐数，3表示快乐数
    a[1] = 3; // 1是快乐数
    for( unsigned n=1; n<=N; ++n )
    {
        // 跳过已判断的数
        if( a[n] != 0 )
            continue;

        // 对于大部分的数，一次求和就能得到答案，因此加此快速通道
        unsigned sigma = 0;
        for( unsigned t=n; t!=0; t/=10 )
            sigma += (t%10)*(t%10);
        if( a[sigma] != 0 )
        {
            a[n] = a[sigma];
            continue;
        }

        std::vector<unsigned> tmp( 1, n ); // 用以保存正在判断的数(a[sigma]==1)，目的是为了加快速度

        for( unsigned m=sigma; ; )
        {
            a[m] = 1;
            tmp.push_back( m );

            // 平方和
            unsigned sigma = 0;
            for( unsigned t=m; t!=0; t/=10 )
                sigma += (t%10)*(t%10);

            // 在a中查找sigma
            if( a[sigma] == 0 )
            {
                m = sigma;
            }
            else
            {
                // 当生成的数已经出现(a[sigma]==1)或当生成的数为非快乐数(a[sigma]==2)时，将所有正在判断的数(a[sigma]==1)置为非快乐数(2)
                // 当生成的数为快乐数(a[sigma]==3)时，将所有正在判断的数(a[sigma]==1)置为非快乐数(3)
                char v = a[sigma]!=3 ? 2 : 3;

                for( std::vector<unsigned>::const_iterator itor=tmp.begin(); itor!=tmp.end(); ++itor )
                    a[*itor] = v;

                break;
            }
        }
    }

    // 返回
    std::vector<unsigned> ret( N+1, 0 );
    for( unsigned i=1; i<=N; ++i )
        ret[i] = ret[i-1] + (a[i]-2);
    return ret;
}

#include <iostream>
using namespace std;

int main()
{
    unsigned T;
    cin >> T;
    std::vector<unsigned> Ns( T, 0 );
    unsigned max_N = 0;
    for( unsigned i=0; i<T; ++i )
    {
        cin >> Ns[i];

        if( max_N < Ns[i] )
            max_N = Ns[i];
    }

    std::vector<unsigned> result = foo( max_N );

    for( unsigned i=0; i<T; ++i )
    {
        cout << result[ Ns[i] ] << '\n';
    }

    return 0;
}
输入
2
10
5000000
输出
3
704156
在我这里测试时，最差情况下耗时 0.140 秒。
如果将vector换成数组的话，不知道能不能再提升点速度，你可以试一试。
#8
欣飞飞2013-10-09 11:24
回复 7楼 rjsp
大神，首先谢谢你能帮我弄这些对你来说是简单题的题，我刚接触C++不久（半个月），你编的我几乎都不理解，能不能用一些基础的解一下题！！
#9
peach54602013-10-09 14:50
从语法上来说,好像没什么很高深很生僻的语法呀???
回复楼上...
#10
rjsp2013-10-10 09:56
昨晚突然想起，将整数分解到十进制的每一位也是很耗时的，于是改代码如下，可以将最差情况下耗时0.140秒所见到0.062秒
程序代码：
#include <vector>

// 返回 1-1,1-2,1-3,……,1-N 之内有多少个快乐数
std::vector<unsigned> foo( unsigned N )
{
    unsigned s1[7] = { 0, 0, 0, 0, 0, 0, 0 };
    unsigned s2[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };

    std::vector<char> a( 5000001, 0 ); // 0表示未决，1表示正在判断，2表示非快乐数，3表示快乐数
    a[1] = 3; // 1是快乐数
    for( unsigned n=1; n<=N; ++n )
    {
        // 加快将整数分解到一位位
        for( size_t i=0; ; ++i )
        {
            if( s1[i] == 9 )
            {
                s1[i] = 0;
                s2[i] = s2[i+1];
            }
            else
            {
                ++s1[i];
                s2[i] = s2[i+1] + s1[i]*s1[i];
                for( size_t j=i; j!=0; --j )
                    s2[j-1] = s2[i];
                break;
            }
        }
        unsigned sigma = s2[0];

        // 跳过已判断的数
        if( a[n] != 0 )
            continue;

        // 对于大部分的数，一次求和就能得到答案，因此加此快速通道
        //unsigned sigma = 0;
        //for( unsigned t=n; t!=0; t/=10 )
        //    sigma += (t%10)*(t%10);
        if( a[sigma] != 0 )
        {
            a[n] = a[sigma];
            continue;
        }

        std::vector<unsigned> tmp( 1, n ); // 用以保存正在判断的数(a[sigma]==1)，目的是为了加快速度

        for( unsigned m=sigma; ; )
        {
            a[m] = 1;
            tmp.push_back( m );

            // 平方和
            unsigned sigma = 0;
            for( unsigned t=m; t!=0; t/=10 )
                sigma += (t%10)*(t%10);

            // 在a中查找sigma
            if( a[sigma] == 0 )
            {
                m = sigma;
            }
            else
            {
                // 当生成的数已经出现(a[sigma]==1)或当生成的数为非快乐数(a[sigma]==2)时，将所有正在判断的数(a[sigma]==1)置为非快乐数(2)
                // 当生成的数为快乐数(a[sigma]==3)时，将所有正在判断的数(a[sigma]==1)置为非快乐数(3)
                char v = a[sigma]!=3 ? 2 : 3;

                for( std::vector<unsigned>::const_iterator itor=tmp.begin(); itor!=tmp.end(); ++itor )
                    a[*itor] = v;

                break;
            }
        }
    }

    // 返回
    std::vector<unsigned> ret( N+1, 0 );
    for( unsigned i=1; i<=N; ++i )
        ret[i] = ret[i-1] + (a[i]-2);
    return ret;
}

#include <iostream>
using namespace std;

int main()
{
    unsigned T;
    cin >> T;
    std::vector<unsigned> Ns( T, 0 );
    unsigned max_N = 0;
    for( unsigned i=0; i<T; ++i )
    {
        cin >> Ns[i];

        if( max_N < Ns[i] )
            max_N = Ns[i];
    }

    std::vector<unsigned> result = foo( max_N );

    for( unsigned i=0; i<T; ++i )
    {
        cout << result[ Ns[i] ] << '\n';
    }

    return 0;
}
1
©2025, BC-CN.NET
电脑版