再帰呼び出しと再帰方程式
再帰関数と再帰方程式 再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。 // 階乗 (末尾再帰) int f […]
授業アンケート結果(ぷちブルーな気分)
情報ネットワーク基礎(3EI/後期) 楽しんで受講してくれた人からの意見があり、ポイントでも85ポイントと高評価であった。内容理解やシラバスについてポイントが若干低いようであるが、誤差の範疇と思われる。理解把握のポイント […]
処理時間のオーダー(回答編)
2分探索法の処理時間の見積もり コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。 データ10000件なら何[sec]かかるか？ 解答 2分探索法なので、処理時間はO(logN) であり、T(N […]
ループ処理時間とオーダー記法と再帰
先週に、単純繰り返し処理の時間分析をやったので、次のステップに。 2分探索法の処理時間 データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。 // 2分探索法 O(log N) […]
2019年度情報構造論ガイダンス
情報構造論のガイダンス プログラムを評価する3つのポイント この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。 プログラムの速度 […]
情報構造論2018-講義録
情報構造論ガイダンス 繰り返し処理とオーダ記法 再帰処理の処理時間 マージソートのオーダー メモリを効率よく使うには mallocとfree 様々なメモリ確保 前期中間テストの答案返却 リスト構造について リスト構造での […]
オブジェクト指向と演習
データ構造を扱うプログラムの書き方を説明してきたので、それらを便利に書くためのオブジェクト指向の入り口を紹介する。 データ指向のプログラム記述 名前と年齢のデータを扱うプログラムを書く時、私なら以下のようなプログラムを作 […]
動的メモリ確保(malloc()とfreelist)
C言語では、動的メモリ領域をどのように管理していくのか解説する。 局所変数とスタック 局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。 関数の中で関数が呼び出 […]
参照カウンタ法とガベージコレクタ
共有のあるデータの取扱の問題 リスト構造で集合計算おこなう場合の和集合を求める処理を考える。 struct List* join( struct List* a , struct List* b ) { struct L […]
ハッシュ法(チェイン法)
前回説明のハッシュ法(オープンアドレス法)は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。 チェイン法 チェイン法は、 […]