«前の日記(2017-12-25) 最新 次の日記(2018-02-12)» 編集

tueda's diary


2018-01-16 tueda's diary

_ 連続する整数の和で表される整数

前回の【大阪・さんすう勉強会】 終了後に,参加者さんから質問を頂きました.とあるコースウェアでプログラミングの勉強をされているようで,そのお題についてでした.ざっくりこんな問いです(ちょっと変えてます).

  • 整数には,連続する整数の和で表すことができるものがある
    • 5 = [2 + 3], 18 = [3 + 4 + 5 + 6]
  • なかには複数の連続する整数の組み合わせが存在するものもある
    • 18 = [3 + 4 + 5 + 6], [5 + 6 + 7]

このように複数の組み合わせが存在するもののうち,ふたつ以上の組みが連続して現れるもの,たとえば

  • 3 = [1 + 2], [3]
  • 15 = [4 + 5 + 6], [7 + 8]
  • 27 = [2 + 3 + 4 + 5 + 6 + 7], [8 + 9 + 10] [13 + 14]

のようなものもある.このような正の整数を小さいものから順に表示するプログラムを作成せよ.

最初に聞いた時は「こんなの総当たりするしかないんじゃないの?」と思ってたんですが,なんと,ご質問者さんと勉強会参加者の方々が色々調べてくださって,実はこんな性質があることが分かりました.

  • 連続する整数の和で表される整数は,1以外の奇数の約数を持つ
  • この奇数の約数の個数だけ,和の組みが存在する
  • 具体的な組み合わせは以下の手順で求められる
    • 元の数を奇数の約数で割った商を中心に,割った奇数と同じ個数の連続した数を足すと元の数になる(0やマイナスもとりあえず並べる)
    • 小さい方がマイナスになる場合は,正の側と相殺する

参考: http://www.eikoh-seminar.com/echtas/blog/2015/10/post-224.html

ここまで分かれば,プログラムを書くのは簡単です.

戦略

以下の手順でプログラムを書くことにしましょう.

  • 与えられた数の,奇数の約数のリストを作る関数を作成する(総当たり)
  • そのリストで割った商を中心に,最小値と最大値だけを保持した配列を作る
    • 対象がその数自体の場合は単純にふたつに分ける
  • 配列が全部できたら,とりあえずまた総当たりで (最大値+1=最小値) となっているものを探す
  • 見つけたらそこで終了

実は質問者さんも最初,この戦略の事を仰ってたのですが,私が上記の性質を知らなかったのでちゃんと対応できなかったのでした.ゴメンなさい><;

コード(Java)

とりあえず私の手元ですぐに書けるのが Java だったので,Java で書いて見ました.戦略さえ立ててしまえば,コーディングには30分もかかりませんでした!(IntelliJ にだいぶ助けてもらってるからですけど(;´Д`))

いやー,算数の知識って重要ですね(ぁ)

import java.util.ArrayList;
import java.util.List;

/*
 * 解説
 * 連続する整数の和で表す事のできる整数は,1以外の奇数の約数をも ち,
 * そのような約数の個数分,和がその整数と同じ値になる連続ブロックを
 * もつ(らしい).
 * この時,奇数の約数(v)で元の整数(n)を割った値(c)を中心にし て
 * v 個の連続する数の和が n と等しくなる(ようだ).
 *
 * この性質は整数(負の数を含む)の範囲で有効であるが,今回は自然数
 * の範囲で連続性を見ることが条件なので,負の部分は正の部分と相殺す る.
 *
 */

public class Renzoku {

    public static void main(String [] args) {

        Renzoku r = new Renzoku();

        int count = 1;
        for (int n = 3; count <= 80; n++) {
            if (r.process(n, count)) {
                count++;
            }
        }

    }

    public boolean process(int n, int count) {
        boolean ret = false;
        ArrayList<MinMax> minmaxAll = new ArrayList<>();

        /*
         * 奇数の約数を求める(ほぼ総当たりだけど,loop は n の
         * 平方根までに押さえて,同じ loop の回数の中で反対側の
         * 計算もしている)
         */
        List<Integer> div = divisor(n);
        for (int v : div) {
            /*
             * 約数で割った数を中心に,最大値と最小値を求める
             */
            int c = n / v;
            int min = c - v / 2;
            int max = c + v / 2;

            /*
             * 元の数は単純にふたつに分ける
             */
            if (v == n) {
                min = n / 2;
                max = n /2 + 1;
            }
            /*
             * 最小値が負の数になる場合は正の側を相殺する
             */
            if (min <= 0) {
                min = min * -1 + 1;
            }

            /*
             * 区間の最小値と最大値だけを覚えておく
             */
            minmaxAll.add(new MinMax(min, max));
       }

        boolean isGot = false;
        for (MinMax minmax : minmaxAll) {
            for (MinMax minmax2 : minmaxAll) {
                if (minmax == minmax2) {
                    continue;
                }
                if (minmax.min == minmax2.max + 1) {
                    isGot = true;
                    break;
                }
            }
        }
        if (isGot) {
            System.out.println("Got!: " + count + ": " + n);
            ret = true;
        }
        return ret;
    }

    /**
     * 約数のリストを作る(奇数のみ)
     */
    public static final List<Integer> divisor(final int n) {
        final List<Integer> list = new ArrayList<>();

        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                /*
                 * 平方根までしか見ないので,偶数であっても割った結果が
                 * 奇数になるものを掬う必要がある.
                 */
                if (i % 2 != 0) {
                    list.add(i);
                }
                int j = n / i;
                if (i != j && j % 2 != 0) {
                    list.add(n / i); // 逆向き
                }
            }
        }
        return list;
    }

    class MinMax {
        public int min;
        public int max;

        public MinMax(int min, int max) {
            this.min = min;
            this.max = max;
        }
    }
}

やっつけなので効率の悪いところや美しくないところは多々ありますが,そこは目をつぶるか,できたら綺麗に書き直してください(ぉ)

本日のツッコミ(全2件) [ツッコミを入れる]
_ いけばた (2018-01-17 11:32)

勉強会で質問させてもらった張本人ですw <br>解説ありがとうございます!解いてしばらくしたら、内容絶対忘れるので、解説していただいて本当にありがたいです…! <br>比率からの分数の話、面白かったです。有理数、よくわかりました。次の無理数、楽しみにしてます! <br>

_ うえお (2018-01-17 11:52)

ご参加ありがとうございました! <br>最近は日記ならぬ年記になっていたので,良いお題を頂いて良かったですw <br>来月もまたご参加お待ちしております.


総訪問者数: 本日の訪問者数: 昨日の訪問者数: