sironekotoroの日記

Perl と Mac の初心者の備忘録

Perl入学式 in 東京 秋開講 第2回 ピザ会でのお題「コラッツの問題」

Perl入学式 in 東京では各回の講義終了後にピザ会(ピザ&ジュース代は参加者負担)を開催しており、そこでサポーター・受講者さんと雑談などをしております。

サポーター含め参加者が抱えているプログラムの問題や、詰まってしまったところを相談したり、エディタやGitの使い方、PerlExcelなど他のツール・ソフトの連携方法、業界の動向について話したりしています。全体的にゆるーい雰囲気です。

その中で、id:xtetsuji さんが課題が出し、志願者がコードを書いてその場で発表、という試みを行っています。

今回のお題:コラッツの問題

xtetsujiさんからのお題ですが、今回は「コラッツの問題」でした。コラッツ・・・聞いたことないですね・・・コラッタの仲間かな?来年ねずみ年だし・・・

コラッツの問題 - Wikipedia

コラッツの問題は、「任意の正の整数 n をとり、

n が偶数の場合、n を 2 で割る
n が奇数の場合、n に 3 をかけて 1 を足す

という操作を繰り返すと、どうなるか」というものである。

ねずみ関係なかった。

このコラッツの問題を 1, 2, 3, 4, 5 ・・・ と与える数字を変えていき、どのような経緯で数値が変わっていくかを出して欲しい、というものでした。

コラッツの問題を解くには・・・?

この問題は今回学習した、「繰り返し」と「条件分岐」に「四則演算」で解くことができますが、それだけではちょっと足りません。

例えば、n = 5 とすると以下のような経緯を経て1になります。

5: 16 -> 8 -> 4 -> 2 -> 1 -> end

n = 7 の場合にはこう。

7: 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end

つまり、与える数によって繰り返しの数が異なります。繰り返しの数が読めない場合、ちょっとした工夫が必要です。

それは、特定の条件の時に繰り返しを終わらせる last です。

繰り返し を抜ける last

これは Hello world! を10回表示するスクリプトです。

for ( 1 .. 10 ) {
    print "Hello world!\n";
}

これに1行加えます。

for ( 1 .. 10 ) {
    print "Hello world!\n";
    last;
}

このようにすると、Hello world!は1回のみ表示されます。処理が last に到達すると、その繰り返しから抜けると動きとなります。

コラッツの問題、何回ループするかは分からないので、とりあえず10000回くらいにしておきます。

lastを使う条件は n = 1 になった時です。

#!/usr/bin/env perl
use strict;
use warnings;

print "input number > ";

my $input_num = <STDIN>;
chomp $input_num;

print "$input_num: ";

for ( 0 .. 10000 ) {

    if ( $input_num == 1 ) {
        print "end\n";
        last;
    }
    elsif ( $input_num % 2 == 0 ) {

        # n が偶数の場合、n を 2 で割る
        $input_num = $input_num / 2;
    }
    else {
        # n が奇数の場合、n に 3 をかけて 1 を足す
        $input_num = $input_num * 3 + 1;
    }

    print $input_num . " -> ";

}

last のようにループ内で使える関数は nextredo があります。

perldoc.jp

回数を指定しないループ、無限ループ

先ほどの解き方だと、10000回の繰り返しで終わらなかった時には途中で終わってしまいます。

このように、繰り返しの回数が分からない場合には while を使います。Perl入学式のテキストでは「落ち穂拾い」として掲載しています。

落ち穂拾い: while ループ

while を使う時には無限ループにならないよう、ループを終わらせる処理を入れることが必要です。last ですね。

もし、処理を書き間違えて無限ループになってしまったら、Ctrl(Control)キーを押しながらCを押すことで強制的に止めることが可能です。

コラッツの問題のwhile版です。

#!/usr/bin/env perl
use strict;
use warnings;

print "input number > ";

my $input_num = <STDIN>;
chomp $input_num;

print "$input_num: ";

while (1) {

    if ( $input_num == 1 ) {
        print "end\n";
        last;
    }
    elsif ( $input_num % 2 == 0 ) {
        # n が偶数の場合、n を 2 で割る
        $input_num = $input_num / 2;
    }
    else {
        # n が奇数の場合、n に 3 をかけて 1 を足す
        $input_num = $input_num * 3 + 1;
    }

    print $input_num . " -> ";

}

繰り返しを繰り返す

さて、当初のレギュレーションでは与える数が変わっていく・・・というものでした。

今回はループの中にループを作る「二重ループ」で実現してみました。このような二重ループは「入れ子いれこ構造」「ネスト構造」などとも呼ばれます。

#!/usr/bin/env perl
use strict;
use warnings;

for my $number ( 1 .. 10 ) {

    print "$number: ";

    while (1) {

        if ( $number == 1 ) {
            print "end\n";
            last;
        }
        elsif ( $number % 2 == 0 ) {

            # n が偶数の場合、n を 2 で割る
            $number = $number / 2;
        }
        else {
            # n が奇数の場合、n に 3 をかけて 1 を足す
            $number = $number * 3 + 1;
        }

        print $number . " -> ";

    }

}
1: end
2: 1 -> end
3: 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end
4: 2 -> 1 -> end
5: 16 -> 8 -> 4 -> 2 -> 1 -> end
6: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end
7: 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end
8: 4 -> 2 -> 1 -> end
9: 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end
10: 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end

二重ループについては、掛け算の「九九の表」をスクリプトで再現してみる、ってのも良いかもしれません。

Perl入学式の第2回までの範囲で書いてみるとこんな感じですかね。

スペースの扱いをもっとスマートにしたい!という人は printf 関数に挑戦してみると良いと思います。

#!/usr/bin/env perl
use strict;
use warnings;

print '    1  2  3  4  5  6  7  8  9' . "\n";

for my $tate (1 .. 9){
    print "$tate:";
    for my $yoko ( 1 .. 9){

        if ($tate * $yoko < 10){
            print '  ' . $tate * $yoko;
        }else{
            print  ' ' . $tate * $yoko;
        }
    }
    print "\n";
}
    1  2  3  4  5  6  7  8  9
1:  1  2  3  4  5  6  7  8  9
2:  2  4  6  8 10 12 14 16 18
3:  3  6  9 12 15 18 21 24 27
4:  4  8 12 16 20 24 28 32 36
5:  5 10 15 20 25 30 35 40 45
6:  6 12 18 24 30 36 42 48 54
7:  7 14 21 28 35 42 49 56 63
8:  8 16 24 32 40 48 56 64 72
9:  9 18 27 36 45 54 63 72 81