情報技術

情報技術
～アルゴリズム演習～
2015年6月25日
笠井俊信
新しいデータ型
• 今までのデータ型
– 変数を1つを宣言
• 今日の新しいデータ型「配列」
– A[N] ・・・Aという配列名で複数の変数を格納
N・・・添字：何番目のデータかを指定
– 配列の参照の仕方（）
• 0番目のデータ → A[0]
• N番目のデータ → A[N]
1
演習問題３
問題：
整数データを１０個入力していき，合計と平均
（整数値）を求めて表示する手順を示せ．
• 合計（SUM）に0を代入する
• 繰り返し制御の変数（I）に0を代入
• （繰り返し）Iの値が１０未満である限り繰り返す
– 数値（DAT）を入力する
– SUMにDAT+SUMを代入
– IにI+1を代入
• 合計値（SUM）を出力
• 平均値（SUM/10）を出力 10個のデータを配列に
格納するアルゴリズムにすると
演習問題３
問題：
整数データを１０個入力していき，合計と平均
（整数値）を求めて表示する手順を示せ．
• 合計（SUM）に0を代入する
• 繰り返し制御の変数（I）に0を代入
• （繰り返し）Iの値が１０未満である限り繰り返す
– 数値（DAT[I]）を入力する
– SUMにDAT[I]+SUMを代入
– IにI+1を代入
• 合計値（SUM）を出力
• 平均値（SUM/10）を出力
2
1000以下の素数をすべて求める
• もっとも単純な方法
– 2から1000までの整数 i を対象とする
– 2から i-1 までの数で割り切れるか？
• 割り切れる数が見つかれば素数ではない
データ構造（方法の1つ）
配列 num[0] ～ num[1000]
3
もっとも単純な方法のアルゴリズム
• 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を出力（素数）
結果の出力
1000以下の素数をすべて求める
• もっとも単純な方法
– 2から1000までの整数 i を対象とする
– 2から i-1 までの数で割り切れるか？
• 割り切れる数が見つかれば素数ではない
• 少し工夫した方法
– 2から1000までの整数 i を対象とする
• 奇数のみ対象とする
– 2から i の平方根までの数で割り切れるか？
• 割り切れる数が見つかれば素数ではない
4
もっとも単純な方法のアルゴリズム
• i（調べる対象）が3～Nまで繰り返す
– ｊ（約数を探す）を2～i-1まで繰り返す
• （条件分岐） i ÷ j の余りが0？
– Yesなら，num[i] = 0
約数が見つかったので j の繰り返しから抜ける
• j を1増やす
– i を1増やす
少し工夫した方法のアルゴリズム
• i（調べる対象）が3～Nまで繰り返す
– ｊ（約数を探す）を2～ iの平方根まで繰り返す
• （条件分岐）i ÷2の余りが0？
– Yesなら，偶数なので何もしない
– Noなら，（条件分岐）i ÷ j の余りが0？
» Yesなら，num[i] = 0
約数が見つかったので j の繰り返しから抜ける
• j を1増やす
– i を1増やす
5

Download Report