| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 851 人关注过本帖
标题:c++校园竞赛题
只看楼主 加入收藏
欣飞飞
Rank: 1
等 级:新手上路
帖 子:20
专家分:1
注 册:2013-10-6
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:9 
c++校园竞赛题
给定一个正数,然后将其每一位数字进行平方求和后形成下一个数,循环往复,直到生成的数在前面已经出现为止,变换结束。
例:给定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】之间有多少个“快乐数”
搜索更多相关主题的帖子: 竞赛题 正整数 校园 
2013-10-08 21:50
Sicgl
Rank: 2
等 级:论坛游民
帖 子:17
专家分:61
注 册:2013-10-8
收藏
得分:0 
思路很明显啊...为什么不试试?

Sky!.......忘了说,如果灌水严重...不小心上榜了...大家别投我票...!
2013-10-08 23:55
blueskiner
Rank: 8Rank: 8
等 级:蝙蝠侠
帖 子:227
专家分:707
注 册:2008-9-22
收藏
得分:0 
。。。动不动就求作业。。求答案。。
2013-10-09 09:10
303770957
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:6
帖 子:838
专家分:2125
注 册:2005-9-10
收藏
得分:0 
竞赛题你还拿来求助,那还竞赛个P呀。

♂ 死后定当长眠,生前何须久睡。♀
2013-10-09 09:19
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:0 
写上“总统竞选题” 也没有用的

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2013-10-09 09:54
欣飞飞
Rank: 1
等 级:新手上路
帖 子:20
专家分:1
注 册:2013-10-6
收藏
得分:0 
竞赛好了,我还是不会所以来求助的啊!!
2013-10-09 10:30
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:10 
以下是引用欣飞飞在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换成数组的话,不知道能不能再提升点速度,你可以试一试。
2013-10-09 11:01
欣飞飞
Rank: 1
等 级:新手上路
帖 子:20
专家分:1
注 册:2013-10-6
收藏
得分:0 
回复 7楼 rjsp
大神,首先谢谢你能帮我弄这些对你来说是简单题的题,我刚接触C++不久(半个月),你编的我几乎都不理解,能不能用一些基础的解一下题!!
2013-10-09 11:24
peach5460
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:武汉
等 级:贵宾
威 望:30
帖 子:2780
专家分:6060
注 册:2008-1-28
收藏
得分:0 
从语法上来说,好像没什么很高深很生僻的语法呀???
回复楼上...

我总觉得授人以鱼不如授人以渔...
可是总有些SB叫嚣着:要么给代码给答案,要么滚蛋...
虽然我知道不要跟SB一般见识,但是我真的没修炼到宠辱不惊...
2013-10-09 14:50
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:10 
昨晚突然想起,将整数分解到十进制的每一位也是很耗时的,于是改代码如下,可以将最差情况下耗时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;
}

2013-10-10 09:56
快速回复:c++校园竞赛题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.059782 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved