java-beginner.com ブログ

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

Project EulerのProblem 21~25をやってみた

投稿日:

最終更新日:2016年12月18日

アイキャッチ

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

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

Problem 21

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

d(n)をnの真の約数(nより小さい数でnを割る数)の合計で定義する。
もしd(a) = bかつd(b) = a、ここでa ≠ b、ならば、aとbは友愛数と呼ばれる。

例えば、220の真の約数は1, 2, 4, 5, 10, 11, 20, 22, 44, 55および110である。従って、d(220) = 284である。284の真の約数は1, 2, 4, 71および142であるから、d(284) = 220.

10000未満の友愛数の全ての和を求めよ。

ソース

    private void test() {
        int sum = 0;
        for (int i = 3; i < 10000; i++) {
            int a = i;
            int b = d(a);
            if (d(b) == a && a != b) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    int d(int n) {
        int sum = 0;
        for (int i = 1; i < n; i++) {
            if (n % i == 0) {
                sum += i;
            }
        }
        return sum;
    }

private int d(int n)メソッドが問題文の関数dです。引数nに対して、nより小さい約数の和を求めます。for文でiの開始は3からにしていますが、1からでも大丈夫だと思います。後で出力してみた結果ですが、最初の友愛数が220のようなので、開始を220にしても良いと思います。

Problem 22

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

5000個のファーストネームを含む46Kテキストファイルnames.txtを使うことで、それをアルファベット順に並べよ。このとき、各名前に対してアルファベットの順に値を振り、リスト中のアルファベット順の位置と掛け合わせることで名前のスコアを算出する。

例えば、リストがアルファベット順にソートされているとき、COLINは3 + 15 + 12 + 9 + 14 = 53の値を持ち、リスト中938番目である。なので、COLINは938 × 53 = 49714のスコアを持つ。

このファイル中の名前のスコアの合計は何か?

ソース

        try (BufferedReader br = new BufferedReader(new FileReader("resource/p022_names.txt"))){
            String s = br.readLine();
            int row = 1;
            int sum = 0;
            while(s != null){
                int value = 0;
                for (int i = 0; i < s.length(); i++) {
                    value += s.charAt(i) - 'A' + 1;
                }
                sum += value * row;
                s = br.readLine();
                row ++;
            }
            System.out.println(sum);
        } catch (IOException e) {
            e.printStackTrace();
        }

元々ダウンロードしたファイルは「”MARY”,”PATRICIA”,…」というファイルです。テキストエディタでダブルクォーテーションは削除し、カンマは改行に変換しました。さらに表計算ソフトで昇順にソートしました。なので、以下のようなファイルになりました。

整形済みファイル

AARON
ABBEY
ABBIE
・
・
・
ZULMA

その結果、Javaのプログラムの方では一行ずつ読み取っているだけです。’A’を1に対応させるため、「s.charAt(i) – ‘A’ + 1」という記述をしています。名前に対応する値を計算した後は行数を掛けて、合計に加算するだけです。

Problem 23

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

完全数とは真の約数の合計がそれ自身に一致する数のことである。例えば、28の真の約数は1 + 2 + 4 + 7 + 14 = 28であり、28は完全数である。

数nが不足数とは、真の約数の合計がnより小さい時に呼び、過剰数とは個の合計がnより大きいときに呼ぶ。

12は最小の過剰数で、1 + 2 + 3 + 4 + 6 = 16であり、2つの過剰数の合計で表すことができる最小の数は24である。数学的解析により、28123より大きい全ての整数は2つの過剰数で表すことができることが示されている。しかしながら、(略)

2つの過剰数で表すことができない正の数すべての合計を求めよ。

ソース

    private void test() {
        Set<Integer> abundantNumbers = new HashSet<>();
        abundantNumbers.add(12);
        for (int i = 13; i <= 28123; i++) {
            if (checkAbundanceOf(i)) {
                abundantNumbers.add(i);
            }
        }

        int sum = 0;
        for (int i = 1; i <= 28123; i++) {
            boolean isWritten = false;
            for (Integer abundantNumber : abundantNumbers) {
                if (abundantNumbers.contains(i - abundantNumber)) {
                    isWritten = true;
                    break;
                }
            }
            if (!isWritten) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    private boolean checkAbundanceOf(int n) {
        int sum = 0;
        for (int i = 1; i < n; i++) {
            if (n % i == 0) {
                sum += i;
                if (sum > n) {
                    return true;
                }
            }
        }
        return false;
    }

最初に28123以下の過剰数を全体の集合を求めています。これはあとで過剰数であるかどうかの判定を繰り返さないためです。この集合の要素を使って和で書き表すことができない数の合計を算出しています。その部分の考え方は過剰数に対して「その数 – 過剰数」が過剰数の集合に属するかという考え方です。for文を使って、過剰数の集合すべてについて計算していますが、過剰数の和で表すことができた場合break文でfor文を抜けるようにしています。

Problem 24

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

順列とは物の順番の並びである。例えば、3124は数字1, 2, 3および4の一つの順列である。もし数字またはアルファベット順に並べた順列全てがリストされているならば、辞書式順序と呼ぶ。0, 1および2の辞書式順序は次である。

012 021 102 120 201 210

0, 1, 2, 3, 4, 5, 6, 7, 8および9の辞書式順序で100万番目は何か。

ソース

    private void test() {
        int[] nums = new int[10];
        int nthDigit = nums.length - 1;
        int targetRow = 1000000;
        int currentRow = 1;
        while (currentRow < targetRow) {
            int nextRows = factorialOf(nthDigit);
            if (targetRow < currentRow + nextRows) {
                nthDigit --;
            } else {
                currentRow += nextRows;
                int index = nums.length - 1 - nthDigit;
                if (index < nums.length - 1) {
                    // 右端でない場合、次の順序を格納
                    nums[index] ++;
                }
            }
        }

        List<String> list = IntStream.range(0, 10)
                .mapToObj(n -> String.valueOf(n))
                .collect(Collectors.toList());

        StringBuilder permutation = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            permutation.append(list.remove(nums[i]));
        }
        System.out.println(permutation);
    }

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

nums配列に残っている文字の何番目の文字を使うかを格納しています。並べる文字はListに格納し、removeで取り出します。これで重複しない文字の順列を表現します。例えばnumsが[0, 0, 0]でListが[0, 1, 2]なら要素番号0を順番にremoveで取り出すので012という順列になります。

順列を辞書式順序で縦に並べると仮定し、変数currentRowが現在の行数であるとします。numsの初期値が[0, 0, 0]であるので、currentRow = 1です。

currentRowが100万という値に対応するnumsの内容を算出できれば良いことになります。実際にそれを求めるためには、順列の公式を利用しました。要するにn個の異なる文字の順列はn!通りあるという公式です。問題では0から9の10個の文字からなる順列で、100万番目を求めます。なので先頭0のときは9!通りあります。先頭が1のときも9!通りです。currentRowに9!を何度か足していくと100万を超えます。このとき、先頭の文字が決定されるということです。nums[0]の値が決まります。この考えを残りのnums配列の要素に適用します。そのような繰り返し操作なので、while文を使いました。

nums配列が決定した後は、格納された数値に従い、順列を出力します。

Problem 25

この問題は自分なりに要約しました。

Fibonacciで1000桁になる最小の項は第何項か?

ソース

    private void test() {
        BigInteger a = new BigInteger("1");
        BigInteger b = new BigInteger("1");
        int index = 2;
        BigInteger term = new BigInteger("1");
        while (term.toString().length() < 1000) {
            term = next(a, b);
            index ++;
            a = b;
            b = term;
        }
        System.out.println(index);
    }

    private BigInteger next(BigInteger a, BigInteger b) {
        return a.add(b);
    }

JavaにはBigIntegerがあるので、それを使いました。toString().length()で桁数になります。