座学 補助資料(text01_z.pdf,1281KB)

分類
Z
3
新教科「情報」現職教員等講習会
補助テキスト
アルゴリズムの基礎
座学1
補助テキスト作成者
北海道札幌稲北高等学校
早苗
雅史
主
催
文部省、北海道教育委員会
会
場
北海道立教育研究所附属情報処理教育センター
期
間
平成 13 年 7 月 25 日(水)∼8 月 10 日(金)
1 目的・ねらい
教科「情報」講習会テキスト
アルゴリズムの基礎
2001.7∼8
1_1 アルゴリズムの基本的考え
1_2 「情報」における目的
1_3 講座の内容
札幌稲北高校 早苗 雅史
URL www.nikonet.or.jp/spring/sanae/text/text01/text01.swf
@[email protected];2001.6.4
1_1 アルゴリズムの基本的考え
・アルゴリズム
問題を解決するための処理手順
・アルゴリズムの基本的な要素
効率と分かりやすさ
1_3 講座の内容
(1) アルゴリズムの概念と
流れ図での表現
(2) 基本的なアルゴリズム
・集計,最大値・最小値
・整列
・探索
1_2 「情報」における目的
・普通教科「情報」
基本的なアルゴリズムの学習を
通してその重要性を理解
・専門教科「情報」
アルゴリズム,データ構造に
関する知識・技術の習得と活用
する能力・態度の育成
2 学習指導要領における取り扱い
−普通教科「情報」
2_1 学習指導要領における位置
2_2 内容の取り扱い
2_3 「コンピュータにおける
情報の処理」の理解
(3) 簡単なプログラミング
2_1 学習指導要領における位置
「情報B」
(2)コンピュータの仕組みと働き
イ コンピュータにおける情報の処理
コンピュータの仕組み,
コンピュータ内部での基本的な
処理の仕組み及び簡単な
アルゴリズムを理解させる。
2_2 内容の取り扱い
・図を利用した説明などによる
基本的な考え方の理解
・1つ1つの命題がステップで
動くことの理解
・並べ変えや探索などの基本的なもの
2_3 コンピュータにおける情報処理
・入力・出力,記憶,演算,
制御機能の役割の理解
・処理手順を明確に記述する
ことの必要性
・並べ替えや探索などの基本的な実習
・表計算ソフトの表機能の活用など
3_1 アルゴリズムの定義
3 アルゴリズムの基礎
3_1 アルゴリズムの定義
3_2 アルゴリズムは一通りではない
3_3 アルゴリズムの評価
3_4 よいプログラムの要件
3_5 構造化定理
3_6 3つの制御構造
3_7 順次構造
3_8 繰返し構造
3_9 選択構造
3_2 アルゴリズムは一通りではない
明確に定義された有限個の規則の
集まりであって,
有限回適用することにより問題を
解くもの (JIS)
2の4倍は?
2足す
2
+2
2+
+2
2
×
4
2足す
2足す
2足す
結果は8
3_3 アルゴリズムの評価
3_4 よいプログラムの要件
よいプログラムの要件
高品質
わかりやすさ
効率がよいアルゴリズム
正確でわかり
やすい
複雑
わかりずらい
違う答えに
なってしまう
3_5 構造化定理
1つの入り口と1つの出口を持つように
プログラムが設計されていれば,
3つの制御構造の組合せによって,
どんなプログラム論理(ロジック)も
記述できる
高品質なプログラムは
アルゴリズムに支えられている
3_6 3つの制御構造
入
口
・順次構造
・繰返し構造
・選択構造
プログラム
順
次
繰
返
し
出
口
選
択
3_7 順次構造
3_8 繰返し構造
繰返し構造
処理1
1つの処理が終了したら
次の処理に進むと
いうように順に
処理していく論理構造
ある条件を満たすまで
処理を繰返し実行し
条件を満たしたら
次の処理に進む論理構造
処理2
ループ
条件
処理
ループ
条件
処理3
3_9 選択構造
4 アルゴリズムの表現
ある条件によって
2つの処理のどちらを
選択して実行する
といった論理構造
YES
条件
処理1
NO
処理2
4_1 流れ図(フローチャート)
4_1 流れ図(フローチャート)
4_2 フローチャート記号(JISX0121)
4_3 流れ図記述例 順次構造
4_4 流れ図記述例 繰返し構造①
4_5 流れ図記述例 繰返し構造②
4_6 流れ図記述例 選択構造①
4_7 流れ図記述例 選択構造②
4_8 構造化チャート
4_9 NSチャート
4_10 SPD
4_2 フローチャート記号(JISX0121)
問題の定義,分析,または解法の
図的表現であって,
演算,データ,流れ,装置などを
表現するために記号を用いたもの
12→A
34→B
A×B→S
判 断
準 備
ループ端
START
0→W
ループ
Kは1から始まり
1ずつ増加し10まで
W+K→W
ループ
S
W
END
処 理
定義済み
処理
1から10までの和を表示する
FOR型
LET A=12
LET B=34
LET S=A*B
PRINT S
END
端 子
4_4 流れ図記述例 繰返し構造①
縦の長さが12,横の長さが34の長方形の面積を
計算する
START
入出力
手操作
入力
表 示
同じ記述ルールを用いることで
他の人のアルゴリズムを理解でき
それが利用できるようになる
4_3 流れ図記述例 順次構造
流れ線
END
W=0
FOR K=1 to 10
W=W+K
NEXT K
PRINT W
END
4_5 流れ図記述例 繰返し構造②
正の数を入力して,3倍した数字を表示する.
ただし,負の数を入力したら終了させる.
WHILE型
START
DO
ループ
W+K→W
ループ
X≧0のあいだ
繰返す
4_6 流れ図記述例 選択構造①
1つの数値xを入力してその値が1なら「正解」
そうでないならば「エラー」と表示する
二分岐選択
START
INPUT X
PRINT 3*X
LOOP WHILE X>=0
END
X
X=1
YES
INPUT X
If X = 1 THEN
PRINT "正解"
ELSE
PRINT "エラー"
END IF
END
NO
正解
エラー
W
END
END
4_7 流れ図記述例 選択構造②
1つの値を入力して,その値が
1のときは「合格確実」 2のときは「努力せよ」
それ以外のときは「逆転をめざせ」
と表示する
多分岐選択
START
X
INPUT X
SELECT CASE X
CASE 1
PRINT "合格確実"
それ以外
CASE 2
エラー
PRINT "努力せよ"
CASE ELSE
PRINT "逆転をめざせ"
END SELECT
END
X
1
正解
2
正解
END
4_9 NSチャート
WHILE条件
条件
真
偽
処理1
矢線(GOTO文)を多用すると
複雑になり非構造的になる
⇒矢線を用いないアルゴリズムの表現
・NS (Nassi-Shneiderman chart)
・SPD (Structured Programing Diagrams)
・PAD (Problem Analysis Diagrams)
・HCP (Hierarchical and Compact
description chart)
・YACⅡ (Yet Another Control chart Ⅱ)
4_10 SPD
繰返し構造
(Do While)
選択構造
4_8 構造化チャート
処理
選択構造
(IF:条件)
THEN
処理2
ELSE
5 データ構造の基礎
5_1
5_2
5_3
5_4
5_5
5_6
基本的なデータ構造
データ構造の分類
単純型
ポインタ型
配列型
レコード型
繰返し構造
(Do While)
処理1
(WHILE:条件)
処理
処理2
5_1 基本的なデータ構造
データ型
コンピュータが扱うことができるデータで
同じ性質を持つデータの集合
データ構造
データ型をコンピュータで扱うことが
できる型にしたもの
5_2 データ構造の分類
5_3 単純型
単純型
基本データ型
基本データ
構造
ポインタ型
レコード型
構造型
最も基本的なデータ型で
ほとんどのプログラム言語で定義されている
配列型
データ構造
整数型
3.14,-2.03
論理型
文字型
木構造
問題向き
データ構造
実数型
1,2
リスト構造
abc,アイウ
スタック構造
true,false
列挙型
SUN,MON,TUE
キュー構造
5_4 ポインタ型
5_5 配列型
変数,ファイルのレコード,オブジェクトなどの
データを参照するためそれぞれのデータがどこに
あるのかという情報(記憶装置上のアドレス)を
示す値を持つデータ型
ポインタ型変数
同じデータ型の要素から構成される1次元,
あるいは多次元の並びを持つデータ型
変数X
変数Xの番地
データ値
主記憶装置での番地(アドレス)で示す
5_6 レコード型
A(1,1)
A(1,2)
A(1,3)
A(1,4)
A(2,1)
A(2,2)
A(2,3)
A(2,4)
A(3,1)
A(3,2)
A(3,3)
A(3,4)
6 基本的なアルゴリム
6_1 集計処理① 合計
6_2 集計処理② 最大値・最小値
6_3 整列のアルゴリズム
6_4 整列① 交換法
6_5 整列① 交換法の流れ図
6_6 整列② 選択法
6_7 整列② 選択法の流れ図
6_8 整列③ 挿入法
6_9 整列③ 挿入法の流れ図
6_10 探索のアルゴリズム
6_11 探索① 線形探索
6_12 探索① 線形探索の流れ図(1)
6_13 探索① 線形探索の流れ図(2)
6_14 探索② 二分探索
6_15 探索② 二分探索の流れ図
複数のデータがある規則で並んだものを
レコードといい,レコードの集まった
データ構造
レコードを構成する各項目をフィールド
101
商品A
200
25
102
商品B
250
30
103
商品C
430
30
103
商品D
180
40
6_1 集計処理① 合計
6_2 集計処理② 最大値・最小値
5つのデータを入力して合計を求め表示する
START
0→S
ループ
Nは1から始まり
1ずつ増加し5まで
X
S+X→S
S
ループ
END
S=0
FOR N=1 TO 5
INPUT X
S=S+X
NEXT
PRINT S
END
5つのデータを入力して最大値を求め表示する
START
0→MAX
ループ
Nは1から始まり
1ずつ増加し5まで
X
X>MAX
YES
X→MAX
ループ
S
END
NO
MAX=0
FOR N=1 TO 5
INPUT X
IF X>MAX THEN
LET MAX=X
END IF
NEXT N
PRINT MAX
END
6_3 整列のアルゴリズム
6_4 整列① 交換法
・ある順番にデータを並べ替えることを
整列(ソート)
24 17 16 31 18 入れ替え
16 17 18 24 31
17 24 16 31 18 入れ替え
16 17 18 24 31
17 16 24 31 18
16 17 18 24 31
17 16 24 31 18 入れ替え
・小さい順に並べることを昇順
大きい順に並べることを降順
17 16 24 18 31 確定
・交換法(バブルソート),選択法
挿入法,シェルソート
クイックソート
17 16 24 18 31 入れ替え
START
a(J)>a(J+1)
データ決定
ループ1
Iは4から始まり
1ずつ減少し1まで
ループ2
Jは1から始まり
1ずつ増加しIまで
NO
YES
入替え
ループ1
END
=
=
=
=
=
24
17
16
31
18
6_7 整列② 選択法の流れ図
START
データ決定
ループ1
Iは1から始まり
1ずつ増加し4まで
ループ2
I→min
ループ2
JはI+1から始まり
1ずつ増加し5まで
a(min)>a(J)
NO
YES
J→min
I≠min
入替え
ループ1
END
DIM a(5)
LET a(1) = 24
LET a(2) = 17
LET a(3) = 16
LET a(4) = 31
LET a(5) = 18
FOR I = 1 To 4
LET min=I
FOR J = I+1 TO 5
IF a(min) > a(J) THEN
min=J
ENDIF
NEXT J
IF I < > min THEN
dumy = a(I)
a(I) = a(min)
a(min) = dumy
END IF
NEXT I
END
6_9 整列③ 挿入法の流れ図
START
データ決定
ループ1
Iは2から始まり
1ずつ増加し5まで
ループ2
JはIから始まり
1ずつ減少し2まで
a(J-1)>a(J)
YES
入替え
ループ2
ループ1
END
NO
確定
16 17 18 24 31
確定
確定
6_6 整列② 選択法
For I = 4 To 1 Step -1
For J = 1 To I
If a(J) > a(J + 1) Then
dumy = a(J)
a(J) = a(J + 1)
a(J + 1) = dumy
END IF
NEXT J
NEXT I
END
ループ2
16 17 18 24 31
16 17 24 18 31 入れ替え
初期値 MIN=1
DIM a(5)
LET a(1)
LET a(2)
LET a(3)
LET a(4)
LET a(5)
16 17 18 24 31
16 17 24 18 31
16 17 18 24 31
6_5 整列① 交換法の流れ図
確定
DIM a(5)
LET a(1) = 24
LET a(2) = 17
LET a(3) = 16
LET a(4) = 31
LET a(5) = 18
FOR I = 2 To 5
FOR J = I To 2 STEP -1
IF a(J - 1) > a(J) THEN
dumy = a(J - 1)
a(J - 1) = a(J)
a(J) = dumy
ELSE
EXIT FOR
END IF
NEXT J
NEXT I
END
24 17 16 31 18 MIN=2
16 17 24 31 18 MIN=3
24 17 16 31 18 MIN=3
16 17 24 31 18
24 17 16 31 18
16 17 18 31 24 確定
入替え
24 17 16 31 18
入替え
16 17 24 31 18 確定
16 17 24 31 18 MIN=2
16 17 18 31 24
入替え
16 17 18 24 31 確定
16 17 18 24 31 確定
16 17 24 31 18
16 17 24 31 18
16 17 24 31 18 確定
6_8 整列③ 挿入法
24 17 16 31 18
入替え
16 17 24 31 18
17 24 16 31 18
確定
16 17 24 18 31
17 24 16 31 18
入替え
17 16 24 31 18
入替え
16 17 24 31 18
確定
入替え
16 17 18 24 31
16 17 18 24 31
確定
16 17 24 31 18
16 17 24 31 18
確定
6_10 探索のアルゴリズム
・配列,グラフ,リストなどのデータの
集まりから必要なデータを取り出す
ことを探索(サーチ)
・線形探索,二分探索,ハッシュ法
6_11 探索① 線形探索
6_12 探索① 線形探索の流れ図(1)
15個のデータから番号14のデータを探す
START
例外処理
逐次法
1
11
沢田 聖子
2
12
歌田 光
A
3
13
畠中みゆき
4
14
ループ
Iは1から始まり
1ずつ増加し15まで
14
34
林 寛子
・
・
・
野口 次郎
15
35
山元 昌広
データ決定
A=a(I)
YES
I>15
YES
NO
a(I);b(I)
NO
データなし
ループ
END
6_13 探索① 線形探索の流れ図(2)
6_14 探索② 二分探索
整列された15個のデータから番号13のデータを探す
例外処理
フラグを
たてる
START
A=a(I)
NO
YES
データ決定
True→check
False→check
a(I);b(I)
A
ループ
Iは1から始まり
1ずつ増加し15まで
ループ
check=False
NO
YES
データなし
END
6_15 探索② 二分探索の流れ図
START
データ決定
0→L
16→H
<
M→L
X
ループ
H=L+1まで
(L+H)/2→M
X:a(M)
11
沢田 聖子
11
沢田 聖子
11
沢田 聖子
2
12
歌田 光
12
歌田 光
12
歌田 光
3
13
畠中みゆき
13
畠中みゆき
13
畠中みゆき
13
畠中みゆき
4
14
林 寛子
14
林 寛子
14
林 寛子
14
林 寛子
5
15
武 雄高
15
武 雄高
6
21
小林 亜月
21
小林 亜月
7
22
鈴木 一郎
22
鈴木 一郎
8
23
星野 千ニ
23
星野 千ニ
9
24
川上 鉄伸
10
25
中根 郁子
11
31
鈴木 千鶴
12
32
松下 政治
13
33
福留 次郎
14
15
34
野口 次郎
35
山元 昌広
下限
中央値
上限
7 プログラミング言語
=
7_1
7_2
7_3
7_4
7_5
>
M→H
ループ
H=L+1
1
プログラムとは
プログラム作成の手順
プログラミング支援ツール
使用する言語の選択
考えられる言語例
NO
YES
データなし
a(I);b(I)
END
7_1 プログラムとは
・コンピュータに与える命令の集まり
・プログラムを作成することを
プログラミング
7_2 プログラム作成の手順
1.問題の明確化
2.入力データの出力結果の明確化
3.処理手順の表現
(フローチャートの作成)
4.処理手順にそったプログラムの作成
5.プログラムの修正
7_3 プログラミング支援ツール
7_4 使用する言語の選択
第1世代言語…機械語
プログラム
言語
言語処理
プログラム
第2世代言語…アセンブラ語
第3世代言語…COBOL,Fortran
PL/I,C,BASIC など
第4世代言語…SQL など
コンパイラ
・生徒の実態や興味・関心に応じて
・各学校の実情(購入費用など)
に応じて
インタプリタ
テキストエディタ
エディタ
構造化エディタ
7_5 考えられる言語例
・表計算ソフトのマクロ作成支援
Excel VBA
・Windows上で動くBASIC
10BASIC
・ブラウザ上で動く言語
Java Script
・その他
Visual Basic,C
LISP,Delphi,Java Applet
8_1 表計算ソフト「Excel」
8 Excel VBA
8_1
8_2
8_3
8_4
8_5
表計算ソフト「Excel」
VBA(Visual Basic for Applications)
VBAプログラミングの流れ
コードの実行をトレース(追跡)
VBAにおけるデバッグ機能
8_2 VBA(Visual Basic for Applications)
・ワークシート,セル
・集計処理,グラフ作成
シミュレーション
・関数の利用,データベース
・マクロの命令を記述するための言語
・マクロ
Excel上で行う様々な処理を
自動的に実行するプログラム
・プログラミング言語
Visual Basic が基本
8_3 VBAプログラミングの流れ
1.[ツール(T)]-[マクロ(M)]
-[Visual Basic Editor(V) Alt+F11]
2.[挿入(I)]-[標準モジュール(M)]
3.コードウインドウへプロシージャー名を記述
(sub+プロシージャー名)
4.コードの記述
5.プロシージャーの実行
6.プロシージャーの中の任意の位置にカーソルを
置いて[実行(R)]-[Sub/ユーザーフォームの実行 F5]
7.実行結果の表示
LINK
☆ VBAプログラミングの流れ ☆
・Microsoft Office の
アプリケーション共通で利用
8_4 コードの実行をトレース(追跡)
・デバッグ機能
・アプリケーションエラーを見つけ,訂正
・項目や変数の値の監視
・1 行ずつの実行,ブレークポイント
の設定,実行停止
・コードが設計どおりに機能しているか
どうかを検査
8_5 VBAにおけるデバッグ機能
1.[表示(V)]−[ローカルウインドウ(S)]
2.プロシージャーの中の任意の位置に
カーソルを置いて
[デバッグ(D)]−[ステップ イン F8]
9 JIS Full BASIC
9_1
9_2
9_3
9_4
9_5
JIS Full BASIC
(仮称)十進BASIC
どこから手に入れるのか
10Basicプログラミングの流れ
10Basicにおけるデバッグ機能
3.[F8]キー(ステップイン)で変数の値が変化
LINK
☆ ローカルウインドウでのデバッグ ☆
9_1 JIS Full BASIC
9_2 (仮称)十進BASIC
・BASIC言語の新しい日本工業規格(JIS)
・JIS Full BASIC にそったBASIC言語
・数値演算の正確さに関する厳格な規定
・独自の拡張として複素数や有理数の
計算を行うモード
・論理的な構造を明確に表現する
ための文法
・グラフィックスに関する規定
9_3 どこから手に入れるのか
・動作環境
Windows95/98/NT4.0
・ファイルサイズ 854KB (2000年4月22日,ver. 4.53)
9_4 10Basicプログラミングの流れ
・著作者 文教大学教育学部 白石和夫
1.BASICを起動 ⇒ エディタ画面
・「(仮称)十進BASICのホームページ」
http://hp.vector.co.jp/authors/VA008683/
2.コードの記述
3.プログラムの実行[実行(R)]
−[実行(R) F9]
⇒ 出力結果表示ウィンドウ
LINK
9_5 10Basicにおけるデバッグ機能
1.BASICを起動 ⇒ エディタ画面
2.コードの記述
3.プログラムの実行[実行(R)]
−[ステップ実行(S) F10]
⇒ デバッグウィンドウ
4.ステップを選択してOKボタン
⇒ 1ステップづつ実行
LINK
☆ デバッグ機能 ☆
☆ 10Basicプログラミングの流れ ☆
10 Java Script
10_1
10_2
10_3
10_4
Java
Java
Java
Java
Scriptとは
Script の特徴
Script の欠点
Script プログラミングの流れ
10_1 Java Scriptとは
・スクリプト言語(短いプログラム)
Netscape社が開発
10_2 Java Script の特徴
・Webブラウザ上で動作
・OSを選ばない(Java VM上で動作)
・システム管理を簡単に
・JavaAppletとは別物
10_3 Java Script の欠点
・JavaScriptをサポートしていない
ブラウザでは動かない
・NNやIEのバージョンによってかなり
動作が異なる
・バグが多い
11 指導上の留意点
11_1
11_2
11_3
11_4
11_5
11_6
基本的なおさえ
流れ図について
集計処理について
整列と探索
トレース
使用する言語
11_2 流れ図について
・クライアント側で動作
(cgi→サーバ側)
10_4 Java Script プログラミングの流れ
1.エディタの起動 ⇒ エディタ画面
2.基本になるタグの記述
3.コードの記述
4.[ファイル(F)]−[名前をつけて保存(A)]
(拡張子 *.htm)
5.ブラウザの起動 −[ファイル(F)]
−[開く(O) Ctrl+O] ⇒ ファイルを開く
6.コードの訂正 エディタに切り替え
−[ファイル(F)]−[上書き保存(S)]
7.ブラウザに切り替え
−[表示(V)]−[最新の情報に更新(R) F5]
LINK
☆ Java Script プログラミングの流れ ☆
11_1 基本的なおさえ
・普通教科「情報」
・・・高度な内容に深入りしない
・専門教科「情報」
・・・基本的な知識の習得
+活用する能力・態度の育成
11_3 集計処理について
・「情報」を学ぶ上での基本
・身近な例で解説
・構造化定理は確実に指導
・頭の中で処理している考え方との比較
・配列についての考え方の理解
11_4 整列と探索
11_5 トレース
・基本事項として確実に指導
・変数の値の観察
・整列は「交換法」を指導
・正確なアルゴリズムの構築
・探索は「線形探索」を指導
12_1 演習①
12 演習
12_1 演習①
12_2 演習②
12_3 作業用フォルダ・ファイルの作成
12_2 演習②
(2) VBAを用いた集計処理(40分)
Visual Basic Editor で作成
(ex_1.xlsをダウンロード)
12_3 作業用フォルダ・ファイルの作成
(3) VBAを用いた整列(40分)
Visual Basic Editor で作成
(ex_2.xls)
(4) VBAを用いた探索(40分)
Visual Basic Editor で作成
(ex_3.xls(14Kb)をダウンロード)
13 テキストのURL
13_1
13_2
13_3
(1) フローチャートの作成(40分)
指定用紙へ記入
テキストのページ名
関連ページ
テキストのURL
・フォルダ Kensyuu(K:)¥K** (**にログインするときの番号)
・ファイル
ex_1.xls(Sub ex_1())
ex_2.xls(Sub ex_2_1(),Sub ex_2_1())
ex_3.xls(Sub ex_3())
13_1 テキストのページ名
・教科「情報」講習会テキスト
アルゴリズムの基礎
・これだけで大丈夫
「情報」におけるプログラミング
フローチャート 編
・これだけで大丈夫
「情報」におけるプログラミング
Excel VBA 編
13_2 関連ページ
・これだけで大丈夫
「情報」におけるプログラミング
JIS Full BASIC 編
・これだけで大丈夫
「情報」におけるプログラミング
Java Script 編
13_3 テキストのURL
「数学とソフトウエア M.Sanae'S HomePage」
http://www.nikonet.or.jp/spring/sanae/