2016/10/19
アルゴリズムの活用
コンピュータになんらかの手続きをし、問題を解決する
多くの場合繰り返し処理を含む
最大公約数 (GCD)
16と40
約数
16の約数
1 2 4 8 16
40の約数
1 2 4 5 8 10 20 40
決まった手続きで、答えを求められる
1から10の合計を求める
-> 等差数列
-> 差が1の数列
// 1から10までの繰り返し
for (var i = 1; i <= 10; i++) {
console.log(i);
}
1回めの繰り返しで1を足す
2回めの繰り返しで2を足す
...
10回めの繰り返しで10を足す
var a = 0;
for (var i=1; i<=10; i++) {
a = a + i;
console.log(i + ":" + a);
}
1から5までの掛け算
5の階乗(5!)
// ありがちな間違い
var a = 0; // 初期値が0だとすべて0
for (var i=1; i<=5; i++) {
a = a * i;
console.log(i + ":" + a);
}
// 初期値を1にする
var a = 1;
for (var i=1; i<=5; i++) {
a = a * i;
console.log(i + ":" + a);
}
16と40の最大公約数
1から順に割る方法
var a = 16;
var b = 40;
var gcd = 1;
for (var i=1; i<=16; i++) {
if (a % i == 0 && b % i == 0) { // aとbが両方iで割り切れた
gcd = i;
console.og(gcd); // どちらの数字も割り切れた
}
}
console.log("最大公約数:" + gcd); // 最大公約数
答えを求めるために16回繰り返し処理をしている
1からではなく16から割り切れる数を探す（逆順）
var a = 16;
var b = 40;
var gcd = 1;
for (var i=16; i>=1; i--) {
console.log(i);
if (a % i === 0 && b % i === 0) {
gcd = i;
break; // for文をやめる
}
}
console.log("最大公約数:" + gcd); // 最大公約数
1から繰り返すより計算回数が少なくなった
計算回数が少ないほうがアルゴリズムとして良い場合が多い
(問題) 1071 と 1029 の最大公約数を求める。
1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。
1072 % 1029 = 42
1024 % 42 = 21
42 % 21 = 0
for(;;) {// 無限ループ
if (r == 0) {// rが割り切れる場合にループを終了する
break;
}
}
ユークリッド互除法を利用したプログラム
var a = 1072;
var b = 1029;
var gcd = 1;
var r = 0;
for(;;) {
r = a % b;
if (r == 0) {
gcd = b;
break;
}
a = b;
b = r;
}
console.log("最大公約数: " + gcd);
1から13までのカードをバラバラに重ねられている
どのように並び替えるか？
1回目
1. [8, 3, 5, 1, 9]
2. [3, 8, 5, 1, 9]
3. [3, 5, 8, 1, 9]
4. [3, 5, 1, 8, 9]
2回目
1. [3, 5, 1, 8, 9]
2. [3, 1, 5, 8, 9]
3. [3, 1, 5, 8, 9]
4. [3, 1, 5, 8, 9]
3回目 (完了)
1. [3, 1, 5, 8, 9]
2. [1, 3, 5, 8, 9]
3. [1, 3, 5, 8, 9]
4. [1, 3, 5, 8, 9]
プログラム
var ar = [8, 3, 5, 1, 9];
console.log(ar);
// 0番目と1番目を入れ替える
var tmp = ar[0];
ar[0] = ar[1];
ar[1] = tmp;
console.log(ar);
小さなプログラムを作って方法を確認することが大事
var ar = [8, 3, 5, 1, 9];
console.log(ar);
// 繰り返し文にする。0と1番目の要素を5回入れ替える
for (var i=0; i<5; i++) {
var tmp = ar[0];
ar[0] = ar[1];
ar[1] = tmp;
console.log(ar);
}
配列要素のインデックスをiに置き換える
var ar = [8, 3, 5, 1, 9];
console.log(ar);
for (var i=0; i<5-1; i++) { // ar[5]の要素はないため
var tmp = ar[i];
ar[i] = ar[i+1];
ar[i+1] = tmp;
console.log(ar); // 先頭の要素が末尾に移動した
}
条件をつける
var ar = [8, 3, 5, 1, 9];
console.log(ar);
for (var i=0; i<5-1; i++) { // ar[5]の要素はないため
if (ar[i] > ar[i+1]) { // 左の要素が大きい場合のみ入れ替える
var tmp = ar[i];
ar[i] = ar[i+1];
ar[i+1] = tmp;
}
console.log(ar); // 先頭の要素が末尾に移動した
}
1要素の入れ替え処理を繰り返す
var ar = [8, 3, 5, 1, 9];
console.log(ar);
for (var j=0; j<100; j++) { // 適当に100回ぐらい実行してみる
for (var i=0; i<5-1; i++) { // ar[5]の要素はないため
if (ar[i] > ar[i+1]) {
var tmp = ar[i];
ar[i] = ar[i+1];
ar[i+1] = tmp;
}
console.log(ar); // 先頭の要素が末尾に移動した
}
}
何回繰り返せばよいか？
今回の場合は5要素を並び替えるため4回
計算量O（オーダー）
(n-1)(n-1)
n * n
O(n^2)
var ar = [8, 3, 5, 1, 9];
console.log(ar);
for (var j=0; j<5-1; j++) { // n-1
for (var i=0; i<5-1; i++) { // n-1
if (ar[i] > ar[i+1]) {
var tmp = ar[i];
ar[i] = ar[i+1];
ar[i+1] = tmp;
}
console.log(ar); // 先頭の要素が末尾に移動した
}
}
1度並び変えを行った場合右端の要素は確定するため、繰り返しを減らして良い
var ar = [8, 3, 5, 1, 9];
console.log(ar);
for (var j=0; j<5-1; j++) {
for (var i=0; i<5-1-j; i++) { // 確定した要素の繰り返し回数を減らす
if (ar[i] > ar[i+1]) {
var tmp = ar[i];
ar[i] = ar[i+1];
ar[i+1] = tmp;
}
console.log(ar); // 先頭の要素が末尾に移動した
}
}
// 篩のもとになるリストを作成
var ar = [];
for (var i = 2; i <= 120; i++) {
ar.push(i);
}
console.log(ar);
var ar = [];
for(var i=0; i<=20; i++){
ar[i] = i;
}
console.log(ar);
ar[0] = -1;
ar[1] = -1;
var tp=0;
for(;;){
if(ar[tp] !== -1){
var val = ar[tp];
for(var i=2; val*i<=20; i++){
ar[val * i] = -1;
}
tp++;
}else{
tp++;
if(tp > Math.sqrt(20)){
break;
}
}
}
console.log(ar);
コードまとめ
GCDを求めるプログラム３種
バブルソート
選択ソート
エラトステネスの篩
フィボナッチ数列（おまけ）