在 Swift 3 中，当结果变得太高时如何计算阶乘? [英] In Swift 3, how to calculate the factorial when the result becomes too high?

问题描述

我写了这个函数来返回给定数字的阶乘

func 阶乘(_ n: Int) ->诠释{如果 n == 0 {返回 1}别的 {返回 n * 阶乘(n - 1)}}打印(阶乘(20))//2432902008176640000

只要给定的数字不超过 20，就可以正常工作，因为那样结果就太高了！

我怎样才能绕过这个限制，从而计算更高数字的阶乘?

我四处搜索并找到了一些用于 Swift 的 bignum 库.我这样做是为了学习和熟悉 Swift，因此我想自己解决这个问题.

解决方案

这里有一个方法可以让你找到非常大的阶乘.

将大数表示为数字数组.例如 987 将是 [9, 8, 7].将该数字乘以整数 n 需要两个步骤.

1. 将该数组中的每个值乘以 n.
2. 执行进位运算以返回再次为单个数字的结果.

例如987 * 2:

让 arr = [9, 8, 7]让 arr2 = arr.map { $0 * 2 }print(arr2)//[18, 16, 14]

现在，执行进位操作.从个位数开始，14太大了，所以保留4，携带1.将1添加到16得到17.

[18, 17, 4]

重复十位:

[19, 7, 4]

然后是百位:

[1, 9, 7, 4]

最后，为了打印，您可以将其转换回字符串:

让 arr = [1, 9, 7, 4]打印(arr.map(String.init).joined())

<块引用>

1974

<小时>

应用该技术，这里有一个执行进位操作的 carryAll 函数，以及一个使用它来计算非常大的阶乘的 factorial:

func carryAll(_ arr: [Int]) ->[诠释] {var 结果 = [整数]()var 进位 = 0对于 arr.reversed() 中的 val {让总计 = val + 进位让数字 = 总计 % 10进位 = 总数/10结果.追加(数字)}同时携带>0 {让数字 = 携带 % 10进位 = 进位/10结果.追加(数字)}返回结果.reversed()}func 阶乘(_ n: Int)->细绳 {变量结果 = [1]对于我在 2...n {结果 = 结果.map { $0 * i }结果 = 携带所有(结果)}返回结果.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.

1. Multiply each value in that array by n.
2. 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

这篇关于在 Swift 3 中，当结果变得太高时如何计算阶乘?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！