| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1057 人关注过本帖
标题:【编程大题】花朵数
只看楼主 加入收藏
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
结帖率:100%
收藏
已结贴  问题点数:100 回复次数:10 
【编程大题】花朵数
一个 N 位的十进制正整数,如果它的每个位上的数字的 N 次方的和等于这个数本身,则称其为花朵数。

例如:当 N=3 时,153 就满足条件,因为 1^3 + 5^3 + 3^3 = 153,这样的数字也被称为水仙花数(其中,“^”表示乘方,5^3 表示 5 的 3 次方,也就是立方)。

当 N=4 时,1634 满足条件,因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。

当 N=5 时,92727 满足条件。

实际上,对 N 的每个取值,可能有多个数字满足条件。


程序代码:
程序的任务是:求 N=21 时,所有满足条件的花朵数。注意:这个整数有 21 位,它的各个位数字的 21 次方之和正好等于这个数本身。 

如果满足条件的数字不只有一个,请从小到大输出所有符合条件的数字,每个数字占一行。因为这个数字很大,请注意解法时间上的可行性。要求程序在 1 分钟内运行完毕。 

【程序运行参考结果】 
128468643043731391252 
449177399146038697307 


求高效的算法,提供可行思路也可以!

[ 本帖最后由 azzbcc 于 2013-11-21 17:42 编辑 ]
搜索更多相关主题的帖子: 水仙花 十进制 正整数 
2013-11-21 17:41
Susake
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:女儿国的隔壁
等 级:贵宾
威 望:23
帖 子:2288
专家分:6481
注 册:2012-12-14
收藏
得分:10 
mark!

仰望星空...........不忘初心!
2013-11-21 17:52
pink_duo
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:209
专家分:1054
注 册:2013-11-5
收藏
得分:50 
程序代码:
//楼主我百度来的,说实话,真难啊
#include <stdio.h>
#include <time.h>
int num_time[10]={0};   //num_time[10]用来得到0-9数字出现的个数
int sum[10][21]={{0,0}},sumc[10][21]={{0,0}}; //sum数组用来计算出0-9的21次方。sumc用来计算数字出现次数*它的21次方
int count=0;   //计算得到几个水仙花数了,得到2个以后就结束程序

void initProgramm()   //这个函数用来获得0-9的21次方,存在sum数组里
{
    int i,j,k;
    for(i=0;i<10;i++)
        sum[i][20]=i;

    for(k=2;k<10;k++)
    {
        for(i=1;i<21;i++)
        {
            for(j=20;j>=0;j--)
            {
                sum[k][j]*=k;
            }
            for(j=20;j>0;j--)
            {
                sum[k][j-1]+=sum[k][j]/10;
                sum[k][j]%=10;
            }
        } 
    }
}


void check(int i0,int i1,int i2,int i3,int i4,int i5,int i6,int i7,int i8,int i9) //检测数字是不是水仙花数
{
    int i,j;
    int getAdd[21]={0};
    int j1=0,j2=0,j3=0,j4=0,j5=0,j6=0,j7=0,j8=0,j9=0,j0=0; 

       for(j=0;j<21;j++)            //把数字出现次数*它的21次方
    {
           sumc[1][j]=sum[1][j]*i1;
           sumc[2][j]=sum[2][j]*i2;
        sumc[3][j]=sum[3][j]*i3;
        sumc[4][j]=sum[4][j]*i4;
        sumc[5][j]=sum[5][j]*i5;
        sumc[6][j]=sum[6][j]*i6;
        sumc[7][j]=sum[7][j]*i7;
        sumc[8][j]=sum[8][j]*i8;
        sumc[9][j]=sum[9][j]*i9;
    }

       for(i=0;i<10;i++)     //进位
        for(j=20;j>0;j--)
        {
            sumc[i][j-1]+=sumc[i][j]/10;
            sumc[i][j]%=10;
        } 

    for(i=0;i<10;i++)       //得到一个数每位的21次方的和,就是把sumc叠加起来
        for(j=20;j>=0;j--)
            getAdd[j]+=sumc[i][j];
    
    for(i=20;i>0;i--)    //进位
    {
        getAdd[i-1]+=getAdd[i]/10;
        getAdd[i]%=10;
    }
         
    for(i=20;i>=0;i--)         //用来判断和里面每个数字出现的次数
    {
        switch(getAdd[i])
        {
            case 0:j0++;break;
            case 1:j1++;break;
            case 2:j2++;break;
            case 3:j3++;break;
            case 4:j4++;break;
            case 5:j5++;break;
            case 6:j6++;break;
            case 7:j7++;break;
            case 8:j8++;break;
            case 9:j9++;break;
        }
    }
    
/*如果一个数字,和里0-9出现的次数与这个数字里0-9出现的次数相同,那么和就应该是水仙花数(第一位数字不能为0)*/
    if((i0==j0)&&(i1==j1)&&(i2==j2)&&(i3==j3)&&(i4==j4)&&(i5==j5)&&(i6==j6)&&(i7==j7)&&(i8==j8)&&(i9==j9)&&(getAdd[0]!=0))
    {
        printf("\n");
        count++;
        for(i=0;i<21;i++)
            printf("%d",getAdd[i]);
        printf("\n");
    }
}

