ハノイの塔と再帰を使った並び替え
ハノイの塔
ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。
ハノイの塔は、3本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。
一般解の予想
ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。
… ①
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。
再帰方程式
上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、
… ②
… ③
ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想①が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、
枚では、
… ③より
… ①を代入
… ①の
の場合
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
これらのことから、ハノイの塔の処理時間は、で表せる。
再帰を用いた並び替え
データを並び替えるプログラムとして、繰り返し処理の分析では「選択法」について説明した。
選択法は、 のアルゴリズムで、あまり速い並び替え手法ではない。
アルゴリズム | 処理時間のオーダー | ||
---|---|---|---|
バブルソート | |||
選択ソート | |||
クイックソート, マージソート |
ここで、最も高速なアルゴリズムとしては、クイックソートが有名である。クイックソートプログラムは、処理時間のオーダはで表せる。
本当であれば、クイックソートのプログラムの処理時間の分析を説明したいけど、イメージがわかりにくいので、同じオーダ式であらわせるマージソートで説明を行う。
(マージソートのオーダは、クイックソートと同じだけど、計算途中のデータを一時的に覚える場所を確保する処理が必要で、その処理に手間がかかるため、効率はクイックソートに比べ遅くなる。)
import java.util.*; // マージソートは、リスト構造を使っているので、 // クイックソートより効率が悪い。 // でもオーダーとしては、O( N log N ) のアルゴリズム public class Main { public static LinkedList merge_sort( LinkedList list ) { // データ件数が1件ならソート不要 if ( list.size() <= 1 ) { return list; } // 左右2つに分割 int mid = list.size() / 2 ; LinkedList<Integer> left = new LinkedList<>( list.subList( 0 , mid ) ) ; LinkedList<Integer> right = new LinkedList<>( list.subList( mid , list.size() ) ) ; // 左右をそれぞれマージソート LinkedList<Integer> sorted_left = merge_sort( left ) ; LinkedList<Integer> sorted_right = merge_sort( right ) ; // 左右のリストをマージする。 LinkedList merged = new LinkedList<>() ; // 初期状態は空っぽ // 左右のリストの小さい方を取り出して答えに追加していく while( !sorted_left.isEmpty() && !sorted_right.isEmpty() ) { int left_top = sorted_left.get( 0 ) ; int right_top = sorted_right.get( 0 ) ; if ( left_top > right_top ) { merged.add( sorted_right.removeFirst() ) ; } else { merged.add( sorted_left.removeFirst() ) ; } } // 残ったリストを追加 while( !sorted_left.isEmpty() ) merged.add( sorted_left.removeFirst() ) ; while( !sorted_right.isEmpty() ) merged.add( sorted_right.removeFirst() ) ; return merged ; } public static void main( String[] args ) { // ソート対象のデータ LinkedList<Integer> data = new LinkedList<>() ; data.add( 38 ) ; data.add( 27 ) ; data.add( 43 ) ; data.add( 3 ) ; data.add( 9 ) ; data.add( 82 ) ; data.add( 10 ) ; System.out.println( "ソート前: " + data ) ; LinkedList<Integer> sorted_data = merge_sort( data ) ; System.out.println( "ソート後: " + sorted_data ) ; } }
- LinkedListを用いたマージソート(Paiza.io)
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。
:
よって、
選択法とクイックソートの処理時間の比較
データ数 N = 10 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。
複素数クラスによる演習
複素数クラスの例
隠蔽化と基本的なオブジェクト指向の練習課題として、前回の授業では、直交座標系による複素数クラスを示した。今回の授業では、演習を行うとともに直交座標系を極座標系にクラス内部を変更したことにより、隠蔽化の効果について考えてもらい、第1回レポートとする。
直交座標系
前回の授業で示した直交座標系のクラス。比較対象とするために再掲。
#include <stdio.h> #include <math.h> // 直交座標系の複素数クラス class Complex { private: double re ; // 実部 double im ; // 虚部 public: void print() { printf( "%lf + j%lf¥n" , re , im ) ; } Complex( double r , double i ) // 実部虚部のコンストラクタ : re( r ) , im( i ) {} Complex() // デフォルトコンストラクタ : re( 0.0 ) , im( 0.0 ) {} void add( Complex z ) { // 加算は、直交座標系だと極めてシンプル re = re + z.re ; im = im + z.im ; } void mul( Complex z ) { // 乗算は、直交座標系だと、ちょっと煩雑 double r = re * z.re - im * z.im ; double i = re * z.im + im * z.re ; re = r ; im = i ; } double get_re() { return re ; } double get_im() { return im ; } double get_abs() { // 絶対値 return sqrt( re*re + im*im ) ; } double get_arg() { // 偏角 return atan2( im , re ) ; } } ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね int main() { // 複素数を作る Complex a( 1.0 , 2.0 ) ; Complex b( 2.0 , 3.0 ) ; // 複素数の計算 a.print() ; a.add( b ) ; a.print() ; a.mul( b ) ; a.print() ; return 0 ; }
極座標系
上記の直交座標系の Complex クラスは、加減算の関数は単純だけど、乗除算の関数を書く時には面倒になってくる。この場合、極座標系でプログラムを書いたほうが判りやすいかもしれない。
// 局座標系の複素数クラス class Complex { private: double r ; // 絶対値 r double th ; // 偏角 θ public: void print() { printf( "%lf ∠ %lf¥n" , r , th / 3.14159265 * 180.0 ) ; } Complex() // デフォルトコンストラクタ : r( 0.0 ) , th( 0.0 ) {} // 表面的には、同じ使い方ができるように // 直交座標系でのコンストラクタ Complex( double x , double y ) { r = sqrt( x*x + y*y ) ; th = atan2( y , x ) ; // 象限を考慮したatan() } // 極座標系だと、わかりやすい処理 void mul( Complex z ) { // 極座標系での乗算は r = r * z.r ; // 絶対値の積 th = th + z.th ; // 偏角の和 } // 反対に、加算は面倒な処理になってしまう。 void add( Complex z ) { ; // 自分で考えて } // ゲッターメソッド double get_abs() { return r ; } double get_arg() { return th ; } double get_re() { // 直交座標系との互換性のためのゲッターメソッド return r * cos( th ) ; } double get_im() { return r * sin( th ) ; } } ; // ←しつこく繰り返すけど、セミコロン忘れないでね(^_^;
このように、プログラムを開発していると、当初は直交座標系でプログラムを記述していたが、途中で極座標系の方がプログラムが書きやすいという局面となるかもしれない。しかし、オブジェクト指向による隠蔽化を正しく行っていれば、利用者に影響なく「データ構造」や「その手続き(メソッド)」を書換えることも可能となる。
このように、プログラムをさらに良いものとなるべく書換えることは、オブジェクト指向ではリファクタリングと呼ぶ。
正しくクラスを作っていれば、クラス利用者への影響が最小にしながらリファクタリングが可能となる。
const 指定 (経験者向け解説)
C++ では、間違って値を書き換えるような処理を書けないようにするための、const 指定の機能がある。
void bar( char* s ) { // void bar( const char* s ) {...} printf( "%s\n" , s ) ; // で宣言すべき。 } void foo( const int x ) { // ~~~~~~~~~~~ x++ ; // 定数を書き換えることはできない。 printf( "%d\n" , x ) ; } int main() { const double pi = 3.141592 ; // C言語で #define PI 3.141592 と同等 bar( "This is a pen" ) ; // Warning: string constant to 'char*' の警告 int a = 123 ; foo( a ) ; return 0 ; }
前述の、getter メソッドの例では要素を参照するだけで、オブジェクトの中身が変化しない。逆に言えば、getter のメソッド内にはオブジェクトに副作用のある処理を書いてはいけない。こういった用途に、オブジェクトを変化させないメソッド宣言がある。先の、get_re() は、
class ... { : inline double get_re() const { // ~~~~~ re = 0 ; // 文法エラー return re ; } } ;
クラスオブジェクトを引数にする場合
前述の add() メソッドでは、”void add( Complex z ) { … }” にて宣言をしていた。しかし、引数となる変数 z の実体が巨大な場合、この書き方では値渡しになるため、データの複製の処理時間が問題となる場合がある。この場合は、(書き方1)のように、z の参照渡しにすることで、データ複製の時間を軽減する。また、この例では、引数 z の中身を間違って add() の中で変化させる処理を書いてしまうかもしれない。そこで、この事例では(書き方2)のように const 指定もすべきである。
// (書き方1) class Complex { : void add( Complex& z ) { re += z.re ; im += z.im ; } } ; // (書き方2) class Complex { : void add( const Complex& z ) { // ~~~~~~~~~~~~~~~~ re += z.re ; im += z.im ; } } ;
レポート1(複素数の加減乗除)
授業中に示した、直交座標系・極座標系の複素数のプログラムをベースに、記載されていない減算・除算のプログラムを作成し、レポートを作成する。 レポートには、下記のものを記載すること。
- プログラムリスト
- プログラムへの説明
- 動作確認の結果
- プログラムより理解できること。
- 実際にプログラムを書いてみて分かった問題点など…
JavaScriptによるフロントエンドとPHPバックエンド入門
前回の講義では、インターネットの仕組みを復習し、そこで使われるプログラミング言語などを紹介した。
今回の授業では、インターネットのブラウザ側(フロントエンド)で使われるプログラム言語である JavaScript の基本について整理しなおし、簡単な穴埋め問題による演習を行う。
JavaScriptによるフロントエンドプログラミング
-
- 以下のサンプル(sample3.html~sampleA.html)は、各HTMLファイルを開くとソースコードが表示されます。JavaScriptによるプログラムなので、自分のパソコンにダウンロードし、演習についてはダウンロードしたファイルを編集して、ブラウザで動作を確認してください。
- sample3.html
- sample4.html
- sample5.html
- sample6.html — 簡単な穴埋め問題
- sample7.html
- sample8.html
- sample9.html — 簡単な穴埋め問題
- sampleA.html
- sampleA.css
- 以下のサンプル(sampleB2.html~sampleC2.html)は、jquery が html ファイルと同じ場所に置いてある必要があり、ダウンロードしたファイルを開いてもこのままでは動きません。動作確認のページにて実行結果を確認してください。
- sampleB2.html 動作確認Webページ
- sampleC2.html 動作確認Webページ
- sampleC.json
- 無名関数の説明
- 練習問題 6 , 9 の提出先
- 2024/情報メディア工学(4/24)小テスト