| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 997 人关注过本帖
标题:21 位花朵数,我求解的方法有问题,请求指点迷津
只看楼主 加入收藏
icanbestrong
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:100
专家分:138
注 册:2013-3-13
结帖率:50%
收藏
已结贴  问题点数:50 回复次数:15 
21 位花朵数,我求解的方法有问题,请求指点迷津
我先说一下我的算法思想,恳求大家帮帮看看出错出,我觉得是在major函数处,但又不知怎么错了。想法是这样的:首先得到1~9的21次方,然后枚举每一位出现的可能,即(1~9),总共有21位,但照我这样最后是不出现应打印出的花朵数。麻烦大家了。花朵数:(1的三次方+3的3次方+5的三次方=135),135就是三位数的花朵数
#include<stdio.h>
#include<stdlib.h>
//得到1~9的21次方
void multi(int a[21],int n){
int i,j;
int temp,nextemp;
for(i=1;i<=21;i++)
{
temp=0;
for(j=0;j<=20;j++)
{
nextemp=(a[j]*n+temp)/10;
a[j]=(a[j]*n+temp)%10;
temp=nextemp;
}
}   
}
//任意2个1~9的21次方相加
void add(int a[21],int b[21],int c[21]){
int temp,nextemp;
int i;
temp=0;
for(i=0;i<=20;i++)
{
nextemp=(a[i]+b[i]+temp)/10;
c[i]=(a[i]+b[i]+temp)%10;
temp=nextemp;
}
}
//判断temp是不是花朵数
int fanhui(int temp[21],int a[9][21]){
int ans[21]={0};   
int question[10]={0};   
int i,j;
for(i=0;i<=20;i++)
for(j=1;j<=9;j++)
if(temp[i]==j)
{
question[j]++;
break;
}
for(i=1;i<=9;i++)
for(j=question[i];j>0;j--)
add(ans,a[i-1],ans);
for(i=0;i<=20;i++)
{
if(ans[i]!=temp[i])
break;
}
if(i==21)
{
for(j=0;j<=20;j++)
printf("%d",temp[j]);
printf("\n");
}
}
//递归产生temp
void major(int n,int temp[21],int a[9][21]){
int come[21];
int i;
for(i=0;i<=20;i++)
come[i]=temp[i];
if(n==21) {
fanhui(temp,a);
return;
}
for(i=0;i<=8;i++)
{
add(temp,a[i],temp);
major(n+1,temp,a);
for(i=0;i<=20;i++)
temp[i]=come[i];
}
}
int main(){
int temp[21]={0};
int a[9][21]={0};
int i,j;
for(i=0;i<=8;i++)
a[i][0]=1;
for(i=0;i<=8;i++)
multi(a[i],i+1);
for(i=0;i<=8;i++)
{
for(j=20;j>=0;j--)
printf("%d",a[i][j]);
printf("\n");
}
major(1,temp,a);
return 0;
}
搜索更多相关主题的帖子: include 
2014-05-26 20:20
vvvcuu
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:12
帖 子:353
专家分:1253
注 册:2014-4-22
收藏
得分:5 
9的21次方太大.

int型已经远远不能满足存储要求, 即使long int型也不能满足要求, 需要实型来存储,但实型一般来说也不会得到精确值. 因为一般来说只能保留到18位左右的有效值,  而9的21次方有21位数.  

不知道C99对各数据类型的有效值是否有修改.

代码测试环境:  WinXP+C-Free5.0.
2014-05-26 20:47
icanbestrong
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:100
专家分:138
注 册:2013-3-13
收藏
得分:0 
我用的是数组存的
2014-05-26 21:26
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:10 
你这个计算N^21次幂的函数就不对  你自己测试了没有

程序代码:
//得到1~9的21次方
void multi(int a[21],int n)
{
    int i,j;
    int flag=0;
    int tmp;
    a[20]=n;
    for(j=0;j<20;j++)   //21次方 去除1
    {
        for(i=20;i>=0;i--)
        {
            tmp=n*a[i]+flag;
            a[i]=tmp %10;
            flag=tmp/10;
        } 
    }
}


[ 本帖最后由 wp231957 于 2014-5-27 09:11 编辑 ]

