Problem 164

Posted by ygc on August 22, 2008 Leave a comment (2) Go to comments

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

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)