Problem 164

Numbers for which no three consecutive digits have a sum greater than a given value.

How many 20 digit numbers n (without any leading zero) exist such that no three consecutive digits of n have a
sum greater than 9?

这道题计算的时候,还是超出了精度。很多题都这样,当然我还是可以跟以前一样,把数拆成数组,但是经常这样,很烦人啊。
找到了一个C库GMP,   这个世界爽YY了。。。

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
library(gmp)  
 
mem <- array(NA, c(10, 10, 20)) 
 
rec.cnt <- function(a, b, n) {
    if (n == 2)
        return (1)
    cnt <- 0
    if (! is.na(mem[a+1,b+1,n]))
        return (mem[a+1,b+1,n])
 
    C <- 9-a-b      
    if (C >= 0) {               
        for (c in 0:C) {                       
            cnt <- cnt +rec.cnt(b, c, n-1)                      
        }       
    }
 
    mem[a+1,b+1,n] <<-  cnt      
    return (cnt)
}
 
cnt <- as.bigz(0)
n <- 20
for (a in 1:9)
    for (b in 0:9)
    cnt <- cnt + rec.cnt(a,b,n)
 
print(cnt)

Answer: 378158756814587

m4s0n501

Related Posts

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>