プログラミングはゲーム感覚の、ユゲタです。
最近SNSでよく見かける、入社試験で行った問題で、「２つの数値から最大公約数を返すプログラミングをせよ」というのを見かけて、自分でもやってみたくなったので、ブログで挑戦してみたいと思います。
ちなみに、最大公約数を求めるので、最小公倍数も求めてみたいと思います。
なんとなく、この２つは、関連する処理になりそうな気がするという想定なんですよね。
最大公約数？最小公倍数？
中学校の数学で習った事を覚えていますが、ようするに、
最大公約数というのは、２つの数値で割り切れる（割った後整数になる値）一番大きい数値で、
最小公倍数は、２つの値に整数値を掛け合わせていった時に、同じ数になる一番小さい値の事です。
忘れてしまっている人は、思い出してみましょう！
最大公約数を求めるプログラム
function GreatestCommonDivisor(a , b){
for(let i=a-1; i>=0; i--){
var a2 = a/i
var b2 = b/i
if(~~a2 === a2
&& ~~b2 === b2){
console.log(i)
break
}
}
}
var a = Math.floor(Math.random() * 99)+1
var b = Math.floor(Math.random() * 99)+1
console.log(a +" & "+ b)
GreatestCommonDivisor(a , b)
> 56 & 42
> 14
できた！
ランダムで100までの数値を２つ出してその２つの数値の最大公約数を求めています。
1ずつ引き算をしていって、それぞれが同時に小数点がなくなった状態が最大公約数と判定しています。
もっと短くかけそうだけど、わかりやすいこの状態でゴールにしましょう。
最小公倍数を求めるプログラム
function LatestCommonMultiple(a , b){
// 掛け合わせた最大値を求める
var maxMultiple = a * b
// 大きい方の数値を取得
var largeNum = a > b ? a : b
//
for(i=largeNum+1; i<=maxMultiple; i++){
var a2 = i / a
var b2 = i / b
if(a2 === ~~a2
&& b2 === ~~b2){
console.log(i)
return i
}
}
return null
}
var a = Math.floor(Math.random() * 99)+1
var b = Math.floor(Math.random() * 99)+1
console.log(a +" & "+ b)
LatestCommonMultiple(a , b)
> 95 & 12
> 1140
やはり想像通り、最大公約数と似たような感じで作成できました。
今回は、２つの値を掛け合わせて、その数字を上限として、加減をa,bのどちらか大きい値で、１つずつ値を足して行きます。
そして、２つの値とも、足し込んだ数値を割った時に、整数になれば、その値が最大公約数になるという事です。
こういうアルゴリズム的なプログラミングは一度は書いておくと、その後スキルが上がった時に、めちゃくちゃ効率が良くなった事が自分で判定できるようになるので、オススメです。
0 件のコメント:
コメントを投稿