連載
» 2014年12月12日 10時00分 UPDATE

無償ソフトで技術計算しよう【プログラミング応用編】(3):コンピュータ「オイラと数学しよう」 ――オイラープロジェクトの問題にチャレンジ(その2) (1/3)

「プログラミング応用編」では、プログラミングコンテストの問題などをFreeMatでプログラム作成していく。今回も「オイラープロジェクト」の問題を解こう。

[伊藤孝宏,MONOist]

 前回に引き続き、今回もオイラープロジェクトの問題をFreeMatで解いてみます。

筆者注:FreeMatはコマンド入力後にエンターキーを押すとコマンドを実行します。本連載ではエンターキーの記述を省略しますが、操作の際にはコマンド入力後にエンターキーが必要です。



問題5

Problem 5  Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

 意味は、「2520は1〜10の全ての数字で割り切れる数値の中で最小の値です。では、1〜20の全ての数字で割り切れる数値の中で最小の値を求めなさい」。

 FreeMatは剰余計算modも配列で行えます。従って、1〜nまでの配列mを用意して、mod(k,m)が全て0となれば、kは1〜nの全ての数で割り切れることになります。whileループでmod(k,m)の合計が0になるまでkを増加させると、求める数が得られます。

 以上の考え方をFreeMatのプログラムにしたのが、ex329.mです。

function p5=ex329(n)
    k=n;m=1:n;
    while(sum(mod(k,m))~=0)
        k=k+1;
    end
    p5=k;
ex329.m

>>「ex329.m」ダウンロード

 下記のようにコマンドウィンドウに入力すると、2520と正しい結果が得られることが分かります。

--> ex329(10)
ans = 2520

 次は、本番の1〜20での計算になりますが、例での計算でもけっこうな時間がかかっています。そこで、処理を高速化させる必要があります。ただ、ex329.mは5行しかないので、高速化させるにも限度があります。

 そこで、考え方を変えてみます。1〜nの全ての数で割り切れる最小の数ということは、1〜nの最小公倍数になります。そこで、1〜nの最小公倍数を求めることにします。1〜nの最小公倍数は、1と2の最小公倍数を求め、次に求めた最小公倍数と3との最小公倍数を求めてと、前に求めた最小公倍数と次の数値との最小公倍数を次の数値がnになるまで求めれば得られます。以上をFreeMatのプログラムにしたのがex330.mです。最小公倍数を求める関数をlcm(a,b)として、kを2からnまで増加させながら、lcmを呼び出して計算していきます。

function p5=ex330(n)
    p5=1;
    for k=2:n
        p5=lcm(p5,k);
    end
 
function lc=lcm(a,b)
    m=a;n=b;
    while(m~=n)
        if(m>n)
            m=m-n;
        else
            n=n-m;
        end
    end
    lc=a*b/m;
ex330.m

>>「ex330.m」ダウンロード

 本番の1〜20の全ての数で割り切れる最小の数値を求めると、以下のようになります。

--> ex330(20)
ans = 232792560
       1|2|3 次のページへ

Copyright© 2017 ITmedia, Inc. All Rights Reserved.