数学オリンピックの問題をJSで解いてみた (2016年日本ジュニア数学オリンピック予選　第8問）

概要

• 数学オリンピックの問題をプログラムで解きました。
• 言語はJavascriptを使います。
• 数学での解き方はわかりません。

問題文

各桁の数字が相異なるような37の倍数のうち、最大のものを求めよ。

要点

問題文から以下の内容を読み取れます。
この内容をもとにコーディングしていきます。

• 0~9を使った最大の数値は、9876543210である
• 37の倍数である

コーディング

まずは、同じ数字が存在するかチェックする関数を作成しました。

/*
 * 同じ数字が存在するかチェックする
 * @param  {Number} n 自然数
 * @return {Boolean}
 *         同じ数字が存在しない場合: True
 *         同じ数字が存在する場合: False
 */
function duplicateNumCheck(n) {
    var arr1 = String(n).split('');       //数値を桁ごとに切り分ける
    var before = arr1.length;             //配列の数をカウントする
    var arr2 = Array.from(new Set(arr1)); //配列の中の重複した値を排除する
    var after = arr2.length;              //重複を排除した配列の数をカウントする
    return before !== after;              //配列の数を比較して結果を返す
}

上記関数を利用し、37から順に37倍数をチェックしていく、プログラムを作成しました。
答えは、'9876435012'と出力されたのですが
処理の時間がかかりすぎてしまいます。修正が必要です。
for文のループの回数を数えてみたら266,933,600回となりました。

var n = 37; //倍数を指定
var max = 9876543210; //ループを抜ける条件
var r; //解を格納する

for (i=1;i*n<max;i++) {
    if (duplicateNumCheck(i*n) === false) {
        r = i*n;
    }
}
console.log(r);

コーディング（修正）

処理時間が掛かり過ぎたため、
最大値からマイナスにでループするように変更しました。
ループ回数は、2925回で済むようになりました。

var n = 37;
var max = 9876543210;
var loop = Math.floor(max/n); //先にループする回数を計算
var r;

for (i=loop;i*n>0;i--) { //マイナスへループするよう修正
    if (duplicateNumCheck(i*n) === false) {
        r = i*n;
        break; //最初の一回目が最大値なのでbreakでループ抜ける
    }  
}
console.log(r);

結論

もっと他に良い方法があるかと思いますが、下記コードが最終系となります。
また、数学で解く楽しみは減りましたが、nを書き換えることでいろんな数を簡単に試せるのがプログラムで解く利点と感じました。

/*
 * 各桁の数字が相異なるかをチェックする
 * @param  {Number} n 自然数
 * @return {Boolean}
 *         同じ数字が存在しない場合: True
 *         同じ数字が存在する場合: False
 */
function duplicateNumCheck(n) {
    var arr1 = String(n).split('');
    var before = arr1.length;
    var arr2 = Array.from(new Set(arr1));
    var after = arr2.length;
    return before !== after;
}

var n = 37;
var max = 9876543210;
var loop = Math.floor(max/n);
var r;

for (i=loop;i*n>0;i--) {
    if (duplicateNumCheck(i*n) === false) {
        r = i*n;
        break;
    }  
}
console.log(r);

以上