codewars.com の問題を解いていて、右往曲折あってどうにか答えにたどり着くまでの流れを復習の意味でまとめています。
頭の良い記事ではありませんが、数学的センスを何処かに置いてきたので解説とか読んでもよく分からないけど、バカが悩んでる様を見ると少し理解が早まるぞ！という方のお役に立てれば幸いです。
書いてる人
- 数学知識は皆無（高校でやったはずですがほとんど覚えていません、、算数ができる程度です）
- 主にJSを利用（以下の問題もJSで解いています）
- JSに関して初学者ではないが、リファレンスに載ってる関数を全部把握してるかと言われると微妙というレベル
- アルゴリズムってねーあれだよねー
という感じですので、同じような人におすすめです。
codewars.com や projecteuler.net を解きながら初歩の初歩から数学やアルゴリズムの勉強をしている最中です。
codewars
codewars.com はサイト上でプログラミングの問題を解いていくサービスです。
以下が詳しいです。
https://qiita.com/javacommons/items/7c473cda7825ab99e08c
今回の問題
渡される引数が10の場合 1 * 2 * 3 * .... 10 まで掛け算を行い、出てきた値の末尾に並ぶゼロは何個ですか？という問題です。高校生の頃、数学の教科書でぼんやり目にしたような気のする階乗というもので10!と表現するやつです。
そして 10! = 3628800 なので、正解は 2 になります。さらに「1000!だと2568桁だからね！」という内容の注記があります。愚直に掛け算を繰り返したらすぐに桁落ちしそうです。
右往曲折その１ 『不要な桁を捨てて計算を繰り返す』
まず試してみたのが
- 左から順に掛け算
- 末尾がゼロになったら、ゼロの数を記録
- 末尾の0を削る
- 大きい桁を捨てる（10桁まで残す事にしました）
- 1に戻って繰り返し
という処理です。
例えば20!まで進んだ状況だと
5100408832 * 20 = 102008176640- 増えた末尾ゼロの数を記録（
+=1） - ゼロを削る
10200817664 - 10桁以上の桁を削る
200817664 - １に戻る
200817664 * 21
という具合。これなら桁落ちもせず不要に大きな掛け算が省かれます。
コード
function zeros(n) {
let size = n;
let base = 1;
let zeroSize = 0;
for (let index = 2; index <= size; index++) {
base = base * index;
if (base % 10 == 0) {
let tmp = pruneZero(base, 0);
base = tmp[0];
zeroSize += tmp[1];
}
base = base % 1000000000;
}
return zeroSize;
}
function pruneZero(num, zeroSize) {
num = num / 10;
zeroSize++;
if (num % 10 == 0) {
return pruneZero(num, zeroSize);
} else {
return [num, zeroSize];
}
}
処理速度の問題
一番最初に書いたコードでは、桁の操作に正規表現を利用していましたが演算で処理をする方が断然速かったので直しています。
また 4.大きい桁を捨てる の部分ですが、最初は掛け合わせる数の桁数+1 を切り出していたのですが、都度切り出す桁数を計算するよりも切り出す桁数を固定する方が処理が速かった為10桁に固定しました。
と、諸々修正はしたものの、手元で実行したところ 100000000! で 2.78s 掛かりました。codewarsにソースを提出すると、timeoutでrejectされます。
右往曲折その２ 『5だけ考える』
ちょっとした工夫で処理が簡単になるのだろうとは思うのですがよくわかりません。
分からないので、右往曲折1のコードを使って答えを書き出して並べてみます。
// [n!,末尾ゼロの桁数]
[ 0, 0 ]
[ 1, 0 ]
[ 2, 0 ]
[ 3, 0 ]
[ 4, 0 ]
[ 5, 1 ]
[ 6, 1 ]
[ 7, 1 ]
[ 8, 1 ]
[ 9, 1 ]
[ 10, 2 ]
[ 11, 2 ]
[ 12, 2 ]
[ 13, 2 ]
[ 14, 2 ]
[ 15, 3 ]
[ 16, 3 ]
[ 17, 3 ]
[ 18, 3 ]
[ 19, 3 ]
[ 20, 4 ]
[ 21, 4 ]
[ 22, 4 ]
[ 23, 4 ]
[ 24, 4 ]
[ 25, 6 ]
[ 26, 6 ]
[ 27, 6 ]
[ 28, 6 ]
[ 29, 6 ]
[ 30, 7 ]
[ 31, 7 ]
[ 32, 7 ]
[ 33, 7 ]
[ 34, 7 ]
[ 35, 8 ]
[ 36, 8 ]
[ 37, 8 ]
[ 38, 8 ]
[ 39, 8 ]
[ 40, 9 ]
まず気が付くのは、5回を1セットにゼロの桁数が増えていくことです。よくよく考えると当たり前ですが、末尾をゼロにしようと思ったら5の倍数と偶数を掛ける以外にありません。
そして、5で割るだけでいいの？？と思いかけましたが、40! → 9 で割る５とは限りませんでした。
ズレてる部分を探すと 24! → 4 25! → 6 と25！のところでゼロの桁数が2増えています。25 = 5 * 5 なので、5に注目するという方向は間違いなさそうです。
さらに桁が1以上増える箇所を探してみたところ
[ 49, 50 ]
[ 50, 12 ]
[ 74, 16 ]
[ 75, 18 ]
[ 99, 22 ]
[ 100, 24 ]
[ 124, 28 ]
[ 125, 31 ]
という具合に増えていきます。注目すべきは125!で3桁増えている部分ですが、125 = 5 * 5 * 5 なので、２５!で２桁増えることも考えると5の累乗分ゼロが増えるっぽいぞ、という事が分かりました。確認の為にそれ以降の5の累乗を確認すると
5 * 5 * 5 * 5 = 625 → 4桁増加
5 * 5 * 5 * 5 * 5 = 3125 → 5桁増加
となっていて間違いなさそうです。
さらに5の累乗では無い数字も見ていくと 50→2桁増加に対して、 250→3桁増加 となっています。
それも踏まえて並べてみると
25 = 5 * 5
50 = 5 * 5 * 2
125 = 5 * 5 * 5
250 = 5 * 5 * 5 * 2
という事で5の何乗であるかというより、元の数字を５の掛け算に分解した時に5が何回出てくるか（５で何回割れるか）で末尾ゼロの桁数を求めれそうです。
コード
5の倍数の数字を５で割れるまで繰り返し、割った総数を書き足していきます。
function zeros(n) {
let zeroSize = 0;
for (let index = 5; index <= n; index = index + 5) {
zeroSize = divisionAt5(index, zeroSize);
}
return zeroSize;
}
function divisionAt5(num, zeroSize) {
zeroSize++;
num = num / 5;
if (num % 5 == 0) {
return divisionAt5(num, zeroSize)
} else {
return zeroSize;
}
}
それでも処理速度の問題
まず5の倍数だけをチェックすればよいので、ループの回数が1/5になります。また1ステップ毎の計算もだいぶ減っています。
その結果 100000000! で 0.25s まで短縮出来ました。右往曲折1に比べて実行時間が1/10以下になったのですが、それでもcodewarsに提出するとtimeoutでrejectされます。
右往曲折その3 『そもそもループしてては無理』
codewarsでタイムアウトするまでの流れを見ていると、かなり大きな桁数のテストが行われています。
そもそもループして数えるのではなく 「125!ならゼロは31桁です」と、バシッと125から直接31を導かないと無理そうです。
改めて幾つかの例（特徴的なところと一般的なところ）を並べ、これが導き出せる計算式を考えてみます。
[ 0, 0 ]
[ 1, 0 ]
[ 5, 1 ]
[ 9, 1 ]
[ 10, 2 ]
[ 11, 2 ]
[ 25, 6 ]
[ 40, 9 ]
[ 99, 22 ]
[ 100, 24 ]
[ 124, 28 ]
[ 125, 31 ]
[ 1000, 249 ]
10の場合
10 / 5 = 2 でそのまま答えが出ています。
そして右往曲折2と同様ですが 5 * 5 が含まれるパターンでは桁が増え
25 ( 5 * 5 ) の場合
25 / 5 = 5 に +1 した 6 が答えです。
125 ( 5 * 5 * 5 ) の場合
125/5 = 25 に +6 した 31 が答えになっています。
*5 の出てくる回数分が増える感じですね。
そして
100 ( 5 * 5 * 4 ) の場合
100 / 5 = 20 に +4 した 24 が答えです。
お！ 100 = 5 * 5 * 4 で +4 なのかな。
それを踏まえて改めて 25 の場合
まず 25! の中に含まれる
5の倍数は 5, 10, 15, 20, 25 の 5つ
25の倍数は 25 の 1つ になります。
そして 25 = 5 * 5 なので、25には 2つの5 が入っているのですが
2つのうち、1つは 5の倍数の方の25 で既にカウントされているので+２の必要はなく 5 + 1 = 6 で 25! に含まれる5の個数が求められそうです。
計算の手順としては
25 / 5 = 5
25 / 25 = 1 で合計が 6 となります。
試してみる
100!の場合
100/5 = 20
100/25 = 4 → 24
250!の場合
250/5 = 50
250/25 = 10
250/125 = 2 → 62
あってる！
コード
最初に5の累乗の配列をnより小さい値まで作り、5累乗リストの小さい値から順番に割った数を足していっています。
function zeros(n) {
let checkNumbers = [];
let fiveMultiple = 5;
while (fiveMultiple <= n){
checkNumbers.push(fiveMultiple);
fiveMultiple *= 5;
}
return checkNumbers.reduce((a,b)=>{
return a + Math.floor( n / b);
}, 0)
}
nに対してのループ処理が無くなったので10!でも10000000!でもそれほど処理時間に変化がなくなり、codewarsでもタイムアウトせず無事に通ります。
そして回答後に出てくる他の方のコードを見るともっと賢く
function zeros (n) {
var zs = 0;
while(n>0){
n=Math.floor(n/5);
zs+=n
}
return zs;
}
という感じで5で割った値を更に5で割るという処理を繰り返しています。
250の場合
250/5 = 50
50/5 = 10
10/5 = 2 → 62
という流れです。
よく考えれば、250/125 = 250/5/5/5 ですので、割った答えが5以下になるまで5で割り続け、１ステップ毎に結果を足していくという流れで完結しますね。
まとめ
問題を解いて気がついた事
- 与えられた値が増えたらその分時間を食う処理を、アルゴリズムを考えるとそうではない処理に変換出来る（すごい）
- 大きい数字を小さく分解するってモデルは多分他でも色々使えるんだろうと想像（また出てきそう）
- 計算資源が手元にあり余ってる21世紀人なので、とりあえず力技で大量の答えを書き出してから考え始める事ができる（強い）
そしてだいぶ話がそれるのですが、例えば今回の問題の引数と答えを大量に作って機械学習させると、アルゴリズムなんぞ知らなくても正解が出せるのでは？と思って調べて見つけた記事『素数を求めて（ディープラーニング編）』が内容半分も理解できなくても面白かったです。
さらに記事の中にリンクのあるquoraの回答。
Could you train a machine learner to predict the next prime number?
現在のディープラーニングだと「7で割れるか」も正しい答えが出せないとのこと。面白い。
それではまた次回。
アルゴリズム体操のインデックス
週イチ更新が目標でしたがちょっと無理そうです。思っていたより記事に時間が掛かりますね、、