java-beginner.com ブログ

プログラミングを学習するブログ(Javaをメインに)

Project EulerのProblem 31~35をやってみた

投稿日:

最終更新日:2017年01月29日

アイキャッチ

こんにちは。「Javaを復習する初心者」です。

Project Eulerという数学の問題サイトがあります。そのサイトのProblem 31から35を解いてみました。

Problem 31

自分なりに直訳してみました。

Englandではpound £とpence pがあり、一般的に以下の8種類の硬貨がある。

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p)。

£2は次のように表すことができる。
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

£2を表す方法は何通りか?

ソース

    private final int SUM_OF_PRICE = 200;

    private int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };

    private void test() {
        System.out.println(countCoin(coins.length - 1, SUM_OF_PRICE));
    }

    private int countCoin(int currentIndexOfCoin, int targetSum) {
        int count = 0;

        int numOfCoins = 0;
        int coin = coins[currentIndexOfCoin];
        int sum = numOfCoins * coin;
        while (sum < targetSum) {
            if (currentIndexOfCoin > 0){
                count += countCoin(currentIndexOfCoin - 1, targetSum - sum);
            }
            numOfCoins ++;
            sum = numOfCoins * coin;
        }
        if (sum == targetSum) {
            count ++;
        }

        return count;
    }

硬貨の枚数のパターンを数える問題です。色々やり方はあると思いますが、penceの大きい硬貨の枚数から決定していくような再帰呼び出しを定義して求めました。countCoinというメソッドが再帰呼び出しのメソッドです。フィールドcoinsはコインの種類を要素番号として、硬貨に対応するpenceを設定しています。

Problem 32

自分なりに直訳してみました。

n桁の数がpandigitalとは、1からnまでの数がちょうど一回使われているときにいう;例えば、5桁の数15234は1から5のpandigitalである。

積7254は39 × 186 = 7254とみなすことで、掛けられる数、掛ける数そして積が1から9 pandigitalである。

掛けられる数/掛ける数/積が1から9のpandigitalとして書き表すことができるようなすべての積の和を求めよ。

ヒント:ある積は1つ以上の方法で得られるが、和の中で一度のみ含めよ。

ソース

    private void test() {
        int sum = 0;
        for (int i = 1; i < 10000; i++) {
            if (checkPandigitalOf(i)) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    private boolean checkPandigitalOf(int n) {
        int sqrt = (int)Math.sqrt(n);
        for (int p = 2; p <= sqrt; p++) {
            if (n % p == 0) {
                int q = n / p;

                int[] counts = new int[10];
                push(n, counts);
                push(p, counts);
                push(q, counts);

                if (counts[0] > 0) {
                    continue;
                }
                boolean isPandigital = true;
                for (int i = 1; i < counts.length; i++) {
                    if (counts[i] != 1) {
                        isPandigital = false;
                        break;
                    }
                }
                if (isPandigital) {
                    return true;
                }
            }
        }
        return false;
    }

    private void push(int num, int[] counts) {
        String s = String.valueOf(num);
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - '0'] ++;
        }
    }

自然数nを1から順番に調べる方法にしました。nに対して2つの積で表し、組み合わせがpandigitalであるかどうかを調べるメソッドを作りました。各桁に登場する数(0から9)に対して、登場回数を配列countsに格納して、この配列を使って、pandigitalかどうかを判断するという考え方です。counts[0]が0より大きい場合、falseです。counts[0]が0かつcounts[1]からcounts[9]がすべて1の場合、trueという処理をしています。

自然数nを1から順番にいくつまで調べればよいかは、プログラムを動かしながら適当に決めてます。for文で10000未満まで調べてますが、桁数を考慮するとこのくらいだと考えました。実際にはもう一桁多い100000未満までを実行して求まる合計値が変わらないことを確認しました。

Problem 33

自分なりに直訳してみました。

49/98は興味深い分数であり、9を取り除くことによって得られる49/98 = 4/8は正しい。

30/50 = 3/5のような分数は自明な例であると考える。

1より小さく、分母と分子が2桁である、4つの自明でない例がある。

それら4つの分数の積が約分して与えられたとき、分母の値を求めよ。

