变态的算法题

koolcoy

smilence

A.com

刚才看到有人说二叉树不给用递归，想起来这个数字的变化其实是可预期的，譬如把某位的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

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

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

A.com

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

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

l2y3n2

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

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

~$ time ./f.py
449177399146038697307
128468643043731391252

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

1. 
   
2. #! /usr/bin/env python
   
3. # -*- coding: UTF-8 -*-
   
4. 
   
5. def check(value, nums):
   
6.     tmp = [0] * 10
   
7.     for c in str(value):
   
8.         tmp[ord(c) - ord('0')] += 1
   
9.     for i in range(0, 10):
   
10.         if tmp[i] != nums[i]:
    
11.             return False
    
12.     return True
    
13. 
    
14. 
    
15. def action(exps, nums, n, leftn, value, idx):
    
16.     value += exps[idx] * leftn
    
17.     nums[idx] = leftn
    
18.     if len(str(value)) < n:
    
19.         return
    
20. 
    
21.     if (idx == 0):
    
22.         if (check(value, nums)):
    
23.             print(value)
    
24.         return
    
25. 
    
26.     for i in range(0, leftn + 1):
    
27.         if len(str(value)) <= n:
    
28.             action(exps, nums, n, leftn - nums[idx], value, idx - 1)
    
29.         value -= exps[idx]
    
30.         nums[idx] -= 1
    
31. 
    
32. 
    
33. def main(n):
    
34.     exps = [i ** n for i in range(0, 10)]
    
35.     nums = [0] * 10
    
36.     action(exps, nums, n, n, 0, 9)
    
37. 
    
38. 
    
39. if __name__ == '__main__':
    
40.     main(21)
    
41. 
    
42. 
    

复制代码

oiacm

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

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

KBTiller

想请问你具体怎么做的？我想的是对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楼）

蔡万钊

晕死，这里哪有用到乘法啊，分明就只有加法。

蔡万钊

我给个思路吧。

不用去算数。

char N[21]

用循环的方式。

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

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

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

蔡万钊

利用  99 乘法表，直接查表不通过计算。

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