變態(tài)的算法題

koolcoy

smilence

A.com

剛才看到有人說(shuō)二叉樹(shù)不給用遞歸，想起來(lái)這個(gè)數(shù)字的變化其實(shí)是可預(yù)期的，譬如把某位的0變成1，那么整個(gè)數(shù)字就是N+1，無(wú)論這個(gè)0在什么位置，他變成1的結(jié)果都是相同的。也就是說(shuō)只有組合相關(guān)性沒(méi)有排列相關(guān)性。又因?yàn)檫@21位數(shù)里面至少要有一位是9（沒(méi)有9的組合不可能大于10^20），所以實(shí)際需要遍歷的總次數(shù)是10個(gè)數(shù)字的20位組合減去9個(gè)以上9的組合{:3_190:}


最暴力的辦法就是寫就是20層循環(huán)，前8層0-9，后12層0-8，最里面別忘了加上一個(gè)9^21。才282529536481次循環(huán)就行了，

KBTiller

沒(méi)有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 發(fā)表于 2011-05-05 18:06

    呃，算錯(cuò)了。。{:3_185:}

l2y3n2

隨便用Python寫了個(gè)窮舉的，用時(shí)間正好3分鐘、Python自帶的大數(shù)運(yùn)算、程序也沒(méi)有優(yōu)化過(guò)。
就是窮舉9、8、7、……、0的個(gè)數(shù)，然后對(duì)比結(jié)果。

用C的話時(shí)間上應(yīng)該還是沒(méi)問(wèn)題的

~$ 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. 
    

復(fù)制代碼

oiacm

用了40多秒
KBTiller 發(fā)表于 2011-05-03 22:07

    想請(qǐng)問(wèn)你具體怎么做的？我想的是對(duì)21位數(shù)進(jìn)行枚舉，但是那樣很崩潰，太慢了

KBTiller

想請(qǐng)問(wèn)你具體怎么做的？我想的是對(duì)21位數(shù)進(jìn)行枚舉，但是那樣很崩潰，太慢了
oiacm 發(fā)表于 2011-05-13 13:10

    基本是按照10樓的那種思路做的
    只對(duì)21位數(shù)的各種組合驗(yàn)算
    提供組合大體上是這樣實(shí)現(xiàn)的

    選擇某位數(shù)字( 1 , 1 );    //選第1位數(shù)字,從1開(kāi)始


void 選擇某位數(shù)字(const int 第幾位 , const  int 起始的數(shù)字 )
{
    if (  第幾位 >  21  ){
        //驗(yàn)算
        return ;
    }   
    for (int 數(shù)字 = 起始的數(shù)字 ; 數(shù)字 < 10 ; 數(shù)字 ++  ){
        選擇某位數(shù)字 ( 第幾位 + 1 , ( 第幾位 == 1 ? 0 : 數(shù)字 )  ) ;  //第2位及以后各位從0開(kāi)始選擇  
    }   
}

   就是第一位1~9。第二位及以后都從0開(kāi)始選數(shù)字，但要保證第二位以后是個(gè)有序的數(shù)字序列

   此外用到了：各個(gè)數(shù)字的21次方事先計(jì)算好，以后查表計(jì)算各個(gè)數(shù)字的21次方的和；9的個(gè)數(shù)不能太多

   我過(guò)幾天會(huì)把詳細(xì)的解法寫出來(lái)
==============================
這個(gè)有點(diǎn)聰明反被聰明誤了
最初，并沒(méi)有考慮第一位不可以為0
但這樣多了一個(gè)21位都為0的情況
為了表達(dá)的更自然
后來(lái)改進(jìn)成第一位不能為0
后面各位有序
但這樣實(shí)際上多了若干重復(fù)的組合（見(jiàn)41樓）

蔡萬(wàn)釗

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

蔡萬(wàn)釗

我給個(gè)思路吧。

不用去算數(shù)。

char N[21]

用循環(huán)的方式。

先計(jì)算 21 一個(gè) 1 的結(jié)果，
然后是  20 個(gè) 1 , 一個(gè) 2 ...
依次類推

在每次便利中，尋找一個(gè)可能的 21 個(gè)數(shù)字的排序使得結(jié)合的大叔是一樣大的。

大數(shù)用 long long 就可以表示了吧？

蔡萬(wàn)釗

利用  99 乘法表，直接查表不通過(guò)計(jì)算。

暈死，我馬上寫一個(gè)，我對(duì)這個(gè)數(shù)字的確切大小非常感興趣。