【プログラミング】計算量を再認識した話【PHP】

プログラミング
この記事は約6分で読めます。
スポンサーリンク

答えは 7の倍数の「7, 14, 21, 28, 35, 42, 49」 以外の数なので 43個です!

程よい難易度の問題を出されると答えが気になってしまい、クリックしたくなるのが人間の習性だそうです!
アイキャッチで釣られた人すみません…笑

今回はそれに関連したプログラミングの話になります。

先日こちらの問題を解こうとしたところ勉強になったので紹介します。

AtCoder Beginner Contest 131 C – Anti-Division

問題文

整数 A, B, C, D が与えられます。
A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を求めてください。

誤った解法

日本語の通り、プログラムを書いてみます

<?php
    const INPUT_DELIMITER = " ";

    // 入力
    $input = fgets(STDIN);
    $inputArray = explode(INPUT_DELIMITER, $input);

    $A = $inputArray[0];
    $B = $inputArray[1];
    $C = $inputArray[2];
    $D = $inputArray[3];

    // 割り切れないものの個数
    $count = 0;

    // A 以上 B 以下の整数
    for ($i = $A; $i <= $B; $i++) {
        // C でも割り切れない かつ D でも割り切れない
        if ($i % $C != 0 && $i % $D != 0) {
            // その個数を数える
            $count++;
        }
    }

    echo $count;

数が少なければ問題なく動きます。

しかし大きな数になるとこのプログラムは重すぎて動かなくなってしまいます。

入力例3より 
    ~省略~
    $A = $inputArray[0]; // 314159265358979323
    $B = $inputArray[1]; // 846264338327950288
    $C = $inputArray[2]; // 419716939
    $D = $inputArray[3]; // 937510582

    $count = 0;
    for ($i = $A; $i <= $B; $i++) {
        // 50京(!?)回計算してしまう!!
        if ($i % $C != 0 && $i % $D != 0) {
            // その個数を数える
            $count++;
        }
    }

正しい解法

そのため別の方法で計算していきます

C でも割り切れない かつ D でも割り切れない

はド・モルガンの法則より、言い換えると、

C で割り切れる または D でも割り切れる

そのような数を出せばOKです。

上のベン図のように、CとDの公倍数は共通部分のため、

Cの倍数の総数 + Dの倍数の総数 – CとDの公倍数

を求めていきます。(高校でやったな…)
最小公倍数の求め方に関してはEuclidの互除法を用いました。
もはや忘れ去られた知識なのでググりました…

<?php
    const INPUT_DELIMITER = " ";

    // 最小公倍数を求める
    function getLCM ($a, $b) {
        return $a * $b / getGCM($a, $b);
    }

    // 最大公約数を求める
    function getGCM ($a, $b) {
        if ($a < $b) {
            list($min, $max) = [$a, $b];
        } else {
            list($min, $max) = [$b, $a];
        }

        $mod = $max % $min;
        if ($mod === 0) {
            return $min;
        }
        // 数を変えてもう一度計算する
        return getGCM($min, $mod);
    }

    // 入力
    $input = fgets(STDIN);
    $inputArray = explode(INPUT_DELIMITER, $input);

    $A = $inputArray[0];
    $B = $inputArray[1];
    $C = $inputArray[2];
    $D = $inputArray[3];


    // CとDの公倍数
    $CD = getLCM($C, $D);

    $range = $B - $A;
    // 割り切れないものの個数
    $countC = floor($range / $C);
    $countD = floor($range / $D);
    $countCD = floor($range / $CD);

    // 計算
    $count = bcsub($range , ($countC + $countD - $countCD));
    echo $count;

最大公約数を計算する上で数回計算が入りますが、最初の解法とは異なり膨大な計算をする必要はありません。

ちょっと詳しい話

誤った解法の計算量は、数が大きくなるほど、計算量が増えるプログラムです。誤った解法の計算量は O(n) です。y = x のグラフのように右肩上がりなイメージで計算量が増えます。

一方正しい解法の計算量ですが、数が大きくなれば計算量は増えることはありますが、getGCM 内の割り算によってはかなり計算量が減らせるのがわかるかと思います。
少なくとも割り算をした余りを使うので、 必ず計算を2回行うたびに計算に使う数の大きさは半分以下になっていきます

① 13 ÷ 8 = 1 … 5 → 余りは必ず割られる数の半分以下の値
② 8 ÷ 5 = 1 … 3 →先程の余りが割る数になり、、
③ 5 ÷ 3 = 1 … 2 → 割られる数になる(①と比較して半分以下の値)

そのため大きい数でもそこまで膨大な数にはならず、O(logN) となります。
詳しい資料は色々な大学の講義資料にまとまっているので気になる方は調べてみると良いかと思います。

まとめ

日本語の解釈をそのままコードに書くことは誤りではありません。
実務でプログラムを書いているときは、そこまで大きな数を扱うことはないので、あまり意識をせずに書けていましたが、今回問題を解いてみて、アルゴリズムの大事さを思い出させられました。

ここまで読んでくださりありがとうございました!

コメント

タイトルとURLをコピーしました