亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

<button id="je1ka"></button>

<samp id="je1ka"></samp>

Chinaunix

標(biāo)題: 變態(tài)的算法題 [打印本頁]

---

作者: DNFCF    時(shí)間: 2011-04-27 21:00
標(biāo)題: 變態(tài)的算法題
一個(gè)N位的十進(jìn)制正整數(shù)，如果它的每個(gè)位上的數(shù)字的N次方的和等于這個(gè)數(shù)本身，則稱其為花朵數(shù)。
例如：
當(dāng)N=3時(shí)，153就滿足條件，因?yàn)?1^3 + 5^3 + 3^3 = 153，這樣的數(shù)字也被稱為水仙花數(shù)（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
當(dāng)N=4時(shí)，1634滿足條件，因?yàn)?1^4 + 6^4 + 3^4 + 4^4 = 1634。
當(dāng)N=5時(shí)，92727滿足條件。
實(shí)際上，對N的每個(gè)取值，可能有多個(gè)數(shù)字滿足條件。

程序的任務(wù)是：求N=21時(shí)，所有滿足條件的花朵數(shù)。注意：這個(gè)整數(shù)有21位，它的各個(gè)位數(shù)字的21次方之和正好等于這個(gè)數(shù)本身。
如果滿足條件的數(shù)字不只有一個(gè)，請從小到大輸出所有符合條件的數(shù)字，每個(gè)數(shù)字占一行。因?yàn)檫@個(gè)數(shù)字很大，請注意解法時(shí)間上的可行性。要求程序在3分鐘內(nèi)運(yùn)行完畢。

---

作者: molin0010    時(shí)間: 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    時(shí)間: 2011-04-27 22:28
我錯(cuò)了  沒看到后面的 程序的任務(wù)是：求N=21時(shí)

---

作者: damcool    時(shí)間: 2011-04-28 08:27
大數(shù)乘法和加法問題

---

作者: hellioncu    時(shí)間: 2011-04-28 08:44
這個(gè)肯定不能死算吧

---

作者: cokeboL    時(shí)間: 2011-04-28 09:25
感覺主要是時(shí)間問題吧

---

作者: noword2k    時(shí)間: 2011-04-28 10:11
要先完成一個(gè)大數(shù)運(yùn)算庫。

---

作者: cjaizss    時(shí)間: 2011-04-28 14:40
我的想法是湊數(shù),8^21已經(jīng)很小,
7^21已經(jīng)很小,對于9^21大小都可以忽略.
9肯定是主流
但不能超過9個(gè)
于是可以從開始湊
1,2,3,4,5,6,7,8,9個(gè)9開始湊

---

作者: julu99    時(shí)間: 2011-04-28 14:49
可以把N=3那肯定是0-3之間，得到的結(jié)果，在是N=5之間，在是N=7之間，這個(gè)題可以用數(shù)學(xué)的的思維去想。

---

作者: A.com    時(shí)間: 2011-04-28 17:40


其實(shí)就是0、1、2097152……9^21的組合，要求組合的和是個(gè)21位的數(shù)字且順序符合。
先湊夠數(shù)字，就是21個(gè)數(shù)之和大于10^20。然后是檢測21個(gè)元素的集合和這個(gè)和的數(shù)字集合是否一致
程序需要循環(huán)21^21次。。。

---

作者: pmerofc    時(shí)間: 2011-04-28 22:03
提示: 作者被禁止或刪除 內(nèi)容自動(dòng)屏蔽

---

作者: DNFCF    時(shí)間: 2011-04-28 22:04
回復(fù) 8# cjaizss


    不懂。。。。

---

作者: DNFCF    時(shí)間: 2011-04-28 22:05

回復(fù)  DNFCF


      硬件環(huán)境是什么
pmerofc 發(fā)表于 2011-04-28 22:03

    硬件可以不考慮，這個(gè)主要是考算法。。。。

---

作者: pmerofc    時(shí)間: 2011-04-28 22:07
提示: 作者被禁止或刪除 內(nèi)容自動(dòng)屏蔽

---

作者: DNFCF    時(shí)間: 2011-04-28 22:09

回復(fù)  DNFCF


    問題是要求3分鐘，有的機(jī)器快，有的機(jī)器慢
pmerofc 發(fā)表于 2011-04-28 22:07

    老大，你先忽略這個(gè)時(shí)間限制行不？？先給個(gè)算法思路吧。。。。

---

作者: pmerofc    時(shí)間: 2011-04-28 22:13
提示: 作者被禁止或刪除 內(nèi)容自動(dòng)屏蔽

---

作者: DNFCF    時(shí)間: 2011-04-28 22:28

我的想法和10樓差不多

先把 0~9 的21次方算好存起來
然后從 10的20次方開始 到 10的21次方-1 窮舉 計(jì)算 ...
pmerofc 發(fā)表于 2011-04-28 22:13

    問題是數(shù)太大了，會(huì)溢出的��？？？

---

作者: cjaizss    時(shí)間: 2011-04-28 22:37

問題是數(shù)太大了，會(huì)溢出的��？？？
DNFCF 發(fā)表于 2011-04-28 22:28

不是窮舉，是湊數(shù)。
看看每個(gè)數(shù)的差距
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    時(shí)間: 2011-04-28 22:57

不是窮舉，是湊數(shù)。
看看每個(gè)數(shù)的差距
linux-0gt0:~ # bc
bc 1.06
Copyright 1991-1994, 1997, 199 ...
cjaizss 發(fā)表于 2011-04-28 22:37

    可是在C語言下，好像超過10位就會(huì)溢出啊，怎么解決�。�？

---

作者: KBTiller    時(shí)間: 2011-04-29 06:30

可是在C語言下，好像超過10位就會(huì)溢出啊，怎么解決��？？
DNFCF 發(fā)表于 2011-04-28 22:57

    想辦法創(chuàng)造新的“類型”。編程的樂趣之一就是這種創(chuàng)造性。感覺你還沒體會(huì)到什么是數(shù)據(jù)結(jié)構(gòu)
    手懶，抄段書（自《狂人C》第3章）給你，希望能對你有所啟發(fā)

1976年，著名的計(jì)算機(jī)大師、Pascal語言之父Niklaus Wirth提出

       算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序

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

難道C語言對待如此簡單的小學(xué)生都會(huì)做的算術(shù)問題都束手無策嗎？倒也不是這樣，辦法是有的，但需要你自己去想。編程的樂趣大抵在此。

由于本題目問題的核心在于兩個(gè)較大的數(shù)相乘超過了int類型的范圍，所以可以考慮把乘數(shù)拆成較小的數(shù)。比如

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類型表示的。

在這種情況下，用一個(gè)int變量存儲123456或654321是不行的，需要兩個(gè)，一個(gè)用來記錄123456或654321的前三位，另一個(gè)記錄后三位。這種對數(shù)據(jù)的組織和安排方式，就是所謂的數(shù)據(jù)結(jié)構(gòu)。盡管這里的還只是一種很粗糙的數(shù)據(jù)結(jié)構(gòu)。此外還可以發(fā)現(xiàn)，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)首先涉及到的問題恰恰是選擇合適的數(shù)據(jù)類型。

在這種數(shù)據(jù)結(jié)構(gòu)下的算法就是：首先求出（123×654）、（123×321+ 456×654）、456×321�？梢詳喽ǚe的最后三位是456×321對1000求余的結(jié)果，最前面幾位是（123×654）+（123×321+ 456×654）/103，中間三位的值為（123×321+ 456×654）%103+456×321/1000。（這些示意性的東西叫偽代碼（Pseudocode））

從對算法的描述中還可以發(fā)現(xiàn)，積最好用三個(gè)int來表示。

所以，所謂的算法無非就是對操作步驟的描述。描述算法的方式有很多，其中之一就是使用自然語言來描述。用C語言描述的算法和數(shù)據(jù)結(jié)構(gòu)就是C代碼。

1. /*編程求123456*654321*/
   
2. 
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. 
   
6. #define CS1 123456  //乘數(shù)1
   
7. #define CS2 654321  //乘數(shù)2
   
8. #define YQ  1000    //一千
   
9. 
   
10. int main(void)
    
