最大公約数（除算禁止） in Perl DouKaku?

最大公約数（除算禁止）

あなたが使っている言語で除算と剰余が使えなくなりました。

以下の条件のもと最大公約数を求めるプログラムを書いてください。

条件

除算および剰余の使用禁止
加算や乗算から除算・剰余を単純に定義することも禁止とする
ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
多倍長演算をサポートすること（各言語のライブラリ状況を見たいので）
引数は2つの正整数と仮定して構わない
F_1=1, F_2=1のフィボナッチ数列で2000番目と1999番目の最大公約数を求めたときのループ回数を教えてください

post comment

Posted feedbacks - Perl

回答は二種類。単純減算と正規表現利用バージョン。ただし後者の方はfib(2000)とかは出来ません。

Greediest Cruftiest Dan

#!/usr/local/bin/perl
use strict;
use warnings;
use bignum;
use Memoize;

no warnings 'recursion';

sub fib{
    my $n = shift;
    return 1 if $n <= 2;
    fib($n-2)+fib($n-1);
}
memoize 'fib';

sub gcd{
    my ($m, $n) = @_;
    return gcd($n, $m) if $m < $n;
    my $r = $m % $n;
    return $n unless $r;
    gcd($n, $r);
}

sub gcd_nodiv{
    my ($m, $n) = @_;
    return gcd($n, $m) if $m < $n;
    $m -= $n while $m > $n;
    return $n unless $m;
    gcd($n, $m);

}

sub gcd_regexp{
    my ($m, $n) = @_;
    return gcd($n, $m) if $m < $n;
    my $sm = 1 x $m;
    my $sn = 1 x $n;
    $sm =~ s/^$sn//g;
    return $n unless $sm;
    gcd($n, length $sm);
}

sub say { local $\="\n"; print @_ };
say gcd_regexp(fib(25), fib(24));
say gcd_nodiv(fib(1999),fib(2000));

DouKaku?

最大公約数（除算禁止）

条件

条件(易)

条件(難)

補足

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq