求大數(shù)花朵數(shù)的新思路

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

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

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

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

num_time下標(biāo)

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

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

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

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

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

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

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

（2）n=10時(shí)，二者計(jì)算量相同

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

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

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

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

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

注：

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

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

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

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

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

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

189

+257

-------

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

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

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

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

這兩種情況都可以用bit%10和bit/10來(lái)表示。

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

（1）a的最高位相加后無(wú)進(jìn)位，eg.7+1<10。

74

+9911

--------

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

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

74

+9981

--------

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

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

74

+219981

--------

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

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

74

+2181

--------

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