Skip to content

Instantly share code, notes, and snippets.

@sugumura
Last active November 2, 2016 14:51
Show Gist options
  • Save sugumura/a9e3f183eec611bba6febf7900bf0235 to your computer and use it in GitHub Desktop.
Save sugumura/a9e3f183eec611bba6febf7900bf0235 to your computer and use it in GitHub Desktop.
第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