問(wèn)題描述
我寫(xiě)了這個(gè)函數(shù)來(lái)返回給定數(shù)字的階乘
func 階乘(_ n: Int) ->詮釋{如果 n == 0 {返回 1}別的 {返回 n * 階乘(n - 1)}}打印(階乘(20))//2432902008176640000只要給定的數(shù)字不超過(guò) 20，就可以正常工作，因?yàn)槟菢咏Y(jié)果就太高了！
我怎樣才能繞過(guò)這個(gè)限制，從而計(jì)算更高數(shù)字的階乘?
我四處搜索并找到了一些用于 Swift 的 bignum 庫(kù).我這樣做是為了學(xué)習(xí)和熟悉 Swift，因此我想自己解決這個(gè)問(wèn)題.
這里有一個(gè)方法可以讓你找到非常大的階乘.
將大數(shù)表示為數(shù)字?jǐn)?shù)組.例如 987 將是 [9, 8, 7].將該數(shù)字乘以整數(shù) n 需要兩個(gè)步驟.
- 將該數(shù)組中的每個(gè)值乘以
n. - 執(zhí)行進(jìn)位運(yùn)算以返回再次為單個(gè)數(shù)字的結(jié)果.
例如987 * 2:
讓 arr = [9, 8, 7]讓 arr2 = arr.map { $0 * 2 }print(arr2)//[18, 16, 14]現(xiàn)在，執(zhí)行進(jìn)位操作.從個(gè)位數(shù)開(kāi)始，14太大了，所以保留4，攜帶1.將1添加到16得到17.
[18, 17, 4]重復(fù)十位:
[19, 7, 4]然后是百位:
[1, 9, 7, 4]最后，為了打印，您可以將其轉(zhuǎn)換回字符串:
讓 arr = [1, 9, 7, 4]打印(arr.map(String.init).joined())<塊引用>
1974
<小時(shí)>
應(yīng)用該技術(shù)，這里有一個(gè)執(zhí)行進(jìn)位操作的 carryAll 函數(shù)，以及一個(gè)使用它來(lái)計(jì)算非常大的階乘的 factorial:
func carryAll(_ arr: [Int]) ->[詮釋] {var 結(jié)果 = [整數(shù)]()var 進(jìn)位 = 0對(duì)于 arr.reversed() 中的 val {讓總計(jì) = val + 進(jìn)位讓數(shù)字 = 總計(jì) % 10進(jìn)位 = 總數(shù)/10結(jié)果.追加(數(shù)字)}同時(shí)攜帶>0 {讓數(shù)字 = 攜帶 % 10進(jìn)位 = 進(jìn)位/10結(jié)果.追加(數(shù)字)}返回結(jié)果.reversed()}func 階乘(_ n: Int)->細(xì)繩 {變量結(jié)果 = [1]對(duì)于我在 2...n {結(jié)果 = 結(jié)果.map { $0 * i }結(jié)果 = 攜帶所有(結(jié)果)}返回結(jié)果.map(String.init).joined()}打印(階乘(1000))<塊引用>
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887325197795059509952761208749754624970436014182780946464962910563938874378864873371191810458257836478499770124766328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791438537195882498081268678383745597317461360853795345242215865932019280908782973084313928444032812315586110369768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215668325720808213331861168115536??15836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
I have written this function to return the factorial of a given number
func factorial(_ n: Int) -> Int {
if n == 0 {
return 1
}
else {
return n * factorial(n - 1)
}
}
print( factorial(20) ) // 2432902008176640000
Works as it should, as long the given number does not exceed 20, because then the result becomes too high!
How can I circumvent this limit and thus calculate the factorial of higher numbers?
I have searched around and found some bignum libraries for Swift. I'm doing this to learn and be familiar with Swift, therefore I want to figure this out on my own.
Here's an approach that will let you find very large factorials.
Represent large numbers as an array of digits. For instance 987 would be [9, 8, 7]. Multiplying that number by an integer n would require two steps.
- Multiply each value in that array by
n. - Perform a carry operation to return a result that is again single digits.
For example 987 * 2:
let arr = [9, 8, 7]
let arr2 = arr.map { $0 * 2 }
print(arr2) // [18, 16, 14]
Now, perform the carry operation. Starting at the one's digit, 14 is too big, so keep the 4 and carry the 1. Add the 1 to 16 to get 17.
[18, 17, 4]
Repeat with the ten's place:
[19, 7, 4]
And then with the hundred's place:
[1, 9, 7, 4]
Finally, for printing, you could convert this back to a string:
let arr = [1, 9, 7, 4]
print(arr.map(String.init).joined())
1974
Applying that technique, here is a carryAll function that performs the carry operation, and a factorial that uses it to calculate very large factorials:
func carryAll(_ arr: [Int]) -> [Int] {
var result = [Int]()
var carry = 0
for val in arr.reversed() {
let total = val + carry
let digit = total % 10
carry = total / 10
result.append(digit)
}
while carry > 0 {
let digit = carry % 10
carry = carry / 10
result.append(digit)
}
return result.reversed()
}
func factorial(_ n: Int) -> String {
var result = [1]
for i in 2...n {
result = result.map { $0 * i }
result = carryAll(result)
}
return result.map(String.init).joined()
}
print(factorial(1000))
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
這篇關(guān)于在 Swift 3 中，當(dāng)結(jié)果變得太高時(shí)如何計(jì)算階乘?的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！