Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
第3回Javascript勉強会@未来会議室(プログラミング超入門) http://otona.connpass.com/event/41816/

2016/10/19

Javascript勉強会第三回

アルゴリズム

アルゴリズムの活用
コンピュータになんらかの手続きをし、問題を解決する
多くの場合繰り返し処理を含む

最大公約数 (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から繰り返すより計算回数が少なくなった
計算回数が少ないほうがアルゴリズムとして良い場合が多い

ユークリッドの互除法

ユークリッドの互除法 - Wikipedia

(問題) 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);	// 先頭の要素が末尾に移動した
	}
}

エラトステネスの篩(えらとすてねすのふるい)

エラトステネスの篩 - Wikipedia

// 篩のもとになるリストを作成
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を求めるプログラム3種

バブルソート

選択ソート

エラトステネスの篩

フィボナッチ数列(おまけ)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.