Chinaunix

标题: 变态的算法题 [打印本页]

作者: DNFCF 时间: 2011-04-27 21:00
标题: 变态的算法题
一个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次方之和正好等于这个数本身。
如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。

作者: molin0010 时间: 2011-04-27 22:21
# include <stdio.h>
# include <math.h>

int IsYes(int goal, int len)
{
int i = 0, sum = 0, goal1=goal;
int * pArr;

pArr = (int)malloc(sizeof(int) * len);
while(goal > 10)
{
pArr[i] = goal % 10;
i++;
goal /= 10;
}
pArr[i] = goal;

for(i=0; i<len; i++)
{
sum += pow(pArr[i], len);
}
if(sum == goal1)return 1;
else return 0;
}

int main(void)
{
int len = 3, i = 0;
int LBound = 0, UBound = 0;

scanf("%d", &len);
LBound = pow(10, len-1);
UBound = pow(10, len);

for(i=LBound; i<UBound; i++)
{
if( IsYes(i, len) )printf("%d\n", i);
}

return 0;
}

作者: molin0010 时间: 2011-04-27 22:28
我错了没看到后面的程序的任务是：求N=21时

作者: damcool 时间: 2011-04-28 08:27
大数乘法和加法问题

作者: hellioncu 时间: 2011-04-28 08:44
这个肯定不能死算吧

作者: cokeboL 时间: 2011-04-28 09:25
感觉主要是时间问题吧

作者: noword2k 时间: 2011-04-28 10:11
要先完成一个大数运算库。

作者: cjaizss 时间: 2011-04-28 14:40
我的想法是凑数,8^21已经很小,
7^21已经很小,对于9^21大小都可以忽略.
9肯定是主流
但不能超过9个
于是可以从开始凑
1,2,3,4,5,6,7,8,9个9开始凑

作者: julu99 时间: 2011-04-28 14:49
可以把N=3那肯定是0-3之间，得到的结果，在是N=5之间，在是N=7之间，这个题可以用数学的的思维去想。

作者: A.com 时间: 2011-04-28 17:40
本帖最后由 A.com 于 2011-04-28 17:52 编辑

其实就是0、1、2097152……9^21的组合，要求组合的和是个21位的数字且顺序符合。
先凑够数字，就是21个数之和大于10^20。然后是检测21个元素的集合和这个和的数字集合是否一致
程序需要循环21^21次。。。

作者: pmerofc 时间: 2011-04-28 22:03
提示: 作者被禁止或删除内容自动屏蔽

作者: DNFCF 时间: 2011-04-28 22:04
回复 8# cjaizss

不懂。。。。

作者: DNFCF 时间: 2011-04-28 22:05

回复 DNFCF

硬件环境是什么
pmerofc 发表于 2011-04-28 22:03

硬件可以不考虑，这个主要是考算法。。。。

作者: pmerofc 时间: 2011-04-28 22:07
提示: 作者被禁止或删除内容自动屏蔽

作者: DNFCF 时间: 2011-04-28 22:09

回复 DNFCF

问题是要求3分钟，有的机器快，有的机器慢
pmerofc 发表于 2011-04-28 22:07

老大，你先忽略这个时间限制行不？？先给个算法思路吧。。。。

作者: pmerofc 时间: 2011-04-28 22:13
提示: 作者被禁止或删除内容自动屏蔽

作者: DNFCF 时间: 2011-04-28 22:28

我的想法和10楼差不多

先把 0~9 的21次方算好存起来
然后从 10的20次方开始到 10的21次方-1 穷举计算 ...
pmerofc 发表于 2011-04-28 22:13

问题是数太大了，会溢出的啊？？？

作者: cjaizss 时间: 2011-04-28 22:37

问题是数太大了，会溢出的啊？？？
DNFCF 发表于 2011-04-28 22:28

不是穷举，是凑数。
看看每个数的差距
linux-0gt0:~ # bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
for(i=1;i<=9;i++)
print i^21,"\n"
1
2097152
10460353203
4398046511104
476837158203125
21936950640377856
558545864083284007
9223372036854775808
109418989131512359209

作者: DNFCF 时间: 2011-04-28 22:57

不是穷举，是凑数。
看看每个数的差距
linux-0gt0:~ # bc
bc 1.06
Copyright 1991-1994, 1997, 199 ...
cjaizss 发表于 2011-04-28 22:37

可是在C语言下，好像超过10位就会溢出啊，怎么解决啊？？

作者: KBTiller 时间: 2011-04-29 06:30
本帖最后由 KBTiller 于 2011-04-29 06:40 编辑

可是在C语言下，好像超过10位就会溢出啊，怎么解决啊？？
DNFCF 发表于 2011-04-28 22:57

想办法创造新的“类型”。编程的乐趣之一就是这种创造性。感觉你还没体会到什么是数据结构
手懒，抄段书（自《狂人C》第3章）给你，希望能对你有所启发

1976年，著名的计算机大师、Pascal语言之父Niklaus Wirth提出

算法 + 数据结构 = 程序

（Algorithms + Data Structures = Programs）
……
例题：编程求123456×654321。
……

难道C语言对待如此简单的小学生都会做的算术问题都束手无策吗？倒也不是这样，办法是有的，但需要你自己去想。编程的乐趣大抵在此。

由于本题目问题的核心在于两个较大的数相乘超过了int类型的范围，所以可以考虑把乘数拆成较小的数。比如

123456×654321=（123×103+456）×（654×103+321）

=123×103×（654×103+321）+ 456×（654×103+321）

=123×103×654×103+123×103×321+ 456×654×103+ 456×321

=123×654×106+123×321×103+ 456×654×103+ 456×321

=（123×654）×106+（123×321+ 456×654）×103+ 456×321

如果能分别求出（123×654）、（123×321+ 456×654）、456×321，问题不就解决了吗？而（123×654）、（123×321+ 456×654）、456×321，可以确信，是可以用int类型表示的。

在这种情况下，用一个int变量存储123456或654321是不行的，需要两个，一个用来记录123456或654321的前三位，另一个记录后三位。这种对数据的组织和安排方式，就是所谓的数据结构。尽管这里的还只是一种很粗糙的数据结构。此外还可以发现，设计数据结构首先涉及到的问题恰恰是选择合适的数据类型。

在这种数据结构下的算法就是：首先求出（123×654）、（123×321+ 456×654）、456×321。可以断定积的最后三位是456×321对1000求余的结果，最前面几位是（123×654）+（123×321+ 456×654）/103，中间三位的值为（123×321+ 456×654）%103+456×321/1000。（这些示意性的东西叫伪代码（Pseudocode））

从对算法的描述中还可以发现，积最好用三个int来表示。

所以，所谓的算法无非就是对操作步骤的描述。描述算法的方式有很多，其中之一就是使用自然语言来描述。用C语言描述的算法和数据结构就是C代码。