DO IT YOURSELF !
2014-05-27 08:43
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
你的2个int[]相加运算也不对

程序代码:
//任意2个N的21次方相加
void add(int a[21],int b[21],int c[21])
{
    int tmp;
    int flag=0;
    int i;
    for(i=20;i>=0;i--)
    {
        tmp=a[i]+b[i]+flag;
        c[i]=tmp%10;
        flag=tmp/10;
    }
}


[ 本帖最后由 wp231957 于 2014-5-27 09:06 编辑 ]

DO IT YOURSELF !
2014-05-27 08:57
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
这个课题最关键的地方是:有0-9这10个数字组成的任意21位数  也太多了一些啊  我不会计算  但是应该是指数级别的

DO IT YOURSELF !
2014-05-27 09:05
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
应该是10的21次幂种排列   这啥电脑能跑下来啊

DO IT YOURSELF !
2014-05-27 09:16
Explorerlxz
Rank: 9Rank: 9Rank: 9
来 自:zzu
等 级:蜘蛛侠
威 望:4
帖 子:302
专家分:1032
注 册:2013-4-24
收藏
得分:5 
楼主一点都不严谨,135不是水仙花数,153才是,关于解法参见http://www.
2014-05-27 12:05
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:18 
乱敲出一段代码,仅供参考,因为算法可能有误,而且我对这个算法的效率不是很满意
程序代码:
#include <stdio.h>
#include <string.h>
//#include <stdint.h>
//typedef unsigned uint32_t;

// 21位数,若每位都为9,则其值需要70bits存储,其各位数的21次方和需要71bits存储
// 因此这里用3个32bits的整型来存储

const unsigned pow21[10][3] = {     0,       0,       0
                              ,     0,       0,       1
                              ,     0,       0, 2097152
                              ,     0,     104,60353203
                              ,     0,   43980,46511104
                              ,     0, 4768371,58203125
                              ,     2,19369506,40377856
                              ,    55,85458640,83284007
                              ,   922,33720368,54775808
                              , 10941,89891315,12359209 };

void foo_plus( unsigned a[3], const unsigned b[3] )
{
    unsigned t = a[2]+b[2];
    a[2] = t % 100000000;
    t = a[1]+b[1]+t/100000000;
    a[1] = t % 100000000;
    a[0] = a[0]+b[0]+t/100000000;
}
void foo_minus( unsigned a[3], const unsigned b[3], unsigned n )
{
    unsigned t = 2100000000+a[2]-b[2]*n;
    a[2] = t % 100000000;
    t = 2100000000+a[1]-b[1]*n+t/100000000-21;
    a[1] = t % 100000000;
    a[0] = a[0]-b[0]*n+t/100000000-21;
}

int main()
{
    unsigned num[10] = { 21, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    unsigned sum[3] = { 0, 0, 0 };

    while( num[9] != 21 )
    {
        // next
        if( num[0] != 0 )
        {
            --num[0];
            ++num[1];    foo_plus( sum, pow21[1] );
        }
        else
        {
            size_t idx;
            for( idx=0; num[idx]==0; ++idx );
            num[0]=num[idx]-1;
            foo_minus( sum, pow21[idx], num[idx] );    num[idx]=0;
            foo_plus( sum, pow21[idx+1] );             ++num[idx+1];
        }

        if( sum[0] >= 10000 )
        {
            // 分解
            unsigned num2[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
            for( size_t i=0; i!=3; ++i )
                for( unsigned t=sum[i]; t; t/=10 )
                    ++num2[t%10];

            // 比较
            if( memcmp(num+1,num2+1,sizeof(num)-sizeof(num[0])) == 0 )
                printf( "%u%08u%08u\n", sum[0], sum[1], sum[2] );
        }
    }

    return 0;
}

2014-05-27 13:58
icanbestrong
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:100
专家分:138
注 册:2013-3-13
收藏
得分:0 
回复 6 楼 wp231957
亲,两个功能函数都不会有问题,我早已亲自测试过,至于后面的枚举,我也想到了,就是时间复杂度的问题,我写的程序可以运行,但不出花朵数,就这样
2014-05-27 20:18
快速回复:21 位花朵数,我求解的方法有问题,请求指点迷津
数据加载中...
 
   



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

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