11. {
    
12. int cs1_q3w,cs1_h3w,cs2_q3w,cs2_h3w;//乘數(shù)1、乘數(shù)2的前3位和后3位
    
13. int ji_q,ji_z,ji_h; //積的前、中、后三個(gè)部分
    
14.   
    
15. cs1_q3w = CS1 / YQ ;
    
16. cs1_h3w = CS1 % YQ ;
    
17.   
    
18. cs2_q3w = CS2 / YQ ;
    
19. cs2_h3w = CS2 % YQ ;
    
20. 
    
21. //求出（123×654）、（123×321+ 456×654）、456×321
    
22. ji_q = cs1_q3w * cs2_q3w ;
    
23. ji_z = cs1_q3w * cs2_h3w + cs1_h3w * cs2_q3w ;
    
24. ji_h = cs1_h3w * cs2_h3w ;  
    
25. 
    
26. //進(jìn)位處理,注意：次序很重要
    
27. ji_q = ji_q + ji_z / YQ ;
    
28. ji_z = ji_z % YQ + ji_h / YQ ;
    
29. ji_h = ji_h % YQ ;
    
30. //輸出  
    
31. printf("%d×%d == %d%d%d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
    
32. 
    
33. system("PAUSE");
    
34. return 0;
    
35. }

復(fù)制代碼

程序輸出

123456×654321 == 80779853376

與程序代碼3-5的輸出相比，這個(gè)結(jié)果至少可以說可信度很高，盡管我們還無法確信。

增強(qiáng)對程序正確性信心的方法只有通過測試。由于這段代碼對于兩個(gè)不多于6位的十進(jìn)制數(shù)都應(yīng)該成立，所以可以選擇易于驗(yàn)算的情況運(yùn)行程序，比如把123456改為100000再運(yùn)行程序。

然而，很遺憾，程序求100000×654321的結(jié)果竟然是

100000×654321 == 654321000

造成這個(gè)錯(cuò)誤的原因是，代碼中ji_z、ji_h表示的都是三位的十進(jìn)制數(shù)，但當(dāng)它們的值為0時(shí)，%d這種格式只輸出1個(gè)0而不是3個(gè)0。改進(jìn)的辦法是把它們對應(yīng)的%d改成%03d。其中3表示輸出三位，0表示如果前面有空格則填充0（可以自己上機(jī)對比一下%03d、%3d和%d之間的區(qū)別）。

把輸出改寫為

printf("%d×%d == %d%03d%03d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
之后，可以發(fā)現(xiàn)程序求100000×654321的結(jié)果是正確的。如果還不放心，可以再找一些數(shù)據(jù)進(jìn)行測試。

---

作者: cjaizss    時(shí)間: 2011-04-29 08:59

可是在C語言下，好像超過10位就會(huì)溢出啊，怎么解決��？？
DNFCF 發(fā)表于 2011-04-28 22:57

    大數(shù)運(yùn)算啊

---

作者: DNFCF    時(shí)間: 2011-04-29 09:38
回復(fù) 20# KBTiller


    恩，看了很受教，弱弱的問下，大數(shù)拆小數(shù)有沒有神馬規(guī)律�。�？

---

作者: DNFCF    時(shí)間: 2011-04-29 09:40
回復(fù) 20# KBTiller


      恩，看了很受教，弱弱的問下，大數(shù)拆小數(shù)有沒有神馬規(guī)律�。�？

---

作者: KBTiller    時(shí)間: 2011-04-29 11:36

回復(fù)  KBTiller


      恩，看了很受教，弱弱的問下，大數(shù)拆小數(shù)有沒有神馬規(guī)律��？？
DNFCF 發(fā)表于 2011-04-29 09:40

沒什么規(guī)律
構(gòu)造一個(gè)數(shù)據(jù)結(jié)構(gòu)要結(jié)合具體的算法
最主要的原則我認(rèn)為是能方便地讀寫

你這個(gè)題目
我認(rèn)為可以用一個(gè)數(shù)組來模擬一個(gè)“大數(shù)”（當(dāng)然這不是最精致的方案）
例如
int dashu[22];
用dashu[0]存?zhèn)�位數(shù)
用dashu[1]存十位數(shù)
用dashu[2]存百位數(shù)
……
建議你先試一下計(jì)算9^21再輸出(前面有答案便于測試)

---

作者: koolcoy    時(shí)間: 2011-04-29 12:27
回復(fù) 24# KBTiller


    這種大數(shù)表示方法有些低效{:3_189:}

---

作者: KBTiller    時(shí)間: 2011-04-29 12:45
回復(fù) 25# koolcoy


    是的。主要考慮到樓主的經(jīng)驗(yàn)不多。
    您的方案是？

---

作者: koolcoy    時(shí)間: 2011-04-29 13:16
回復(fù) 26# KBTiller

    兩個(gè)64位整數(shù)并做一個(gè)128位整數(shù)使用，或者使用匯編調(diào)使用bcd指令

---

作者: A.com    時(shí)間: 2011-04-29 13:47
大數(shù)運(yùn)算的基本原理就是進(jìn)制，假設(shè)某個(gè)系統(tǒng)的數(shù)據(jù)寬度為兩位的2進(jìn)制，那么這個(gè)系統(tǒng)對于任何大于3的數(shù)來說，都無法直接運(yùn)算。要想做超過3的運(yùn)算，可以用2個(gè)2位也就是4位來表示數(shù)據(jù)，就能處理最大值為15的數(shù)了。所以要做大數(shù)運(yùn)算，只需要再虛擬出一層x進(jìn)制就行了。

---

作者: KBTiller    時(shí)間: 2011-04-30 09:34

回復(fù)  KBTiller

    兩個(gè)64位整數(shù)并做一個(gè)128位整數(shù)使用，或者使用匯編調(diào)使用bcd指令
koolcoy 發(fā)表于 2011-04-29 13:16

    呵呵，這個(gè)當(dāng)然高效
    不過我估計(jì)樓主只有小米加步槍，不會(huì)有“64位整數(shù)”這種原子彈

---

作者: KBTiller    時(shí)間: 2011-04-30 13:40
這個(gè)題目的算法其實(shí)不難
從根本上來說考察的是構(gòu)造數(shù)據(jù)的能力
數(shù)據(jù)組織的好，往往并不需要什么精妙的算法

---

作者: KanonInD    時(shí)間: 2011-05-01 10:00


大數(shù)用 __int128 好了。
http://gcc.gnu.org/onlinedocs/gc ... g_t_005f_005fint128

---

作者: koolcoy    時(shí)間: 2011-05-01 11:05

這個(gè)題目的算法其實(shí)不難
從根本上來說考察的是構(gòu)造數(shù)據(jù)的能力
數(shù)據(jù)組織的好，往往并不需要什么精妙的算法
KBTiller 發(fā)表于 2011-04-30 13:40

你顯然低估了這個(gè)問題，這個(gè)問題的解空間是10^21。我還沒找到啥號的剪枝辦法{:3_195:}

---

作者: koolcoy    時(shí)間: 2011-05-01 11:16
這個(gè)問題的難點(diǎn)還是對10^21的解空間的縮小或者dp優(yōu)化。大數(shù)模擬都是小事情

---

作者: KBTiller    時(shí)間: 2011-05-02 17:01


回復(fù) 32# koolcoy


    確實(shí)，我目前還沒想的那么遠(yuǎn)，只考慮了樓主的“溢出”問題。但我30樓的觀點(diǎn)不變
    現(xiàn)在看來，10樓A.com 的想法更徹底些
    不過“程序需要循環(huán)21^21次”我覺得是估計(jì)過高了，應(yīng)該是10^19這個(gè)量級

---

作者: A.com    時(shí)間: 2011-05-02 17:28

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

復(fù)制代碼

那么符合條件的數(shù)列里，9出現(xiàn)的頻度在1-9次。而且，末位數(shù)其實(shí)是有規(guī)律的

---

作者: KBTiller    時(shí)間: 2011-05-02 18:56

末位數(shù)其實(shí)是有規(guī)律的
A.com 發(fā)表于 2011-05-02 17:28

這個(gè)性質(zhì)真有趣

---

作者: KBTiller    時(shí)間: 2011-05-03 22:07

1. 449177399146038697307
   
2. 128468643043731391252
   
3. 請按任意鍵繼續(xù). . .

復(fù)制代碼

用了40多秒

---

作者: KBTiller    時(shí)間: 2011-05-03 22:15
27907865009977052567814
35452590104031691935943
27879694893054074471405
28361281321319229463398
21887696841122916288858
請按任意鍵繼續(xù). . .
23位
1分40秒

---

作者: KBTiller    時(shí)間: 2011-05-03 23:02
174088005938065293023722
239313664430041569350093
188451485447897896036875
請按任意鍵繼續(xù). . .
24位
2分27秒

---

作者: KBTiller    時(shí)間: 2011-05-04 17:41

其實(shí)就是0、1、2097152……9^21的組合，要求組合的和是個(gè)21位的數(shù)字且順序符合。
先湊夠數(shù)字，就是21個(gè)數(shù)之 ...
A.com 發(fā)表于 2011-04-28 17:40

    這個(gè)組合的數(shù)目很少，我計(jì)算的結(jié)果是620309379690  90135045種
--------------------------------------------------------------------
90135045包含了一些充分的組合，還是大了
應(yīng)該是 14139189

---

作者: koolcoy    時(shí)間: 2011-05-04 23:35
smilence

---

作者: A.com    時(shí)間: 2011-05-05 17:04


剛才看到有人說二叉樹不給用遞歸，想起來這個(gè)數(shù)字的變化其實(shí)是可預(yù)期的，譬如把某位的0變成1，那么整個(gè)數(shù)字就是N+1，無論這個(gè)0在什么位置，他變成1的結(jié)果都是相同的。也就是說只有組合相關(guān)性沒有排列相關(guān)性。又因?yàn)檫@21位數(shù)里面至少要有一位是9（沒有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    時(shí)間: 2011-05-05 18:06

沒有9的組合不可能大于10^20

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

---

作者: A.com    時(shí)間: 2011-05-06 08:38

11 * 8^21= 101,457,092,405,402,533,888
KBTiller 發(fā)表于 2011-05-05 18:06

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

---

作者: l2y3n2    時(shí)間: 2011-05-06 20:14


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

用C的話時(shí)間上應(yīng)該還是沒問題的

~$ 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    時(shí)間: 2011-05-13 13:10

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

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

---

