CodeIQ172_test.pl

#/usr/bin/perl

use strict;
use warnings;
use utf8;

printf "(%10s, %10s)\n", "WIDTH", "HEIGHT";
print "-"x48 . "\n";

my $m = 1;
my $n = 1;

# フィボナッチ数列を生成
while( 1 ) {
  my $c = $m + $n;
	$n = $m;
	$m = $c;

	# 最大公約数と切った回数を求める
	my ( $gcd, $count ) = gcd( $m, $n );
	printf "(%10d, %10d) => GCD : %2d, COUNT : %2d\n", $m, $n, $gcd, $count;

	# 切った回数が 40 回になったら終了
	last if ( $count == 40 );
}

exit 0;

sub gcd {
	my ( $m, $n ) = @_;

	# m >= n となるようにする
	if ( $m < $n ) {
		my $c = $m;
		$m = $n;
		$n = $c;
	}

	# 切った回数
	my $count = 0;

	# m / n のあまりを求める
	my $r = $m % $n;

	while ( $r != 0 ) {
		# 切る
		$count++;

		# 次のステップへ
		$m = $n;
		$n = $r;
		$r = $m % $n;
	}

	# 最大公約数と切った回数を返す
	return ( $n, $count );
}

1;