變態(tài)的算法題

KBTiller

回復(fù) 90# koolcoy


    “如果按各個(gè)數(shù)位上的數(shù)字來(lái)枚舉的話”，按照10樓得那種枚舉方法，總數(shù)并不多

koolcoy

兩種算法的組合數(shù)是不一樣的，這兩種算法有著本質(zhì)的區(qū)別。
如果按照“各個(gè)數(shù)位上的數(shù)字來(lái)枚舉”的話，即10樓的算法，數(shù)字 123XXXX和321XXXX是兩種不同的情況，需要計(jì)算兩次。
如果按照“1出現(xiàn)的次數(shù)為n1，2出現(xiàn)的次數(shù)n2，3出現(xiàn)的次數(shù)為n3...”這種方法來(lái)枚舉的話123XXXX和321XXXX是同一種情況，只需要計(jì)算一次。

KBTiller

不，10樓的算法提到了“順序符合”，即“有序”，這個(gè)很重要
123XXXX和321XXXX不可能都出現(xiàn)

koolcoy

回復(fù) 94# KBTiller

但是有個(gè)問題，按照10樓得算法，當(dāng)你驗(yàn)證后發(fā)現(xiàn)123XXXX不滿足條件，怎么知道321XXXX是否滿足條件呢？如果不知道的話，那么你就還要驗(yàn)證321XXXX是否滿足條件。也就是說(shuō)對(duì)于123XXXX和321XXXX這兩個(gè)數(shù)字你需要驗(yàn)證兩次。但是按照我的那種算法，如果發(fā)現(xiàn)123XXXX不滿足條件后，我就可以肯定321XXXX不滿足條件。

ps: 對(duì)于21位的數(shù)字，俺已經(jīng)突破1.4秒了{(lán):3_203:}

KBTiller

回復(fù) 95# koolcoy


    “123XXXX不滿足條件，怎么知道321XXXX是否滿足條件呢？”
   和你那種是一樣的
   用123XXXX計(jì)算出各位數(shù)字N次方的和并統(tǒng)計(jì)各數(shù)字出現(xiàn)的次數(shù)
   然后檢查“各位數(shù)字N次方的和”的各個(gè)數(shù)字出現(xiàn)的次數(shù)與“123XXXX“的“各數(shù)字出現(xiàn)的次數(shù)”是否一致

KBTiller

回復(fù) 95# koolcoy


   

對(duì)于21位的數(shù)字，俺已經(jīng)突破1.4秒了

    可喜可賀�。ú贿^(guò)不知道硬件環(huán)境是否一致）
    我后面也準(zhǔn)備改進(jìn)一下，看看能提高多少

koolcoy

回復(fù) 97# KBTiller

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

xxw19840406

128468643043731391252
449177399146038697307