再帰呼び出しと処理時間の見積もり
再帰呼び出しの基本
次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。
再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。
// 階乗 (末尾再帰)
int fact( int x ) {
if ( x <= 1 )
return 1 ;
else
return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
if ( x <= 1 )
return 1 ;
else
return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
if ( x <= 2 )
return 1 ;
else
return fib( x-1 ) + fib( x-2 ) ;
}
import java.util.*;
public class Main {
// 階乗(末尾再帰)
public static int fact( int x ) {
if ( x <= 1 )
return 1 ;
else
return x * fact( x - 1 ) ;
}
// ピラミッド体積(末尾再帰)
public static int pyra( int x ) {
if ( x <= 1 )
return 1 ;
else
return x * x + pyra( x - 1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
public static int fib( int x ) {
if ( x <= 2 )
return 1 ;
else
return fib( x - 1 ) + fib( x - 2 ) ;
}
public static void main(String[] args) throws Exception {
System.out.println( "fib(5)=" + fib( 5 ) ) ;
System.out.println( "pyra(5)=" + pyra( 5 ) ) ;
System.out.println( "fib(5)=" + fib( 5 ) ) ;
}
}
- 単純な再帰関数(Paiza.io)
階乗 fact(N) を求める処理は、以下の様に再帰が進む。
また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。
再帰呼び出しの処理時間
次に、この再帰処理の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=Ta で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(Tb)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 T(N)=Tb=T(N-1)で表せる。
} 再帰方程式
このような、式の定義自体を再帰を使って表した式は再帰方程式と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式 が得られる。
T(1)=Ta
T(2)=Tb+T(1)=Tb+Ta
T(3)=Tb+T(2)=2×Tb+Ta
:
T(N)=Tb+T(N-1)=Tb + (N-2)×Tb+Ta
一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。
ここで、フィボナッチ数列のプログラムは、末尾再帰ではない。この fib( intx ) の処理時間を表す再帰方程式は、どのような式で表せるだろうか？
再帰を含む一般的なプログラム例
ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で表現し、処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？
int array[ 8 ] = {
3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;
int sum( int a[] , int L , int R ) { // 非末尾再帰
if ( R - L == 1 ) {
return a[ L ] ;
} else {
int M = (L + R) / 2 ;
return sum( a , L , M ) + sum( a , M , R ) ;
}
}
int main() {
printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
return 0 ;
}
import java.util.*;
public class Main {
public static int[] array = {
3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;
public static int sum( int[] a , int L , int R ) {
if ( R - L == 1 ) {
return a[ L ] ;
} else {
int M = (L + R) / 2 ;
return sum( a , L , M ) + sum( a , M , R ) ;
}
}
public static void main(String[] args) throws Exception {
System.out.println( "sum()=" + sum( array , 0 , array.length ) ) ;
}
}
- 再帰による配列の合計(分割統治法?)(Paiza.io)
このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに２つに分割して解いている。
このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。
このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間Ts(N)は次の再帰方程式で表せる。
← Tβ + (L〜M)の処理時間 + (M〜R)の処理時間
これを代入の繰り返しで解いていくと、
ということで、このプログラムの処理時間は、 で表せる。
ハノイの塔
ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。
ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。
一般解の予想
ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。
… ①
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。
再帰方程式
上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、
… ②
… ③
ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想①が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、
枚では、
… ③より
… ①を代入
… ①の
の場合
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
これらのことから、ハノイの塔の処理時間は、で表せる。
創造工学演習・予備実験(2)・8queen
創造工学演習の予備実験 part 2 として、Flood Fill , 8queen にチャレンジしてみる。
Flood fill アルゴリズム
前の問題は、今年度のプログラミングコンテストの課題のパズルとは、方向性が違うので、今年度のプロコンの競技部門にちょっとだけ近い2次元フィールドのパズルネタで演習。(Wikipedia Flood-fill参照)
以下の image のような2次元配列が与えられたら、指定座標(x,y)を中心に周囲を塗りつぶす処理を作成せよ。
include <stdio.h>
// *は壁 SPCは白 この領域の指定位置を#で塗りつぶす。
char image1[10][10] = { // (4,4)始点で塗りつぶし後
"*********" , // *********
"* * *" , // * *###*
"* * *" , // * *###*
"* * *" , // * *####*
"*** ***" , // ***###***
"* * *" , // *####* *
"* * *" , // *###* *
"* * *" , // *###* *
"*********" , // *********
} ;
char image2[10][10] = { // 応用問題用の画像例
"*********" , // * のような隙間は通り抜けられる
"* * *" , // * ようにするにはどうすればいい？
"* ** *" , // **
"* ** *" , // ** これは通り抜けられない
"*** ***" , // **
"* * *" ,
"* * *" ,
"* * *" ,
"*********" ,
} ;
// 盤面を表示
void print_image( char image[10][10] ) {
for( int y = 0 ; y < 9 ; y++ ) {
for( int x = 0 ; x < 9 ; x++ ) {
printf( "%c" , image[y][x] ) ;
}
printf( "\n" ) ;
}
}
// 再帰呼び出しを使った flud_fill アルゴリズム
void flood_fill( char image[10][10] , int x , int y , char fill ) {
// image: 塗りつぶす画像
// x,y: 塗りつぶす場所
// fill: 書き込む文字
// 指定座標が空白なら
if ( image[y][x] == ' ' ) {
// その座標を埋める
image[y][x] = fill ;
//////////////////////////////////////
// ここに周囲をflud_fillする処理を書く //
//////////////////////////////////////
}
}
int main() {
print_image( image1 ) ;
flood_fill( image1 , 4 , 4 , '#' ) ;
print_image( image1 ) ;
return 0 ;
}
import java.util.*;
public class Main {
public static String[] image1 = {
"*********" , // *********
"* * *" , // * *###*
"* * *" , // * *###*
"* * *" , // * *####*
"*** ***" , // ***###***
"* * *" , // *####* *
"* * *" , // *###* *
"* * *" , // *###* *
"*********" , // *********
} ;
// 文字配列を文字の2次元配列に変更
public static char[][] map_from_string( String[] image ) {
char[][] map = new char[ image.length ][ image[0].length() ] ;
for( int i = 0 ; i < image.length ; i++ ) {
for( int j = 0 ; j < image[ i ].length() ; j++ ) {
map[ i ][ j ] = image[ i ].charAt( j ) ;
}
}
return map ;
}
// 2次元配列を出力
public static void print_image( char[][] map ) {
for( int i = 0 ; i < map.length ; i++ ) {
for( int j = 0 ; j < map[i].length ; j++ ) {
System.out.print( map[ i ][ j ] ) ;
}
System.out.println() ;
}
}
// 塗りつぶし処理
public static void flood_fill( char[][] map , int x , int y , char c ) {
if ( map[x][y] == ' ' ) {
// 指定された場所に埋める文字を代入
map[x][y] = c ;
////////////////////////////////////////////
// ここに周囲を flood_fill する処理を書く //
////////////////////////////////////////////
}
}
public static void main(String[] args) throws Exception {
char[][] map = map_from_string( image1 ) ;
print_image( map ) ;
flood_fill( map , 4 , 4 , '#' ) ;
print_image( map ) ;
}
}
- Flood Fill Java版(Paiza.io)
応用問題
Wikipediaのflood-fill のプログラムの説明のアルゴリズムでは、左図黒のような斜めに並んだブロックは、境界として通り抜けられないようにつくられている。
そこで、斜めに並んだブロックは通り抜けられるルールとした場合のプログラムを記述せよ。
レポート提出
レポートでは、指定長を辺の組み合わせで作るテーマか、Flood-fill のテーマのいずれかにて、以下の内容をまとめてレポートとして提出すること。
-
- レポートの説明(自分の選んだテーマと自分なりの説明)
- プログラムリスト
- 動作確認の結果
N Queen
パズル問題の定番の8 Queen を考えてみる。
8 Queen とは、8×8のチェスの盤面に、8つの Queen をお互いに取られないように配置するパズル。
import java.util.*;
public class Main {
public final static int size = 4 ;
public static int[] board = new int[ size ] ;
// できあがった盤面を表示する補助関数
public static void print_board( int[] board ) {
for( int i = 0 ; i < size ; i++ ) {
for( int j = 0 ; j < board[ i ] ; j++ )
System.out.print( "+ " ) ;
System.out.print( "Q " ) ;
for( int j = board[ i ] + 1 ; j < size ; j++ )
System.out.print( "+ " ) ;
System.out.println() ;
}
System.out.println() ;
}
// n_queen本体
// 4 queen の boad 配列
// [ 1 3 0 2 ]
// + + Q +
// Q + + +
// + + + Q
// + Q + +
public static void n_queen( int[] board , int n , int i ) {
// nは盤面の大きさ
// i列目のj行目に置く(i=2)
// [ 1 3 j ? ]
// 0 1 2 3
// 0 + + + +
// 1 Q + + +
// 2 + +[Q]+ j=2
// 3 + Q + +
if ( i == n ) {
// 右端まですべて埋まったら答えとして表示
print_board( board ) ;
} else {
// j行目に置くのを試す
for( int j = 0 ; j < size ; j++ ) {
// 同じ行に置かれたものが無いか探す
boolean flag = true ;
for( int k = 0 ; k < i && flag ; k++ ) {
if ( board[ k ] == j )
flag = false ; // 同じ行にすでに置かれている
}
if ( flag ) { // 同じ行が使われていなければ
// 斜め左上に向かってぶつかるQueenを探す
for( int u = j - 1 , h = i - 1 ; u >= 0 && h >= 0 && flag ; u-- , h-- ) {
if ( board[ h ] == u )
flag = false ;
}
// 斜め左下に向かってぶつかるQueenを探す
for( int d = j + 1 , h = i - 1 ; d < size && h >= 0 && flag ; d++ , h-- ) {
if ( board[ h ] == d )
flag = false ;
}
if ( flag ) {
// 左横、左斜め上、左斜め下にぶつかるQueenが無かったら、再帰
board[ i ] = j ;
n_queen( board , n , i + 1 ) ;
}
}
}
}
}
public static void main(String[] args) throws Exception {
n_queen( board , size , 0 ) ;
print_board( board ) ;
}
}
- N Queen(Paiza.io)
複素数クラスとC++の演算子オーバーロード
複素数クラスの例
隠蔽化と基本的なオブジェクト指向の練習課題として、複素数クラスをあげる。ここでは、複素数の加算・乗算を例に説明をするので、減算・除算などの処理を記述することで、クラスの扱いに慣れてもらう。
直交座標系の複素数クラス
#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 ) { // 初期化はこのように書いてもいい
} // 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 ;
}
C++と演算子のオーバーロード
C++では、演算子のオーバーロードという機能がある。前の例では、複素数の計算で a.add( b ) といった呼び出しで 複素数の a + b の計算をして、計算結果が a に格納されていた。でもやっぱり、c = a + b ; と書けたらすごく便利。
ということで、C++ では、関数名を書く欄に、operator 演算子( 右辺 ) { … } という書き方ができる。
関数の返り値の前に inline を書くと、開いたサブルーチンにしてくれる。
仮引数宣言の const は、引数に対して修正が行われないことを示す。
型 関数名( 仮引数, … ) const { … } としてメソッドを定義すると、オブジェクトを書き換えないことを明示できる。
#include <stdio.h>
#include <math.h>
// 直交座標系の複素数クラス
class Complex {
private:
double re ; // 実部
double im ; // 虚部
public:
Complex( double r , double i ) // コンストラクタで要素の
: re( r ) , im( i ) { // 初期化はこのように書いてもいい
} // re = r ; im = i ; の意味
Complex() // デフォルトコンストラクタ
: re( 0.0 ) , im( 0.0 ) {}
// C++ではそのクラス専用の演算子を定義できる(演算子のオーバーロード)
Complex operator+( const Complex &z ) const {
// 加算は、直交座標系だと極めてシンプル
return Complex( re + z.re , im + z.im ) ;
}
Complex operator*( const Complex &z ) const {
// 乗算は、直交座標系だと、ちょっと煩雑
double r = re * z.re - im * z.im ;
double i = re * z.im + im * z.re ;
return Complex( r , i ) ;
}
// getter メソッド
inline double get_re() const { return re ; }
inline double get_im() const { return im ; }
double get_abs() const { return sqrt( re*re + im*im ) ; } // 絶対値
double get_arg() const { return atan2( im , re ) ; } // 偏角
void print() {
printf( "%lf + j%lf\n" , get_re() , get_im() ) ;
}
void print_polar() {
printf( "%lf ∠ %lf\n" , get_abs() , get_arg() / 3.141592 * 180.0 ) ;
}
} ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね
int main() {
// 複素数を作る
Complex a( 1.0 , 2.0 ) ;
Complex b( 2.0 , 3.0 ) ;
// 複素数の計算
Complex c = a + b ;
Complex d = a * b ;
// 結果の表示
c.print() ;
d.print() ;
c.print_polar() ;
d.print_polar() ;
return 0 ;
}
創造工学演習・予備実験(1)・パズル問題
プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。また、課題部門や自由部門であっても、複数の条件の組み合わせの中から最良のものを選ぶといった処理も求められる。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。
組み合わせ問題の基礎
簡単な問題として「100未満の整数の値を３つ選び、その値を辺の長さとした場合、 直角三角形となるものをすべて表示する。」について考える。
一番簡単な方法は、以下となるであろう。
#include <stdio.h>
#include <math.h>
#include <time.h>
// 整数比の直角三角形の一覧を求める。
void integer_triangle( int n ) {
for( int a = 1 ; a < n ; a++ ) {
for( int b = 1 ; b < n ; b++ ) {
// 一番ダサい方法
for( int c = 1 ; c < n ; c++ ) {
if ( a*a + b*b == c*c ) {
printf( "%d %d %d\n" , a , b , c ) ;
}
}
}
}
}
int main() {
integer_triangle( 100 ) ;
return 0 ;
}
しかしこのプログラムの欠点としては、100×100×100回のループで無駄な処理が多い。
ループ回数を減らすだけなら、最も内側の処理を、計算で整数値か確認すればいい。
void integer_triangle( int n ) {
for( int a = 1 ; a < n ; a++ ) {
for( int b = 1 ; b < n ; b++ ) {
// ココも改良できるよね？
int d = a*a + b*b ;
int c = (int)sqrt( d ) ;
// 斜辺Cの整数値を求め、改めて確認する。
if ( c*c == d ) {
printf( "%d %d %d\n" , a , b , c ) ;
}
}
}
}
(1) 計算誤差の問題を考えてみよう。
たとえば、3:4:5の直角三角形で、3*3+4*4 = 25 だが、sqrt(25)は実数で計算するから、 計算誤差で4.99999で求まったらどうなるだろうか？
1～100までの数値で、”int c = sqrt( (double)(i*i) ) ;” を計算してみて、 異なる値が求まることはあるか？ 多少の計算誤差があっても正しく処理が行われるにはどうすればいいか、考えてみよう。
(2) 無駄な答えについて考えてみよう。
このプログラムの答えでは、簡単な整数比の答えの「整数倍の答え」も表示されてしまう。 たとえば、(3:4:5)の答えのほかに、(6:8:10)も表示される。 こういった答えを表示しないようにするにはどうすればよいか？
また、この2つのプログラムの処理時間を実際に比べてみる。
#include <stdio.h>
#include <time.h>
int main() {
time_t start , end ;
// time() 関数は、秒数しか求まらないので、
// あえて処理を1000回繰り返し、数秒かかる処理にする。
start = time( NULL ) ;
for( int i = 0 ; i < 1000 ; i++ ) {
// ただし、関数内のprintfをコメントアウトしておくこと
integer_triangle( 100 ) ;
}
end = time( NULL ) ;
printf( "%lf\n" , difftime( end , start ) ) ;
return 0 ;
}
再帰プログラミング
組み合わせ問題では、forループの多重の入れ子で問題を解けない場合が多い。 (書けないことはないけど無駄なループで処理が遅くなるか、入れ子段数が可変にできない。)
こういった場合には、再帰プログラミングがよく利用される。 もっとも簡単な再帰の例として、階乗のプログラムを考える。 通常であれば、以下のような for ループで記述することになるだろう。
// 階乗の計算
int fact( int x )
{ // ループ
int f = 1 ;
for( int i = 2 ; i <= x ; i++ )
f = f * i ;
return f ;
}
再帰呼び出しでは、関数の処理の中に、自分自身の関数呼び出しが含まれる。 また、無限に自分自身を呼び出したら処理が止まらないので、 問題を一つ小さくして、これ以上小さくできないときは処理を止めるように記述する。
int fact( int x )
{ // 再帰呼び出し
if ( x <= 1 )
return 1 ;
else
return x * fact( x - 1 ) ;
}
ここ以降は、指定長さを指定辺の組み合わせで作る課題と、後に述べるFlood-fill 課題の選択とする。
指定長を指定辺の組み合わせで作る(テーマ1)
再帰を使った簡単なパズル問題として、以下のプログラムを作成したい。
配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
(例) 辺の長さ10を作るには、(5,4,1)とか(7,3)などが考えられる。
これは、ナップサック問題の基本問題で、容量の決まったナップサックに最大量入れる組合せを求めるのと同じである。
このプログラムを解くには…
10 を [4,5,2,1,3,7] で作るには... (0) 6=10-4 を [4|5,2,1,3,7]で作る。 (1) 5=10-5 を [5|4,2,1,3,7]で作る。 (2) 8=10-2 を [2|5,4,1,3,7]で作る。 (3) 9=10-1 を [1|5,2,4,3,7]で作る。 (4) 7=10-3 を [3|5,2,1,4,7]で作る。 (5) 3=10-7 を [7|5,2,1,3,4]で作る。
そこで、ここまでの考えを、以下のようなプログラムで記述してみる。
# まだ再起呼び出しにはしていない。
// 指定されたデータを入れ替える。
void swap( int*a , int*b )
{ int x = *a ;
*a = *b ;
*b = x ;
}
void check( int array[] , int size , int len , int n )
{
// array[] 配列
// size 配列サイズ
// len 作りたい長さ
// n 使った個数
for( int i = n ; i < size ; i++ ) {
// i番目を先頭に...
swap( &array[ n ] , &array[ i ] ) ;
printf( "check( array , %d , %d , %d )\n" ,
size , len - array[ n ] , n+1 ) ;
// 最初のswapでの変更を元に戻す。
swap( &array[ i ] , &array[ n ] ) ;
}
}
int main() {
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
check( a , 6 , 10 , 0 ) ;
}
(1) これを再帰呼び出しにしてみよう。どう書けばいい？
void check( int array[] , int size , int len , int n )
{
// array[] 配列
// size 配列サイズ
// len 作りたい長さ
// n 使った個数
if ( len < 0 ) {
// 指定した丁度の長さを作れなかった。
;
} else if ( len == 0 ) {
// 指定した長さを作れたので答えを表示。
for( int i = 0 ; i < n ; i++ ) {
printf( "%d " , array[ i ] ) ;
}
printf( "\n" ) ;
} else {
// 問題を一つ小さくして再帰。
for( int i = n ; i < size ; i++ ) {
swap( &array[ n ] , &array[ i ] ) ;
printf( "check( array , %d , %d , %d )\n" ,
size , len - array[ n ] , n+1 ) ;
check( array , size , len - array[ n ] , n + 1 ) ;
swap( &array[ i ] , &array[ n ] ) ;
}
}
}
(2) 少ない組み合わせの方がポイントが高い場合には、プログラムをどう変更する？
(3) 答えが１つだけで良い場合は、プログラムをどう変更する？
(4) このプログラムでは、冗長な答えがあるか？ないか？検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。
# レポートでは、(2),(3),(4)を検討した結果を実験すること。(5)までチャレンジした人は(2),(3),(4)の説明は簡単に記載するだけで良い。
繰り返し処理と処理時間の見積もり
単純サーチの処理時間
ここで、プログラムの実行時間を細かく分析してみる。
// ((case-1))
// 単純サーチ O(N)
#include <stdio.h>
int main() {
int a[ 10 ] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int N = 10 ; // 実際のデータ数(Nとする)
int key = 21 ; // 探すデータ
for( int i = 0 ; i < N ; i++ )
if ( a[i] == key )
break ;
return 0 ;
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
// Your code here!
int a[] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int N = a.length ;
int key = 21 ;
for( int i = 0 ; i < N ; i++ )
if( a[i] == key )
break ;
}
}
例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ,
,
,
とする。
この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。
ここで例題
この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか？
感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、Tβ,Tα は何秒だったのだろうか？ 上記のT(N)=Tα+N ✕ Tβ に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。
ここで一番のポイントは、データ処理では N が小さな値の場合(データ件数が少ない状態)はあまり考えない。N が巨大な値であれば、Tαは、1000Tβに比べれば微々たる値という点である。よって
で考えれば良い。これであれば、T(1000)=5μ秒=Tβ×1000 よって、Tβ=5n秒となる。この結果、T(10000)=Tβ×10000=50μ秒 となる。
2分探索法と処理時間
次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。データはあらかじめ昇順に並べておくことで、一度の比較で対象件数を減らすことで高速に探すことができる。
下記プログラムを読む場合の注意点：
- Lは、探索範囲の一番左端のデータのある場所。
- Rは、探索範囲の一番右端のデータのある場所 + 1
// ((case-2))
// 2分探索法 O(log N)
#include <stdio.h>
int main() {
int a[] = {
9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
} ;
int L = 0 ; // L : 左端のデータの場所
int R = 10 ; // R : 右端のデータの場所+1
while( L != R ) {
int M = (L + R) / 2 ;
if ( a[M] == key )
break ;
else if ( a[M] < key )
L = M + 1 ;
else
R = M ;
}
return 0 ;
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
} ;
int L = 0 ; // L : 左端のデータの場所
int R = a.length ; // R : 右端のデータの場所+1
int key = 73 ;
while( L != R ) {
int M = (L + R) / 2 ;
if ( a[M] == key )
break ;
else if ( a[M] < key )
L = M + 1 ;
else
R = M ;
}
}
}
このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、
件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。
…両辺のlogをとる
2分探索は、繰り返し処理であるから、処理時間は、
… (Mはループ回数)
ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式 ()で係数が出てくるが、これはTβに含めて考えればいい。
単純なソート(選択法)の処理時間
次に、並べ替え処理の処理時間について考える。
単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。
// ((case-3))
// 選択法 O(N^2)
#include <stdio.h>
int main() {
int a[] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int size = 10 ;
for( int i = 0 ; i < size - 1 ; i++ ) {
int tmp ;
// i..size-1 の範囲で一番大きいデータの場所を探す
int m = i ;
for( int j = i + 1 ; j < size ; j++ ) {
if ( a[j] > a[m] )
m = j ;
}
// 一番大きいデータを先頭に移動
tmp = a[i] ;
a[i] = a[m] ;
a[m] = tmp ;
}
return 0 ;
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int size = a.length ;
for( int i = 0 ; i < size - 1 ; i++ ) {
int tmp ;
int m = i ;
for( int j = i + 1 ; j < size ; j++ ) {
if ( a[j] > a[m] )
m = j ;
}
tmp = a[i] ;
a[i] = a[m] ;
a[m] = tmp ;
}
}
}
このプログラムの処理時間T(N)は…
… i=0の時
… i=1の時
:
… i=N-1の時
…(参考 数列の和の公式)
となる。
オーダー記法
ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、
の部分の方が重要である。
| 単純サーチ | |
| ２分探索法 | |
| 最大選択法 |
そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を取り除いた式で表現する。これをオーダー記法と言う。
| 単純サーチ | オーダーNのアルゴリズム | |
| 2分探索法 | オーダー log N のアルゴリズム | |
| 最大選択法 | オーダー N2 のアルゴリズム |
練習問題
- ある処理のデータ数Nに対する処理時間が、
であった場合、オーダー記法で書くとどうなるか？
- コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか？
(ヒント: 底変換の公式) の処理時間を要するアルゴリズム(データ件数が変わっても処理時間は一定)を、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
(ヒント: ロピタルの定理)
- 2と4の解説
- 1は、N→∞において、N2 ≪ 2Nなので、O(2N) 。厳密に回答するなら、練習問題4と同様の証明が必要。
- 3は、O(1)。
- 誤答の例：O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。
- 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
インターネットとWebの仕組み
前回の講義では、最初のガイダンスとしてOSの仕組みについて説明をおこなった。
2回目の授業では、インターネットのWebページを作るために使われているHTMLやCSSやプログラム言語について解説を行う。
Webページの生成とプログラム言語
理解確認
- こちらの小テストに回答してください。
構造体からクラスの導入
構造体の参照渡し
構造体のデータを関数で受け渡しをする場合は、参照渡しを利用する。
struct Person {
char name[ 20 ] ;
int age ;
} ;
void print( struct Person* this ) {
printf( "%s %d¥n" , this->name , this->age ) ;
}
void main() {
struct Person saitoh ;
strcpy( saitoh.name , "t-saitoh" ) ;
saitoh.age = 50 ;
print( &saitoh ) ; // ポインタによる参照渡し
}
このようなプログラムの書き方をすると、「データ saitoh に、print() せよ…」 といった処理を記述したようになる。 これを発展して、データ saitoh に、print という命令をするイメージにも見える。
この考え方を、そのままプログラムに反映させ、Personというデータは、 名前と年齢、データを表示するprintは…といったように、 データ構造と、そのデータ構造への処理をペアで記述すると分かりやすい。
オブジェクト指向の導入
構造体でオブジェクト指向もどき
例えば、名前と年齢の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ利用者で分けて 仕事ができることを説明。
// この部分はデータ構造の設計者が書く
// データ構造を記述
struct Person {
char name[10] ;
int age ;
} ;
// データに対する処理を記述
void setPerson( struct Person* this , char s[] , int a ) {
// ポインタの参照で表記
strcpy( (*this).name , s ) ;
(*this).age = a ;
}
void printPerson( struct Person* this ) {
// アロー演算子で表記 "(*this).name" は "this->name" で書ける
printf( "%s %d¥n" ,
this->name , this->age ) ;
}
// この部分は、データ利用者が書く
int main() {
// Personの中身を知らなくてもいいから配列を定義(データ隠蔽)
struct Person saitoh ;
setPerson( &saitoh , "saitoh" , 55 ) ;
struct Person table[ 10 ] ; // 初期化は記述を省略
for( int i = 0 ; i < 10 ; i++ ) {
// 出力する...という雰囲気で書ける(手続き隠蔽)
printPerson( &table[i] ) ;
}
return 0 ;
}
このプログラムの書き方では、mainの中を読むだけもで、 データ初期化とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、setPerson()や、printPerson()という関数の中身についても、 初期化・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。
C++のクラスで表現
上記のプログラムをそのままC++に書き直すと以下のようになる。
#include <stdio.h>
#include <string.h>
// この部分はクラス設計者が書く
class Person {
private: // クラス外からアクセスできない部分
// データ構造を記述
char name[10] ; // メンバーの宣言
int age ;
public: // クラス外から使える部分
// データに対する処理を記述
void set( char s[] , int a ) { // メソッドの宣言
// pのように対象のオブジェクトを明記する必要はない。
strcpy( name , s ) ; // メソッドは隠れた引数としてオブジェクトへのポインタ this がある。
age = a ; // このため strcpy( this->name , s ) ; , this->age = a ; などと書いてもいい。
}
void print() {
printf( "%s %d¥n" , name , age ) ;
}
} ; // ← 注意ここのセミコロンを書き忘れないこと。
// この部分はクラス利用者が書く
int main() {
Person saitoh ;
saitoh.set( "saitoh" , 55 ) ;
saitoh.print() ;
// 文法エラーの例
printf( "%d¥n" , saitoh.age ) ; // age は private なので参照できない。
return 0 ;
}
用語の解説：C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
この様にC++のプログラムに書き換えたが、内部の処理は元のC言語と同じであり、オブジェクトへの関数呼び出し saitoh.set(…) などが呼び出されても、set() は、オブジェクトのポインタを引数して持つ関数として、機械語が生成されるだけである。
用語の解説：C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのデータに対し具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
C++では隠蔽化をさらに明確にするために、private: や public: といったアクセス制限を指定できる。private: は、そのメソッドの中でしか使うことができない要素や関数であり、public: は、メソッド以外からでも参照したり呼出したりできる。オブジェクト指向でプログラムを書くとき、データ構造や関数の処理方法は、クラス内部の設計者しか触れないようにしておけば、その内部を改良することができる。しかし、クラスの利用者が勝手に内部データを触っていると、内部設計者が改良するとそのプログラムは動かないものになってしまう。
隠蔽化を的確に行うことで、クラスの利用者はクラスの内部構造を触ることができなくなる。一方でクラス設計者はクラスの外部への挙動が変化しないようにクラス内部を修正することに心がければ、クラス利用者への影響がないままクラスの内部を改良できる。このように利用者への影響を最小に、常にプログラムを修正することをリファクタリングと呼ぶ。
クラス限定子
前述のプログラムでは、class 宣言の中に関数内部の処理を記述していた。しかし関数の記述が長い場合は、書ききれないこういう場合はクラス限定子を使って、メソッドの具体的な処理をクラス宣言の外に記載する。
class Person {
private:
char name[10] ;
int age ;
public:
// メソッドのプロトタイプ宣言
void set( char s[] , int a) ;
void print() ;
} ;
// メソッドの実体をクラス宣言の外に記載する。
void Person::set( char s[] , int a ) { // Person::set()
strcpy( name , s ) ;
age = a ;
}
void Person::print() { // Person::print()
printf( "%s %d¥n" , name , age ) ;
}
inline 関数と開いたサブルーチン
オブジェクト指向では、きわめて簡単な処理な関数を使うことも多い。
例えば、上記のプログラム例で、クラス利用者に年齢を読み出すことは許しても書き込みをさせたくない場合、以下のような、inline 関数を定義する。(getterメソッド)
# 逆に、値の代入専用のメソッドは、setterメソッドと呼ぶclass Person { private: char name[10] ; int age ; public: // メソッドのプロトタイプ宣言 inline int get_age() { return age ; } // getter inline void set_age( int a ) { age = a ; } // setter } ;ここで inline とは、開いた関数(開いたサブルーチン)を作る指定子である。通常、機械語を生成するとき中身を参照するだけの機械語と、get_age() を呼出したときに関数呼び出しを行う機械語が作られる(閉じたサブルーチン)が、age を参照するだけのために関数呼び出しの機械語はムダが多い。inline を指定すると、入り口出口のある関数は生成されず、get_age() の処理にふさわしい age を参照するだけの機械語が生成される。
# 質問：C言語で開いたサブルーチンを使うためにはどういった機能があるか？
コンストラクタとデストラクタ
プログラムを記述する際、データの初期化忘れや終了処理忘れで、プログラムの誤動作の原因になることが多い。
このための機能がコンストラクタ(構築子)とデストラクタ(破壊子)という。
コンストラクタは、返り値を記載しない関数でクラス名(仮引数…)の形式で宣言し、オブジェクトの宣言時に初期化を行う処理として呼び出される。デストラクタは、~クラス名() の形式で宣言し、オブジェクトが不要となる際に、自動的に呼び出し処理が埋め込まれる。
class Person {
private:
// データ構造を記述
char name[10] ;
int age ;
public:
Person() { // (A) 引数なしのコンストラクタ
name[0] = 'class Person {
private:
// データ構造を記述
char name[10] ;
int age ;
public:
Person() { // (A) 引数なしのコンストラクタ
name[0] = '\0' ;
age = 0 ;
}
Person( char s[] , int a ) { // (B) 引数ありのコンストラクタ
strcpy( name , s ) ;
age = a ;
}
~Person() { // デストラクタ
print() ;
}
void print() {
printf( "'%s' = %d¥n" , name , age ) ;
}
} ;
int main() {
Person saitoh( "saitoh" , 55 ) ; // オブジェクトsaitohを"saitoh"と55で初期化
Person tomoko ; // 引数なしのコンストラクタで初期化される。
return 0 ;
// main を抜ける時にオブジェクトsaitohは不要になるので、
// デストラクタが自動的に呼び出され、'saitoh' = 55 が表示。
// 同様に tomoko のデストラクタでは、'' = 0 を表示。
}
' ;
age = 0 ;
}
Person( char s[] , int a ) { // (B) 引数ありのコンストラクタ
strcpy( name , s ) ;
age = a ;
}
~Person() { // デストラクタ
print() ;
}
void print() {
printf( "'%s' = %d¥n" , name , age ) ;
}
} ;
int main() {
Person saitoh( "saitoh" , 55 ) ; // オブジェクトsaitohを"saitoh"と55で初期化
Person tomoko ; // 引数なしのコンストラクタで初期化される。
return 0 ;
// main を抜ける時にオブジェクトsaitohは不要になるので、
// デストラクタが自動的に呼び出され、'saitoh' = 55 が表示。
// 同様に tomoko のデストラクタでは、'' = 0 を表示。
}
このクラスの中には、(A)引数無しのコンストラクタと、(B)引数ありのコンストラクタが出てくる。C++では、同じ名前の関数でも引数の数や型に応じて呼出す関数を適切に選んでくれる。(関数のオーバーロード)
デストラクタは、データが不要となった時に自動的に呼び出してくれる関数で、一般的にはC言語でのファイルの fopen() , fclose() のようなものを使う処理で、コンストラクタで fopen() , デストラクタで fclose() を呼出すように使うことが多いだろう。同じように、コンストラクタで malloc() を呼出し、デストラクタで free() を呼出すというのが定番の使い方だろう。
nitfcei ディスク移行
実験用にさくらインターネットのサーバを借りて運用しているけど、経年劣化にともなう危険性拡大の緩和ということで、ディスクを移行しろとな。
クラウドのコンソールで、サーバを止めて、マニュアルに従って移行ボタンをポチっとな。
情報構造論ガイダンス2025
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。
プログラムを評価する3つのポイント
まずは以下を読む前に、質問。
- あなたが”良い”プログラムを作るために何を考えて作りますか？ ※1
- ここまでの段階で3つの要点を考えメモしてください。
具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。
- プログラムの速度
- プログラムのわかり易さ
- メモリの使用量
プログラムを作る場合、この３要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。
メモリの使用量の影響
メモリを大量に使用すると、どういった影響がでるのか？ OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)
しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)
int 型のメモリ使用量は？
int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。
32bit の0/1情報の組み合わせで、232通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-231～0～231-1 の範囲を扱うことができる。231 = 2×210×210×210 ≒ 2×10003
32bit = 4byte
ソフトウェアとアルゴリズムとプログラム
用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か？
- アルゴリズム – 計算手順の考え方。
- プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
- ソフトウェア – プログラムと、その処理に必要なデータ。
(日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない) - パラダイム – プログラムをどう表現すると分かりやすいか？
トレードオフ関係をプログラムで確認
例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。
// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int main() {
int a[ SIZE ] = {
52 , 14 , 82 , 62 , 15
} ; // 配列
int size = 5 ; // 実際のデータ数(Nとする)
int key = 62 ; // 探すデータ
for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル
if ( a[i] == key ) {
printf( "Find %d¥n" , key ) ;
break ;
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
52 , 14 , 82 , 62 , 15
} ;
int key = 62 ;
for( int i = 0 ; i < a.length ; i++ ) {
if ( a[i] == key ) {
System.out.println( "Find " + key ) ;
break ;
}
}
}
}
// import java.util.Arrays; // こういった正当なJavaのプログラムでは、
// public class Main { // データ件数が大きくなった時の挙動がわからない
// public static void main( String[] args ) {
// Integer a[] = {
// 52 , 14 , 82 , 62 , 15 // Integer型 int 型は何が違うの？
// } ;
// if ( Arrays.asList( a ).contains( 62 ) ) {
// System.out.println("配列内に値が存在しています。");
// }
// }
// }
しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)
// ((case-2))
// 2分探索法 O(log N)
// 速いけど、プログラムは分かりにくく(複雑に)なった
int main() {
int a[] = {
14 , 15 , 52 , 62 , 82 // データはあらかじめ昇順に並べておく
} ;
int L=0 , R= 5 ;
while( L != R ) {
int M = (L + R) / 2 ;
if ( a[M] == key )
break ;
else if ( a[M] < key )
L = M + 1 ;
else
R = M ;
}
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
14 , 15 , 52 , 62 , 82 // データはあらかじめ昇順に並べておく
} ;
int key = 62 ;
int L = 0 ;
int R = a.length ;
while( L != R ) {
int M = (L + R) / 2 ;
if ( a[M] == key )
break ;
else if ( a[M] < key )
L = M + 1 ;
else
R = M ;
}
}
}
でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)
// ((case-3)) // 添字がデータ O(1) // 探すデータが電話番号 272925 のような 6 桁ならば、データを以下の様に保存すればいい。 int a[ 1000000 ] ; a[ 272925 ] = 272925 ; ： // データを探したければ a[ 電話番号 ] で探せばいい printf( "%d\n" , a[ 621111 ] ) ; // 処理速度はクソ速いけど、メモリは大量消費
良いプログラムを作るとは
プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。
実際には、限られた予算からメモリやCPUが決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。
皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ？ゲームがバグですぐに変な動きしたらキレるでしょ！(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!
