15回目へジャンプ
各回のポイント一言 (2024)
| 話題、キーワード | 例題、演習 | ポイント | 配布資料、教科書 | |
|---|---|---|---|---|
| （1） 9/27 |
Cプログラミング ウォーミングアップ１ いじわるな問題 (MaNaBoクイズ） |
例題集 へ (アルゴリズム１） 2つの課題問題 (ページ中盤 課題 0101 課題0102) |
プログラムスタイル と 読み | １章 pp.1-6を確認 資料1. .アルゴリズム、フローチャート、疑似言語 |
| （２） 10/4 |
ウォーミングアップ2 例題集 0102の フローチャート （二分岐型（双岐）選択 |
0103 (二重ループ) 0104 複数の解法を意識 nが大きくなると、実行時間が、どのように増加するかを考えてみよう) |
プログラムにコメント やってみよう
|
資料2 (表）アルゴリズムの定義 （裏） 時間計算量、実行回数とO記法の「ざっと入門」編 1章 pp. 7-14を準備 |
| (3) 10/11 |
アルゴリズム） 配列操作 |
STEP1.0 （配列中の最大値) (教科書p6 例1.1) 解答例 (ツールから) 要素数nが大きくなると、実行時間はどのように増加するかを考えること 1桁の乱数 (1〜9) N個の 配列中に STEP1.1 (7があるとき、ある) 解答例 STEP1.2 (なければ、ない) 解答例 STEP1.3 （あれば、個数も) 解答例 |
<
|
イメージとコードの 対応付け ツール (2018) |
| (4) 10/18 |
探索（検索） 線形探索 レポートに注意！ |
STEP 2 （キーxが、配列sの要素にあるか。あれば、添え字を. まずは、素直に探そう) 解答例 STEP2.1 (p.73) (線形探索; 上から探索) (パーツ分解；関数) 解答例 コーディング過程例 少しずつコーディングする例 (2018) |
探索の準備と他の話題を
|
3．線形探索 breakは、例題0302 関数は、例題0と8 4章71-73 |
| (5） 10/25 |
二分探索 |
STEP2.2 (p.75) （二分探索；半分ずつ範囲を。 古い教科書の回答はそのままでは課題の解答になりません。課題中のデータは整列済です） 解答例 STEP2.2 python解答例 STEP2.3 ハッシュ法 STEP2.4 (ファイル中の整列化データを線形探索） STEP2.5 （ファイル中の整列化データを二分探索） |
STEP2.2
|
4．二分探索 STEP2.3の実装は自習 STEP2.4 STEP2.5 は、使ってください。 |
| (6) 11/1 |
ハッシュ法 （STEP 2.3) 文字列照合 イントロ |
STEP3.1 (テキストとパターン 素朴な方法) |
文字列の定番処理 k=0; while(s[k] != '\0') { 各文字の処理; k++; } 例題集では、5 |
4. （裏） まとめ、ハッシュ法 O (1) |
| 11/3 | 学校祭です！ | |||
| (7) 11/8 |
kmp法のエッセンス kmp法 失敗関数のなぞり |
STEP3.1A （素朴な方法の解答、教科書との対応） STEP3.1AA （別解の例） STEP3.1 python解答例 (以下、付録） STEP3.1B （入力方法変更） STEP3.1C (文字列操作の組み込み、標準関数の利用。p.101脚注にある比較終了条件) STEP3.1D (配列とポインターによるもの） |
|
5. kmp法演習 |
| (8) 11/15 |
(簡略)bm法 スキップ関数のなぞり |
以下、2つの問題はオプション STEP3.2 (kmp法) (解答例) STEP3.3 (簡略bm法) (解答例) (別の例) 課題の〆切は2023年12月3日 |
|
6. bm法演習 |
| (9) 11/22 |
再帰 Part 1 (基本編） |
基本例題 STEP4.1a (階乗、非再帰） クイズ編(2013) 解答 STEP4.1b （階乗、再帰） クイズ編(2013) 解答 演習問題 STEP4.2 (よくわかるC p.51 解答) STEP4.3 （数式表現を読む） （作る） 解答 STEP4.4 (実行過程) STEP4.5 (より面倒な数式表現) 解答 定番の例題 フィボナッチ数列 (解答は例題集 9 ) STEP4.6 (STEP2.2 二分探索 再帰版) 解答 STEP4.6 Python解答例 |
階乗(再帰）を 写経 (2021) 1. 再帰的（定義、プログラム）
STEP4.3は、複雑な例 3. （資格試験にあるような）数式表現 問題例 4. 再帰の考え方で問題を見る。作る。 |
ループと再帰 実行イメージページ 再帰的なプログラミング |
| (10) 11/29 |
最大公約数 イントロ 解説 |
巧くない, 素朴法 STEP5.0 巧い方法 STEP5.1 (ループで; ガイド付き） （解答例) 実行 (2016) STEP5.2 （再帰で; ガイド付き） （解答例) 実行 (2016) 参考 python STEP5.3 （もう一つの方法） (資格問題例の実装） |
|
課題はパワーポイントで 確認のこと
|
| (11) 12/6 |
N以下素数列挙 イントロ MaNaBoで 競争の部屋 (STEP6.1 ②を 自分がやってみる) みんなの方法一覧 代表的な解法確認 （自分はどの方法なのかをMaNaBoに） |
STEP6.1 (自分の方法をプログラム) 3解答例比較(2016) STEP6.1a STEP6.1b STEP6.1c |
二重ループを 写経 ! 「iより前」、「iより後ろ」など iのループを固定して jの動きを考えよう |
|
| (12) 12/13 |
MaNaBoで 謎解きの部屋 (エラトステネスのふるいの確認） 歌 解説 (数学は自習） |
STEP6.2 （エラトステネス法の実装） 解答例 関数を用いた例 再帰的関数 |
なぞりのイメージから プログラムのイメージ 対応付けツール (2018) コーディング過程 (2018) |
実装と 計算量 （直観レベルでよい） 素因数分解と暗号、署名 (RSA暗号) プログラム |
| (13) 12/20 |
ソート イントロ MaNaBoで 謎解きの部屋 1. 自分がやってみる 2. ソートA Sort Aについて (まとめはMaNaBo) |
ソート STEP7 (全体のテンプレート) STEP7.1 （STEP7をうめよう） 解答 |
swapを 写経 STEP7 使用している配列は大域変数 （よくわかるC p.46) |
実装と 計算量分析 教科書：解説 pp. 33-38 |
| 2024 | よいお年を | |||
| 2025 | 飛躍の年に | |||
| (14) 1/10 |
MaNaBoで 謎解きの部屋 1. ソートB Sort Bについて (まとめはMaNaBo) |
STEP7 (全体のテンプレート) STEP7.2 (STEP7をうめよう) 解答1 解答2 |
|
実装と 計算量分析 教科書：解説 pp. 38-42 計算量は42ページ |
| ついに (15) 1/17 |
MaNaBoで SortC |
STEP7.3 (ソートC) 解答 教科書p.48の工夫と 実装 p.171は自習 |
|
アルゴリズム確認のあと 教科書：解説 pp.. 43-48 計算量は47ページ バケットソートは65ページ |
| 1/31 | 試験 13:00開始 12:50には着席、準備 座席指定です 13:20 入室不可 (判定F) 13:30 退室可 |
課題 (重視) ＋ 試験
|
||
| 春へ | 春は：
C言語による実装のためには
|
|||
| 2025年度 | アルゴリズム２ | 木曜日1時間目です | ２時間目も必修授業 | |
| 以下 予定です | ||||