次のような九九表を表示する関数 ninety_nine() を定義してください。
| 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
整数 n から m までの和、二乗の和、三乗の和を求める関数 sum_of_int(n. m), sum_of_square(n, m), sum_of_cube(n, m) を次に示す公式を使って定義してください。
x の y 乗を求める関数 power(x, y) を定義してください。ここでは、x を浮動小数点数, y を整数とします。
下図に示すフィボナッチ関数 fibo(n) を定義してください。
整数 n を b 進数 (2 <= b <= 16) で画面 (標準出力) に表示する関数 print_int(n, b) を定義してください。
n 個の中から r 個を選ぶ組み合わせの数 nＣr を整数で求める関数 combination(n, r) を定義してください。
1 から n までの数字から m 個を選ぶ順列を画面に表示する関数 permutations(n, m) を定義してください。
1 から n までの数字から重複を許して m 個を選ぶ順列を画面に表示する関数 repeat_perm(n, m) を定義してください。
1 から n までの数字から r 個を選ぶ組み合わせを画面に表示する関数 combinations(n, r) を定義してください。
1 から n までの数字から重複を許して r 個を選ぶ組み合わせを画面に表示する関数 repeat_comb(n, r) を定義してください。
リスト : 九九表 (yapp01.pl)
use strict;
use warnings;
sub ninety_nine {
print " | 1 2 3 4 5 6 7 8 9\n";
print "---+---------------------------\n";
for (my $i = 1; $i <= 9; $i++) {
printf("%2d | ", $i);
for (my $j = 1; $j <= 9; $j++) {
printf("%2d ", $i * $j);
}
print "\n";
}
}
ninety_nine();
九九表は二重の for ループで簡単に作ることができます。関数 printf はＣ言語の printf とほぼ同じです。printf の書式 %2d の 2 はフィールド幅を指定します。%nd は表示する整数が n 桁未満の場合、上位の桁には空白文字が埋められます。
リスト : 整数の和、二乗の和、三乗の和 (yapp02.pl)
use strict;
use warnings;
# 1 から n までの合計値を求める
sub sum_of_int_1 {
my $n = shift;
$n * ($n + 1) / 2;
}
sub sum_of_square_1 {
my $n = shift;
$n * ($n + 1) * (2 * $n + 1) / 6;
}
sub sum_of_cube_1 {
my $n = shift;
return $n * $n * ($n + 1) * ($n + 1) / 4;
}
# n から m までの合計値を求める
sub sum_of_int {
my ($n, $m) = @_;
sum_of_int_1($m) - sum_of_int_1($n - 1);
}
sub sum_of_square {
my ($n, $m) = @_;
sum_of_square_1($m) - sum_of_square_1($n - 1);
}
sub sum_of_cube {
my ($n, $m) = @_;
sum_of_cube_1($m) - sum_of_cube_1($n - 1);
}
printf("%.0f\n", sum_of_int(1, 10000));
printf("%.0f\n", sum_of_int(100, 10000));
printf("%.0f\n", sum_of_square(1, 10000));
printf("%.0f\n", sum_of_square(100, 10000));
printf("%.0f\n", sum_of_cube(1, 10000));
printf("%.0f\n", sum_of_cube(100, 10000));
$ perl yapp02.pl 50005000 50000050 333383335000 333383006650 2500500025000000 2500500000497500
1 から n までの合計値を関数 sum_of_xxx_1 で求めます。あとは sum_of_xxx_1($m) - sum_of_xxx_1($n - 1) を計算するだけです。printf の書式 %.0f の .0 は精度の指定です。f 指定子の場合、精度は小数点以下の桁数を表します。.0 と指定することで、小数点以下を非表示にすることができます。
リスト : 累乗 (yapp03.pl)
use strict;
use warnings;
# 単純な繰り返し
sub power {
my ($x, $y) = @_;
my $a = 1.0;
while ($y-- > 0) {
$a *= $x;
}
$a;
}
# 再帰定義
sub power_rec {
my ($x, $y) = @_;
return 1 if ($y == 0);
my $z = power_rec($x, int($y / 2));
if ($y % 2 == 0) {
$z * $z;
} else {
$x * $z * $z;
}
}
printf("%.0f\n", power(2, 16));
printf("%.0f\n", power(2, 32));
printf("%.0f\n", power(2, 64));
printf("%.0f\n", power_rec(2, 16));
printf("%.0f\n", power_rec(2, 32));
printf("%.0f\n", power_rec(2, 64));
$ perl yapp03.pl 65536 4294967296 18446744073709551616 65536 4294967296 18446744073709551616
累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。
pow (x, y) = x ** y x ** 3 = x * x * x; x ** 4 = x * x * x * x; x ** 5 = x * x * x * x * x; 図 : 累乗の計算
これをそのままプログラムしたものが関数 power です。プログラムは簡単なので説明は割愛します。この場合、n 回の乗算が必要になります。ところが、式を変形するともっと少ない回数で求めることができます。
x ** 4 = (x ** 2) ** 2 -> 2 回
x ** 8 = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回
一般化すると
x ** y = (x ** (y / 2)) ** 2 （n は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （n は奇数）
図 : 累乗の高速化
階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。x ** (y / 2) を計算する部分は、再帰を使えば簡単です。
この考え方でプログラムしたものが関数 power_rec です。局所変数 $z を定義します。$z の値は $x ** ($y / 2) で、power_rec を再帰呼び出しすれば簡単に求めることができます。関数 int は小数点数を切り捨てて整数を返します。あとは、$y が偶数であれば $z * $z を返し、奇数であれば $x * $z * $z を返します。このように、再帰呼び出しを使って累乗を効率的に計算することができます。
リスト : フィボナッチ関数 (yapp04.pl)
use strict;
use warnings;
# 二重再帰
sub fibo {
my $n = shift;
if ($n == 0 || $n == 1) {
$n;
} else {
fibo($n - 1) + fibo($n - 2);
}
}
# 末尾再帰
sub fibo_sub {
my ($n, $a, $b) = @_;
if ($n == 0) {
$a;
} else {
fibo_sub($n - 1, $a + $b, $a);
}
}
sub fibo_rec {
my $n = shift;
fibo_sub($n, 0, 1);
}
# 繰り返し
sub fiboi {
my $n = shift;
my $a = 0, $b = 1;
while ($n-- > 0) {
my $c = $a;
$a += $b;
$b = $c;
}
return $a;
}
printf("%d\n", fibo(30));
printf("%d\n", fibo_rec(30));
printf("%d\n", fiboi(30));
$ perl yapp04.pl 832040 832040 832040
フィボナッチ関数は再帰呼び出しを使えば簡単にプログラムできます。関数 fibo は自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。
fibo(5) ┬ fibo(4) ┬ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │ │ │
│ │ │ └ fibo(0)
│ │ └ fibo(1)
│ └ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
│
└ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
└ fibo(1)
図 : 関数 fibo のトレース
同じ値を何回も求めているため、関数 fibo の効率はとても悪いのです。この場合、二重再帰を「末尾再帰」に変換すると高速化することができます。累算変数を使って二重再帰を末尾再帰へ変換したものが関数 fibo_rec と fibo_sub です。
関数 fibo_sub の累算変数 a と b の使い方がポイントです。現在のフィボナッチ数を変数 $a に、ひとつ先の値を変数 $b に格納しておきます。あとは $a と $b を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo_sub の呼び出しを下図に示します。
fibo_sub(5, 0, 1)
fibo_sub(4, 1, 1)
fibo_sub(3, 1, 2)
fibo_sub(2, 2, 3)
fibo_sub(1, 3, 5)
fibo_sub(0, 5, 8)
=> a の値 5 を返す
=> 5
=> 5
=> 5
=> 5
=> 5
図 : 関数 fibo_sub の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行することができます。
Perl の場合、規格では末尾再帰最適化をサポートしてませんが、末尾再帰を繰り返しに変換することは簡単です。関数 fibo を繰り返しに変換すると関数 fiboi のようになります。このように、末尾再帰は簡単に繰り返しに変換することができます。
リスト ; 整数の n 進数表示 (yapp05.pl)
use strict;
use warnings;
our @table = qw/0 1 2 3 4 5 6 7 8 9 A B C D E F/;
sub print_int_sub {
my ($n, $b) = @_;
if ($n >= $b) {
print_int_sub(int($n / $b), $b);
}
print $table[$n % $b];
}
sub print_int {
my ($n, $b) = @_;
if ($b > 1 || $b <= 16) {
if ($n < 0) {
print "-";
print_int_sub(-$n, $b);
} else {
print_int_sub($n, $b);
}
} else {
print "基数は 2 以上 16 以下の数を指定してください";
}
print "\n";
}
print_int(123456789, 2);
print_int(-123456789, 8);
print_int(123456789, 10);
print_int(-123456789, 16);
print_int(0xabcdef, 10);
print_int(0xabcdef, 16);
print_int(0x7fffffff, 10);
print_int(0x7fffffff, 16);
$ perl yapp05.pl 111010110111100110100010101 -726746425 123456789 -75BCD15 11259375 ABCDEF 2147483647 7FFFFFFF
実際の印字処理は関数 print_int_sub で行います。上位の桁から表示するため再帰呼び出しを使っています。$n < $b が再帰呼び出しの停止条件です。$n が $b 以上であれば、$n を $b で割り算して print_int_sub を再帰呼び出しします。戻ってきたら、n % b の印字コードを文字列 table から求めて、それを print で出力します。print_int は引数の条件をチェックして print_int_sub を呼び出すだけです。
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Perl で use integer を指定すると、M.Hiroi が使用している処理系では 64 bit 整数として計算されるので、公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
この式は (n, r) と (n, r - 1) の関係を表しています。あとは階乗やフィボナッチ関数と同じように、再帰定義を使って簡単にプログラムできます。
リスト : 組み合わせの数を求める (yapp06.pl)
use strict;
use warnings;
use integer;
sub combination {
my ($n, $r) = @_;
if ($n == $r || $r == 0) {
1;
} else {
combination($n, $r - 1) * ($n - $r + 1) / $r;
}
}
for (my $i = 8; $i < 32; $i++) {
my $j = $i * 2;
print "($j, $i) => ";
print combination($j, $i), "\n";
}
とても簡単ですが、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。
(16, 8) => 12870 (18, 9) => 48620 (20, 10) => 184756 (22, 11) => 705432 (24, 12) => 2704156 (26, 13) => 10400600 (28, 14) => 40116600 (30, 15) => 155117520 (32, 16) => 601080390 (34, 17) => 2333606220 (36, 18) => 9075135300 (38, 19) => 35345263800 (40, 20) => 137846528820 (42, 21) => 538257874440 (44, 22) => 2104098963720 (46, 23) => 8233430727600 (48, 24) => 32247603683100 (50, 25) => 126410606437752 (52, 26) => 495918532948104 (54, 27) => 1946939425648112 (56, 28) => 7648690600760440 (58, 29) => 30067266499541040 (60, 30) => 118264581564861424 (62, 31) => -284401161134521734
Perl の場合、桁あふれが発生してもランタイムエラーは発生しません。なお、Perl は use integer のかわりに use bigint を指定すると多倍長整数で計算することができます。実行結果は次のようになります。
(16, 8) => 12870 ・・・省略・・・ (50, 25) => 126410606437752 (52, 26) => 495918532948104 (54, 27) => 1946939425648112 (56, 28) => 7648690600760440 (58, 29) => 30067266499541040 (60, 30) => 118264581564861424 (62, 31) => 465428353255261088
リスト : 順列 (yapp07.pl)
use strict;
use warnings;
our @buffer = (0, 0, 0, 0, 0, 0, 0, 0, 0);
our @used = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
sub perm_sub {
my ($n, $m) = @_;
if ($n == $m) {
print @buffer[0 .. $n - 1], "\n";
} else {
for (my $i = 1; $i <= $n; $i++) {
next if $used[$i];
$buffer[$m] = $i;
$used[$i] = 1;
perm_sub($n, $m + 1);
$used[$i] = 0;
}
}
}
sub permutations {
my $n = shift;
if ($n > 0 || $n <= @buffer) {
perm_sub($n, 0);
}
}
permutations(4);
permutations(5);
実際の処理は関数 perm_sub で行います。第 2 引数 $m が選んだ数字の個数を表します。$n と $m が等しいときが再帰呼び出しの停止条件になります。print で順列を表示します。選んだ数字 $i を配列 $buffer[$m] に格納し、配列 $used[$i] に印をつけてから perm_sub を再帰呼び出しします。再帰呼び出しから戻ってきたら @used を元に戻します。これで順列を表示することができます。
実際に実行すると次のように表示されます。
$ perl yapp07.pl 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 12345 12354 12435 ・・・省略・・・ 54231 54312 54321
リスト : 重複順列 (yapp08.pl)
use strict;
use warnings;
our @buffer = (0, 0, 0, 0, 0, 0, 0, 0, 0);
sub repeat_perm_sub {
my ($n, $m) = @_;
if ($n == $m) {
print @buffer[0 .. $n - 1], "\n";
} else {
for (my $i = 1; $i <= $n; $i++) {
$buffer[$m] = $i;
repeat_perm_sub($n, $m + 1);
}
}
}
sub repeat_perm {
my $n = shift;
if ($n > 0 || $n <= @buffer) {
repeat_perm_sub($n, 0);
}
}
repeat_perm(3);
repeat_perm(4);
重複順列は簡単です。数字は重複してもよいので、配列 @used で数字をチェックする必要はありません。実行結果は次のようになります。
$ perl yapp08.pl 111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333 1111 1112 1113 ・・・省略・・・ 4442 4443 4444
1 から 5 までの数字の中から 3 個を選ぶ組み合わせは次のようになります。
[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5],
最初に 1 を選択した場合、次は [2, 3, 4, 5] の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は [3, 4, 5] の中から 1 個を選べばいいわけです。これで、[1, 2, 3], [1, 2, 4], [1, 2, 5] が生成されます。[2, 3, 4, 5] の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は [3, 4, 5] の中から 2 個を選べばいいわけです。ここで 3 を選ぶと [1, 3, 4], [1, 3, 5] が生成できます。同様に、3 を除いた [4, 5] の中から 2 個を選ぶと [1, 4, 5] を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり [2, 3, 4, 5] から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は組み合わせの公式と同じです。
nC0 = nCn = 1 nCr = n-1Cr-1 + n-1Cr
プログラムは次のようになります。
リスト : 組み合わせ (yapp09.pl)
use strict;
use warnings;
our @buffer = (0, 0, 0, 0, 0, 0, 0, 0, 0);
sub comb_sub {
my ($n, $r, $m) = @_;
if ($r == 0) {
print @buffer[0 .. $m - 1], "\n";
} elsif ($n == $r) {
for (my $i = $r; $i > 0; $i--) {
$buffer[$m++] = $i;
}
print @buffer[0 .. $m - 1], "\n";
} else {
comb_sub($n - 1, $r, $m);
$buffer[$m] = $n;
comb_sub($n - 1, $r - 1, $m + 1);
}
}
sub combinations {
my ($n, $r) = @_;
if ($r > 0 && $r <= @buffer) {
comb_sub($n, $r, 0);
}
}
combinations(5, 3);
combinations(6, 4);
実際の処理は関数 comb_sub で行います。comb_sub は、1 から $n までの数字の中から $r 個を選ぶ組み合わせを生成します。引数 $m は選んだ数字の個数を表します。選んだ要素は配列 @buffer に格納します。$r が 0 になったら組み合わせを一つ生成できたので、print で組み合わせを表示します。$n が $r と等しくなったならば、残りの数字 (1 から $r まで) を全て選択します。for ループで 1 から $r までの数字を @buffer に追加してから print で表示します。
この 2 つの条件が再帰呼び出しの停止条件になります。あとは comb_sub を再帰呼び出しするだけです。最初の呼び出しは数字 $n を選ばない場合です。残りの数字の中から $r 個の数字を選びます。最後の呼び出しが数字 $n を選択する場合です。数字 $n を @buffer に追加して、残りの数字の中から $r - 1 個を選びます。
実際に実行すると次のように表示されます。
$ perl yapp09.pl 321 421 431 432 521 531 532 541 542 543 4321 5321 5421 5431 5432 6321 6421 6431 6432 6521 6531 6532 6541 6542 6543
要素の順番が逆になっていますが、正常に動作しています。
リスト : 重複組み合わせ (yapp10.pl)
use strict;
use warnings;
our @buffer = (0, 0, 0, 0, 0, 0, 0, 0, 0);
sub repeat_comb_sub {
my ($n, $r, $m) = @_;
if ($r == 0) {
print @buffer[0 .. $m - 1], "\n";
} elsif ($n == 1) {
for (my $i = $r; $i > 0; $i--) {
$buffer[$m++] = 1;
}
print @buffer[0 .. $m - 1], "\n";
} else {
repeat_comb_sub($n - 1, $r, $m);
$buffer[$m] = $n;
repeat_comb_sub($n, $r - 1, $m + 1);
}
}
sub repeat_comb {
my ($n, $r) = @_;
if ($r > 0 && $r <= @buffer) {
repeat_comb_sub($n, $r, 0);
}
}
repeat_comb(3, 2);
repeat_comb(4, 3);
重複組み合わせを求める repeat_comb も簡単です。実際の処理は関数 repeat_comb_sub で行います。2 番目の elsif 節で、$n が 1 の場合は 1 を $r 個選びます。最後の else 節では、$n を選んだあとそれを取り除かないで $r - 1 個の要素を選びます。実行結果は次のようになります。
$ perl yapp10.pl 11 21 22 31 32 33 111 211 221 222 311 321 322 331 332 333 411 421 422 431 432 433 441 442 443 444