void main()
{
    int t,t1,t2;
    int i0,i1,i2,i3,i4,i5,i6,i7,i8,i9;
    initProgramm();
    t1=time(NULL);
    
    for(i9=0;i9<10;i9++)    
    {
        for(i0=1;i0<22;i0++)
        {
            if(count==2)     //出现2个水仙花数以后break
                break;
            if(i9+i0==21)   //几个数字的出现次数和为21以后就break,因为后面的数字出现次数和一定大于21,就超过了21位
            {    check(i0,0,0,0,0,0,0,0,0,i9);break;} 
            for(i2=0;i2<22;i2++)
            {
                if(count==2)
                    break;
                if(i9+i0+i2==21)
                {    check(i0,0,i2,0,0,0,0,0,0,i9);break;}
                for(i3=0;i3<22;i3++)
                {
                    if(count==2)
                        break;
                    if(i9+i0+i2+i3==21)
                    {    check(i0,0,i2,i3,0,0,0,0,0,i9);break;}
                    for(i4=0;i4<22;i4++)
                    {
                        if(count==2)
                            break;
                        if(i9+i0+i2+i3+i4==21)
                        {    check(i0,0,i2,i3,i4,0,0,0,0,i9);break;}
                        for(i5=0;i5<22;i5++)
                        {
                            if(count==2)
                                break;
                             if(i9+i0+i2+i3+i4+i5==21)
                            {    check(i0,0,i2,i3,i4,i5,0,0,0,i9);break;}
                            for(i6=0;i6<22;i6++)
                            {
                                if(count==2)
                                    break;
                                if(i9+i0+i2+i3+i4+i5+i6==21)
                                {    check(i0,0,i2,i3,i4,i5,i6,0,0,i9);break;}
                                for(i7=0;i7<22;i7++)
                                {
                                    if(count==2)
                                        break;
                                    if(i9+i0+i2+i3+i4+i5+i6+i7==21)
                                    {    check(i0,0,i2,i3,i4,i5,i6,i7,0,i9);break;}
                                    for(i8=0;i8<22;i8++)
                                    {
                                        if(count==2)
                                            break;
                                        if(i9+i0+i2+i3+i4+i5+i6+i7+i8==21)
                                        {    check(i0,0,i2,i3,i4,i5,i6,i7,i8,i9);break;}
                                        for(i1=0;i1<22;i1++)
                                        {
                                            if(count==2)
                                                  break;
                                            if(i9+i0+i2+i3+i4+i5+i6+i7+i8+i1==21)
                                            {    check(i0,i1,i2,i3,i4,i5,i6,i7,i8,i9);break;}
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    t2=time(NULL);
    t=t2-t1;
    printf("\n%d s\n",t);
}


[ 本帖最后由 pink_duo 于 2013-11-21 18:48 编辑 ]
收到的鲜花
  • Susake2013-11-21 19:23 送鲜花  1朵   附言:原来修改帖子了!5555

埋头做牛,抬头做人,低头做狗
2013-11-21 18:06
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
你们俩!!!

无论如何给点思路啊!!!


[fly]存在即是合理[/fly]
2013-11-21 18:14
Susake
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:女儿国的隔壁
等 级:贵宾
威 望:23
帖 子:2288
专家分:6481
注 册:2012-12-14
收藏
得分:0 
回复 4楼 azzbcc
2到9的21次方用快速幂事先处理掉...!
然后相加的事情,可能有数学方法解决或者用一些手段缩小试加范围...坐等楼下!

仰望星空...........不忘初心!
2013-11-21 18:19
Susake
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:女儿国的隔壁
等 级:贵宾
威 望:23
帖 子:2288
专家分:6481
注 册:2012-12-14
收藏
得分:0 
goole一下好像前24位的水仙花都已经被算出来了,且都是具体的数值,【如果是竞赛题】不妨直接用数组存储这些数,然后判断位数直接输出结果提交
【如果纯属算法探讨】见识有限,只能坐等楼下了...!

仰望星空...........不忘初心!
2013-11-21 18:28
天楚
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:楚地
等 级:小飞侠
帖 子:550
专家分:2113
注 册:2013-3-14
收藏
得分:8 
这个应该用到大数

没有哪条路好走,选择了,就坚持下去~~~~
2013-11-21 19:17
韶志
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:斗气大陆
等 级:贵宾
威 望:44
帖 子:2223
专家分:13592
注 册:2013-3-22
收藏
得分:8 
围观看热闹

三十年河东,三十年河西,莫欺少年穷!
2013-11-21 22:46
toofunny
Rank: 4
等 级:业余侠客
帖 子:71
专家分:200
注 册:2012-7-22
收藏
得分:8 
内容不能为空

[ 本帖最后由 toofunny 于 2013-11-22 00:45 编辑 ]
2013-11-22 00:16
鱼儿海
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:77
专家分:194
注 册:2013-8-14
收藏
得分:8 
不懂
2013-11-22 07:11
快速回复:【编程大题】花朵数
数据加载中...
 
   



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

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