Keep Hacking :)

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

Project Euler 92的解答

題目是這樣說的，妳只要將一個數字的各位數字平方後相加, 然後妳就一直重複這樣做，要嘛會停在1，不然就會掉到一個由89開頭的迴圈中(是有沒有這麼神奇！？)。

問題就是要去問說，在一千萬以下，有多少數字會跑到89？

直觀的做法

由於經過一次操作過後，數字和一定不會超過567，所以我們可以做一個表，然後去看在0到567中間的數字會停在1或者是89。之後在去檢查小於一千萬裡面的數，有多少會掉到會回到89的數裡面，就可以算出來答案了。

可是寫出來的程式跑的不是很快，讓人心情不是很好，所以就想了另一個演算法。

改進過的做法

後來想想，如果像是1234567的7!種組合，其實經過一次操作後，都會回到同一個數字，可是我之前的做法就會重複算了7!次，就會慢了許多，因為一直重複算一樣的東西。

所以新的做法，我是先去算出小於一千萬的數字經過一次操作後，所有可能的數字還有她們的組合數，然後再去看她們有多少會跑到89。

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

#!/usr/bin/env perl
use v5.12;
use warnings;
use List::Util qw(sum);

sub to_1or89 {
    my $x = shift;
    while ( $x != 89 && $x != 1 ) {
        $x = sum( map { $_ * $_ } split //, $x );
    }
    return $x;
}

my %hash = ( 0 => 1 );
my @squares = ( 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 );
foreach ( 0 .. 6 ) {
    my %tmp;
    while ( my ( $k, $v ) = each %hash ) {
        $tmp{ $k + $_ } += $v foreach @squares;
    }
    %hash = %tmp;
}

my %ans = ( 1 => 0, 89 => 0 );
delete $hash{0};
while ( my ( $k, $v ) = each %hash ) {
    $ans{ to_1or89($k) } += $v;
}
say $ans{89}

這樣改寫後，速度有十分大的提升啊，不到一秒就算完了，看來之後這種題目還是多花一點心思想一下好了。

其他資訊

Happy Number:http://en.wikipedia.org/wiki/Happy_number

Comments