2015/8/5 情報技術 ～アルゴリズム演習～ 2015年7月2日 笠井俊信 1000以下の素数をすべて求める • もっとも単純な方法 – 2から1000までの整数 i を対象とする – 2から i-1 までの数で割り切れるか？ • 割り切れる数が見つかれば素数ではない • 少し工夫した方法 – 2から1000までの整数 i を対象とする • 奇数のみ対象とする – 2から i の平方根までの数で割り切れるか？ • 割り切れる数が見つかれば素数ではない 1 2015/8/5 もっとも単純な方法のアルゴリズム • 1～Nまでの変数列（num[i]）を用意 • i（調べる対象）が0～Nまで繰り返す – num[i] = 1 配列の用意と初期化 • num[0] = 0, num[1] = 0 • i（調べる対象）が3～Nまで繰り返す – ｊ（約数を探す）を2～i-1まで繰り返す • （条件分岐） i ÷ j の余りが0？ – Yesなら，num[i] = 0 • j を1増やす 約数が見つかったので j の繰り返しから抜ける – i を1増やす • i（調べる対象）が1～Nまで繰り返す – （条件分岐）num[i] = 1? • Yesなら，iを出力（素数） 結果の出力 少し工夫した方法のアルゴリズム • i（調べる対象）が3～Nまで繰り返す – ｊ（約数を探す）を2～ iの平方根 まで繰り返す • （条件分岐）i ÷2の余りが0？ – Yesなら，偶数なので何もしない – Noなら，（条件分岐）i ÷ j の余りが0？ » Yesなら，num[i] = 0 約数が見つかったので j の繰り返しから抜ける • j を1増やす – i を1増やす 2 2015/8/5 素数を求める有名な解法 • エラトステネスのふるい – もっとも小さい素数2から順に，その倍数を削 除する。 – 1000の平方根まで調べる 解法の理解 エラトステネスのふるい 3 2015/8/5 解法の理解 エラトステネスのふるい 解法の理解 エラトステネスのふるい 4 2015/8/5 解法の理解 エラトステネスのふるい 解法の理解 エラトステネスのふるい 5 2015/8/5 解法の理解 エラトステネスのふるい 解法の理解 エラトステネスのふるい 6 2015/8/5 解法の理解 エラトステネスのふるい エラトステネスのふるい のアルゴリズム • i（倍数を排除する元）が2～Nの平方根ま で繰り返す – （条件分岐） num[i] = 0 ? • Yesなら，素数ではないので何もしない • Noなら，ｊ（i を何倍するか）をi～N/i まで繰り返す – num[i*j]=0 – jを1増やす – i を1増やす 7 2015/8/5 ソートアルゴリズム １．基本選択法 • 基本選択法とは？ – 数列の中から最大の数値を探すことを繰り返 し，大きい数字の位置から確定していく 5 3 9 6 9 3 5 6 9 6 5 3 8 2015/8/5 ソートのステップ 6 6 7 7 7 7 2 2 2 6 6 6 5 5 5 5 5 5 3 3 3 3 4 4 1 1 1 1 1 3 7 7 6 2 2 2 4 4 4 4 3 1 6 2 5 3 1 7 4 suu [0] [1] [2] [3] [4] [5] [6] i j p 0 0 1 3 4 1 7 7 7 7 0 5 5 6 6 i ・・・ 何番目に大きい数か j ・・・ どこまで数を調べたか p ・・・ 1番大きい数の場所 １．基本選択法のアルゴリズム （7個の数列のソート） • iを0から5まで繰り返す – 最大値の場所pにiを代入 – カウンタ２jにi+1を代入 – jをi+1から6まで繰り返す • （条件分岐）suu[p] < suu[j]? – Yesなら，pにjを代入 • jを1増やす – tempにsuu[i]を，suu[i]にsuu[p]を，suu[p]にtempを代入 – iを1増やす 6 2 5 3 1 7 4 suu [0] [1] [2] [3] [4] [5] [6] i ・・・ 何番目に大きい数か j ・・・ どこまで数を調べたか p ・・・ 1番大きい数の場所 9
© Copyright 2024 ExpyDoc
