第２章
第３節 情報のあらわし方と処理手順の工夫
第３節 情報のあらわし方と
処理手順の工夫
１ 処理手順の工夫
２ 情報のあらわし方の工夫
第２章
第３節 情報のあらわし方と処理手順の工夫
１ 処理手順の工夫
• 同じ解を得るためのアルゴリズムは，１つで
はない。
• アルゴリズムの工夫について学習しよう。
第２章
第３節 情報のあらわし方と処理手順の工夫
正しい？アルゴリズム
• ある問題を解くためのアルゴリズムは，１つだけと
はかぎらない。
• 正しい解が，早く見つかるアルゴリズムが，もっと
も正しいアルゴリズムと考えられる。
• 単純なアルゴリズムでは，計算に何日もかかる。
• 複雑なアルゴリズムは，計算はすぐに終わるが，
プログラムをつくるのに何日もかかるし，ミスが発
生しやすい。
アルゴリズムの工夫が，重要である。
第２章
第３節 情報のあらわし方と処理手順の工夫
素数
• １より大きい整数で，１とその数自身でしか割り切
れない数を素数という。
–
–
–
–
–
–
１は素数でない（１より大きくない）。
２は素数である（１と２でしか割り切れない）。
３は素数である（１と３でしか割り切れない）。
４は素数でない（１と４のほかに２で割り切れる）。
５は素数である（１と５でしか割り切れない）。
６は素数でない（１と６のほかに２や３で割り切れる）。
第２章
第３節 情報のあらわし方と処理手順の工夫
素数を求めるアルゴリズム
数nを読みこむ。
変数nを２からnの手前まで変化させながら繰り返し，
sosu←真。
変数iを2からxの手前まで変化させながら繰り返し，
もしxがiで割り切れるならsosu←偽。
ここまで繰り返し。
もしsosuが真ならxを出力する。
ここまで繰り返し。
第２章
第３節 情報のあらわし方と処理手順の工夫
アルゴリズムの工夫
このアルゴリズムの無駄を省くには・・・・
数nを読みこむ。
変数nを２からnの手前まで変化させながら繰り返し，
sosu←真。
iの上限は，√xまででよい。
iについても，３以上の奇数だけを調
２以外の素数はすべて奇数である。
割り切れたら，すぐに繰り返しを終わ
べればよい。
らせればよい。
２を最初に出力して，あとは３以上の
奇数だけを調べればよい。
変数iを2からxの手前まで変化させながら繰り返し，
もしxがiで割り切れるならsosu←偽。
ここまで繰り返し。
もしsosuが真ならxを出力する。
ここまで繰り返し。
第２章
第３節 情報のあらわし方と処理手順の工夫
JavaScriptによるプログラムの例
<script>
n = parseFloat(prompt('いくつ未満の素数を計算しますか'));
for(x = 2; x < n; ++x) {
「偽」をあらわす
「真」をあらわす
特別な値である。
sosu = true;
２つずつ変化させるには，
++x
for(i = 2; i < x; ++i) {
のかわりに，
x = x + 2
if(x % i == 0){ sosu = false; }
とすればよい。
}
「○の手前まで」の条件を
「○まで」とするには，
if(sosu){document.write(x + ' '); }
<
のかわりに，
}
<=
</script>
を使えばよい。
第２章
第３節 情報のあらわし方と処理手順の工夫
２ 情報のあらわし方の工夫
• 情報のあらわし方を工夫すると，アルゴリズ
ムを改良したり，プログラムを書きやすくでき
る。
第２章
第３節 情報のあらわし方と処理手順の工夫
データ構造
• データ構造
– 情報をあらわすために用いる構造。
– データ構造を工夫することで，はじめて可能になる
ようなアルゴリズムの工夫も多い。
第２章
第３節 情報のあらわし方と処理手順の工夫
エラトステネスのふるい
• ２からはじめて，配列を順にしらべていく。
• しるしのついていない箇所があれば，その番
号は素数であると判断する。
• 素数が見つかると，その番号の倍数の箇所に
すべてしるしをつける。
• 次の素数は，しるしのついていない次の数とし
て見つかる。
第２章
第３節 情報のあらわし方と処理手順の工夫
エラトステネスのふるい
０
１
２
３
４
５
６
７
８
９
１０
１１
１２
１３
１４
１５
１６
１７
１８
１９
２０
２１
２２
２３
２４
２５
２６
２７
２８
２９
３０
３１
３２
３３
３４
３５
３６
３７
３８
３９
４０
４１
４２
４３
４４
４５
４６
４７
４８
４９
５０
５１
５２
５３
５４
５５
５６
５７
５８
５９
６０
６１
６２
６３
６４
６５
６６
６７
６８
６９
２は，しるしがついていないので素数とわかる。
まず，２からはじめる。
・・・しるしのついていない数が，素数である。
次は，17。
次は，13。
次は，11。
次は，７。
次は，５。
３の倍数すべてに，しるしをつける。
３は素数であるとわかる。
次の，しるしがついていない数は３。
２の倍数すべてに，しるしをつける。
第２章
第３節 情報のあらわし方と処理手順の工夫
エラトステネスのふるい
数nを読みこむ。
a←要素数がn個の配列。
変数xを2からnの手前まで変化させながら繰り返し，
もしa[x]にしるしがついていないなら
xを出力する。
変数iをxからnの手前までxずつ変化させながら繰り返し，
a[i]にしるしをつける。
ここまで繰り返し。
枝分かれ終わり。
ここまで繰り返し。
第２章
第３節 情報のあらわし方と処理手順の工夫
JavaScriptによるプログラムの例
<script>
a = parseFloat(prompt('いくつ未満の素数を計算しますか'));
a = new Array(n);
for(x = 2; x < n; ++x) {
if(a[x] == null) {
配列をつくる。
配列のすべての要素にはｎｕｌｌ（なに
もはいっていないことをあらわす特
別な値）がはいった状態になる。
document.write(x + ' ');
for(i = x; i < n; i = i + x) {a[i] = 1; }
}
}
</script>
© Copyright 2024 ExpyDoc
