6/24(月)の大雨による休講で7/1(月)に説明

テスト前のリスト導入の復習

前回のリスト構造の導入では、配列のデータに次のデータの入っている番号を添えることで途中にデータを挿入できるデータ構造の説明をした。

また、それをクラスを用いたプログラムを示した。

リスト構造 ListNode

前述の data と next で次々とデータを続けて保存する方法を、next の部分を次のデータへの参照を用いるように、リスト構造(連結リスト)を定義する。

import java.util.*;

class ListNode {
    int      data ;   // データ部分
    ListNode next ;   // 次のデータへの参照
    // コンストラクタ
    ListNode( int d , ListNode nx ) {
        this.data = d ;
        this.next = nx ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
        // 途中にデータを入れる
        top.next = new ListNode( 15 , top.next ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

リスト操作

リスト構造に慣れるために簡単な練習をしてみよう。リスト構造のデータに対するメソッドをいくつか作ってみよう。print() や sum() を参考に、データ数を求める count() , 最大値を求める max() , データを検索する find() を完成させてみよう。

class ListNode {
    (略)
} ;

public class Main {
    static void print( ListNode p ) {   // リストを表示
        for( ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }

    static int sum( ListNode p ) {      // リストの合計を求める
        int s = 0 ;
        for( ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }

    static int count( ListNode p ) {    // データ件数を数える

    }

    static int max( ListNode p ) {      // データの最大値を求める

    }

    static boolean find( ListNode p , int key ) { // データ列の中から特定のデータを探す
                                                  //   見つかったら true , 見つからなければ false
    }
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        print( top ) ;
        System.out.println( "合計:" + sum( top ) ) ;
        System.out.println( "件数:" + count( top ) ) ;
        System.out.println( "最大:" + max( top ) ) ;
        System.out.println( "検索:" + (find( top , 22 )
                                       ? "みつかった" : "みつからない" ) ) ;
    }
}

オブジェクト指向っぽく書いてみる

前述のプログラムでは、print( top ) のように使う static な関数としてプログラムを書いていた。しかし、オブジェクト指向であれば、オブジェクトに対するメソッドだと top.print() のように書きたい。この場合だと、以下のように書くかもしれない。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
    int sum() {    // リストの合計を求める
        int  s = 0 ;
        for( ListNode p = this ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = null ;
        list_empty.print() ;  // 実行時エラー java.lang.NullPointerException ぬるぽ！
    }
}

しかし、データ件数 0件 に対してメソッドを呼び出せない。

ListNode と List というクラスで書いてみる

ひとつの方法として、リストの先頭だけのデータ構造を宣言する方法もある。

class ListNode {
    int   data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

class List {
    ListNode top ;
    List( ListNode p ) {
        this.top = p ;
    }
    void print() {
        for( ListNode p = top ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        List list = new List( new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ) ;
        list.print() ;
        
        List list_empty = new List( null ) ;
        list_empty.print() ;
    }
}

しかし、List と ListNode の2つのデータの型でプログラムを書くのは面倒くさい。

授業ではシンプルに説明したいので、今後はこの方法は極力避けていく。

先頭にダミーデータを入れる

複数のクラス宣言するぐらいなら、リストデータの先頭は必ずダミーにしておく方法もあるだろう。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this.next ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode list = new ListNode( -1 , null ) ;
        list.next = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = new ListNode( -1 , null ) ;
        list_empty.print() ;
    }
}

以降、必要に応じて、先頭にダミーを入れる手法も取り混ぜながらプログラムを書くこととする。

入力データをリストに追加

入力しながらデータをリストに格納する処理を考えてみる。

リストでデータを追加保存するのであれば、一番簡単なプログラムは、以下のように先頭にデータを入れていく方法だろう。

class ListNode {
    (略)
    void print() {
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data ) ;
        System.out.println() ;
    }
} ;
    
public class Main {
    public static void main(String[] args) throws Exception {
        int[] inputs = { 11 , 22 , 33 } ;
        ListNode top = null ;

        for( int datum : inputs )
            top = new ListNode( datum , top ) ;
        top.print() ;
    }
}

でもこの方法だと、先頭にデータを入れていくため、保存されたデータは逆順になってしまう。

末尾にデータを入れる

逆順になるのを避けるのであれば、データを末尾に追加する方法があるだろう。ただし初期状態でデータが0件だと処理が書きづらいので、先頭にダミーを入れておく方法で書いてみる。

public class Main {
    public static void main(String[] args) throws Exception {
        int[] test_data = { 11 , 22 , 33 } ;

        ListNode top = new ListNode( -1 , null ) ; // ダミー
        ListNode tail = top ;
        for( int x : test_data ) {
            tail.next = new ListNode( x , null ) ;
            tail = tail.next ;
        }
        top.print() ; // -1   11  22  33
    }                 // ダミー
}

今日は、テスト返しの残り時間で、4年の情報構造論で、リスト構造などの内容を進める前に、3年プログラミング応用でクラスなどに自信がない人向けの簡単レクチャ。

クラスは、データ構造と手続き

例えば、名前と年齢のデータをクラスで扱うのであれば、以下のようなコードが基本となるだろう。

import java.util.*;

class NameAge {
    String name ;          // インスタンス変数
    int    age ;           // インスタンス変数
    static int count = 0 ; // クラス変数
    // コンストラクタ
    NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

実行結果
tsaitoh,59
member = 1
age = 59
tomoko,48
member = 2

クラスとは、データ構造(オブジェクト)とそのデータ構造を扱うための関数(メソッド)をまとめて扱う。

クラス NameAge の中で宣言されている、NameAge() の関数は、オブジェクトを初期化するための関数(メソッド)であり、特にコンストラクタと呼ばれる。

実際にデータを保存するための tsaitoh や tomoko とよばれる変数に NameAge オブジェクトの実体を作る時には 「new クラス名」 とやることで、初期化ができる。

イメージでは、下図のようなデータ構造ができあがる。

でも、年齢の覚え方は、将来的に誕生日を覚えるように変化するかもしれない。この際に、Main 関数の中で age を使うと後で混乱の元になるかもしれない。こういう時は、NameAge クラス以外では中身を勝手に使わせないために、インスタンス変数などに public / private といったアクセス制限を加える。

import java.util.*;
class NameAge {
    private String name ;          // インスタンス変数
    private int    age ;           // インスタンス変数
    public  static int count = 0 ; // クラス変数
    // コンストラクタ
    public  NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    public void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ここがエラーになる。NameAge::age は private 
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

クラス自体も、public class NameAge … のように宣言することもあるが、public なクラスは 1つ の *.java ファイルの中に1つしか書けないというルールがあるので要注意。

中間試験問題の回答

import java.util.*;
import java.util.* ;

class Item {
    int    id ;
    String name ;
    int    price ;
    Item( int i , String n , int p ) {
        this.id    = i ;
        this.name  = n ;
        this.price = p ;
    }
} ;

class Buy {
    int    id ;
    int    count ;
    Buy( int i , int n ) {
        this.id    = i ;
        this.count = n ;
    }
} ;

public class Main {
    static Item[] item_list = {
        new Item( 1010 , "orange" ,      50 ) ,
        new Item( 1020 , "apple" ,      100 ) ,
        new Item( 1022 , "pineapple" , 1000 ) ,
    } ;
    static Buy[] buy_list = {
        new Buy( 1010 , 5 ) ,
        new Buy( 1020 , 3 ) ,
        new Buy( 1022 , 1 ) ,
    } ;
    public static void main( String[] args ) {
        System.out.println( total_price( item_list , buy_list ) ) ;
    }
    static int total_price( Item[] i_list , Buy[] b_list ) {
        int sum = 0 ;
        for( Item item : i_list )
            for( Buy buy : b_list )
                if ( item.id == buy.id )
                    sum += item.price * buy.count ;
        return sum ;
    }
    // static int total_price( Item[] i_list , Buy[] b_list ) {
    //     int sum = 0 ;
    //     for( int i = 0 ; i < i_list.length ; i++ )
    //         for( int j = 0 ; j < b_list.length ; j++ )
    //             if ( i_list[ i ].id == b_list[ j ].id )
    //                 sum += i_list[ i ].price * b_list[ j ].count ;
    //     return sum ;
    // }
}

練習問題

科目(Subject)と学生(Student)の情報があり、科目を受講した成績(Result)で成績を管理している。
このデータを管理するためのクラスを宣言し、下に示すような出力が得られるプログラムを作成せよ。

今回の中間テストで成績が悪かった人は、テスト前に示したレポート課題ではなく下記の課題で提出してよいこととする。

科目: Subject
id    name       teacher   // Subject[] subject_table = {
10010 情報構造論 t-saitoh   //    new Subject( 10010 , "情報構造論" , "t-saitoh" ) ,
10020 電気磁気学 takaku     //    new Subject( ....
10030 電気回路   komatsu    // } ;

成績: Result
s_id  id         point      // Result[] result_table = {
16213 10020      83         //    new Result( 16213 , 10020 , 83 ) ,
18348 10010      95         //    new Result( ...
17101 10030      64         // } ;
16213 10010      89

学生: Student
s_id  name       age        // Student[] student_table = {
16213 斉藤太郎   18          //    new Student( 16213 , "斉藤太郎" , 18 ) ,
17101 山田次郎   19          //    new Student( ...
18348 渡辺花子   18          // } ;

以下のようなデータが出力されること
斉藤太郎 電気磁気学 83
渡辺花子 情報構造論 95
山田次郎 電気回路   64
斉藤太郎 情報構造論 89

C言語でのポインター

#include <stdio.h>

int main() {
    int  x  = 123 ; //                             px [ 〇 ]
    int* px ;       // px はポインタ                      ↓
    px = &x ;       // x の変数の番地を px に代入      x [ 123 ]
    *px = 321 ;     // px の指し示す場所に 321 を代入
    printf( "%d\n" , x ) ; // 321 を出力
    return 0 ;
}

値渡し(pass by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
   return 0 ;
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか？

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
   return 0 ;
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
int main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
   return 0 ;
}

ポインタ渡し(pass by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
int main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
   return 0 ;   // さらに125と増える
}

ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを極力使わないようにするために、参照渡しを利用する。ただし、ポインタ渡しも参照渡しも、機械語レベルでは同じ処理にすぎない。

参照渡し(pass by reference)

// ポインタ渡しのプログラム
void foo( int& x ) {  // xは参照
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後 main::a は 124 に増えている。
   foo( a ) ;  // 124
   return 0 ;  // さらに125と増える。
}

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味 (参照”悪趣味なプログラム”)

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

ポインタと文字列処理

#include <stdio.h>

void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '
#include <stdio.h>

void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

int main(void){
    char str[ 20 ] ;

    my_tolower( str , "AaBcDeF Hoge" ) ;
    printf( "%s\n" , str ) ;
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '
#include <stdio.h>

void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

int main(void){
    char str[ 20 ] ;

    my_tolower( str , "AaBcDeF Hoge" ) ;
    printf( "%s\n" , str ) ;
    return 0 ;
}
' ;
}

int main(void){
    char str[ 20 ] ;

    my_tolower( str , "AaBcDeF Hoge" ) ;
    printf( "%s\n" , str ) ;
    return 0 ;
}

• my-tolower-1

間違ったプログラム

C言語の面倒な点は、データがどのように格納されるのかを考えないと正しく動かない所であろう。

下記のプログラムの問題点がわかるだろうか？

#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}

• my_tolower-2

ポインタインクリメントと式

C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。

// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '\0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '\0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}

しかし、この strcpy は、ポインタを使って書くと以下のように書ける。

// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )   // while( *p++ = *q++ ) ; でも良い
      ;
}

 

Javaでの引数に対する副作用

Javaでのプログラムにおいて、下記のように関数に引数でデータが渡された場合、呼び出し元の変数が変化する／変化しないの違いが分かるであろうか？

import java.util.*;

class A {
    private int a ;
    public A( int x ) { a = x ; }
    public void set( int x ) { a = x ; }
    public int get() { return a ; }
}

public class Main {
    public static void foo( int x , Integer y , String s , int z[] , A a ) {
        x = 12345 ;        // プリミティブな引数の書き換え
        y = 23456 ;        // イミュータブルな引数の書き換え
        s = "hoge" ;
        z[0] = 34567 ;     // 参照で渡されたオブジェクトの書き換え
        a.set( 45678 ) ;
    }
    public static void main(String[] args) throws Exception {
        int     mx = 11111 ;        // プリミティブなデータ
        Integer my = 22222 ;        // イミュータブルなオブジェクト
        String  ms = "aaa" ;
        int     mz[] = { 33333 } ;  // それ以外のオブジェクト
        A       ma = new A( 44444 ) ;

        foo( mx , my , ms , mz , ma ) ;

        System.out.println( "mx="+mx+",my="+my+",ms="+ms+",mz[0]="+mz[0]+",ma="+ma.get() );
    }
}

• Paiza.ioのプログラム

上記のプログラムでは、foo() の第1引数 mx は、プリミティブ型なので関数の引数に渡される際には、コピーが生成されて渡されるため、呼び出し元の変数 mx の値は変化していない。

Javaでは、プリミティブ型以外のデータは、ヒープ領域に実体が保存され、そのデータの場所(ポインタ)によって管理される。

しかし、Integer型のオブジェクト my や、String型のオブジェクト ms は、参照(データの場所)が渡されるが、イミュータブルな(変更できない)オブジェクトなので、値の代入が発生すると新しいオブジェクトが生成され、そのアドレスが参照を保存している変数(ポインタ)に代入される。このため、呼び出し元の my や ms は値が変化しない。

これに対し、配列 mz や クラスオブジェクト ma は、オブジェクトの中身を関数 foo で値を変更すると、呼び出し元の変数の内容が変更される。こういった関数やメソッドの呼び出しによって、呼び出し元の値が変化することは「副作用」と呼ばれる。

こういった参照のメカニズムは、データの管理の仕方を正しく理解する必要があることから、もっと原始的な C 言語にて理解を目指す。

C言語の基礎

#include <stdio.h>

int main() {
   int n ;
   scanf( "%d" , &n ) ;  // 標準入力から整数をnに保存
   int m = 1 ;
   for( int i = 1 ; i <= n ; i++ )
      m *= i ;
   printf( "%d! = %d\n" , n , m ) ; // 
   return 0 ;
}

printf の最初の引数は、表示する際のフォーマットであり、%d の部分には対応する引数の値に置き換えて表示される。

   型                |   基数             |   型            |   表示方式
  long int      %ld  |  10進数        %d  |  double    %lf  |  固定小数点表示 %f  12.34
  int           %d   |  16進数        %x  |  float     %f   |  指数小数点表示 %e  1.234e+1
  short int     %hd  |   8進数        %o  |                 |  固定/指数自動  %g
  char          %c   |                    |  printf( "%5.2f" , 1.2345 ) ; □1.23
  char[], char* %s   |                    |

// Compile by C++
#include <stdio.h>

int main(void) {
    long int  x = 123456789L ;
    int       y = 1234567 ;
    short int z = 32767 ;
    printf( "%ld %d %hd\n" , x , y , z ) ;
    //      123456789 1234567 32767
    printf( "%d %x %o\n" , 0x1000 , 32767 , 32767 ) ;
    //      4096 7fff 77777
  
    double    p = 123.45678L ;
    float     q = 12.345 ;

    printf( "%lf %f\n" , p , q ) ;
    //      123.456780 12.345000
    printf( "(%lf) (%8.3lf) (%le)\n" , p , p , p ) ;
    //      (123.456780) ( 123.457) (1.234568e+02)   

    char      c = 0x41 ;
    char      s[] = "ABCDE" ;
    char      t[] = { 0x41 , 0x42 , 0x43 , 0x0 } ; // C言語の文字列の末尾には'
// Compile by C++
#include <stdio.h>

int main(void) {
    long int  x = 123456789L ;
    int       y = 1234567 ;
    short int z = 32767 ;
    printf( "%ld %d %hd\n" , x , y , z ) ;
    //      123456789 1234567 32767
    printf( "%d %x %o\n" , 0x1000 , 32767 , 32767 ) ;
    //      4096 7fff 77777
  
    double    p = 123.45678L ;
    float     q = 12.345 ;

    printf( "%lf %f\n" , p , q ) ;
    //      123.456780 12.345000
    printf( "(%lf) (%8.3lf) (%le)\n" , p , p , p ) ;
    //      (123.456780) ( 123.457) (1.234568e+02)   

    char      c = 0x41 ;
    char      s[] = "ABCDE" ;
    char      t[] = { 0x41 , 0x42 , 0x43 , 0x0 } ; // C言語の文字列の末尾には'\0'が必要

    printf( "(%c) (%s) (%s)\n" , c , s , t ) ;   
    //       (A) (ABCDE) (ABC)
    return 0 ;
}
'が必要

    printf( "(%c) (%s) (%s)\n" , c , s , t ) ;   
    //       (A) (ABCDE) (ABC)
    return 0 ;
}

C言語でのポインター

#include <stdio.h>

int main() {
    int  x  = 123 ; //                             px [ 〇 ]
    int* px ;       // px はポインタ                      ↓
    px = &x ;       // x の変数の番地を px に代入      x [ 123 ]
    *px = 321 ;     // px の指し示す場所に 321 を代入
    printf( "%d\n" , x ) ; // 321 を出力
    return 0 ;
}

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味 (参照”悪趣味なプログラム”)

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

ポインタインクリメントと式

C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。

// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}

しかし、この strcpy は、ポインタを使って書くと以下のように書ける。

// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )   // while( *p++ = *q++ ) ; でも良い
      ;
}

 

前回の講義で説明できなかった、オーダーの問題の解説

練習問題

1. の処理時間を要するアルゴリズム(データ件数が変わっても処理時間は一定)を、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
2. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか？
3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
   (ヒント: ロピタルの定理)

• 1は、O(1)。
  • 誤答の例：O(0)と書いちゃうと、T(N)=T_α×0=0になってしまう。
  • 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
• 2は、N→∞において、N² ≪ 2^Nなので、O(2^N) 。厳密に回答するなら、練習問題3と同様の証明が必要。
• 3の解説

---

再帰呼び出しの基本

次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
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 ) ;
}

階乗 fact(N) を求める処理は、以下の様に再帰が進む。(N=5の場合)

また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。(N=5の場合)

再帰呼び出しの処理時間

次に、この再帰処理の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=T_a で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(T_b)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 T(N)=T_b=T(N-1)で表せる。

} 再帰方程式

このような、式の定義自体を再帰を使って表した式は再帰方程式(漸化式)と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式  が得られる。

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b + (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で表現し、処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

// 分割統治法による配列合計

#include <stdio.h>

int sum( int a[] , int L , int R ) { // 非末尾再帰
    // L : 左端のデータ
    // R : 右端のデータが入っているの場所+1
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    int array[ 8 ] = {
    // L=0  1   2   3   4   5   6   7   R=8
        3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
    } ;
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

// 分割統治法による配列合計

import java.util.*;

public class Main {
    static int sum( int a[] , int L , int R ) { // 非末尾再帰
        // L : 左端のデータ
        // R : 右端のデータが入っているの場所+1
        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 {
        int array[] = {
        // L=0  1   2   3   4   5   6   7  R=8  
            3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
        } ;
        System.out.println( sum( array , 0 , array.length ) );
    }
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに２つに分割して解いている。

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

   ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

ということで、このプログラムの処理時間は、 で表せる。

---

ハノイの塔

ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。

ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
　… ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想①が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

　… ③より
 … ①を代入
      … ①のの場合

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

また、ハノイの塔の処理時間は、で表せる。