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

竟然一月一更。。。

第四题 
假设一根木棒n厘米，需要切分为一厘米长的木棒，每根木棒只可以一个人切，木棒切成两根可以两个人切； 
求：n厘米长木棒，m个人最少要切几次，比如n=8，m=3，则需要切4次。

#! perl#20170930#use strict;sub cut {    my $barLength = @_[0];    my $num = @_[1];    my $currentParts = @_[2];    if($currentParts >= $barLength) {        0;    } elsif($currentParts <= $num) {        1 + &cut($barLength, $num, $currentParts * 2);    } else {        1 + &cut($barLength, $num, $currentParts + $num);    }}my $res1 = &cut(20, 3, 1);my $res2 = &cut(100, 5, 1);print $res1, "\n";print $res2, "\n";
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

n=100,m=5 答案为22 
n=20,m=3 答案为8

第五题 
1000日元兑换，可以兑换为10元、50元、100元、500元的硬币。 
要求兑换的硬币数不超过15个。

#! perl#20171010use strict;my $y10 = 0;my $y50 = 0;my $y100 = 0;my $y500 = 0;for($y10 = 0; $y10 <= 15; $y10 ++ ) {    for($y50 = 0; $y50 <= 15; $y50 ++ ) {        for($y100 = 0; $y100 <= 15; $y100 ++ ) {            for($y500 = 0; $y500 <= 2; $y500 ++ ) {                if($y10 + $y50 + $y100 + $y500 <= 15 ) {                    if($y10 * 10 + $y50 * 50 + $y100 * 100 + $y500 * 500 == 1000) {                        print "10yaun : ", $y10, " 50yuan ", $y50, " 100yuan "                            , $y100, " 500yuan ", $y500, "\n";                    }                }            }           }    }}
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

答案： 
10yaun : 0 50yuan 0 100yuan 0 500yuan 2 
10yaun : 0 50yuan 0 100yuan 5 500yuan 1 
10yaun : 0 50yuan 0 100yuan 10 500yuan 0 
10yaun : 0 50yuan 2 100yuan 4 500yuan 1 
10yaun : 0 50yuan 2 100yuan 9 500yuan 0 
10yaun : 0 50yuan 4 100yuan 3 500yuan 1 
10yaun : 0 50yuan 4 100yuan 8 500yuan 0 
10yaun : 0 50yuan 6 100yuan 2 500yuan 1 
10yaun : 0 50yuan 6 100yuan 7 500yuan 0 
10yaun : 0 50yuan 8 100yuan 1 500yuan 1 
10yaun : 0 50yuan 8 100yuan 6 500yuan 0 
10yaun : 0 50yuan 10 100yuan 0 500yuan 1 
10yaun : 0 50yuan 10 100yuan 5 500yuan 0 
10yaun : 5 50yuan 1 100yuan 4 500yuan 1 
10yaun : 5 50yuan 1 100yuan 9 500yuan 0 
10yaun : 5 50yuan 3 100yuan 3 500yuan 1 
10yaun : 5 50yuan 5 100yuan 2 500yuan 1 
10yaun : 5 50yuan 7 100yuan 1 500yuan 1 
10yaun : 5 50yuan 9 100yuan 0 500yuan 1 
10yaun : 10 50yuan 0 100yuan 4 500yuan 1

第六题 
改版考拉兹猜想 
n为偶数时 用n除以2 
n位奇数时 用n乘以3再加1 
如此循环操作，无论n为多少最后都是1 
改版： 
当初始值为偶数时，则执行n乘以3再加1，之后按照上述操作。

求10000以内可以得到初始值的偶数（比如2、4）个数

#! perl#20171031use strict;my $res = 0;for(my $i = 0; $i < 10000; $i += 2) {    my $j = $i;    $j = $j * 3 + 1;    while(1) {        if($j % 2 == 0) {            $j = $j / 2;        } else {            $j = $j * 3 + 1;        }        if($j == $i && $j != 1) {            $res ++;        } elsif($j == 1) {            last;        }    }}print "sum is ", $res, "\n";
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

答案为34个