程序员的算法趣题Perl版（四）

第十一题 
用斐波那契数列中的每一个数除以其数位上所有数字之和，求出能整除的数。我这里设置的范围是前1000个数字。

#! perl# 20180108# this program is used to find out some numbers in Fibonacci , and the numbers can be divisible# by the sum of its every single number;use strict;# the special Fibonacci;my @fibonacci;# the maximum of times that the recusive function is executed my $max = 1000;&createFibonacci(1, 1, 0, \@fibonacci);# printforeach(@fibonacci) {    print $_ . "\n";}sub createFibonacci {    my $first = shift;    my $second = shift;    # the     my $count = shift;    # the array point    my $p = shift;    my $third = $first + $second;    # push if the number is matched    push @$p, $third if &check($third);    $count ++;    # the length of array now;    my $size = @$p;    return 0 if($size == 11);    return 0 if $count == $max;    # if not contiue...    &createFibonacci($second, $third, $count, $p);}sub check {    my $num = shift;    my $leng = length $num;    my $sum = &sum($num, $leng);    return 1 if ($num % $sum) == 0;    0;}# this function is used to sum a number`s every single numbers;sub sum {    my $num = shift;    my $leng = shift;    my $sum = 0;    for(my $i = 0; $i < $leng; $i ++) {        return $num if $leng == 1;        $sum += substr $num, $i, 1;    }    $sum;}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

答案： 
2 
3 
5 
8 
21 
144 
2584 
14930352 
86267571272 
498454011879264 
160500643816367088

第十二题 
求在计算平方根的时候，最早让0-9全部出现的最小整数。

#! perl# 20180109# 20180110use strict;for(my $i = 2; $i < 5000; $i ++) {    if(&check($i, 0)) {        print "$i\n";        last;    }}sub check {    # the number checked    my $num = shift;    # '0' means that includes integer, '1' means just decimal    my $justDecimal = shift;    # get the square root of a number    my $sqrtR = sprintf "%10.10f", sqrt $num;    # split with '.'    my @allNum = split /\./, $sqrtR;    # this array is used to check if the number is repeat    my @arr;    if($justDecimal) {        # just split the decimal part        @arr = split //, $allNum[1];    } else {        my @integerArr = split //, $allNum[0];        my @decimalArr = split //, $allNum[1];        # include integer, get 10 numbers from the left        @arr = (@integerArr, @decimalArr)[0..9];    }    &isRepeat(\@arr);}sub isRepeat {    # the point of the array    my $p = shift;    # key is numbers, value is times    my %hash = ();    my @uniqueArr = grep {        # put the number which is found only once into the hash        ++ $hash{$_} < 2;        } @$p;    # the array is repeat if the size of the array is not 10    return 1 if $#uniqueArr + 1 == 10;}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

答案： 
包含整数部分：1362 
只有小数部分：143

第十三题 
给字母赋值，求使下列算式成立的解有多少种。字母代表的数字不可以相等。

#! perl# 20180114# 20180116# this guy is used to compute READ + WRITE + TALK = SKILL;use Algorithm::Combinatorics qw(                                combinations                                combinations_with_repetition                                variations                                variations_with_repetition                                tuples                                tuples_with_repetition                                permutations                                circular_permutations                                derangements                                complete_permutations                                partitions                                subsets                            );use strict;my $start = time;my @numbers = (0..9);my @result;my $count = 0;&sum(\@numbers, 10);foreach (@result) {    print "$_\n";}print "$count \n";my $duration = time - $start;print "$duration s\n";sub sum {    my $numbersP = shift;    my $k = shift;    # permutation    my $iter = variations($numbersP, $k);    while(my $item = $iter -> next) {        &isRight($item);    }}sub isRight {    my @str_arr = @{@_[0]};    my ($r, $e, $a, $d, $w, $i, $t, $l, $k, $s) = @str_arr;    # The highest number of digits can not be zero.    return 0 if $r == 0 || $w == 0 || $t == 0 || $s == 0;    my $read = $r * 1000 + $e * 100 + $a * 10 + $d;    my $write = $w * 10000 + $r * 1000 + $i * 100 + $t * 10 + $e;    my $talk = $t * 1000 + $a * 100 + $l * 10 + $k;    my $skill = $s * 10000 + $k * 1000 + $i * 100 + $l * 10 + $l;    if ($read + $write + $talk == $skill) {        push @result, "$read + $write + $talk = $skill";        $count ++;        return 1;    }    0}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

答案： 
10种 
1632 + 41976 + 7380 = 50988 
2543 + 72065 + 6491 = 81099 
4905 + 24689 + 8017 = 37611 
5094 + 75310 + 1962 = 82366 
5096 + 35710 + 1982 = 42788 
5180 + 65921 + 2843 = 73944 
5270 + 85132 + 3764 = 94166 
7092 + 37510 + 1986 = 46588 
7092 + 47310 + 1986 = 56388 
9728 + 19467 + 6205 = 35400