ソース

    private class Fraction {
        private int p;
        private int q;

        public Fraction(int p, int q) {
            this.p = p;
            this.q = q;
        }

        public int getP() {
            return p;
        }

        public int getQ() {
            return q;
        }
    }

    private void test() {
        List<Fraction> fractions = new ArrayList<>();
        for (int p = 10; p < 100; p++) {
            for (int q = 10; q < 100; q++) {
                if (p < q) {
                    if (checkCancellingOf(p, q)) {
                        fractions.add(new Fraction(p, q));
                    }
                }
            }
        }
        int p = 1;
        int q = 1;
        for (Fraction f : fractions) {
            p *= f.getP();
            q *= f.getQ();
        }
        int gcd = calGcdOf(p, q);
        System.out.println(q / gcd);

    }

    private boolean checkCancellingOf(int p, int q) {
        // 自明な場合
        if (p % 10 == 0 && q % 10 == 0) {
            return false;
        }

        int p_1 = p % 10;
        int q_1 = q % 10;
        int p_2 = p / 10;
        int q_2 = q / 10;
        if (   (p_1 == q_1 && checkEqualityOf(p, q, p_2, q_2)) // 1桁目と1桁目が等しい
            || (p_1 == q_2 && checkEqualityOf(p, q, p_2, q_1)) // 1桁目と2桁目が等しい
            || (p_2 == q_1 && checkEqualityOf(p, q, p_1, q_2)) // 2桁目と1桁目が等しい
            || (p_2 == q_2 && checkEqualityOf(p, q, p_1, q_1)) // 2桁目と2桁目が等しい
            ) {
            return true;
        }

        return false;
    }

    private boolean checkEqualityOf(int p1, int q1, int p2, int q2) {
        if (q1 == 0 || q2 == 0) {
            return false;
        }
        int gcd1 = calGcdOf(p1, q1);
        int gcd2 = calGcdOf(p2, q2);

        return p1 / gcd1 == p2 / gcd2 && q1 / gcd1 == q2 / gcd2;
    }

    private int calGcdOf(int p, int q) {
        int tmp;
        while ((tmp = p % q) != 0) {
            p = q;
            q = tmp;
        }
        return q;
    }

分数p/qを考えます。なので変数名もそれに合わせてます。

最終的に分数を4つ求めて、積を作ります。そのためにFractionクラスをリストに格納するようにしました。このリストに自明でないCancelling可能な分数を格納します。

分母q分子pともに2桁の数である各分数について調べます。なのでfor文の2重ループを使っています。for文はどちらも10から始めています。ただし、1を超えない分数という条件があるので、p < qという条件を使っています。 checkCancellingOfメソッドで引数の分数がCancelling可能かを調べています。地道に分母分子の各桁の等しいパターンを調べています。数字を取り除いた分数と元の分数が等しいかどうかは、checkEqualityOfメソッドで調べています。2つの分数が等しいかどうかは、約分して等しくなるかをチェックしています。

Problem 34

自分なりに直訳してみました。

145は興味深い数であり、1! + 4! + 5! = 1 + 24 + 120 = 145である。

各桁の階乗の和に等しくなる数の和を求めよ。

注意:1! = 1と2! = 2は和に含めない。

ソース

    private Map<Integer, Integer> factorials = new HashMap<>();

    private void test() {
        factorials.put(0, 1);
        for (int i = 1; i <= 9; i++) {
            factorials.put(i, calcFactorialOf(i));
        }

        int sum = 0;
        for (int i = 10; i < 400000; i++) {
            if (check(i)) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    private int calcFactorialOf(int n) {
        if (n == 1) {
            return n;
        } else {
            return n * calcFactorialOf(n - 1);
        }
    }

    private boolean check(int num) {
        String s = String.valueOf(num);
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += factorials.get(s.charAt(i) - '0');
        }
        return sum == num;
    }

階乗の計算は再帰呼び出しのメソッドを作ってますが、0から9の階乗のみ使うため、最初に結果をMapに格納しています。便宜上、0の階乗は1だと思うのですが、問題文自体には書いていません。

各桁の階乗の和が自身に一致する自然数を求めるのですが、1と2は例外とするように問題文に書いてあります。なのでfor文の開始は10からにしました。ここで最大でどこまでチェックすればよいのかとう問題なのですが、今回も適当に決めてしまいました。9!より大きい400000未満の数についてチェックを実施するようにしました。この数値は勘です。

checkメソッドを作って、与えられた引数について、各桁の階乗の和が自身に一致するかをチェックしています。各桁を求める方法は色々あると思いますが、String#charAt()メソッドを使うことにしました。ただし、文字コードが取得されるため、’0’との差を取っています。

Problem 35

自分なりに直訳してみました。

197の各桁を回転させた数197、971及び719はそれぞれ自身が素数であるため、数197はcircular primeと呼ばれる。

100未満ではそのような素数は13個ある:2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97。

100万未満ではcircular primeである数は何個あるか?

ソース

    private void test() {
        int count = 0;
        for (int i = 2; i < 1000000; i++) {
            if (checkCircularPrimaryOf(i)) {
                count ++;
            }
        }
        System.out.println(count);
    }

    private boolean checkPrimaryOf(int n) {
        int sqrt = (int)Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    private boolean checkCircularPrimaryOf(int n) {
        String s = String.valueOf(n);
        for (int i = 0; i < s.length(); i++) {
            if (!checkPrimaryOf(Integer.parseInt(s.substring(i) + s.substring(0, i)))) {
                return false;
            }
        }
        return true;
    }

checkCircularPrimaryOfメソッドでcircular primeであるかチェックしています。

巡回させた数を求める方法については、文字列sについてi+1番目を先頭にする場合、「s.substring(i) + s.substring(0, i)」で出来ました。「substring(0, 0)」が空文字を返却してくれるため、iが0でもうまく動作します。また、String型クラスは不変クラスであるため、元の文字列sは変化しません。そのため、for文で都合よく動いてくれます。

巡回させた数それぞれに対して、素数であるかチェックしています。素数でない場合は、その時点でreturnしています。