/*编程求123456*654321*/
#include <stdio.h>
#include <stdlib.h>
#define CS1 123456 //乘数1
#define CS2 654321 //乘数2
#define YQ 1000 //一千
int main(void)
{
int cs1_q3w,cs1_h3w,cs2_q3w,cs2_h3w;//乘数1、乘数2的前3位和后3位
int ji_q,ji_z,ji_h; //积的前、中、后三个部分
cs1_q3w = CS1 / YQ ;
cs1_h3w = CS1 % YQ ;
cs2_q3w = CS2 / YQ ;
cs2_h3w = CS2 % YQ ;
//求出（123×654）、（123×321+ 456×654）、456×321
ji_q = cs1_q3w * cs2_q3w ;
ji_z = cs1_q3w * cs2_h3w + cs1_h3w * cs2_q3w ;
ji_h = cs1_h3w * cs2_h3w ;
//进位处理,注意：次序很重要
ji_q = ji_q + ji_z / YQ ;
ji_z = ji_z % YQ + ji_h / YQ ;
ji_h = ji_h % YQ ;
//输出
printf("%d×%d == %d%d%d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
system("PAUSE");
return 0;
}

复制代码

程序输出

123456×654321 == 80779853376

与程序代码3-5的输出相比，这个结果至少可以说可信度很高，尽管我们还无法确信。

增强对程序正确性信心的方法只有通过测试。由于这段代码对于两个不多于6位的十进制数都应该成立，所以可以选择易于验算的情况运行程序，比如把123456改为100000再运行程序。

然而，很遗憾，程序求100000×654321的结果竟然是

100000×654321 == 654321000

造成这个错误的原因是，代码中ji_z、ji_h表示的都是三位的十进制数，但当它们的值为0时，%d这种格式只输出1个0而不是3个0。改进的办法是把它们对应的%d改成%03d。其中3表示输出三位，0表示如果前面有空格则填充0（可以自己上机对比一下%03d、%3d和%d之间的区别）。

把输出改写为

printf("%d×%d == %d%03d%03d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
之后，可以发现程序求100000×654321的结果是正确的。如果还不放心，可以再找一些数据进行测试。

作者: cjaizss 时间: 2011-04-29 08:59

可是在C语言下，好像超过10位就会溢出啊，怎么解决啊？？
DNFCF 发表于 2011-04-28 22:57

大数运算啊

作者: DNFCF 时间: 2011-04-29 09:38
回复 20# KBTiller

恩，看了很受教，弱弱的问下，大数拆小数有没有神马规律啊？？

作者: DNFCF 时间: 2011-04-29 09:40
回复 20# KBTiller

恩，看了很受教，弱弱的问下，大数拆小数有没有神马规律啊？？

作者: KBTiller 时间: 2011-04-29 11:36

回复 KBTiller

恩，看了很受教，弱弱的问下，大数拆小数有没有神马规律啊？？
DNFCF 发表于 2011-04-29 09:40

没什么规律
构造一个数据结构要结合具体的算法
最主要的原则我认为是能方便地读写

你这个题目
我认为可以用一个数组来模拟一个“大数”（当然这不是最精致的方案）
例如
int dashu[22];
用dashu[0]存个位数
用dashu[1]存十位数
用dashu[2]存百位数
……
建议你先试一下计算9^21再输出(前面有答案便于测试)

作者: koolcoy 时间: 2011-04-29 12:27
回复 24# KBTiller

这种大数表示方法有些低效{:3_189:}

作者: KBTiller 时间: 2011-04-29 12:45
回复 25# koolcoy

是的。主要考虑到楼主的经验不多。
您的方案是？

作者: koolcoy 时间: 2011-04-29 13:16
回复 26# KBTiller

两个64位整数并做一个128位整数使用，或者使用汇编调使用bcd指令

作者: A.com 时间: 2011-04-29 13:47
大数运算的基本原理就是进制，假设某个系统的数据宽度为两位的2进制，那么这个系统对于任何大于3的数来说，都无法直接运算。要想做超过3的运算，可以用2个2位也就是4位来表示数据，就能处理最大值为15的数了。所以要做大数运算，只需要再虚拟出一层x进制就行了。

作者: KBTiller 时间: 2011-04-30 09:34

回复 KBTiller

两个64位整数并做一个128位整数使用，或者使用汇编调使用bcd指令
koolcoy 发表于 2011-04-29 13:16

呵呵，这个当然高效
不过我估计楼主只有小米加步枪，不会有“64位整数”这种原子弹

作者: KBTiller 时间: 2011-04-30 13:40
这个题目的算法其实不难
从根本上来说考察的是构造数据的能力
数据组织的好，往往并不需要什么精妙的算法

作者: KanonInD 时间: 2011-05-01 10:00
本帖最后由 KanonInD 于 2011-05-01 17:39 编辑

大数用 __int128 好了。
http://gcc.gnu.org/onlinedocs/gc ... g_t_005f_005fint128

作者: koolcoy 时间: 2011-05-01 11:05

这个题目的算法其实不难
从根本上来说考察的是构造数据的能力
数据组织的好，往往并不需要什么精妙的算法
KBTiller 发表于 2011-04-30 13:40

你显然低估了这个问题，这个问题的解空间是10^21。我还没找到啥号的剪枝办法{:3_195:}

作者: koolcoy 时间: 2011-05-01 11:16
这个问题的难点还是对10^21的解空间的缩小或者dp优化。大数模拟都是小事情

作者: KBTiller 时间: 2011-05-02 17:01
本帖最后由 KBTiller 于 2011-05-03 10:09 编辑

回复 32# koolcoy

确实，我目前还没想的那么远，只考虑了楼主的“溢出”问题。但我30楼的观点不变
现在看来，10楼A.com 的想法更彻底些
不过“程序需要循环21^21次”我觉得是估计过高了，应该是10^19这个量级

作者: A.com 时间: 2011-05-02 17:28
本帖最后由 A.com 于 2011-05-02 17:31 编辑

0 0
1 1
2 2097152
3 10460353203
4 4398046511104
5 476837158203125
6 21936950640377856
7 558545864083284007
8 9223372036854775808
9 109418989131512359209

复制代码

那么符合条件的数列里，9出现的频度在1-9次。而且，末位数其实是有规律的

作者: KBTiller 时间: 2011-05-02 18:56

末位数其实是有规律的
A.com 发表于 2011-05-02 17:28

这个性质真有趣

作者: KBTiller 时间: 2011-05-03 22:07

449177399146038697307
128468643043731391252
请按任意键继续. . .

复制代码

用了40多秒

作者: KBTiller 时间: 2011-05-03 22:15
27907865009977052567814
35452590104031691935943
27879694893054074471405
28361281321319229463398
21887696841122916288858
请按任意键继续. . .
23位
1分40秒

作者: KBTiller 时间: 2011-05-03 23:02
174088005938065293023722
239313664430041569350093
188451485447897896036875
请按任意键继续. . .
24位
2分27秒

作者: KBTiller 时间: 2011-05-04 17:41
本帖最后由 KBTiller 于 2011-05-19 09:55 编辑

其实就是0、1、2097152……9^21的组合，要求组合的和是个21位的数字且顺序符合。
先凑够数字，就是21个数之 ...
A.com 发表于 2011-04-28 17:40

这个组合的数目很少，我计算的结果是~~620309379690~~ 90135045种
--------------------------------------------------------------------
90135045包含了一些充分的组合，还是大了
应该是 14139189

作者: koolcoy 时间: 2011-05-04 23:35
smilence

作者: A.com 时间: 2011-05-05 17:04
本帖最后由 A.com 于 2011-05-05 17:30 编辑

刚才看到有人说二叉树不给用递归，想起来这个数字的变化其实是可预期的，譬如把某位的0变成1，那么整个数字就是N+1，无论这个0在什么位置，他变成1的结果都是相同的。也就是说只有组合相关性没有排列相关性。又因为这21位数里面至少要有一位是9（没有9的组合不可能大于10^20），所以实际需要遍历的总次数是10个数字的20位组合减去9个以上9的组合{:3_190:}

最暴力的办法就是写就是20层循环，前8层0-9，后12层0-8，最里面别忘了加上一个9^21。才282529536481次循环就行了，

作者: KBTiller 时间: 2011-05-05 18:06

没有9的组合不可能大于10^20

11 * 8^21= 101,457,092,405,402,533,888

作者: A.com 时间: 2011-05-06 08:38

11 * 8^21= 101,457,092,405,402,533,888
KBTiller 发表于 2011-05-05 18:06

呃，算错了。。{:3_185:}

作者: l2y3n2 时间: 2011-05-06 20:14
本帖最后由 l2y3n2 于 2011-05-06 20:16 编辑

随便用Python写了个穷举的，用时间正好3分钟、Python自带的大数运算、程序也没有优化过。
就是穷举9、8、7、……、0的个数，然后对比结果。

用C的话时间上应该还是没问题的

~$ time ./f.py
449177399146038697307
128468643043731391252

real 2m54.915s
user 2m54.871s
sys 0m0.012s

#! /usr/bin/env python
# -*- coding: UTF-8 -*-
def check(value, nums):
tmp = [0] * 10
for c in str(value):
tmp[ord(c) - ord('0')] += 1
for i in range(0, 10):
if tmp[i] != nums[i]:
return False
return True
def action(exps, nums, n, leftn, value, idx):
value += exps[idx] * leftn
nums[idx] = leftn
if len(str(value)) < n:
return
if (idx == 0):
if (check(value, nums)):
print(value)
return
for i in range(0, leftn + 1):
if len(str(value)) <= n:
action(exps, nums, n, leftn - nums[idx], value, idx - 1)
value -= exps[idx]
nums[idx] -= 1
def main(n):
exps = [i ** n for i in range(0, 10)]
nums = [0] * 10
action(exps, nums, n, n, 0, 9)
if __name__ == '__main__':
main(21)

复制代码

作者: oiacm 时间: 2011-05-13 13:10

用了40多秒
KBTiller 发表于 2011-05-03 22:07

想请问你具体怎么做的？我想的是对21位数进行枚举，但是那样很崩溃，太慢了

作者: KBTiller 时间: 2011-05-13 20:32
本帖最后由 KBTiller 于 2011-05-19 10:34 编辑

想请问你具体怎么做的？我想的是对21位数进行枚举，但是那样很崩溃，太慢了
oiacm 发表于 2011-05-13 13:10

基本是按照10楼的那种思路做的
只对21位数的各种组合验算
提供组合大体上是这样实现的

选择某位数字( 1 , 1 ); //选第1位数字,从1开始

void 选择某位数字(const int 第几位 , const  int 起始的数字 )
{
if (  第几位 >  21  ){
      //验算
      return ;
}
for (int 数字 = 起始的数字 ; 数字 < 10 ; 数字 ++  ){
      选择某位数字 ( 第几位 + 1 , ( 第几位 == 1 ? 0 : 数字 )  ) ;  //第2位及以后各位从0开始选择
}
}

就是第一位1~9。第二位及以后都从0开始选数字，但要保证第二位以后是个有序的数字序列

此外用到了：各个数字的21次方事先计算好，以后查表计算各个数字的21次方的和；9的个数不能太多

我过几天会把详细的解法写出来
==============================
这个有点聪明反被聪明误了
最初，并没有考虑第一位不可以为0
但这样多了一个21位都为0的情况
为了表达的更自然
后来改进成第一位不能为0
后面各位有序
但这样实际上多了若干重复的组合（见41楼）

作者: 蔡万钊 时间: 2011-05-14 02:17
晕死，这里哪有用到乘法啊，分明就只有加法。

作者: 蔡万钊 时间: 2011-05-14 02:20
我给个思路吧。

不用去算数。

char N[21]

用循环的方式。

先计算 21 一个 1 的结果，
然后是 20 个 1 , 一个 2 ...
依次类推

在每次便利中，寻找一个可能的 21 个数字的排序使得结合的大叔是一样大的。

大数用 long long 就可以表示了吧？

作者: 蔡万钊 时间: 2011-05-14 02:21
利用 99 乘法表，直接查表不通过计算。

晕死，我马上写一个，我对这个数字的确切大小非常感兴趣。

作者: 蔡万钊 时间: 2011-05-14 02:38
晕死。穷举法都不需要3分钟就跑出来了

我还以为这3分钟时间限制是要多牛逼的算法 ....

看来硬件的发展还是可以解放脑力的啊

作者: 蔡万钊 时间: 2011-05-14 06:02
折腾啊我！！

cai@cai ~/workspace/n21cal $ time ./Debug/n21cal
1732949 种组合
the number is 128468643043731391252

real 0m11.479s
user 0m11.165s
sys 0m0.268s

作者: 蔡万钊 时间: 2011-05-14 06:03
本帖最后由蔡万钊于 2011-05-14 06:32 编辑

/*
============================================================================
Name : n21cal.c
Author :
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
unsigned long h;
unsigned long l;
}bignumber;
bignumber table[10]={
{0,0},
{0UL,1UL},
{0UL,2097152UL},
{0UL,10460353203UL},
{0UL,4398046511104UL},
{0UL,476837158203125UL},
{0UL,21936950640377856UL},
{0UL,558545864083284007UL},
{0UL,9223372036854775808UL},
{0x5UL,0xEE7E56E3721F2929UL},
};
bignumber del(bignumber a, bignumber b)
{
bignumber c= {0,0};
c.l = a.l - b.l;
if(a.l < b.l )
{
a.h --;
// c.l++;
}
c.h = a.h - b.h;
return c;
}
bignumber add(bignumber a, bignumber b)
{
bignumber c= {0,0};
c.l = a.l + b.l;
if( ( (-1UL) - a.l ) < b.l)
c.h ++;
c.h += a.h + b.h;
return c;
}
//获得对应的数字
bignumber get_table( int i)
{
return table[i];
}
bignumber get_n_i(int b , int i )
{
bignumber c = {0};
for(; i >0 ; i--)
c = add(c , get_table(b));
return c;
}
int inline mylog2( unsigned long x)
{
int i;
static unsigned long logtable[64] ={
0x8000000000000000,
0x4000000000000000,
0x2000000000000000,
0x1000000000000000,
0x800000000000000,
0x400000000000000,
0x200000000000000,
0x100000000000000,
0x80000000000000,
0x40000000000000,
0x20000000000000,
0x10000000000000,
0x8000000000000,
0x4000000000000,
0x2000000000000,
0x1000000000000,
0x800000000000,
0x400000000000,
0x200000000000,
0x100000000000,
0x80000000000,
0x40000000000,
0x20000000000,
0x10000000000,
0x8000000000,
0x4000000000,
0x2000000000,
0x1000000000,
0x800000000,
0x400000000,
0x200000000,
0x100000000,
0x80000000,
0x40000000,
0x20000000,
0x10000000,
0x8000000,
0x4000000,
0x2000000,
0x1000000,
0x800000,
0x400000,
0x200000,
0x100000,
0x80000,
0x40000,
0x20000,
0x10000,
0x8000,
0x4000,
0x2000,
0x1000,
0x800,
0x400,
0x200,
0x100,
0x80,
0x40,
0x20,
0x10,
0x8,
0x4,
0x2,
0x1,
};
for( i = 0 ; i < 64 ; i++)
{
if (x & logtable[i]) return i;
}
return -1;
}
bignumber dvi_10(bignumber a)
{
bignumber t;
int tmp = mylog2(a.h);
t.h = ((a.h << tmp) | a.l >> ( 64 - tmp)) / 10 ;
unsigned long yu = ((a.h << tmp) | a.l >> ( 64 - tmp)) % 10;
t.l = (((a.l << tmp )>> tmp) | (yu << (64 - tmp))) / 10;
tmp = mylog2(t.l);
a.h = t.h >> tmp;
a.l = t.l | ( t.h << ( 64 - tmp )) ;
return a;
}
void inline revstr(char *str)
{ //省去一变量, 时间换空间法
char *head = str, *tail = str + strlen(str) -1;
for(; head < tail; *head=*head ^ *tail, *tail=*head ^ *tail, *head=*head++ ^ *tail--);
}
void inline to_str(bignumber n, char N[22])
{
//基本原理是，
// 寻找个位，然后除以 10
// 继续
int cur=0;
do{
bignumber n3=n,n2 = dvi_10(n);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
n3 = del(n3,n2);
N[cur++] = '0' + n3.l;
n = n2;
}while( n.h || n.l );
revstr(N);
}
int inline charcnt(const char *ptr, unsigned char ch)
{
int count = 0;
while(*ptr)
{
if(ch == *ptr)
{
count++;
}
ptr++;
}
return count;
}
int main(void)
{
char N[22]="";
int n0,n1,n2,n3,n4,n5,n6,n7,n8,n9;
for(n9 = 1 ; n9 <= 21 ; n9++)
for(n8 = 0 ; n8 <= 21 - n9 ; n8++)
for(n7 = 0 ; n7 <= 21 -n9 - n8 ; n7++)
for(n6 = 0 ; n6 <= 21 -n9 - n8 -n7 ; n6++)
for(n5 = 0 ; n5 <= 21 -n9 - n8 -n7 -n6; n5++)
for(n4 = 0 ; n4 <= 21 -n9 - n8 -n7 -n6 -n5 ; n4++)
for(n3 = 0 ; n3 <= 21 -n9 - n8 -n7 -n6 -n5 -n4 ; n3++)
for(n2 = 0 ; n2 <= 21 -n9 - n8 -n7 -n6 -n5 -n4 -n3; n2++)
for(n1 = 0 ; n1 <= 21 -n9 - n8 -n7 -n6 -n5 -n4 -n3 -n2; n1++)
{
n0 = 21 - n9 - n8 - n7 - n6 - n5 - n4
- n3 - n2 - n1;
bignumber sum = { 0 };
sum.l = n1;
sum = add(sum, get_n_i(2, n2));
sum = add(sum, get_n_i(3, n3));
sum = add(sum, get_n_i(4, n4));
sum = add(sum, get_n_i(5, n5));
sum = add(sum, get_n_i(6, n6));
sum = add(sum, get_n_i(7, n7));
sum = add(sum, get_n_i(8, n8));
sum = add(sum, get_n_i(9, n9));
static long loop;
++loop;
if(sum.h <= 4)
continue;
//开始校验
// 转化为字符串
to_str(sum, N );
// 统计 0 1 2 3 4 5 6 7 8 9 的个数
if(charcnt(N,'9') == n9)
if(charcnt(N,'8') == n8)
if(charcnt(N,'7') == n7)
if(charcnt(N,'6') == n6)
if(charcnt(N,'5') == n5)
if(charcnt(N,'4') == n4)
if(charcnt(N,'3') == n3)
if(charcnt(N,'2') == n2)
if(charcnt(N,'1') == n1)
{
printf("%ld 种组合\n", loop);
printf("the number is %s\n", N);
}
memset(N,0,22);
}
return EXIT_SUCCESS;
}

复制代码

作者: 蔡万钊 时间: 2011-05-14 06:05
我真 TM 有功夫折腾啊！居然折腾了这么久。
对 KBTiller 表示佩服。

作者: 蔡万钊 时间: 2011-05-14 06:36
奇怪，怎么算都只有一个结果的啊！！！为何我的只能那个算出一个结果来！！！！

作者: KBTiller 时间: 2011-05-14 09:22
回复 55# 蔡万钊

一夜就弄出来了，你写得比我快多了

作者: KBTiller 时间: 2011-05-14 09:23
本帖最后由 KBTiller 于 2011-05-14 09:38 编辑

我给个思路吧。

不用去算数。

char N[21]

用循环的方式。

先计算 21 一个 1 的结果，
然后是 20 个 1 , 一个 2 ...
依次类推

...
蔡万钊发表于 2011-05-14 02:20

这个循环嵌套的深度少
更好

作者: 蔡万钊 时间: 2011-05-15 02:36

这个循环嵌套的深度少
更好
KBTiller 发表于 2011-05-14 09:23

还是嵌套了9层呢！

作者: KBTiller 时间: 2011-05-15 10:49
回复 59# 蔡万钊

已经好多了，我那个嵌套21层

作者: KBTiller 时间: 2011-05-16 08:55
回复 54# 蔡万钊

for(n9 = 1 ; n9 <= 21 ; n9++)

n9 是9的个数吗？如果是的话，这里值得推敲

作者: KBTiller 时间: 2011-05-16 09:05
本帖最后由 KBTiller 于 2011-05-16 09:18 编辑

折腾啊我！！

cai@cai ~/workspace/n21cal $ time ./Debug/n21cal
1732949 种组合
the number is 12 ...
蔡万钊发表于 2011-05-14 06:02

我用类似你的想法做，组合数比你这个高一个量级，14139189

作者: leeews 时间: 2011-05-16 13:17
确实变态

作者: KBTiller 时间: 2011-05-16 14:45

我给个思路吧。

不用去算数。

char N[21]

用循环的方式。

先计算 21 一个 1 的结果，
然后是 ...
蔡万钊发表于 2011-05-14 02:20

按你的办法改进了一下，增加了从小到大输出的功能，不到40秒
你的办法真不错

128468643043731391252
449177399146038697307
请按任意键继续. . .

作者: KBTiller 时间: 2011-05-16 14:48

想请问你具体怎么做的？我想的是对21位数进行枚举，但是那样很崩溃，太慢了
oiacm 发表于 2011-05-13 13:10

容我稍微整理一下，很快就会发出来

作者: 蔡万钊 时间: 2011-05-17 00:26
回复 61# KBTiller

是。貌似有人说要至少一个9 ，没9 是不行的 ~~~

就这样写了。

问题是怎么算都只有一个结果，而不是2个，一定是哪里漏了。

作者: KBTiller 时间: 2011-05-17 00:36
回复 66# 蔡万钊

“至少一个9 ，没9 是不行的”，这个不对

n9应该是 0~9 个，可以没有，最多9个

作者: 蔡万钊 时间: 2011-05-17 00:46
回复 67# KBTiller

好，我修改一下看看。

作者: 蔡万钊 时间: 2011-05-17 00:55
回复 67# KBTiller

不行啊！还是只有一个结果。莫非是我的大数的计算错误了？

作者: KBTiller 时间: 2011-05-17 08:50

回复 KBTiller

不行啊！还是只有一个结果。莫非是我的大数的计算错误了？
蔡万钊发表于 2011-05-17 00:55

用 n9 = 4,n8 = 1,n7 = 4
      n6 = 2,n5 = 0,n4 = 3
      n3 = 3,n2 = 0,n1 = 2
      n0 = 2。（449177399146038697307 ）试一下，也许能发现bug

你的机器sizeof(unsigned long)是多少？我的机器上试不起来

作者: KBTiller 时间: 2011-05-17 12:09
献丑！请大家指正

0_问题.h

/*
一个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次方之和正好等于这个数本身。
如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，
每个数字占一行。因为这个数字很大，
请注意解法时间上的可行性。要求程序在3分钟内运行完毕。
*/
#ifndef WENTI_H
#define WENTI_H
#define CESHI //进行测试
//#define QIUJIE //求解21位问题
#ifdef CESHI //测试
#define JINZHI 10 //十进制
#define WEISHU 3 //3位花朵数
#define N WEISHU //幂次==位数
#endif //CESHI_3
#ifdef QIUJIE //求解
#define JINZHI 10 //十进制
#define WEISHU 21 //位数
#define N WEISHU //幂次==位数
#endif //QIUJIE
#endif // WENTI_H
/*
注：
通过修改符号常量的值，可以得到其他进制或其他位数花朵数问题的解
*/

复制代码

作者: KBTiller 时间: 2011-05-17 12:11
1_MAIN_type.h

#ifndef MAIN_T_H
#define MAIN_T_H
//NOTHING
#endif // MAIN_T_H

复制代码

1_MAIN_function.h

#ifndef MAIN_F_H
#define MAIN_F_H
#include "1_MAIN_type.h"
#include "2_数字组合_function.h" //zuhe_sz()及参数
#include "5_处理结果_function.h" //shuchu_jg()
#include <stdlib.h> //system()
#endif // MAIN_F_H

复制代码

1_MAIN.c

/*
Name:花朵数问题
Author: 键盘农夫
Date: 17-05-11
Description: 一个一般性解法，
适用其他进制（<=10）、其他位数的花朵数求解
*/
#include "1_MAIN_function.h"
#define ANY 0
int main( void )
{
zuhe_sz( ZHUNBEI , ANY ); //进行数字组合<=>验算<=>存储结果
//第一个实参为ZHUNBEI时,第二个实参没有用处
shuchu_jg(); //输出结果,释放内存
system("PAUSE");
return 0;
}
#undef ANY
/*
注：稍微修改一下输出的函数shuchu()，程序也适合10以上进制
*/

复制代码

作者: KBTiller 时间: 2011-05-17 12:13
本帖最后由 KBTiller 于 2011-05-18 11:12 编辑

2_数字组合_type.h

#ifndef ZUHE_T_H
#define ZUHE_T_H
#include "3_组合验算_type.h"
#include "0_问题.h"
#endif // ZUHE_T_H

复制代码

2_数字组合_function.h

#ifndef ZUHE_F_H
#define ZUHE_F_H
#include "2_数字组合_type.h"
#include "3_组合验算_function.h"
#include "4_大数运算_function.h"
extern void zuhe_sz( const int , const int );
//zuhe_sz()的两个特殊参数
#define ZHUNBEI JINZHI
#define WANCHENG 0
#endif // ZUHE_F_H

复制代码

2_数字组合.c

#include "2_数字组合_function.h"
//求"WEISU位数"的各种数字组合
//sz:某一数字，gs:该数字可能选择的最大个数
//sz: ZHUNBEI 进行必要准备
//sz: WANCHENG 组合完成（可以确定0的个数时）
extern void zuhe_sz( const int sz , const int gs )
{
static SHUZI_GESHU_t sj_gs , //实际的个数
gs_sx ; //个数的上限
switch ( sz ) {
case ZHUNBEI:
jisuan_zhunbei( & gs_sx ); //计算准备
zuhe_sz ( sz - 1 , WEISHU ) ;
qing0( & gs_sx ); //对 gs_sx清0
break;
default : //尝试某数字（sz）的各种可能的数目（i）
{
int i ;
for ( i = 0 ;
i <= ( (gs < gs_sx[sz]) ? gs : gs_sx[sz] ) ;
i ++ ){
sj_gs [ sz ] = i ;
zuhe_sz ( sz - 1 , gs - i ) ; //下一个数字
sj_gs [ sz ] = 0 ;
}
}
break;
case WANCHENG:
sj_gs [ sz ] = gs ; //0的个数
jianyan( &sj_gs ) ; //对数字组合验算
sj_gs [ sz ] = 0 ;
break;
}
}

复制代码

作者: KBTiller 时间: 2011-05-17 12:15
3_组合验算_type.h

#ifndef YANSUAN_T_H
#define YANSUAN_T_H
#include "0_问题.h"
#include "6_常用.h"
#include "4_大数运算_type.h"
typedef int SHUZI_GESHU_t[JINZHI] ; //描述各个数字出现个数的类型
// 0的个数，1的个数……JINZHI-1的个数
#endif // YANSUAN_T_H

复制代码

3_组合验算_function.h

#ifndef YANSUAN_F_H
#define YANSUAN_F_H
#include "3_组合验算_type.h"
#include "4_大数运算_function.h"
#include "5_处理结果_function.h"
extern void jisuan_zhunbei( SHUZI_GESHU_t * );
extern void qing0 ( SHUZI_GESHU_t * ) ;
extern void jianyan( SHUZI_GESHU_t * ) ;
#endif // YANSUAN_F_H

复制代码

3_组合验算.c

#include "3_组合验算_function.h"
static DASHU_t sjb[JINZHI][WEISHU]; //数据表
////// 1*0^N,2*0^N,……WEISHU*0^N
////// 1*1^N,2*1^N,……WEISHU*1^N
////// 1*2^N,2*2^N,……WEISHU*2^N
////// ……
////// 1*9^N,2*9^N,……WEISHU*9^N
//////================================================
//检验构成组合的各个数字的N次方之和的数字组合
//是否与原来的组合一致
extern void jianyan( SHUZI_GESHU_t * p_zhsm )
{
DASHU_t he ;
fuzhi ( & he , 0 ) ; //初值为0
int i ;
for( i = 1; i < GESHU(sjb) ; i++){ //i=1, 0的N次幂不用加
if ( (* p_zhsm)[i] == 0 ) //某数字不出现
continue ;
jiaru( & he , sjb[i] + (( * p_zhsm )[i] - 1) ); // 求和
}
if( chaoguo_ws ( & he ) == SHI
|| bugou_ws ( & he ) == SHI ) //位数不符合
return ;
if ( xiangtong ( & he , p_zhsm ) == FOU )//和的组合与原来的组合不同
return ;
jilu_jg( &he );
}
//求各个数字的N次方及其整数倍（1,2，……WEISHU倍）
//同时求出各个数字出现次数的上限存入 * p_zhsx
extern void jisuan_zhunbei( SHUZI_GESHU_t * p_zhsx )
{
int hang , lie ;
for ( hang = 0 ; hang < GESHU( sjb ) ; hang++ ){
qiu_mi ( sjb[hang] , hang , N ) ; //求i的N次幂
for ( lie = 1 ; lie < GESHU( sjb[hang] ) ; lie ++ ) { //WEISHU
cheng ( sjb[hang] + lie , sjb[hang] , lie + 1 ) ;
if ( chaoguo_ws ( sjb[hang] + lie ) == SHI ) //结果超过WEISHU
break ;
}
(* p_zhsx)[hang] = lie ; // 某数字出现次数的上限值
}
}
extern void qing0( SHUZI_GESHU_t * p_zhsx )
{
int *p = * p_zhsx ;
while ( p < * ( p_zhsx + 1 ))
*p++ = 0 ;
}

复制代码

作者: KBTiller 时间: 2011-05-17 12:17
4_大数运算_type.h

#ifndef DASHU_T_H
#define DASHU_T_H
#include "0_问题.h"
#include "6_常用.h"
#include "3_组合验算_type.h"
typedef int DASHU_t[WEISHU] ; //大数类型
#endif // DASHU_T_H

复制代码

4_大数运算_function.h

#ifndef DASHU_F_H
#define DASHU_F_H
#include "4_大数运算_type.h"
#include <stdio.h>
#include "3_组合验算_function.h"
extern void qiu_mi ( DASHU_t * const , const int , int ) ;
extern void fuzhi ( DASHU_t * const , const int ) ;
extern void cheng ( DASHU_t * const , DASHU_t * const , const int );
extern void jiaru ( DASHU_t * const , DASHU_t * const );
extern void shuchu ( DASHU_t * const );
extern void copy_ds( DASHU_t * const , DASHU_t * const ) ;
extern SF xiaoyu ( DASHU_t * const , DASHU_t * const ) ;
extern SF chaoguo_ws ( DASHU_t * const ) ;
extern SF bugou_ws ( DASHU_t * const ) ;
extern SF xiangtong ( DASHU_t * const , SHUZI_GESHU_t * const ) ;
#endif // DASHU_F_H

复制代码

4_大数运算.c

#include "4_大数运算_function.h"
extern void shuchu( DASHU_t * const p_ds )
{
int *w = *p_ds , *t = *(p_ds+1) -1;
int i;
while( t > w && *t == 0) //前面的0不输出
t--;
for ( i = t - w ; i >= 0 ; i-- )
printf("%d" , w[i]);
putchar('\n');
}
extern void copy_ds ( DASHU_t * const p_zd, DASHU_t * const p_qd )
{
int i ;
for (i = 0 ; i < GESHU(*p_zd) ; i++ )
(*p_zd)[i] = (*p_qd)[i] ;
}
//判断*p_he的组合是否与*p_szzh相同
SF xiangtong ( DASHU_t * const p_he , SHUZI_GESHU_t * const p_szzh )
{
SHUZI_GESHU_t szgs ;
int i ;
qing0 ( & szgs ) ;
for (i = 0 ; i < GESHU(*p_he) ; i++ )
szgs[(*p_he)[i]]++;
for(i=0;i<GESHU(szgs);i++)
if(szgs[i]!=((*p_szzh)[i]))
return FOU ;
return SHI;
}
//进位
static void jinwei( DASHU_t * const p_ds)
{
int *q = *p_ds ;
while ( q < *( p_ds + 1) - 1 ){
* ( q + 1 ) += * q / JINZHI ;
* q++ %= JINZHI ;
}
}
//小于
extern SF xiaoyu ( DASHU_t * const p_ds1 , DASHU_t * const p_ds2 )
{
int i;
for( i = GESHU(*p_ds1) - 1 ; i >= 0 ; i -- ){
if( (*p_ds1)[i]<(*p_ds2)[i] )
return SHI ;
if( (*p_ds1)[i]>(*p_ds2)[i] )
return FOU ;
}
return FOU ;
}
//将*p_js累加入*p_he
extern void jiaru( DASHU_t * const p_he , DASHU_t * const p_js)
{
int i;
for(i=0;i<GESHU(*p_he);i++)
(*p_he)[i] += (*p_js)[i];
jinwei(p_he) ;
}
//判断是否超过WEISHU
extern SF chaoguo_ws ( DASHU_t * const p_ds )
{
if( p_ds[1][-1] >= JINZHI ){
return SHI ;
}
return FOU;
}
//判断是否位数不到WEISHU
extern SF bugou_ws ( DASHU_t * const p_ds )
{
if( p_ds[1][-1] == 0 )
return SHI ;
return FOU;
}
//cs2*(*p_cs1)=>(*p_ji)
extern void cheng ( DASHU_t * const p_ji , DASHU_t * const p_cs1 , const int cs2)
{
int *p = *p_ji ,*q = *p_cs1;
while ( p < * ( p_ji + 1) )
*p++ = *q++ * cs2 ;
//进位
jinwei( p_ji );
}
//求i的n次幂，放在 * p_ds 中
extern void qiu_mi ( DASHU_t * const p_ds , const int i , int n )
{
fuzhi ( p_ds , i ) ;
while ( --n > 0 )
cheng ( p_ds , p_ds , i);
}
//赋值，大于JINZHI的数也可以
extern void fuzhi ( DASHU_t * const p_ds , const int i )
{
int *q = *p_ds ;
*q = i ;
while ( q < *( p_ds + 1) - 1){
* ( q + 1 ) = * q / JINZHI ;
* q++ %= JINZHI ;
}
}

复制代码

作者: KBTiller 时间: 2011-05-17 12:19
5_处理结果_type.h

#ifndef JIEGUO_T_H
#define JIEGUO_T_H
#include "0_问题.h"
#include "4_大数运算_type.h"
typedef struct JD{
DASHU_t ds ; //大数
struct JD *xyg ;//下一个
} JIEDIAN_t ; //节点类型
typedef JIEDIAN_t *TOU_t ; //头类型
#endif // JIEGUO_T_H

复制代码

5_处理结果_function.h

#ifndef JIEGUO_F_H
#define JIEGUO_F_H
#include "5_处理结果_type.h"
#include "4_大数运算_function.h"
#include <stdio.h>
#include <stdlib.h>
extern void jilu_jg( DASHU_t * );
extern void shuchu_jg ( void );
#endif // JIEGUO_F_H

复制代码

5_处理结果.c

#include "5_处理结果_function.h"
static TOU_t tou = NULL ;
static void jia_jd ( TOU_t ,TOU_t *);
static void shifang_nc(TOU_t);
static void shifang_nc( TOU_t p )
{
TOU_t q ;
if( p == NULL )
return ;
q = p->xyg ;
free(p);
shifang_nc( q );
}
extern void jilu_jg( DASHU_t * p_ds )
{
TOU_t p_jd ;
if( (p_jd = malloc( sizeof (JIEDIAN_t )) ) == NULL ){
shifang_nc( tou );
puts("无法记录结果，程序退出");
exit ( ! EXIT_SUCCESS ) ;
}
copy_ds ( & p_jd->ds , p_ds ) ; //复制
jia_jd ( p_jd , & tou ); //加入链表(p_jd,tou)
}
//按照一定次序加入节点
static void jia_jd ( TOU_t xjd, TOU_t *p_xyg )
{
if( *p_xyg == NULL ||
( xiaoyu ( & xjd -> ds , &(*p_xyg)->ds )) == SHI ){/* 小于 */
xjd->xyg = *p_xyg ;
*p_xyg = xjd ;
return ;
}
jia_jd ( xjd , &(*p_xyg)->xyg ) ;
}
//输出结果，之后释放内存
extern void shuchu_jg( void )
{
TOU_t temp = tou ;
while ( temp != NULL ){
shuchu(&temp->ds);
temp = temp->xyg ;
}
shifang_nc( tou );
tou = NULL ;
}

复制代码

作者: KBTiller 时间: 2011-05-17 12:21
6_常用.h

//我编程常用的成语和俚语
#ifndef CHANGYONG_H
#define CHANGYONG_H
typedef enum { FOU , SHI } SF ;
#define GESHU(A) ((sizeof (A)) / (sizeof (*(A))) )
#endif // CHANGYONG_H

复制代码

作者: KBTiller 时间: 2011-05-17 12:35
从蔡万钊、A.com、koolcoy (娶妻求贤)网友的发言中受到了许多启发，在此致谢！

作者: koolcoy 时间: 2011-05-17 14:26
好多年没看过用拼音写的程序了，怎么看怎么囧，有空了再来研究{:3_196:}

作者: 蔡万钊 时间: 2011-05-17 20:30
回复 70# KBTiller

我是 AMD64 的 Gentoo 系统。

作者: koolcoy 时间: 2011-05-18 10:31
昨晚想了一下这个问题，有这么一个优化方法：
将1^21 * 1, 1^21 * 2, 1^21 * 3 ... 1^21 * 21, 2^21 * 1, 2^21 * 2 ... 2^21 * 21, .... 9^21 * 21一共189个数保存起来。于是原问题抓换成从这189个数中选最多9个数出来，使得他们的和满足一定的条件。整个问题的解空间小于21^9 ，这个数字大概是5000亿，采用深搜，再根据位数为21这个条件剪一下枝，最终的解空间应该不会超过100亿。

这种算法的复杂度是O(N^9)，而不是O(9^N)，N为位数。

作者: KBTiller 时间: 2011-05-18 10:50
本帖最后由 KBTiller 于 2011-05-18 11:16 编辑

回复 81# koolcoy

9^21不需要那么多。位数为21应该可以减去两支

作者: koolcoy 时间: 2011-05-18 19:14
用python实现了一下这个算法
测试结果：
[witch@localhost ~]$ for i in 21 23 24; do
> time ./flower.py $i
> done
449177399146038697307
128468643043731391252

real 1m33.091s
user 1m31.283s
sys    0m0.123s
27879694893054074471405
27907865009977052567814
35452590104031691935943
21887696841122916288858
28361281321319229463398

real 2m49.607s
user 2m47.742s
sys    0m0.164s
174088005938065293023722
188451485447897896036875
239313664430041569350093

real 3m40.527s
user 3m38.041s
sys    0m0.160s

#!/usr/bin/env python
import sys
LENGTH = int(sys.argv[1])
TABLE = tuple([tuple([x * (i**LENGTH) for x in range(1, LENGTH + 1)])
for i in range(1, 10)])
MAX = 10 ** LENGTH - 1
MIN = 10 ** (LENGTH - 1)
def isValidNumber(number, digit):
tmp = [0] * 10
for ch in str(number):
tmp[ord(ch) - ord('0')] += 1
tmp.pop(0)
return tmp == digit
def search(left, index, partialSum, digit):
if index < 8 and left > 0:
search(left, index + 1, partialSum, digit)
for count in range(1, left + 1):
digit[index] = count
value = TABLE[index][count - 1]
sum = partialSum + value
if sum > MAX:
break
if sum > MIN:
if isValidNumber(sum, digit):
print sum
if index < 8 and left > count:
search(left - count, index + 1, sum, digit)
digit[index] = 0
def main():
digit = [0] * 9
search(LENGTH, 0, 0, digit)
if __name__ == "__main__":
main()

复制代码

作者: koolcoy 时间: 2011-05-18 20:02
[witch@localhost ~]$ time ./flower.py 29
23866716435523975980390369295
14607640612971980372614873089
19008174136254279995012734740
19008174136254279995012734741

real 15m38.757s
user 15m0.449s
sys 0m0.333s

作者: believetruelove 时间: 2011-05-18 20:41
先mark一下，今天加班太累了。

作者: koolcoy 时间: 2011-05-18 22:42
又用C++实现了一下这个算法，结果大大地出乎我的意料{:3_189:}

witch:~/Documents/workspace/Flower$ time ./a.out 21
449177399146038697307
128468643043731391252

real 0m9.627s
user 0m9.582s
sys 0m0.008s
witch:~/Documents/workspace/Flower$ time ./a.out 24
174088005938065293023722
188451485447897896036875
239313664430041569350093

real 0m22.139s
user 0m22.119s
sys 0m0.006s

#include <cstdio>
#include <cstring>
#include <cstdlib>
template<int LENGTH>
class Integer {
typedef unsigned int U32;
typedef unsigned long long U64;
public:
Integer() {
for (int i = 0; i < LENGTH; ++i) {
data[i] = 0;
}
}
Integer(U32 that) {
copy(that);
}
const Integer& operator = (U32 that) {
copy(that);
return *this;
}
const Integer& operator += (const Integer& that) {
int carry = 0;
for (int i = 0; i < LENGTH; ++i) {
data[i] += that.data[i] + carry;
if (data[i] > BASE) {
carry = data[i] / BASE;
data[i] = data[i] % BASE;
} else {
carry = 0;
}
}
return *this;
}
const Integer& operator *= (U32 that) {
U64 carry = 0;
for (int i = 0; i < LENGTH; ++i) {
U64 tmp = (U64)data[i] * (U64)that + carry;
if (tmp > BASE) {
carry = tmp / BASE;
data[i] = tmp % BASE;
} else {
carry = 0;
data[i] = tmp;
}
}
return *this;
}
Integer operator + (const Integer& that) const {
Integer tmp = *this;
return tmp += that;
}
Integer operator * (U32 that) const {
Integer tmp = *this;
return tmp *= that;
}
bool operator < (const Integer& that) const {
for (int i = LENGTH - 1; i >= 0; --i) {
if (data[i] < that.data[i]) {
return true;
} else if (data[i] > that.data[i]) {
return false;
}
}
return false;
}
bool operator > (const Integer& that) const {
return std::memcmp(data, that.data, sizeof(data)) != 0
&& !(*this < that);
}
void validate(char digit[9]) const {
char decimal[LENGTH * WIDTH + 1];
toString(decimal);
char actual[10] = {0};
for (int i = 0; i < WIDTH * LENGTH; ++i) {
++actual[decimal[i] - '0'];
}
if (std::memcmp(actual + 1, digit, 9) == 0) {
output(decimal);
}
}
void toString(char* decimal) const {
for (int i = LENGTH - 1; i >= 0; --i) {
std::sprintf(decimal + WIDTH * (LENGTH - 1 - i), "%09d", data[i]);
}
decimal[LENGTH * WIDTH] = 0;
}
void show() const {
char decimal[LENGTH * WIDTH + 1];
toString(decimal);
printf("%s\n", decimal);
}
private:
enum {
BASE = 1000000000, /* This is 10^9 */
WIDTH = 9
};
U32 data[LENGTH];
void copy(U32 that) {
data[0] = that % BASE;
data[1] = that / BASE;
for (int i = 2; i < LENGTH; ++i) {
data[i] = 0;
}
}
static void output(const char* decimal) {
int i = 0;
while (decimal[i] == '0') {
++i;
}
printf("%s\n", decimal + i);
}
};
typedef Integer<3> Bigint;
Bigint MIN;
Bigint MAX;
Bigint** TABLE;
void createSumTable(int length) {
TABLE = new Bigint*[9];
for (int i = 0; i < 9; ++i) {
TABLE[i] = new Bigint[length];
TABLE[i][0] = i + 1;
for (int j = 1; j < length; ++j) {
TABLE[i][0] *= (i + 1);
}
for (int j = 1; j < length; ++j) {
TABLE[i][j] = TABLE[i][0] * (j + 1);
}
}
}
void initialize(int length) {
MIN = 10;
for (int i = 0; i < length - 2; ++i) {
MIN *= 10;
}
MAX = MIN * 10;
createSumTable(length);
}
void search(int left, int index, Bigint partialSum, char* digit) {
if (index < 8 && left > 0) {
search(left, index + 1, partialSum, digit);
}
for (int count = 1; count < left + 1; ++count) {
digit[index] = count;
Bigint sum = partialSum + TABLE[index][count - 1];
if (sum > MAX) {
break;
}
if (sum > MIN) {
sum.validate(digit);
}
if (index < 8 && left > count) {
search(left - count, index + 1, sum, digit);
}
}
digit[index] = 0;
}
int main(int argc, char** argv) {
int length = 0;
if (argc != 2 || sscanf(argv[1], "%d", &length) != 1 || length <= 0) {
std::fprintf(stderr, "Usage: %s <length>\n", argv[0]);
}
initialize(length);
char* digit = (char*)std::calloc(length, 1);
search(length, 0, Bigint(0), digit);
return 0;
}

复制代码

作者: koolcoy 时间: 2011-05-18 22:49
改一行代码：typedef Integer<4> Bigint
{:3_189:}
witch:~/Documents/workspace/Flower$ time ./a.out 31
1927890457142960697580636236639
2309092682616190307509695338915
1145037275765491025924292050346

real 2m55.434s
user 2m52.737s
sys 0m0.200s

作者: koolcoy 时间: 2011-05-18 23:55
本帖最后由 koolcoy 于 2011-05-18 23:59 编辑

把sprintf调用去掉后竟然{:3_182:}{:3_182:}{:3_190:}{:3_190:}

witch:~/Documents/workspace/Flower$ time ./a.out 21
449177399146038697307
128468643043731391252

real 0m2.424s
user 0m2.030s
sys 0m0.003s
witch:~/Documents/workspace/Flower$ time ./a.out 31
1927890457142960697580636236639
2309092682616190307509695338915
1145037275765491025924292050346

real 0m26.691s
user 0m26.639s
sys 0m0.020s

#include <cstdio>
#include <cstring>
#include <cstdlib>
template<int LENGTH>
class Integer {
typedef unsigned int U32;
typedef unsigned long long U64;
public:
Integer() {
for (int i = 0; i < LENGTH; ++i) {
data[i] = 0;
}
}
Integer(U32 that) {
copy(that);
}
const Integer& operator = (U32 that) {
copy(that);
return *this;
}
const Integer& operator += (const Integer& that) {
int carry = 0;
for (int i = 0; i < LENGTH; ++i) {
data[i] += that.data[i] + carry;
if (data[i] > BASE) {
carry = data[i] / BASE;
data[i] = data[i] % BASE;
} else {
carry = 0;
}
}
return *this;
}
const Integer& operator *= (U32 that) {
U64 carry = 0;
for (int i = 0; i < LENGTH; ++i) {
U64 tmp = (U64)data[i] * (U64)that + carry;
if (tmp > BASE) {
carry = tmp / BASE;
data[i] = tmp % BASE;
} else {
carry = 0;
data[i] = tmp;
}
}
return *this;
}
Integer operator + (const Integer& that) const {
Integer tmp = *this;
return tmp += that;
}
Integer operator * (U32 that) const {
Integer tmp = *this;
return tmp *= that;
}
bool operator > (const Integer& that) const {
for (int i = LENGTH - 1; i >= 0; --i) {
if (data[i] > that.data[i]) {
return true;
} else if (data[i] < that.data[i]) {
return false;
}
}
return false;
}
bool operator < (const Integer& that) const {
return std::memcmp(data, that.data, sizeof(data)) != 0
&& !(*this > that);
}
void validate(char digit[9]) const {
char decimal[LENGTH * WIDTH + 1];
toString(decimal);
char actual[10] = {0};
for (int i = 0; i < WIDTH * LENGTH; ++i) {
++actual[decimal[i] - '0'];
}
if (std::memcmp(actual + 1, digit, 9) == 0) {
output(decimal);
}
}
void toString(char* decimal) const {
for (int i = 0; i < LENGTH; ++i) {
convertChunk(data[LENGTH - i - 1], decimal + WIDTH * i);
}
decimal[LENGTH * WIDTH] = 0;
}
private:
enum {
BASE = 1000000000, /* This is 10^9 */
WIDTH = 9
};
U32 data[LENGTH];
static void output(const char* decimal) {
int i = 0;
while (decimal[i] == '0') {
++i;
}
printf("%s\n", decimal + i);
}
static void convertChunk(U32 digit, char* decimal) {
for (int i = 0; i < WIDTH; ++i) {
decimal[WIDTH - 1 - i] = digit % 10 + '0';
digit /= 10;
}
}
void copy(U32 that) {
data[0] = that % BASE;
data[1] = that / BASE;
for (int i = 2; i < LENGTH; ++i) {
data[i] = 0;
}
}
};
typedef Integer<SIZE> Bigint;
Bigint MIN;
Bigint MAX;
Bigint** TABLE;
void createSumTable(int length) {
TABLE = new Bigint*[9];
for (int i = 0; i < 9; ++i) {
TABLE[i] = new Bigint[length];
TABLE[i][0] = i + 1;
for (int j = 1; j < length; ++j) {
TABLE[i][0] *= (i + 1);
}
for (int j = 1; j < length; ++j) {
TABLE[i][j] = TABLE[i][0] * (j + 1);
}
}
}
void initialize(int length) {
MIN = 10;
for (int i = 0; i < length - 2; ++i) {
MIN *= 10;
}
MAX = MIN * 10;
createSumTable(length);
}
void search(int left, int index, Bigint partialSum, char* digit) {
if (index < 8 && left > 0) {
search(left, index + 1, partialSum, digit);
}
for (int count = 1; count < left + 1; ++count) {
digit[index] = count;
Bigint sum = partialSum + TABLE[index][count - 1];
if (sum > MAX) {
break;
}
if (sum > MIN) {
sum.validate(digit);
}
if (index < 8 && left > count) {
search(left - count, index + 1, sum, digit);
}
}
digit[index] = 0;
}
int main(int argc, char** argv) {
int length = 0;
if (argc != 2 || sscanf(argv[1], "%d", &length) != 1 || length <= 0) {
std::fprintf(stderr, "Usage: %s <length>\n", argv[0]);
}
initialize(length);
char* digit = (char*)std::calloc(length, 1);
search(length, 0, Bigint(0), digit);
return 0;
}

复制代码

作者: KBTiller 时间: 2011-05-19 09:26
只要是提供组合数的解法
各种方案的解空间是一样大的

但是
for(n9 = 1 ; n9 <= 21 ; n9++)
for(n8 = 0 ; n8 <= 21 - n9 ; n8++)
……
方案对所谓的“剪枝”可能更好写

作者: koolcoy 时间: 2011-05-19 09:48
回复 89# KBTiller

显然不一样，按这种方法穷举的话，其复杂度是O(N^9)，如果按各个数位上的数字来枚举的话，复杂度O(9^N)，一个是多项式级的复杂度，另外一个是指数级的复杂度。复杂度跟解空间是等价的。

作者: KBTiller 时间: 2011-05-19 09:52
本帖最后由 KBTiller 于 2011-05-19 09:57 编辑

回复 90# koolcoy

怎么会呢？21位数的各种组合的数目是一定的。这个值可以精确求出，14139189
当然，我也赞同嵌套的层数越少越好。但组合的总数目是一样的

作者: KBTiller 时间: 2011-05-19 09:53
回复 90# koolcoy

“如果按各个数位上的数字来枚举的话”，按照10楼得那种枚举方法，总数并不多

作者: koolcoy 时间: 2011-05-19 10:09
两种算法的组合数是不一样的，这两种算法有着本质的区别。
如果按照“各个数位上的数字来枚举”的话，即10楼的算法，数字 123XXXX和321XXXX是两种不同的情况，需要计算两次。
如果按照“1出现的次数为n1，2出现的次数n2，3出现的次数为n3...”这种方法来枚举的话123XXXX和321XXXX是同一种情况，只需要计算一次。

作者: KBTiller 时间: 2011-05-19 10:13
不，10楼的算法提到了“顺序符合”，即“有序”，这个很重要
123XXXX和321XXXX不可能都出现

作者: koolcoy 时间: 2011-05-19 10:40
回复 94# KBTiller

但是有个问题，按照10楼得算法，当你验证后发现123XXXX不满足条件，怎么知道321XXXX是否满足条件呢？如果不知道的话，那么你就还要验证321XXXX是否满足条件。也就是说对于123XXXX和321XXXX这两个数字你需要验证两次。但是按照我的那种算法，如果发现123XXXX不满足条件后，我就可以肯定321XXXX不满足条件。

ps: 对于21位的数字，俺已经突破1.4秒了{:3_203:}

作者: KBTiller 时间: 2011-05-19 10:53
回复 95# koolcoy

“123XXXX不满足条件，怎么知道321XXXX是否满足条件呢？”
和你那种是一样的
用123XXXX计算出各位数字N次方的和并统计各数字出现的次数
然后检查“各位数字N次方的和”的各个数字出现的次数与“123XXXX“的“各数字出现的次数”是否一致

作者: KBTiller 时间: 2011-05-19 10:55
回复 95# koolcoy

对于21位的数字，俺已经突破1.4秒了

可喜可贺！（不过不知道硬件环境是否一致）
我后面也准备改进一下，看看能提高多少

作者: koolcoy 时间: 2011-05-19 11:09
回复 97# KBTiller

Pentium(R) Dual-Core CPU E5700 @ 3.00GHz 32位cygwin

作者: xxw19840406 时间: 2011-06-15 20:28
128468643043731391252
449177399146038697307

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)