【摘 要】對于超過整形范圍的大數(shù)花朵數(shù)，隨著位數(shù)的增長，所需時間以指數(shù)級增加，而且需要用大數(shù)加法和大數(shù)乘法來實現(xiàn)，效率非常低下。本文提出一個算法，去掉了重復(fù)計算的情況，可以大大提高問題的效率。

【關(guān)鍵詞】花朵數(shù) C語言 大數(shù)加法

所謂花朵數(shù)，就是其各個位的位數(shù)次方之和等于其自身的整數(shù)。比如三位數(shù)153 = 1^3 + 3^3 + 5^3，四位數(shù)1634 = 1^4 + 6^4 + 3^4 + 4^4。求花朵數(shù)的常規(guī)算法為：對每個數(shù)字分別取出各個位，求出冪后相加，再判斷是否和原數(shù)相同。當(dāng)位數(shù)為n時，此算法時間復(fù)雜度為10^n。而此算法的效率低下的原因是，計算了多次重復(fù)的情況，比如153、135、315、351、513、531這六個數(shù)，一共計算了六次，但實際上只要計算一次就可以了。所以本文提出的新算法，核心思路就是去掉這些重復(fù)的情況。具體以求3位花朵數(shù)來說明：

在一個3位數(shù)中，0-9每個數(shù)可能出現(xiàn)的次數(shù)是0-3次共4種情況（不考慮最高位為0的情況），也就是說，如果0-9十個數(shù)字出現(xiàn)的次數(shù)（可能為0）之和為3，那么這就是一個“去掉了重復(fù)情況的3位數(shù)”，比如1、5、3各出現(xiàn)1次，而其他七個數(shù)字出現(xiàn)次數(shù)都為0，我們用數(shù)組num_time來存放十個次數(shù)，則有

num_time下標(biāo)

十個次數(shù)之和sum（num_time）的值為1+1+1=3，說明這是一個三位數(shù)。那么這種情況有六種可能：153、135、315、351、513、531。如果按正常的算法從100循環(huán)到999，那么要判斷6次，而現(xiàn)在只要判斷一次。那么這就是一個去掉了重復(fù)情況的三位數(shù)。現(xiàn)在我們只要求出三個數(shù)的三次方，并加起來得到一個值，然后由這個值去判斷。也就是：

1^3 + 3^3 + 5^3 = 153，在這個結(jié)果153中，各個位數(shù)出現(xiàn)的次數(shù)為：

這個結(jié)果，和Num_time中的值是一致的。這就說明這個結(jié)果是一個符合條件的結(jié)果，并且這個結(jié)果只可能是上面六種中的一個，也就是我們需要的一個結(jié)果。如果十個次數(shù)之和不為3，說明不是3位數(shù)，那么跳過就可以了。

下面我們再來看一個反例：兩個數(shù)字2、4，分別出現(xiàn)2、1次。num_time[2]，num_time[4]的值分別為2、1，計算2^3 + 2^3 + 4^3 = 80。結(jié)果中8，0兩個數(shù)字分別出現(xiàn)1、1次，與num_time[2]，num_time[4]的值不同，所以不是結(jié)果。

時間復(fù)雜度分析：

如果僅從循環(huán)次數(shù)上看，對于n位數(shù)，常規(guī)算法循環(huán)次數(shù)為：10^n次。而本算法循環(huán)次數(shù)為： n^10次。則可得出結(jié)論：

（1）n>10時，本算法計算量大于常規(guī)算法

（2）n=10時，二者計算量相同

（3）n>10時，本算法計算量小于常規(guī)算法

而實際上，常規(guī)算法每次循環(huán)都要計算，而本算法中如果次數(shù)之和不為n則跳過。所以當(dāng)n較大時，效率大大提高。所以對于本題，提出的算法是窮舉：把每個數(shù)字出現(xiàn)次數(shù)窮舉出來，挑出共21次的情況來判斷。具體如下：

（1）十重循環(huán)（0-9），讓十個數(shù)字從0-21循環(huán)。也就是說，第i層循環(huán)的第j次，表示i這個數(shù)字在21位數(shù)中出現(xiàn)的次數(shù)。

（2）將十個次數(shù)加起來，如果是21，說明組成了一個21位數(shù)，如果不是21，則跳過。也可以設(shè)九重循環(huán)，最后一次的次數(shù)為21減去之前的次數(shù)和。當(dāng)然，因為總次數(shù)不能大于21，所以每一重循環(huán)先判斷當(dāng)前次數(shù)和是否超過21，若是，則跳過。

（3）按照要求，把它的各位的21次方相加，算出一個值，如果得到的也是21位數(shù)并且其各個位數(shù)出現(xiàn)次數(shù)與循環(huán)中出現(xiàn)的一樣，說明這就是一個符合要求的結(jié)果，輸出。

注：

（1）在求各位的21次方時，使用的是大數(shù)相加的方法，用字符串來模擬加法過程。

（2） 9在21位數(shù)中出現(xiàn)的次數(shù)不能超過9。因為（9^21）*10的結(jié)果已經(jīng)是22位了。所以此重循環(huán)只到9。

（3）大數(shù)加法很費時間，為了效率，可以將10個數(shù)的21次方先求出來，放入二維數(shù)組power_21中，使用時直接用。這個用init（）完成。

（4）reverse（）用于將字符串反轉(zhuǎn)，用于大數(shù)加法。

（5）大數(shù)加法思路：用三個字符串存放兩個加數(shù)與結(jié)果。

每次將兩個數(shù)字相應(yīng)的位相加，再加上低一位的進位。比如：

189

+257

-------

以第二位為例：應(yīng)為8+5+1（1為低一位的進位）。其和放在bit中。而個位相加沒有進位，所以將bit初值設(shè)0。

結(jié)果有兩種情況：

（1）bit>10：則result相應(yīng)位存入bit的個位，bit的十位留在bit中，作為高一位的進位。

（2）bit<10：則result相應(yīng)位存入bit的個位，bit置0。

這兩種情況都可以用bit%10和bit/10來表示。

位數(shù)少的數(shù)（a）結(jié)束后，有這種情況要分別處理

（1）a的最高位相加后無進位，eg.7+1<10。

74

+9911

--------

只需將b后邊的內(nèi)容直接復(fù)制到result即可。

（2）a的最高位相加后有進位，且b相應(yīng)的下面位全是9。

74

+9981

--------

則將所有連續(xù)的9全部置為0。后邊進位為1。

（3）a的最高位相加后有進位，且b相應(yīng)的下面有若干個9，后邊還有。

74

+219981

--------

則將所有連續(xù)的9全部置為0。下一位為b的值+1，然后將b中剩余內(nèi)容復(fù)制到result中。

（4）a的最高位相加后有進位，且b相應(yīng)的下面位不是9。

74

+2181

--------

下一位為b的值+1，然后將b中剩余內(nèi)容復(fù)制到result。