こんにちは。ハンドルネーム「Javaを復習する初心者」です。このサイトはプログラミング言語Javaの復習・学習をするブログです。プログラムの開発・実行はEclipseで行ってます。
スポンサーリンク
お知らせ
  • 参考文献のページ作りました。
  • Amazon.co.jpアソシエイトに参加していますが、参考文献の紹介はもしもアフィリエイトに統一しました。
  • 2016年10月9日からは投稿ペースを落とします。週1回くらいにする予定です。
スポンサーリンク

Project EulerのProblem 36~40をやってみた

こんにちは。「Javaを復習する初心者」です。Project Eulerという数学の問題サイトがあります。そのサイトのProblem 36から40を解いてみました。

Problem 36

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

数585 = 1001001001_2 (2進数)は両方の基数で回文数である。

100万未満で10進数と2進数で回文数になる数の和を求めよ。

(回文数は、両方の基数で、先頭に0を含めないことに注意)

    private void test() {
        int sum = 0;
        for (int i = 1; i < 1000000; i++) {
            if (i % 10 != 0 && i % 10 != 2
                    && check(String.valueOf(i))
                    && check(String.valueOf(Integer.toBinaryString(i)))) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    private boolean check(String s) {
        return s.equals(new StringBuilder(s).reverse().toString());
    }

checkメソッドを作って回文数かを判定しています。文字列の反転はStringBuilder#reverse()メソッドで可能です。反転後のString型オブジェクトはnew StringBuilder(s).reverse().toString()になります。最後のtoString()を忘れると、コンパイルエラーにはなりませんが結果が期待通りになりません。このcheckメソッド自体は任意の文字列に対して、回文かどうかを判定する作りになっています。

このメソッドに自然数iとその2進数表示を渡せばよいのですが、2進数表記はJavaにはInteger#toBinaryString()メソッドがあります。先頭が0で始まるものを含めないという問題なので、回文の先頭が0になるパターンを除いています。その条件は、10進数の場合が「i % 10 != 0」で2進数の場合が「i % 10 != 2」です。後半の条件は2進数表示で1桁目が0にならないということです。

Problem 37

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

数3797は興味深い性質を持つ。それ自身が素数であり、左から右に連続的に桁を取り除いたときに、それぞれの段階で残るのは素数である:3797、797、97、そして7。同様に右から左へも可能である: 3797、379、37、そして3。

左から右と右から左両方で縮められるのは11個の素数のみで、その和を求めよ。

注意:2、3、5、7は縮められる素数とは考えない。

    private void test() {
        int sum = 0;
        for (int i = 10; i < 1000000; i++) {
            if (checkTruncatableOf(i)) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    private boolean checkPrimaricityOf(int n) {
        if (n == 1) {
            return false;
        }

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

    private boolean checkTruncatableOf(int n) {
        if (!checkPrimaricityOf(n)) {
            return false;
        }

        String s = String.valueOf(n);
        for (int i = 1; i < s.length(); i++) {
            if (!checkPrimaricityOf(Integer.parseInt(s.substring(i)))
                    || !checkPrimaricityOf(Integer.parseInt(s.substring(0, i)))) {
                return false;
            }
        }

        return true;
    }

まず素数か判定する必要があるため、checkPrimaricityOf()メソッドを作りました。1は素数ではないので、その場合は最初のif文でfalseを返却するようにしています。

縮められる素数かどうかを判定するため、checkTruncatableOf()メソッドを作りました。まず、自身が素数であるか判定しています。String型変数sに格納し、縮めた数をString#substring()メソッドで求めました。ちょうど、s.substring(i)、s.substring(0, i)で求めることができました。あとはそれぞれが素数かを判定するのみです。String#substring()メソッドの戻り値はString型なのでint型に直す必要がありますが、それはInteger#parseInt()メソッドで出来ます。

問題文では縮められる素数は11個だけあると書いてあります。なのでfor文の上限は実行しながら適当に決めました。while文でも良かったのかもしれません。また、一桁の素数は縮められる素数とは考えないという記述があるため、for文の最初を10にしています。

Problem 38

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

数192と1、2及び3それぞれと積を取る:

  • 192 × 1 = 192
  • 192 × 2 = 384
  • 192 × 3 = 576

各積を連結することにより、1から9のpandigital 192384576が得られる。192384576を192と(1,2,3)の連結積と呼ぶ。

同様に、9で1、2、3、4、5を積を連結すると、pandigital 918273645が得られ、これは9と(1,2,3,4,5)の連結積である。

n > 1で、(1,2, … , n)との連結積を形成する1から9のpandigitalである9桁の数で最大のものは何か?

    private void test() {
        int max = 0;
        for (int i = 1; i < 10000; i++) {
            String s = createConcatenatedProductNear9DigitFrom(i);
            if (checkPandigitalityOf(s)) {
                max = Math.max(max, Integer.valueOf(s));
            }
        }
        System.out.println(max);
    }

    private String createConcatenatedProductNear9DigitFrom(int n) {
        StringBuilder sb = new StringBuilder(String.valueOf(n));
        int multiplier = 1;
        while (sb.length() < 9) {
            sb.append(String.valueOf(n * (++ multiplier)));
        }
        return sb.toString();
    }

    private boolean checkPandigitalityOf(String s) {
        if (s.length() != 9) {
            return false;
        }

        int[] counts = new int[10];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - '0'] ++;
        }

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

createConcatenatedProductNear9DigitFromという長い名前のメソッドを定義しました。与えられた自然数から9桁に近い連結積を作るメソッドです。順番に積を連結していますが、連結回数が複数のため、StringBuilderを使っています。実際はwhile文の条件により、返却値は9桁以上になります。メソッド名は少々良くないかもしれませんが、他に思い浮かびませんでした。

checkPandigitalityOfメソッドを定義しました。これは与えられた自然数の文字列が1から9のpandigitalであるかどうかを判定するメソッドです。最初に9桁でない場合はfalseを返却しています。あとは各桁に1から9が1度だけ登場するということを調べています。注意としては0が登場してはならないということです。

for文によって問題文の条件を満たす最大の数を計算していますが、for文の終わりは適当です。実行しながら決めました。連結積によってはcreateConcatenatedProductNear9DigitFromメソッドの返却値はint型に収まらないかもしれませんが、checkPandigitalityOfメソッドで9桁である連結積のみを扱うことになるため、Integer.valueOf(s)の箇所ではエラーはでません。

Problem 39

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

整数の長さの辺{a,b,c}の直角三角形の1週の長さがpならば、p = 120に対して3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}

p ≤ 1000に対して、解の数の最大となるpは何か?

    private void test() {
        int max = 0;
        int p = 0;
        for (int i = 1; i <= 1000; i++) {
            int sumOfSolutions = numOfRightAngleTriangleWithPerimeter(i);
            if (max < sumOfSolutions) {
                max = sumOfSolutions;
                p = i;
            }
        }
        System.out.println(p);
    }

    private int numOfRightAngleTriangleWithPerimeter(int p) {
        int sum = 0;
        for (int i = 1; i < p; i++) {
            for (int j = i; j < p; j++) {
                int hypotence = p - i - j;
                if (hypotence * hypotence == i * i + j * j) {
                    sum ++;
                }
            }
        }
        return sum;
    }

numOfRightAngleTriangleWithPerimeterというメソッドを作りました。直角三角形の周の長さを引数にしています。for文の2重ループで直角三角形を形成する辺の長さの組み合わせをカウントしています。斜辺以外の辺の長さをi、jとしています。辺の長さの組合せとして{ i, j, p-i-j }を考えます。直角三角形の場合、三平方の定理が成り立つ必要があるということです。つまり、斜辺の2乗が残りの2辺の2乗の和に等しいことを判定しています。

辺の長さの組み合わせのみをカウントするので、for文の2重ループでjの開始はiからにしています。それぞれp未満までとしていますが、斜辺が一番長いことを考えるともう少し条件を小さくできるかもしれません。

Problem 40

無理数は正の整数を連結して得られることで作られる:
0.123456789101112131415161718192021…

小数部分の12桁目は1である。

d_nで小数部分のn桁目表すとき、次の展開の値を求めよ。

d_1 × d_10 × d_100 × d_1000 × d_10000 × d_100000 × d_1000000

    private void test() {
        StringBuilder sb = new StringBuilder();
        int n = 1;
        int nth = 1;
        int value = 1;
        do {
            sb.append(String.valueOf(n++));
            int length = sb.length();
            if (length == 1 || length > nth) {
                value *= Integer.valueOf(sb.charAt(nth - 1) - '0');
                nth *= 10;
            }
        } while (sb.length() < 1000000);
        System.out.println(value);
    }

問題文の無理数は、小数第1位から順番に1, 2, 3, …を順番に後ろに連結した数です。小数部分の並びをStringBuilder型変数に格納することにしました。文字列の連結を繰り返すからString型ではなく、StringBuilder型を使います。StringBuilder#charAtがあるので、これで小数部分のn番目を取り出します。ただし、charAtでは要素番号を指定するのでnth – 1が指定する引数になります。また、文字コードが取得されるので’0’との差を取っています。そのあとvalueに掛け算をしています。

問題文で求める数は1桁の自然数7個の積なので変数valueはint型にしました。

小数部分の長さが1000000を超えたら終わりです。なのでdo-while文の条件はsb.length() < 1000000です。