作者: KBTiller    時(shí)間: 2011-05-13 20:32

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

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

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


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開始選擇  
    }   
}

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

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

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

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 02:17
暈死，這里哪有用到乘法啊，分明就只有加法。

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 02:20
我給個(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 就可以表示了吧？

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 02:21
利用  99 乘法表，直接查表不通過計(jì)算。

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

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 02:38
暈死。 窮舉法都不需要3分鐘就跑出來了

我還以為這3分鐘時(shí)間限制是要多牛逼的算法 ....

看來硬件的發(fā)展還是可以解放腦力的啊

---

作者: 蔡萬釗    時(shí)間: 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

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 06:03

1. 
   
2. /*
   
3. ============================================================================
   
4. Name        : n21cal.c
   
5. Author      :
   
6. Version     :
   
7. Copyright   : Your copyright notice
   
8. Description : Hello World in C, Ansi-style
   
9. ============================================================================
   
10. */
    
11. 
    
12. #include <stdio.h>
    
13. #include <stdlib.h>
    
14. #include <string.h>
    
15. 
    
16. typedef struct {
    
17.         unsigned long h;
    
18.         unsigned long l;
    
19. }bignumber;
    
20. 
    
21. bignumber table[10]={
    
22.                 {0,0},
    
23.                 {0UL,1UL},
    
24.                 {0UL,2097152UL},
    
25.                 {0UL,10460353203UL},
    
26.                 {0UL,4398046511104UL},
    
27.                 {0UL,476837158203125UL},
    
28.                 {0UL,21936950640377856UL},
    
29.                 {0UL,558545864083284007UL},
    
30.                 {0UL,9223372036854775808UL},
    
31. 
    
32.                 {0x5UL,0xEE7E56E3721F2929UL},
    
33. 
    
34. };
    
35. 
    
36. bignumber del(bignumber a, bignumber b)
    
37. {
    
38.         bignumber c= {0,0};
    
39.         c.l = a.l - b.l;
    
40. 
    
41.         if(a.l < b.l )
    
42.         {
    
43.                 a.h --;
    
44. //                c.l++;
    
45.         }
    
46. 
    
47.         c.h = a.h - b.h;
    
48. 
    
49.         return c;
    
50. }
    
51. 
    
52. bignumber add(bignumber a, bignumber b)
    
53. {
    
54.         bignumber c= {0,0};
    
55. 
    
56.         c.l = a.l + b.l;
    
57. 
    
58.         if( ( (-1UL) - a.l ) < b.l)
    
59.                 c.h ++;
    
60.         c.h += a.h + b.h;
    
61. 
    
62.         return c;
    
63. }
    
64. 
    
65. 
    
66. //獲得對應(yīng)的數(shù)字
    
67. bignumber get_table( int i)
    
68. {
    
69. 
    
70.         return table[i];
    
71. 
    
72. }
    
73. 
    
74. bignumber get_n_i(int b , int i )
    
75. {
    
76.         bignumber c = {0};
    
77.         for(; i >0 ; i--)
    
78.                 c = add(c , get_table(b));
    
79.         return c;
    
80. }
    
81. 
    
82. int inline mylog2( unsigned long x)
    
83. {
    
84.         int i;
    
85. 
    
86.         static unsigned long logtable[64] ={
    
87.                         0x8000000000000000,
    
88.                         0x4000000000000000,
    
89.                         0x2000000000000000,
    
90.                         0x1000000000000000,
    
91.                         0x800000000000000,
    
92.                         0x400000000000000,
    
93.                         0x200000000000000,
    
94.                         0x100000000000000,
    
95.                         0x80000000000000,
    
96.                         0x40000000000000,
    
97.                         0x20000000000000,
    
98.                         0x10000000000000,
    
99.                         0x8000000000000,
    
100.                         0x4000000000000,
     
101.                         0x2000000000000,
     
102.                         0x1000000000000,
     
103.                         0x800000000000,
     
104.                         0x400000000000,
     
105.                         0x200000000000,
     
106.                         0x100000000000,
     
107.                         0x80000000000,
     
108.                         0x40000000000,
     
109.                         0x20000000000,
     
110.                         0x10000000000,
     
111.                         0x8000000000,
     
112.                         0x4000000000,
     
113.                         0x2000000000,
     
114.                         0x1000000000,
     
115.                         0x800000000,
     
116.                         0x400000000,
     
117.                         0x200000000,
     
118.                         0x100000000,
     
119.                         0x80000000,
     
120.                         0x40000000,
     
121.                         0x20000000,
     
122.                         0x10000000,
     
123.                         0x8000000,
     
124.                         0x4000000,
     
125.                         0x2000000,
     
126.                         0x1000000,
     
127.                         0x800000,
     
128.                         0x400000,
     
129.                         0x200000,
     
130.                         0x100000,
     
131.                         0x80000,
     
132.                         0x40000,
     
133.                         0x20000,
     
134.                         0x10000,
     
135.                         0x8000,
     
136.                         0x4000,
     
137.                         0x2000,
     
138.                         0x1000,
     
139.                         0x800,
     
140.                         0x400,
     
141.                         0x200,
     
142.                         0x100,
     
143.                         0x80,
     
144.                         0x40,
     
145.                         0x20,
     
146.                         0x10,
     
147.                         0x8,
     
148.                         0x4,
     
149.                         0x2,
     
150.                         0x1,
     
151.         };
     
152. 
     
153.         for( i  = 0 ; i < 64 ; i++)
     
154.         {
     
155.                 if (x & logtable[i]) return i;
     
156.         }
     
157.         return -1;
     
158. }
     
159. 
     
160. bignumber  dvi_10(bignumber a)
     
161. {
     
162.         bignumber t;
     
163.         int tmp = mylog2(a.h);
     
164. 
     
165.         t.h  = ((a.h << tmp) | a.l >> ( 64 - tmp)) / 10 ;
     
166. 
     
167.         unsigned long yu = ((a.h << tmp) | a.l >> ( 64 - tmp)) % 10;
     
168. 
     
169.         t.l = (((a.l << tmp )>> tmp) | (yu << (64 - tmp))) / 10;
     
170. 
     
171.         tmp = mylog2(t.l);
     
172. 
     
173.         a.h = t.h >> tmp;
     
174. 
     
175.         a.l = t.l | ( t.h <<  (  64 - tmp  )) ;
     
176. 
     
177.         return a;
     
178. }
     
179. 
     
180. void inline revstr(char *str)
     
181. {   //省去一變量, 時(shí)間換空間法
     
182.     char *head = str, *tail = str + strlen(str) -1;
     
183.     for(; head < tail; *head=*head ^ *tail, *tail=*head ^ *tail, *head=*head++ ^ *tail--);
     
184. }
     
185. 
     
186. 
     
187. void inline to_str(bignumber n, char N[22])
     
188. {
     
189.         //基本原理是，
     
190. //        尋找個(gè)位，然后 除以 10
     
191. //        繼續(xù)
     
192.         int cur=0;
     
193. 
     
194.         do{
     
195.                 bignumber n3=n,n2 = dvi_10(n);
     
196. 
     
197.                 n3 = del(n3,n2);
     
198.                 n3 = del(n3,n2);
     
199.                 n3 = del(n3,n2);
     
200.                 n3 = del(n3,n2);
     
201.                 n3 = del(n3,n2);
     
202. 
     
203.                 n3 = del(n3,n2);
     
204.                 n3 = del(n3,n2);
     
205.                 n3 = del(n3,n2);
     
206.                 n3 = del(n3,n2);
     
207.                 n3 = del(n3,n2);
     
208. 
     
209.                 N[cur++] = '0' + n3.l;
     
210. 
     
211.                 n = n2;
     
212. 
     
213.         }while( n.h  || n.l   );
     
214. 
     
215.         revstr(N);
     
216. 
     
217. 
     
218. }
     
219. 
     
220. int inline charcnt(const char *ptr, unsigned char ch)
     
221. {
     
222.     int count = 0;
     
223.     while(*ptr)
     
224.     {
     
225.                if(ch == *ptr)
     
226.                {
     
227.                      count++;
     
228.                }
     
229.                ptr++;
     
230.     }
     
231.     return count;
     
232. }
     
233. 
     
234. 
     
235. 
     
236. int main(void)
     
237. {
     
238.         char  N[22]="";
     
239. 
     
240.         int n0,n1,n2,n3,n4,n5,n6,n7,n8,n9;
     
241. 
     
242.         for(n9 = 1 ; n9 <= 21 ; n9++)
     
243.                 for(n8 = 0 ; n8 <= 21 - n9 ; n8++)
     
244.                         for(n7 = 0 ; n7 <= 21 -n9 - n8 ; n7++)
     
245.                                 for(n6 = 0 ; n6 <= 21 -n9 - n8 -n7 ; n6++)
     
246.                                         for(n5 = 0 ; n5 <= 21 -n9 - n8 -n7 -n6; n5++)
     
247.                                                 for(n4 = 0 ; n4 <= 21 -n9 - n8 -n7 -n6 -n5 ; n4++)
     
248.                                                         for(n3 = 0 ; n3 <= 21 -n9 - n8 -n7 -n6 -n5 -n4 ; n3++)
     
249.                                                                 for(n2 = 0 ; n2 <= 21 -n9 - n8 -n7 -n6 -n5 -n4 -n3; n2++)
     
250.                                                                         for(n1 = 0 ; n1 <= 21  -n9 - n8 -n7 -n6 -n5 -n4 -n3 -n2; n1++)
     
251.                                                                         {
     
252.                                                                                 n0 = 21 - n9 - n8 - n7 - n6 - n5 - n4
     
253.                                                                                                 - n3 - n2 - n1;
     
254. 
     
255.                                                                                 bignumber sum = { 0 };
     
256. 
     
257.                                                                                 sum.l = n1;
     
258.                                                                                 sum = add(sum, get_n_i(2, n2));
     
259.                                                                                 sum = add(sum, get_n_i(3, n3));
     
260.                                                                                 sum = add(sum, get_n_i(4, n4));
     
261.                                                                                 sum = add(sum, get_n_i(5, n5));
     
262.                                                                                 sum = add(sum, get_n_i(6, n6));
     
263.                                                                                 sum = add(sum, get_n_i(7, n7));
     
264.                                                                                 sum = add(sum, get_n_i(8, n8));
     
265.                                                                                 sum = add(sum, get_n_i(9, n9));
     
266. 
     
267.                                                                                 static long loop;
     
268. 
     
269.                                                                                 ++loop;
     
270. 
     
271.                                                                                 if(sum.h <= 4)
     
272.                                                                                         continue;
     
273. 
     
274.                                                                                 //開始校驗(yàn)
     
275. 
     
276. //                                                                                轉(zhuǎn)化為字符串
     
277. 
     
278.                                                                                 to_str(sum, N );
     
279. 
     
280. //                                                                                統(tǒng)計(jì) 0 1 2 3 4 5 6 7 8 9 的個(gè)數(shù)
     
281. 
     
282.                                                                                 if(charcnt(N,'9') == n9)
     
283.                                                                                         if(charcnt(N,'8') == n8)
     
284.                                                                                                 if(charcnt(N,'7') == n7)
     
285.                                                                                                         if(charcnt(N,'6') == n6)
     
286.                                                                                                                 if(charcnt(N,'5') == n5)
     
287.                                                                                                                         if(charcnt(N,'4') == n4)
     
288.                                                                                                                                 if(charcnt(N,'3') == n3)
     
289.                                                                                                                                         if(charcnt(N,'2') == n2)
     
290.                                                                                                                                                 if(charcnt(N,'1') == n1)
     
291.                                                                                                                                                
     
292.                                                                                                                                                 {
     
293.                                                                                                                                                                 printf("%ld 種組合\n", loop);
     
294. 
     
295.                                                                                                                                                                 printf("the number is %s\n", N);
     
296.                                                                                                                                                 }
     
297. 
     
298.                                                                                 memset(N,0,22);
     
299.                                                                         }
     
300. 
     
301. 
     
302. 
     
303. 
     
304.         return EXIT_SUCCESS;
     
305. }
     
306. 
     

復(fù)制代碼

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 06:05
我真 TM 有功夫折騰啊！ 居然折騰了這么久。
對 KBTiller 表示佩服。

---

作者: 蔡萬釗    時(shí)間: 2011-05-14 06:36
奇怪，怎么算都只有一個(gè)結(jié)果的�。。�！ 為何我的只能那個(gè)算出一個(gè)結(jié)果來！�。�！

---

作者: KBTiller    時(shí)間: 2011-05-14 09:22
回復(fù) 55# 蔡萬釗


    一夜就弄出來了，你寫得比我快多了

---

作者: KBTiller    時(shí)間: 2011-05-14 09:23

我給個(gè)思路吧。

不用去算數(shù)。

char N[21]

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

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

  ...
蔡萬釗 發(fā)表于 2011-05-14 02:20

這個(gè)循環(huán)嵌套的深度少
更好

---

作者: 蔡萬釗    時(shí)間: 2011-05-15 02:36

這個(gè)循環(huán)嵌套的深度少
更好
KBTiller 發(fā)表于 2011-05-14 09:23

    還是嵌套了9層呢！

---

作者: KBTiller    時(shí)間: 2011-05-15 10:49
回復(fù) 59# 蔡萬釗


    已經(jīng)好多了，我那個(gè)嵌套21層

---

作者: KBTiller    時(shí)間: 2011-05-16 08:55
回復(fù) 54# 蔡萬釗


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

n9 是9的個(gè)數(shù)嗎？如果是的話，這里值得推敲

---

作者: KBTiller    時(shí)間: 2011-05-16 09:05

折騰啊我！！

cai@cai ~/workspace/n21cal $ time ./Debug/n21cal  
1732949 種組合
the number is 12 ...
蔡萬釗 發(fā)表于 2011-05-14 06:02

我用類似你的想法做，組合數(shù)比你這個(gè)高一個(gè)量級 ，14139189

---

作者: leeews    時(shí)間: 2011-05-16 13:17
確實(shí)變態(tài)

---

作者: KBTiller    時(shí)間: 2011-05-16 14:45

我給個(gè)思路吧。

不用去算數(shù)。

char N[21]

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

先計(jì)算 21 一個(gè) 1 的結(jié)果，
然后是  ...
蔡萬釗 發(fā)表于 2011-05-14 02:20

    按你的辦法改進(jìn)了一下，增加了從小到大輸出的功能，不到40秒
    你的辦法真不錯(cuò)

128468643043731391252
449177399146038697307
請按任意鍵繼續(xù). . .

---

作者: KBTiller    時(shí)間: 2011-05-16 14:48

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

    容我稍微整理一下，很快就會(huì)發(fā)出來

---

作者: 蔡萬釗    時(shí)間: 2011-05-17 00:26
回復(fù) 61# KBTiller

是。貌似有人說要至少 一個(gè)9 ， 沒9 是不行的 ~~~

就這樣寫了。

問題是怎么算都只有一個(gè)結(jié)果，而不是2個(gè)，一定是哪里漏了。

---

作者: KBTiller    時(shí)間: 2011-05-17 00:36
回復(fù) 66# 蔡萬釗

“至少 一個(gè)9 ， 沒9 是不行的”，這個(gè)不對

n9應(yīng)該是 0~9 個(gè)，可以沒有，最多9個(gè)

---

作者: 蔡萬釗    時(shí)間: 2011-05-17 00:46
回復(fù) 67# KBTiller


    好，我修改一下看看。

---

作者: 蔡萬釗    時(shí)間: 2011-05-17 00:55
回復(fù) 67# KBTiller


    不行啊！ 還是只有一個(gè)結(jié)果。莫非是我的大數(shù)的計(jì)算錯(cuò)誤了？

---

作者: KBTiller    時(shí)間: 2011-05-17 08:50

回復(fù)  KBTiller


    不行��！ 還是只有一個(gè)結(jié)果。莫非是我的大數(shù)的計(jì)算錯(cuò)誤了？
蔡萬釗 發(fā)表于 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 ）試一下，也許能發(fā)現(xiàn)bug

   你的機(jī)器sizeof(unsigned long)是多少？我的機(jī)器上試不起來

---

作者: KBTiller    時(shí)間: 2011-05-17 12:09
獻(xiàn)丑！請大家指正

0_問題.h

1. 
   
2. /*
   
3. 一個(gè)N位的十進(jìn)制正整數(shù)，如果它的每個(gè)位上的數(shù)字的N次方的和等于這個(gè)數(shù)本身，
   
4. 則稱其為花朵數(shù)。
   
5. 例如：
   
6. 當(dāng)N=3時(shí)，153就滿足條件，因?yàn)?1^3 + 5^3 + 3^3 = 153，
   
7. 這樣的數(shù)字也被稱為水仙花數(shù)（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
   
8. 當(dāng)N=4時(shí)，1634滿足條件，因?yàn)?1^4 + 6^4 + 3^4 + 4^4 = 1634。
   
9. 當(dāng)N=5時(shí)，92727滿足條件。
   
10. 實(shí)際上，對N的每個(gè)取值，可能有多個(gè)數(shù)字滿足條件。
    
11. 程序的任務(wù)是：求N=21時(shí)，所有滿足條件的花朵數(shù)。注意：這個(gè)整數(shù)有21位，
    
12. 它的各個(gè)位數(shù)字的21次方之和正好等于這個(gè)數(shù)本身。
    
13. 如果滿足條件的數(shù)字不只有一個(gè)，請從小到大輸出所有符合條件的數(shù)字，
    
14. 每個(gè)數(shù)字占一行。因?yàn)檫@個(gè)數(shù)字很大，
    
15. 請注意解法時(shí)間上的可行性。要求程序在3分鐘內(nèi)運(yùn)行完畢。
    
16. */
    
17. #ifndef WENTI_H
    
18. #define WENTI_H
    
19.     #define CESHI        //進(jìn)行測試  
    
20.     //#define QIUJIE     //求解21位問題                              
    
21.    
    
22.     #ifdef CESHI             //測試
    
23.       #define JINZHI 10      //十進(jìn)制
    
24.       #define WEISHU 3       //3位花朵數(shù)   
    
25.       #define N      WEISHU  //冪次==位數(shù)
    
26.     #endif //CESHI_3
    
27.    
    
28.     #ifdef QIUJIE            //求解            
    
29.       #define JINZHI 10      //十進(jìn)制
    
30.       #define WEISHU 21      //位數(shù)   
    
31.       #define N      WEISHU  //冪次==位數(shù)
    
32.     #endif //QIUJIE
    
33.    
    
34. #endif // WENTI_H
    
35. /*
    
36. 注：
    
37. 通過修改符號常量的值，可以得到其他進(jìn)制或其他位數(shù)花朵數(shù)問題的解
    
38. */
    
39. 
    

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:11
1_MAIN_type.h

1. 
   
2. 
   
3. #ifndef MAIN_T_H
   
4. #define MAIN_T_H
   
5.     //NOTHING
   
6. #endif // MAIN_T_H
   
7. 
   

復(fù)制代碼

1_MAIN_function.h

1. 
   
2. 
   
3. #ifndef MAIN_F_H
   
4. #define MAIN_F_H
   
5.     #include "1_MAIN_type.h"      
   
6.     #include "2_數(shù)字組合_function.h"  //zuhe_sz()及參數(shù)
   
7.     #include "5_處理結(jié)果_function.h"  //shuchu_jg()
   
8.     #include <stdlib.h>               //system()
   
9.      
   
10. #endif // MAIN_F_H
    
11. 
    

復(fù)制代碼

1_MAIN.c

1. 
   
2. /*
   
3.   Name:花朵數(shù)問題
   
4.   Author: 鍵盤農(nóng)夫
   
5.   Date: 17-05-11
   
6.   Description: 一個(gè)一般性解法，
   
7.                適用其他進(jìn)制（<=10）、其他位數(shù)的花朵數(shù)求解
   
8. */
   
9. #include "1_MAIN_function.h"
   
10. #define ANY 0
    
11. int main( void )
    
12. {
    
13.     zuhe_sz( ZHUNBEI , ANY );    //進(jìn)行數(shù)字組合<=>驗(yàn)算<=>存儲結(jié)果
    
14.            //第一個(gè)實(shí)參為ZHUNBEI時(shí),第二個(gè)實(shí)參沒有用處
    
15.     shuchu_jg();                 //輸出結(jié)果,釋放內(nèi)存   
    
16.     system("PAUSE");
    
17.     return 0;
    
18. }
    
19. #undef ANY
    
20. /*
    
21. 注：稍微修改一下輸出的函數(shù)shuchu()，程序也適合10以上進(jìn)制
    
22. */
    
23. 
    

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:13


2_數(shù)字組合_type.h

1. 
   
2. 
   
3. #ifndef ZUHE_T_H
   
4. #define ZUHE_T_H
   
5.     #include "3_組合驗(yàn)算_type.h"      
   
6.     #include "0_問題.h"
   
7. #endif // ZUHE_T_H
   
8. 
   

復(fù)制代碼

2_數(shù)字組合_function.h

1. 
   
2. 
   
3. #ifndef ZUHE_F_H
   
4. #define ZUHE_F_H
   
5.     #include "2_數(shù)字組合_type.h"
   
6.     #include "3_組合驗(yàn)算_function.h"   
   
7.     #include "4_大數(shù)運(yùn)算_function.h"      
   
8.       
   
9.     extern void zuhe_sz( const int , const int );
   
10.     //zuhe_sz()的兩個(gè)特殊參數(shù)
    
11.         #define ZHUNBEI   JINZHI
    
12.         #define WANCHENG  0
    
13. #endif // ZUHE_F_H
    
14. 
    

復(fù)制代碼

2_數(shù)字組合.c

1. 
   
2. 
   
3. #include "2_數(shù)字組合_function.h"
   
4. //求"WEISU位數(shù)"的各種數(shù)字組合
   
5. //sz:某一數(shù)字，gs:該數(shù)字可能選擇的最大個(gè)數(shù)
   
6. //sz: ZHUNBEI 進(jìn)行必要準(zhǔn)備
   
7. //sz: WANCHENG 組合完成（可以確定0的個(gè)數(shù)時(shí)）
   
8. extern void zuhe_sz( const int sz , const  int gs )
   
9. {
   
10.     static SHUZI_GESHU_t sj_gs , //實(shí)際的個(gè)數(shù)
    
11.                          gs_sx ; //個(gè)數(shù)的上限
    
12.    
    
13.     switch ( sz ) {
    
14.         case  ZHUNBEI:
    
15.                       jisuan_zhunbei( & gs_sx );   //計(jì)算準(zhǔn)備
    
16.                       zuhe_sz ( sz - 1 , WEISHU ) ;
    
17.                       qing0( & gs_sx );            //對 gs_sx清0                     
    
18.                       break;
    
19.         default      :  //嘗試某數(shù)字（sz）的各種可能的數(shù)目（i）
    
20.                       {
    
21.                           int i ;
    
22.                           for ( i =  0 ;
    
23.                                 i <= ( (gs < gs_sx[sz]) ? gs : gs_sx[sz] ) ;
    
24.                                 i ++  ){
    
25.                               sj_gs [ sz ] = i ;
    
26.                               zuhe_sz ( sz - 1 , gs - i ) ; //下一個(gè)數(shù)字
    
27.                               sj_gs [ sz ] = 0 ;
    
28.                           }
    
29.                       }                        
    
30.                       break;
    
31.         case WANCHENG:   
    
32.                       sj_gs [ sz ] = gs  ;         //0的個(gè)數(shù)  
    
33.                       jianyan( &sj_gs )  ;         //對數(shù)字組合驗(yàn)算
    
34.                       sj_gs [ sz ] = 0   ;            
    
35.                       break;
    
36.     }                     
    
37. }
    
38. 
    

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:15
3_組合驗(yàn)算_type.h

1. 
   
2. 
   
3. #ifndef YANSUAN_T_H
   
4. #define YANSUAN_T_H
   
5.     #include "0_問題.h"
   
6.     #include "6_常用.h"   
   
7.     #include "4_大數(shù)運(yùn)算_type.h"        
   
8.     typedef int     SHUZI_GESHU_t[JINZHI]   ;   //描述各個(gè)數(shù)字出現(xiàn)個(gè)數(shù)的類型
   
9.     // 0的個(gè)數(shù)，1的個(gè)數(shù)……JINZHI-1的個(gè)數(shù)     
   
10. #endif // YANSUAN_T_H
    
11. 
    

復(fù)制代碼

3_組合驗(yàn)算_function.h

1. 
   
2. 
   
3. #ifndef YANSUAN_F_H
   
4. #define YANSUAN_F_H
   
5.     #include "3_組合驗(yàn)算_type.h"      
   
6.    
   
7.     #include "4_大數(shù)運(yùn)算_function.h"         
   
8.     #include "5_處理結(jié)果_function.h"         
   
9.          
   
10.     extern void jisuan_zhunbei( SHUZI_GESHU_t * );
    
11.     extern void qing0  ( SHUZI_GESHU_t * )  ;
    
12.     extern void jianyan( SHUZI_GESHU_t * )  ;
    
13. #endif // YANSUAN_F_H
    
14. 
    

復(fù)制代碼

3_組合驗(yàn)算.c

1. 
   
2. #include "3_組合驗(yàn)算_function.h"   
   
3. static DASHU_t sjb[JINZHI][WEISHU]; //數(shù)據(jù)表   
   
4. //////         1*0^N,2*0^N,……WEISHU*0^N
   
5. //////         1*1^N,2*1^N,……WEISHU*1^N
   
6. //////         1*2^N,2*2^N,……WEISHU*2^N
   
7. //////         ……
   
8. //////         1*9^N,2*9^N,……WEISHU*9^N   
   
9. //////================================================
   
10. //檢驗(yàn)構(gòu)成組合的各個(gè)數(shù)字的N次方之和的數(shù)字組合
    
11. //是否與原來的組合一致
    
12. extern void jianyan( SHUZI_GESHU_t * p_zhsm )
    
13. {
    
14.     DASHU_t he ;
    
15.     fuzhi ( & he , 0 ) ;  //初值為0
    
16.     int i ;
    
17.     for( i = 1; i < GESHU(sjb) ; i++){ //i=1, 0的N次冪不用加
    
18.        if ( (* p_zhsm)[i] == 0 )           //某數(shù)字不出現(xiàn)
    
19.            continue ;   
    
20.        jiaru( & he , sjb[i] + (( * p_zhsm )[i] - 1)  ); // 求和
    
21.     }
    
22.    
    
23.     if(  chaoguo_ws ( & he ) == SHI
    
24.       || bugou_ws   ( & he ) == SHI  )     //位數(shù)不符合
    
25.        return ;
    
26.    
    
27.     if ( xiangtong ( & he , p_zhsm ) == FOU )//和的組合與原來的組合不同
    
28.         return ;         
    
29.    
    
30.     jilu_jg( &he );
    
31. }
    
32. //求各個(gè)數(shù)字的N次方及其整數(shù)倍（1,2，……WEISHU倍）
    
33. //同時(shí)求出各個(gè)數(shù)字出現(xiàn)次數(shù)的上限存入 * p_zhsx
    
34. extern void jisuan_zhunbei( SHUZI_GESHU_t * p_zhsx )
    
35. {
    
36.     int hang , lie ;
    
37.    
    
38.     for ( hang = 0 ; hang < GESHU( sjb ) ; hang++ ){
    
39.         
    
40.         qiu_mi ( sjb[hang]  , hang , N  ) ;     //求i的N次冪
    
41.         
    
42.         for ( lie = 1 ; lie < GESHU( sjb[hang] ) ; lie ++  ) { //WEISHU
    
43.             cheng ( sjb[hang] + lie    , sjb[hang]   , lie + 1 ) ;
    
44.             
    
45.             if ( chaoguo_ws ( sjb[hang] + lie ) == SHI ) //結(jié)果超過WEISHU
    
46.                 break ;   
    
47.         }   
    
48.         (* p_zhsx)[hang] = lie  ;    // 某數(shù)字出現(xiàn)次數(shù)的上限值
    
49.     }
    
50. }
    
51. extern void qing0( SHUZI_GESHU_t * p_zhsx )
    
52. {
    
53.     int *p = * p_zhsx ;
    
54.     while ( p < * ( p_zhsx + 1 ))
    
55.         *p++ = 0 ;
    
56. }
    
57. 
    

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:17
4_大數(shù)運(yùn)算_type.h

1. 
   
2. 
   
3. #ifndef DASHU_T_H
   
4. #define DASHU_T_H
   
5.     #include "0_問題.h"
   
6.     #include "6_常用.h"
   
7.     #include "3_組合驗(yàn)算_type.h"
   
8.     typedef int DASHU_t[WEISHU] ; //大數(shù)類型
   
9.    
   
10. #endif // DASHU_T_H
    
11. 
    

復(fù)制代碼

4_大數(shù)運(yùn)算_function.h

1. 
   
2. 
   
3. #ifndef DASHU_F_H
   
4. #define DASHU_F_H
   
5.     #include "4_大數(shù)運(yùn)算_type.h"
   
6.    
   
7.     #include <stdio.h>
   
8.     #include "3_組合驗(yàn)算_function.h"   
   
9.         
   
10.     extern void qiu_mi ( DASHU_t * const , const int , int  ) ;
    
11.     extern void fuzhi  ( DASHU_t * const , const int ) ;
    
12.     extern void cheng  ( DASHU_t * const , DASHU_t * const , const int );
    
13.     extern void jiaru  ( DASHU_t * const ,  DASHU_t * const );
    
14.     extern void shuchu ( DASHU_t * const );
    
15.     extern void copy_ds( DASHU_t * const , DASHU_t * const ) ;
    
16.     extern SF   xiaoyu     ( DASHU_t * const , DASHU_t * const ) ;
    
17.     extern SF   chaoguo_ws ( DASHU_t * const ) ;
    
18.     extern SF   bugou_ws   ( DASHU_t * const ) ;
    
19.     extern SF   xiangtong  (  DASHU_t * const  ,  SHUZI_GESHU_t * const ) ;
    
20. #endif // DASHU_F_H
    
21. 
    

復(fù)制代碼

4_大數(shù)運(yùn)算.c

1. 
   
2. 
   
3. #include "4_大數(shù)運(yùn)算_function.h"
   
4. extern  void shuchu(  DASHU_t * const p_ds )
   
5. {
   
6.     int *w = *p_ds , *t = *(p_ds+1) -1;
   
7.     int i;
   
8.    
   
9.     while( t > w && *t == 0) //前面的0不輸出
   
10.        t--;  
    
11.    
    
12.     for ( i = t - w ; i >= 0 ; i-- )
    
13.        printf("%d" , w[i]);
    
14.     putchar('\n');
    
15. }
    
16. extern void copy_ds ( DASHU_t * const p_zd, DASHU_t * const p_qd )
    
17. {
    
18.     int i ;
    
19.     for (i = 0 ; i < GESHU(*p_zd) ; i++ )
    
20.         (*p_zd)[i] = (*p_qd)[i] ;
    
21. }
    
22. //判斷*p_he的組合是否與*p_szzh相同
    
23. SF xiangtong ( DASHU_t * const p_he ,  SHUZI_GESHU_t * const p_szzh )
    
24. {
    
25.     SHUZI_GESHU_t szgs ;
    
26.     int i ;
    
27.     qing0  ( & szgs ) ;
    
28.     for (i = 0 ; i < GESHU(*p_he) ; i++ )
    
29.         szgs[(*p_he)[i]]++;
    
30.    
    
31.     for(i=0;i<GESHU(szgs);i++)
    
32.         if(szgs[i]!=((*p_szzh)[i]))
    
33.             return FOU ;
    
34.         
    
35.     return SHI;
    
36. }
    
37. //進(jìn)位
    
38. static void jinwei( DASHU_t * const p_ds)
    
39. {
    
40.     int *q = *p_ds ;
    
41.     while ( q < *( p_ds + 1) - 1 ){
    
42.         * ( q + 1 ) += * q / JINZHI ;
    
43.         * q++ %= JINZHI ;
    
44.     }   
    
45. }
    
46. //小于
    
47. extern SF xiaoyu  ( DASHU_t * const p_ds1 , DASHU_t * const p_ds2 )
    
48. {
    
49.     int i;
    
50.     for( i = GESHU(*p_ds1) - 1 ; i >= 0 ; i -- ){
    
51.         if( (*p_ds1)[i]<(*p_ds2)[i] )
    
52.             return SHI ;
    
53.         if( (*p_ds1)[i]>(*p_ds2)[i] )
    
54.             return FOU ;
    
55.     }
    
56.     return FOU ;   
    
57. }
    
58. //將*p_js累加入*p_he
    
59. extern void jiaru( DASHU_t * const p_he ,  DASHU_t * const p_js)
    
60. {
    
61.     int i;
    
62.     for(i=0;i<GESHU(*p_he);i++)
    
63.         (*p_he)[i] += (*p_js)[i];
    
64.         
    
65.     jinwei(p_he) ;
    
66. }
    
67. //判斷是否超過WEISHU
    
68. extern SF chaoguo_ws ( DASHU_t * const p_ds )
    
69. {
    
70.     if( p_ds[1][-1] >= JINZHI ){
    
71.         return SHI ;
    
72.     }
    
73.     return FOU;
    
74. }
    
75. //判斷是否位數(shù)不到WEISHU
    
76. extern SF bugou_ws ( DASHU_t * const p_ds )
    
77. {
    
78.     if( p_ds[1][-1] == 0 )
    
79.         return SHI ;
    
80.     return FOU;
    
81. }
    
82. //cs2*(*p_cs1)=>(*p_ji)
    
83. extern void cheng ( DASHU_t * const p_ji , DASHU_t * const p_cs1 , const int cs2)
    
84. {
    
85.    int *p = *p_ji ,*q = *p_cs1;
    
86.    while ( p < * ( p_ji + 1) )
    
87.         *p++ = *q++ * cs2 ;
    
88.    
    
89.    //進(jìn)位
    
90.    jinwei( p_ji );   
    
91. }
    
92. //求i的n次冪，放在 * p_ds 中
    
93. extern void qiu_mi ( DASHU_t * const p_ds , const int i , int  n  )
    
94. {
    
95.     fuzhi ( p_ds , i ) ;
    
96.     while ( --n > 0 )
    
97.         cheng ( p_ds , p_ds , i);
    
98. }
    
99. //賦值，大于JINZHI的數(shù)也可以
    
100. extern  void fuzhi ( DASHU_t * const p_ds , const int i )
     
101. {
     
102.     int *q = *p_ds ;
     
103.     *q = i ;
     
104.     while ( q < *( p_ds + 1) - 1){
     
105.         * ( q + 1 ) = * q / JINZHI ;
     
106.         * q++ %= JINZHI ;
     
107.     }
     
108. }
     
109. 
     

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:19
5_處理結(jié)果_type.h

1. 
   
2. 
   
3. #ifndef JIEGUO_T_H
   
4. #define JIEGUO_T_H
   
5. 
   
6.    
   
7.     #include "0_問題.h"
   
8.     #include "4_大數(shù)運(yùn)算_type.h"
   
9.     typedef struct JD{
   
10.                       DASHU_t ds   ;  //大數(shù)
    
11.                       struct JD *xyg ;//下一個(gè)
    
12.                      } JIEDIAN_t ;      //節(jié)點(diǎn)類型
    
13.     typedef JIEDIAN_t *TOU_t  ;         //頭類型
    
14. #endif // JIEGUO_T_H
    
15. 
    

復(fù)制代碼

5_處理結(jié)果_function.h

1. 
   
2. #ifndef JIEGUO_F_H
   
3. #define JIEGUO_F_H
   
4.     #include "5_處理結(jié)果_type.h"
   
5.    
   
6.     #include "4_大數(shù)運(yùn)算_function.h"      
   
7.     #include <stdio.h>
   
8.     #include <stdlib.h>
   
9.         
   
10.     extern void jilu_jg( DASHU_t * );
    
11.     extern void shuchu_jg ( void );
    
12.    
    
13. #endif // JIEGUO_F_H
    
14. 
    

復(fù)制代碼

5_處理結(jié)果.c

1. 
   
2. 
   
3. #include "5_處理結(jié)果_function.h"
   
4. static TOU_t tou = NULL ;
   
5. static void jia_jd ( TOU_t ,TOU_t *);
   
6. static void shifang_nc(TOU_t);
   
7. static void shifang_nc( TOU_t p )
   
8. {
   
9.     TOU_t q  ;
   
10.     if( p == NULL )
    
11.         return ;
    
12.    
    
13.     q = p->xyg ;
    
14.     free(p);
    
15.     shifang_nc( q );
    
16. }
    
17. extern void jilu_jg( DASHU_t * p_ds )
    
18. {
    
19.     TOU_t p_jd ;
    
20.     if( (p_jd = malloc( sizeof (JIEDIAN_t )) ) == NULL ){
    
21.         shifang_nc( tou );
    
22.         puts("無法記錄結(jié)果，程序退出");
    
23.         exit ( ! EXIT_SUCCESS ) ;
    
24.     }
    
25.    
    
26.     copy_ds ( & p_jd->ds  , p_ds ) ;   //復(fù)制
    
27.     jia_jd ( p_jd , & tou );           //加入鏈表(p_jd,tou)
    
28. }
    
29. //按照一定次序加入節(jié)點(diǎn)
    
30. static void jia_jd ( TOU_t  xjd, TOU_t  *p_xyg  )
    
31. {
    
32.     if( *p_xyg == NULL ||
    
33.         ( xiaoyu ( & xjd -> ds , &(*p_xyg)->ds )) == SHI ){/* 小于 */
    
34.         xjd->xyg = *p_xyg ;
    
35.         *p_xyg = xjd ;
    
36.         return ;
    
37.     }
    
38.     jia_jd ( xjd  , &(*p_xyg)->xyg ) ;
    
39. }
    
40. //輸出結(jié)果，之后釋放內(nèi)存
    
41. extern void shuchu_jg( void )
    
42. {
    
43.     TOU_t temp = tou ;
    
44.     while ( temp != NULL ){
    
45.         shuchu(&temp->ds);
    
46.         temp = temp->xyg ;
    
47.     }   
    
48.     shifang_nc( tou );   
    
49.     tou = NULL ;
    
50. }
    
51. 
    

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:21
6_常用.h

1. 
   
2. 
   
3. //我編程常用的成語和俚語
   
4. #ifndef CHANGYONG_H
   
5. #define CHANGYONG_H
   
6.     typedef enum { FOU , SHI } SF ;
   
7.    
   
8.     #define GESHU(A) ((sizeof (A)) / (sizeof (*(A))) )
   
9.    
   
10. #endif // CHANGYONG_H
    
11. 
    

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-17 12:35
從蔡萬釗、A.com、koolcoy (娶妻求賢)網(wǎng)友的發(fā)言中受到了許多啟發(fā)，在此致謝！

---

作者: koolcoy    時(shí)間: 2011-05-17 14:26
好多年沒看過用拼音寫的程序了，怎么看怎么囧，有空了再來研究{:3_196:}

---

作者: 蔡萬釗    時(shí)間: 2011-05-17 20:30
回復(fù) 70# KBTiller


    我是 AMD64 的 Gentoo 系統(tǒng)。

---

作者: koolcoy    時(shí)間: 2011-05-18 10:31
昨晚想了一下這個(gè)問題，有這么一個(gè)優(yōu)化方法：
將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個(gè)數(shù)保存起來。于是原問題抓換成從這189個(gè)數(shù)中選最多9個(gè)數(shù)出來，使得他們的和滿足一定的條件。整個(gè)問題的解空間小于21^9 ，這個(gè)數(shù)字大概是5000億，采用深搜，再根據(jù)位數(shù)為21這個(gè)條件剪一下枝，最終的解空間應(yīng)該不會(huì)超過100億。

這種算法的復(fù)雜度是O(N^9)，而不是O(9^N)，N為位數(shù)。

---

作者: KBTiller    時(shí)間: 2011-05-18 10:50


回復(fù) 81# koolcoy


    9^21不需要那么多。位數(shù)為21應(yīng)該可以減去兩支

---

作者: koolcoy    時(shí)間: 2011-05-18 19:14
用python實(shí)現(xiàn)了一下這個(gè)算法
測試結(jié)果：
[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

1. 
   
2. #!/usr/bin/env python
   
3. 
   
4. import sys
   
5. 
   
6. LENGTH = int(sys.argv[1])
   
7. TABLE = tuple([tuple([x * (i**LENGTH) for x in range(1, LENGTH + 1)])
   
8.                                                 for i in range(1, 10)])
   
9. MAX = 10 ** LENGTH - 1
   
10. MIN = 10 ** (LENGTH - 1)
    
11. 
    
12. def isValidNumber(number, digit):
    
13.         tmp = [0] * 10
    
14.         for ch in str(number):
    
15.                 tmp[ord(ch) - ord('0')] += 1
    
16.         tmp.pop(0)
    
17.         return tmp == digit
    
18. 
    
19. def search(left, index, partialSum, digit):
    
20.         if index < 8 and left > 0:
    
21.                 search(left, index + 1, partialSum, digit)
    
22. 
    
23.         for count in range(1, left + 1):
    
24.                 digit[index] = count
    
25.                 value = TABLE[index][count - 1]
    
26.                 sum = partialSum + value
    
27. 
    
28.                 if sum > MAX:
    
29.                         break
    
30. 
    
31.                 if sum > MIN:
    
32.                         if isValidNumber(sum, digit):
    
33.                                 print sum
    
34.                 if index < 8 and left > count:
    
35.                         search(left - count, index + 1, sum, digit)
    
36.        
    
37.         digit[index] = 0
    
38. 
    
39. def main():
    
40.         digit = [0] * 9
    
41.         search(LENGTH, 0, 0, digit)
    
42. 
    
43. if __name__ == "__main__":
    
44.         main()
    

復(fù)制代碼

---

作者: koolcoy    時(shí)間: 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    時(shí)間: 2011-05-18 20:41
先mark一下，今天加班太累了。

---

作者: koolcoy    時(shí)間: 2011-05-18 22:42
又用C++實(shí)現(xiàn)了一下這個(gè)算法，結(jié)果大大地出乎我的意料{: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

1. 
   
2. #include <cstdio>
   
3. #include <cstring>
   
4. #include <cstdlib>
   
5. 
   
6. template<int LENGTH>
   
7. class Integer {
   
8.         typedef unsigned int U32;
   
9.         typedef unsigned long long U64;
   
10. public:
    
11.         Integer() {
    
12.                 for (int i = 0; i < LENGTH; ++i) {
    
13.                         data[i] = 0;
    
14.                 }
    
15.         }
    
16. 
    
17.         Integer(U32 that) {
    
18.                 copy(that);
    
19.         }
    
20. 
    
21.         const Integer& operator = (U32 that) {
    
22.                 copy(that);
    
23.                 return *this;
    
24.         }
    
25. 
    
26.         const Integer& operator += (const Integer& that) {
    
27.                 int carry = 0;
    
28.                 for (int i = 0; i < LENGTH; ++i) {
    
29.                         data[i] += that.data[i] + carry;
    
30.                         if (data[i] > BASE) {
    
31.                                 carry = data[i] / BASE;
    
32.                                 data[i] = data[i] % BASE;
    
33.                         } else {
    
34.                                 carry = 0;
    
35.                         }
    
36.                 }
    
37.                 return *this;
    
38.         }
    
39. 
    
40.         const Integer& operator *= (U32 that) {
    
41.                 U64 carry = 0;
    
42.                 for (int i = 0; i < LENGTH; ++i) {
    
43.                         U64 tmp = (U64)data[i] * (U64)that + carry;
    
44.                         if (tmp > BASE) {
    
45.                                 carry = tmp / BASE;
    
46.                                 data[i] = tmp % BASE;
    
47.                         } else {
    
48.                                 carry = 0;
    
49.                                 data[i] = tmp;
    
50.                         }
    
51.                 }
    
52.                 return *this;
    
53.         }
    
54. 
    
55.         Integer operator + (const Integer& that) const {
    
56.                 Integer tmp = *this;
    
57.                 return tmp += that;
    
58.         }
    
59. 
    
60.         Integer operator * (U32 that) const {
    
61.                 Integer tmp = *this;
    
62.                 return tmp *= that;
    
63.         }
    
64. 
    
65.         bool operator < (const Integer& that) const {
    
66.                 for (int i = LENGTH - 1; i >= 0; --i) {
    
67.                         if (data[i] < that.data[i]) {
    
68.                                 return true;
    
69.                         } else if (data[i] > that.data[i]) {
    
70.                                 return false;
    
71.                         }
    
72.                 }
    
73.                 return false;
    
74.         }
    
75. 
    
76.         bool operator > (const Integer& that) const {
    
77.                 return std::memcmp(data, that.data, sizeof(data)) != 0
    
78.                                 && !(*this < that);
    
79.         }
    
80. 
    
81.         void validate(char digit[9]) const {
    
82.                 char decimal[LENGTH * WIDTH + 1];
    
83.                 toString(decimal);
    
84. 
    
85.                 char actual[10] = {0};
    
86.                 for (int i = 0; i < WIDTH * LENGTH; ++i) {
    
87.                         ++actual[decimal[i] - '0'];
    
88.                 }
    
89.                 if (std::memcmp(actual + 1, digit, 9) == 0) {
    
90.                         output(decimal);
    
91.                 }
    
92.         }
    
93. 
    
94.         void toString(char* decimal) const {
    
95.                 for (int i = LENGTH - 1; i >= 0; --i) {
    
96.                         std::sprintf(decimal + WIDTH * (LENGTH - 1 - i), "%09d", data[i]);
    
97.                 }
    
98.                 decimal[LENGTH * WIDTH] = 0;
    
99.         }
    
100. 
     
101.         void show() const {
     
102.                 char decimal[LENGTH * WIDTH + 1];
     
103.                 toString(decimal);
     
104.                 printf("%s\n", decimal);
     
105.         }
     
106. 
     
107. private:
     
108.         enum {
     
109.                 BASE = 1000000000, /* This is 10^9 */
     
110.                 WIDTH = 9
     
111.         };
     
112.         U32 data[LENGTH];
     
113. 
     
114.         void copy(U32 that) {
     
115.                 data[0] = that % BASE;
     
116.                 data[1] = that / BASE;
     
117.                 for (int i = 2; i < LENGTH; ++i) {
     
118.                         data[i] = 0;
     
119.                 }
     
120.         }
     
121. 
     
122.         static void output(const char* decimal) {
     
123.                 int i = 0;
     
124.                 while (decimal[i] == '0') {
     
125.                         ++i;
     
126.                 }
     
127.                 printf("%s\n", decimal + i);
     
128.         }
     
129. };
     
130. 
     
131. typedef Integer<3> Bigint;
     
132. 
     
133. Bigint MIN;
     
134. Bigint MAX;
     
135. Bigint** TABLE;
     
136. 
     
137. void createSumTable(int length) {
     
138.         TABLE = new Bigint*[9];
     
139.         for (int i = 0; i < 9; ++i) {
     
140.                 TABLE[i] = new Bigint[length];
     
141. 
     
142.                 TABLE[i][0] = i + 1;
     
143.                 for (int j = 1; j < length; ++j) {
     
144.                         TABLE[i][0] *= (i + 1);
     
145.                 }
     
146. 
     
147.                 for (int j = 1; j < length; ++j) {
     
148.                         TABLE[i][j] = TABLE[i][0] * (j + 1);
     
149.                 }
     
150.         }
     
151. }
     
152. 
     
153. void initialize(int length) {
     
154.         MIN = 10;
     
155.         for (int i = 0; i < length - 2; ++i) {
     
156.                 MIN *= 10;
     
157.         }
     
158.         MAX = MIN * 10;
     
159. 
     
160.         createSumTable(length);
     
161. }
     
162. 
     
163. void search(int left, int index, Bigint partialSum, char* digit) {
     
164.         if (index < 8 && left > 0) {
     
165.                 search(left, index + 1, partialSum, digit);
     
166.         }
     
167.         for (int count = 1; count < left + 1; ++count) {
     
168.                 digit[index] = count;
     
169.                 Bigint sum = partialSum + TABLE[index][count - 1];
     
170. 
     
171.                 if (sum > MAX) {
     
172.                         break;
     
173.                 }
     
174.                 if (sum > MIN) {
     
175.                         sum.validate(digit);
     
176.                 }
     
177.                 if (index < 8 && left > count) {
     
178.                         search(left - count, index + 1, sum, digit);
     
179.                 }
     
180.         }
     
181.         digit[index] = 0;
     
182. }
     
183. 
     
184. int main(int argc, char** argv) {
     
185.         int length = 0;
     
186.         if (argc != 2 || sscanf(argv[1], "%d", &length) != 1 || length <= 0) {
     
187.                 std::fprintf(stderr, "Usage: %s <length>\n", argv[0]);
     
188.         }
     
189. 
     
190.         initialize(length);
     
191.         char* digit = (char*)std::calloc(length, 1);
     
192.         search(length, 0, Bigint(0), digit);
     
193.         return 0;
     
194. }
     

復(fù)制代碼

---

作者: koolcoy    時(shí)間: 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    時(shí)間: 2011-05-18 23:55


把sprintf調(diào)用去掉后竟然{: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

1. 
   
2. #include <cstdio>
   
3. #include <cstring>
   
4. #include <cstdlib>
   
5. 
   
6. template<int LENGTH>
   
7. class Integer {
   
8.         typedef unsigned int U32;
   
9.         typedef unsigned long long U64;
   
10. public:
    
11.         Integer() {
    
12.                 for (int i = 0; i < LENGTH; ++i) {
    
13.                         data[i] = 0;
    
14.                 }
    
15.         }
    
16. 
    
17.         Integer(U32 that) {
    
18.                 copy(that);
    
19.         }
    
20. 
    
21.         const Integer& operator = (U32 that) {
    
22.                 copy(that);
    
23.                 return *this;
    
24.         }
    
25. 
    
26.         const Integer& operator += (const Integer& that) {
    
27.                 int carry = 0;
    
28.                 for (int i = 0; i < LENGTH; ++i) {
    
29.                         data[i] += that.data[i] + carry;
    
30.                         if (data[i] > BASE) {
    
31.                                 carry = data[i] / BASE;
    
32.                                 data[i] = data[i] % BASE;
    
33.                         } else {
    
34.                                 carry = 0;
    
35.                         }
    
36.                 }
    
37.                 return *this;
    
38.         }
    
39. 
    
40.         const Integer& operator *= (U32 that) {
    
41.                 U64 carry = 0;
    
42.                 for (int i = 0; i < LENGTH; ++i) {
    
43.                         U64 tmp = (U64)data[i] * (U64)that + carry;
    
44.                         if (tmp > BASE) {
    
45.                                 carry = tmp / BASE;
    
46.                                 data[i] = tmp % BASE;
    
47.                         } else {
    
48.                                 carry = 0;
    
49.                                 data[i] = tmp;
    
50.                         }
    
51.                 }
    
52.                 return *this;
    
53.         }
    
54. 
    
55.         Integer operator + (const Integer& that) const {
    
56.                 Integer tmp = *this;
    
57.                 return tmp += that;
    
58.         }
    
59. 
    
60.         Integer operator * (U32 that) const {
    
61.                 Integer tmp = *this;
    
62.                 return tmp *= that;
    
63.         }
    
64. 
    
65.         bool operator > (const Integer& that) const {
    
66.                 for (int i = LENGTH - 1; i >= 0; --i) {
    
67.                         if (data[i] > that.data[i]) {
    
68.                                 return true;
    
69.                         } else if (data[i] < that.data[i]) {
    
70.                                 return false;
    
71.                         }
    
72.                 }
    
73.                 return false;
    
74.         }
    
75. 
    
76.         bool operator < (const Integer& that) const {
    
77.                 return std::memcmp(data, that.data, sizeof(data)) != 0
    
78.                                 && !(*this > that);
    
79.         }
    
80. 
    
81.         void validate(char digit[9]) const {
    
82.                 char decimal[LENGTH * WIDTH + 1];
    
83.                 toString(decimal);
    
84. 
    
85.                 char actual[10] = {0};
    
86.                 for (int i = 0; i < WIDTH * LENGTH; ++i) {
    
87.                         ++actual[decimal[i] - '0'];
    
88.                 }
    
89.                 if (std::memcmp(actual + 1, digit, 9) == 0) {
    
90.                         output(decimal);
    
91.                 }
    
92.         }
    
93. 
    
94.         void toString(char* decimal) const {
    
95.                 for (int i = 0; i < LENGTH; ++i) {
    
96.                         convertChunk(data[LENGTH - i - 1], decimal + WIDTH * i);
    
97.                 }
    
98.                 decimal[LENGTH * WIDTH] = 0;
    
99.         }
    
100. 
     
101. private:
     
102.         enum {
     
103.                 BASE = 1000000000, /* This is 10^9 */
     
104.                 WIDTH = 9
     
105.         };
     
106.         U32 data[LENGTH];
     
107. 
     
108.         static void output(const char* decimal) {
     
109.                 int i = 0;
     
110.                 while (decimal[i] == '0') {
     
111.                         ++i;
     
112.                 }
     
113.                 printf("%s\n", decimal + i);
     
114.         }
     
115. 
     
116.         static void convertChunk(U32 digit, char* decimal) {
     
117.                 for (int i = 0; i < WIDTH; ++i) {
     
118.                         decimal[WIDTH - 1 - i] = digit % 10 + '0';
     
119.                         digit /= 10;
     
120.                 }
     
121.         }
     
122. 
     
123.         void copy(U32 that) {
     
124.                 data[0] = that % BASE;
     
125.                 data[1] = that / BASE;
     
126.                 for (int i = 2; i < LENGTH; ++i) {
     
127.                         data[i] = 0;
     
128.                 }
     
129.         }
     
130. };
     
131. 
     
132. typedef Integer<SIZE> Bigint;
     
133. 
     
134. Bigint MIN;
     
135. Bigint MAX;
     
136. Bigint** TABLE;
     
137. 
     
138. void createSumTable(int length) {
     
139.         TABLE = new Bigint*[9];
     
140.         for (int i = 0; i < 9; ++i) {
     
141.                 TABLE[i] = new Bigint[length];
     
142. 
     
143.                 TABLE[i][0] = i + 1;
     
144.                 for (int j = 1; j < length; ++j) {
     
145.                         TABLE[i][0] *= (i + 1);
     
146.                 }
     
147. 
     
148.                 for (int j = 1; j < length; ++j) {
     
149.                         TABLE[i][j] = TABLE[i][0] * (j + 1);
     
150.                 }
     
151.         }
     
152. }
     
153. 
     
154. void initialize(int length) {
     
155.         MIN = 10;
     
156.         for (int i = 0; i < length - 2; ++i) {
     
157.                 MIN *= 10;
     
158.         }
     
159.         MAX = MIN * 10;
     
160. 
     
161.         createSumTable(length);
     
162. }
     
163. 
     
164. void search(int left, int index, Bigint partialSum, char* digit) {
     
165.         if (index < 8 && left > 0) {
     
166.                 search(left, index + 1, partialSum, digit);
     
167.         }
     
168.         for (int count = 1; count < left + 1; ++count) {
     
169.                 digit[index] = count;
     
170.                 Bigint sum = partialSum + TABLE[index][count - 1];
     
171. 
     
172.                 if (sum > MAX) {
     
173.                         break;
     
174.                 }
     
175.                 if (sum > MIN) {
     
176.                         sum.validate(digit);
     
177.                 }
     
178.                 if (index < 8 && left > count) {
     
179.                         search(left - count, index + 1, sum, digit);
     
180.                 }
     
181.         }
     
182.         digit[index] = 0;
     
183. }
     
184. 
     
185. int main(int argc, char** argv) {
     
186.         int length = 0;
     
187.         if (argc != 2 || sscanf(argv[1], "%d", &length) != 1 || length <= 0) {
     
188.                 std::fprintf(stderr, "Usage: %s <length>\n", argv[0]);
     
189.         }
     
190. 
     
191.         initialize(length);
     
192.         char* digit = (char*)std::calloc(length, 1);
     
193.         search(length, 0, Bigint(0), digit);
     
194.         return 0;
     
195. }
     

復(fù)制代碼

---

作者: KBTiller    時(shí)間: 2011-05-19 09:26
只要是提供組合數(shù)的解法
各種方案的解空間是一樣大的

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

---

作者: koolcoy    時(shí)間: 2011-05-19 09:48
回復(fù) 89# KBTiller


    顯然不一樣，按這種方法窮舉的話，其復(fù)雜度是O(N^9)，如果按各個(gè)數(shù)位上的數(shù)字來枚舉的話，復(fù)雜度O(9^N)，一個(gè)是多項(xiàng)式級的復(fù)雜度，另外一個(gè)是指數(shù)級的復(fù)雜度。復(fù)雜度跟解空間是等價(jià)的。

---

作者: KBTiller    時(shí)間: 2011-05-19 09:52


回復(fù) 90# koolcoy


    怎么會(huì)呢？21位數(shù)的各種組合的數(shù)目是一定的。這個(gè)值可以精確求出，14139189
    當(dāng)然，我也贊同嵌套的層數(shù)越少越好。但組合的總數(shù)目是一樣的

---

作者: KBTiller    時(shí)間: 2011-05-19 09:53
回復(fù) 90# koolcoy


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

---

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

---

作者: KBTiller    時(shí)間: 2011-05-19 10:13
不，10樓的算法提到了“順序符合”，即“有序”，這個(gè)很重要
123XXXX和321XXXX不可能都出現(xiàn)

---

作者: koolcoy    時(shí)間: 2011-05-19 10:40
回復(fù) 94# KBTiller

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

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

---

作者: KBTiller    時(shí)間: 2011-05-19 10:53
回復(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    時(shí)間: 2011-05-19 10:55
回復(fù) 95# koolcoy


   

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

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

---

作者: koolcoy    時(shí)間: 2011-05-19 11:09
回復(fù) 97# KBTiller

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

---

作者: xxw19840406    時(shí)間: 2011-06-15 20:28
128468643043731391252
449177399146038697307

---

歡迎光臨 Chinaunix (http://www.72891.cn/)

Powered by Discuz! X3.2

感谢您访问我们的网站，您可能还对以下资源感兴趣：

亚洲av成人无遮挡网站在线观看

<nobr id="8e47h"></nobr>