求大數花朵數的新思路

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

【關鍵詞】花朵數 C語言 大數加法

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

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

num_time下標

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

1^3 + 3^3 + 5^3 = 153，在這個結果153中，各個位數出現的次數為：

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

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

時間復雜度分析：

如果僅從循環次數上看，對于n位數，常規算法循環次數為：10^n次。而本算法循環次數為： n^10次。則可得出結論：

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

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

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

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

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

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

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

注：

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

（2） 9在21位數中出現的次數不能超過9。因為（9^21）*10的結果已經是22位了。所以此重循環只到9。

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

（4）reverse（）用于將字符串反轉，用于大數加法。

（5）大數加法思路：用三個字符串存放兩個加數與結果。

每次將兩個數字相應的位相加，再加上低一位的進位。比如：

189

+257

-------

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

結果有兩種情況：

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

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

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

位數少的數（a）結束后，有這種情況要分別處理

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

74

+9911

--------

只需將b后邊的內容直接復制到result即可。

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

74

+9981

--------

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

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

74

+219981

--------

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

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

74

+2181

--------

下一位為b的值+1，然后將b中剩余內容復制到result。