Keep Hacking :)

Life is complex, it has both real and imaginary parts.

Project Euler 113的解答

題目是這樣說的,如果一個數字從左到右的各個位數是不嚴格遞增的話,那我們就說這種數字叫做遞增數,像是134468。反之,如果一個數字從左到右的各個位數是不嚴格遞減的話,那我們就說這種數字叫做遞減數,像是66420。如果一個數字從左到右的各個位數字,不是屬於上述的兩種狀況之一的話,我們就稱它是彈性數(Bouncy Number)。

現在問題來了,想要請問小於10^100中的數字中,有多少不是彈性數?

高中排列組合

好吧,這題其實不是太難,如果妳的高中數學沒有忘的話:)

遞增數的個數是C(109, 9) - 1,遞減數的個數是C(110, 10) - 101,又遞增又遞減的有9 * 100個,所以就只要寫個binomial的函數就可以了:D

附上程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env perl
use v5.12;
use warnings;

sub binomial {
    use bigint;
    my ( $r, $n, $k ) = ( 1, @_ );
    $r = $r * ( $n + 1 - $_ ) / $_ foreach 1 .. $k;
    return $r;
}

my $n = 100;
say binomial( $n + 9, 9 ) - 1 + binomial( $n + 10, 10 ) - 101 - 9 * $n

所以只要善用數學,題目還是可以用很簡單的方法解出來的:D

Comments