第2章
第3節 情報のあらわし方と処理手順の工夫
第3節 情報のあらわし方と
処理手順の工夫
1 処理手順の工夫
2 情報のあらわし方の工夫
第2章
第3節 情報のあらわし方と処理手順の工夫
1 処理手順の工夫
• 同じ解を得るためのアルゴリズムは,1つで
はない。
• アルゴリズムの工夫について学習しよう。
第2章
第3節 情報のあらわし方と処理手順の工夫
正しい?アルゴリズム
• ある問題を解くためのアルゴリズムは,1つだけと
はかぎらない。
• 正しい解が,早く見つかるアルゴリズムが,もっと
も正しいアルゴリズムと考えられる。
• 単純なアルゴリズムでは,計算に何日もかかる。
• 複雑なアルゴリズムは,計算はすぐに終わるが,
プログラムをつくるのに何日もかかるし,ミスが発
生しやすい。
アルゴリズムの工夫が,重要である。
第2章
第3節 情報のあらわし方と処理手順の工夫
素数
• 1より大きい整数で,1とその数自身でしか割り切
れない数を素数という。
–
–
–
–
–
–
1は素数でない(1より大きくない)。
2は素数である(1と2でしか割り切れない)。
3は素数である(1と3でしか割り切れない)。
4は素数でない(1と4のほかに2で割り切れる)。
5は素数である(1と5でしか割り切れない)。
6は素数でない(1と6のほかに2や3で割り切れる)。
第2章
第3節 情報のあらわし方と処理手順の工夫
素数を求めるアルゴリズム
数nを読みこむ。
変数nを2からnの手前まで変化させながら繰り返し,
sosu←真。
変数iを2からxの手前まで変化させながら繰り返し,
もしxがiで割り切れるならsosu←偽。
ここまで繰り返し。
もしsosuが真ならxを出力する。
ここまで繰り返し。
第2章
第3節 情報のあらわし方と処理手順の工夫
アルゴリズムの工夫
このアルゴリズムの無駄を省くには・・・・
数nを読みこむ。
変数nを2からnの手前まで変化させながら繰り返し,
sosu←真。
iの上限は,√xまででよい。
iについても,3以上の奇数だけを調
2以外の素数はすべて奇数である。
割り切れたら,すぐに繰り返しを終わ
べればよい。
らせればよい。
2を最初に出力して,あとは3以上の
奇数だけを調べればよい。
変数iを2からxの手前まで変化させながら繰り返し,
もしxがiで割り切れるならsosu←偽。
ここまで繰り返し。
もしsosuが真ならxを出力する。
ここまで繰り返し。
第2章
第3節 情報のあらわし方と処理手順の工夫
JavaScriptによるプログラムの例
<script>
n = parseFloat(prompt('いくつ未満の素数を計算しますか'));
for(x = 2; x < n; ++x) {
「偽」をあらわす
「真」をあらわす
特別な値である。
sosu = true;
2つずつ変化させるには,
++x
for(i = 2; i < x; ++i) {
のかわりに,
x = x + 2
if(x % i == 0){ sosu = false; }
とすればよい。
}
「○の手前まで」の条件を
「○まで」とするには,
if(sosu){document.write(x + ' '); }
<
のかわりに,
}
<=
</script>
を使えばよい。
第2章
第3節 情報のあらわし方と処理手順の工夫
2 情報のあらわし方の工夫
• 情報のあらわし方を工夫すると,アルゴリズ
ムを改良したり,プログラムを書きやすくでき
る。
第2章
第3節 情報のあらわし方と処理手順の工夫
データ構造
• データ構造
– 情報をあらわすために用いる構造。
– データ構造を工夫することで,はじめて可能になる
ようなアルゴリズムの工夫も多い。
第2章
第3節 情報のあらわし方と処理手順の工夫
エラトステネスのふるい
• 2からはじめて,配列を順にしらべていく。
• しるしのついていない箇所があれば,その番
号は素数であると判断する。
• 素数が見つかると,その番号の倍数の箇所に
すべてしるしをつける。
• 次の素数は,しるしのついていない次の数とし
て見つかる。
第2章
第3節 情報のあらわし方と処理手順の工夫
エラトステネスのふるい
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
2は,しるしがついていないので素数とわかる。
まず,2からはじめる。
・・・しるしのついていない数が,素数である。
次は,17。
次は,13。
次は,11。
次は,7。
次は,5。
3の倍数すべてに,しるしをつける。
3は素数であるとわかる。
次の,しるしがついていない数は3。
2の倍数すべてに,しるしをつける。
第2章
第3節 情報のあらわし方と処理手順の工夫
エラトステネスのふるい
数nを読みこむ。
a←要素数がn個の配列。
変数xを2からnの手前まで変化させながら繰り返し,
もしa[x]にしるしがついていないなら
xを出力する。
変数iをxからnの手前までxずつ変化させながら繰り返し,
a[i]にしるしをつける。
ここまで繰り返し。
枝分かれ終わり。
ここまで繰り返し。
第2章
第3節 情報のあらわし方と処理手順の工夫
JavaScriptによるプログラムの例
<script>
a = parseFloat(prompt('いくつ未満の素数を計算しますか'));
a = new Array(n);
for(x = 2; x < n; ++x) {
if(a[x] == null) {
配列をつくる。
配列のすべての要素にはnull(なに
もはいっていないことをあらわす特
別な値)がはいった状態になる。
document.write(x + ' ');
for(i = x; i < n; i = i + x) {a[i] = 1; }
}
}
</script>
ダウンロード

222300