/*
* 20210521-01-QQQQ.c
* 「Hanoi の塔」を解くプログラム
*
*
[考え方]
| | |
1|1 | |
22|22 | |
333|333 | |
---+--- ---+--- ---+---
(1) (2) (3)
(1) => (2)
三つの塔があり、
一つの塔に、円盤 1 ? N が、下から上に、大きい順にのっている
これらの円盤を、他の塔に移動したい
ただし、次の制限を守りながら、操作する
1) 一度に移動できるのは、一番上の一枚円盤だけ
2) すでにある円盤の上には、それより小さいものしか置けない
からの塔は、どんな大きさもおける
| | |
| 1|1 |
| 22|22 |
| 333|333 |
---+--- ---+--- ---+---
(1) (2) (3)
1 ? N を (1) => (2)
!! 一度では難しい
!! => 分ける
(気が付き)
途中で、かならず N の円盤を動かす必要がある
1. かならずやる
2. 一手でできる
=> 再帰でやるときに、
すぐにできる事を、残りに分ける
=> すぐにできる事に着目するとよい
(3. 対称性の真ん中)
| | |
1|1 | |
22|22 | |
333|333 | |
---+--- ---+--- ---+---
(1) (2) (3)
| | |
[A] | | |
| | 1|1
333|333 | 22|22
---+--- ---+--- ---+---
(1) (2) (3)
| | |
[B] | | |
| | 1|1
| 333|333 22|22
---+--- ---+--- ---+---
(1) (2) (3)
| | |
| 1|1 |
| 22|22 |
| 333|333 |
---+--- ---+--- ---+---
(1) (2) (3)
hanoi( 1-3, (1) => (2) )
->
初期状態から [A] の状況を作る
move(3, (1) => (2) ) [A] -> [B]
[B] の状況から終了状態にする
->
hanoi(1-2, (1) => (3) )
move(3, (1) => (2) ) [A] -> [B]
hanoi(1-2, (3) => (2) )
*/
#include <stdio.h>
#include <string.h>
/*
* one_to_ten ( char *n );
* n が、一進数 "1" 〜 "111111111" の時、十進数の 1 〜 9 に変換する
*/
void one_to_ten ( char *n ) {
if ( !strcmp ( n, "" ) ) {
printf ( "0" );
} else if ( !strcmp ( n, "1" ) ) {
printf ( "1" );
} else if ( !strcmp ( n, "11" ) ) {
printf ( "2" );
} else if ( !strcmp ( n, "111" ) ) {
printf ( "3" );
} else if ( !strcmp ( n, "1111" ) ) {
printf ( "4" );
} else if ( !strcmp ( n, "11111" ) ) {
printf ( "5" );
} else if ( !strcmp ( n, "111111" ) ) {
printf ( "6" );
} else if ( !strcmp ( n, "1111111" ) ) {
printf ( "7" );
} else if ( !strcmp ( n, "11111111" ) ) {
printf ( "8" );
} else if ( !strcmp ( n, "111111111" ) ) {
printf ( "9" );
} else {
printf ( "?" );
}
}
/*
* move ( char *n, char *f, char *t )
* 幅 n の円盤を、f から t に移動する
*/
void move ( char *n, char *f, char *t ) {
/* 画面に 「棒 f から、円盤 (n) を、棒 t に移動 」と出力する */
printf ( f );
printf ( " から、" );
printf ( "円盤 (" );
one_to_ten ( n ); /* 円盤の大きさを 1 進数で表現 */
/* なので、表示する時に、数字に変換して出力 */
printf ( ") を " );
printf ( t );
printf ( " に移動\n" );
}
/*
* hanoi ( char *n, char *f, char *t, char *w )
* 高さ n の塔を f から t へ w を利用して、移動する
*/
void hanoi ( char *n, char *f, char *t, char *w ) {
if ( !strcmp ( n, "" ) ) { /* 高さ 0 の塔 */
/* 何もしなくて良い (動かすものはない) */
/* n は、1 進数で表現された数で、
その意味は、1 ? n までの円盤をさす
n が空文字列であるということは、n が 0 を表している
すなわち、「動かすものがなにもない」事を意味する
*/
} else {
/* f にある n-1 の塔 を、一旦 w に移動する (この時、t を作業場として利用可能) */
hanoi ( n + 1, f, w, t );
/* f に、長さ n の円盤があるので、これを t に移動 */
move ( n, f, t );
/* w にある n-1 の塔 を、t に移動する (この時、f を作業場として利用可能) */
hanoi ( n + 1, w, t, f );
}
}
/*
* main
*/
int main ( void ) {
printf ( "高さ 3 の「Hanoi の塔」\n" );
hanoi ( "111", "棒 1", "棒 3", "棒 2" ); /* Web Page と同じ */
printf ( "------\n" );
printf ( "高さ 5 の「Hanoi の塔」\n" );
/*
** この部分を完成させなさい
*/
return 0;
}
/*
* 20210528-01-QQQQ.c
* 与えられた文字列の文字を二度ずつ出力する関数を作成する
*
[考え方]
double_print ( "abc" );
=> aabbcc
aabbcc => a a bbcc
putchar ( 'a' )
putchar ( 'a' )
double_print ( "bc" )
double_print ( "abc" );
putchar ( 'a' )
putchar ( 'a' )
double_print ( "bc" )
double_print ( "abc" );
putchar ( *"abc" )
putchar ( *"abc" )
double_print ( "abc" + 1 )
double_print ( str );
putchar ( *str )
putchar ( *str )
double_print ( str + 1 )
double_print ( str );
if ( !strcmp( str, "" ) ) {
} else {
putchar ( *str )
putchar ( *str )
double_print ( str + 1 )
}
*/
#include <stdio.h>
#include <string.h>
/*
* double_print
* 与えられた文字列(message)の文字を二度ずつ出力する
*/
void double_print ( char *message ) {
if ( !strcmp ( message, "" ) ) { /* 空文字列だった */
/* なにもする必要はない */
} else {
putchar ( *message ); /* 取り敢えず、一つ分は出す */
putchar ( *message ); /* さらに、もう一つ分を出す */
double_print ( message + 1 ); /* 再帰呼出しをする */
}
}
/*
* main
*/
int main ( void ) {
double_print ( "abc" );
printf ( "\n" );
double_print ( "1234567" );
printf ( "\n" );
return 0;
}
/*
* 20210528-02-QQQQ.c
* 与えられた文字列の文字を逆順に出力する関数を作る
*
[考え方]
reverse_print ( "abc" );
=> cba
=> c ba とすると、難しい
<= cb a にするよい
=>
reverse_print ( "bc" );
putchar ( 'a' );
*/
#include <stdio.h>
#include <string.h>
/*
* reverse_print
* 与えられた文字列(message)の文字を逆順に出力する
*/
void reverse_print ( char *message ) {
if ( !strcmp ( message, "" ) ) { /* 空文字列だった */
/* なにもする必要はない */
} else {
/* ここで再帰呼出しを行うのだが... */
reverse_print ( message + 1 );
putchar ( *message );
}
}
/*
* main
*/
int main ( void ) {
reverse_print ( "abc" );
printf ( "\n" );
reverse_print ( "1234567" );
printf ( "\n" );
return 0;
}
#include <stdio.h>
int main(void) {
printf( "Hello, World\n" );
return 0;
}
/*
文字
ASCII Code 表にのっているもの ( 1 byte で表現 )
数字 ( 0-9 ), 英字 ( a-z, A-Z ), 記号 ( ", ', .. )
=> 表に載っていないものは、
この講義では、扱わない
「'(シングルクォート)」で挟んで、文字を表す
例: 'A' <= 「A」という文字を表し、対応する ASCII Code は 65
出力は putchar 関数を使う
*/
#include <stdio.h>
int main(void) {
putchar ( 'A' ); /* 文字「A」を画面に出力する */
putchar ( '\n' ); /* エスケープシーケンスで表現された文字「\n」(改行)が表示される */
putchar ( 'B' ); /* 文字「B」を画面に出力する */
putchar ( '\n' );
return 0;
}
/*
文字
ASCII Code 表にのっているもの ( 1 byte で表現 )
数字 ( 0-9 ), 英字 ( a-z, A-Z ), 記号 ( ", ', .. )
=> 表に載っていないものは、
この講義では、扱わない
「'(シングルクォート)」で挟んで、文字を表す
例: 'A' <= 「A」という文字を表し、対応する ASCII Code は 65
出力は putchar 関数を使う
*/
#include <stdio.h>
int main(void) {
putchar ( 'A' ); /* 文字「A」を画面に出力する */
putchar ( '\n' ); /* エスケープシーケンスで表現された文字「\n」(改行)が表示される */
putchar ( 'A' + 1 ); /* 文字「A」の次の文字を画面に出力する */
/* 「次の文字」<= ASCII 表上での次 */
/* => 「B」が表示される */
putchar ( '\n' );
putchar ( 'Z' - 1 ); /* 文字「Z」の前の文字を画面に出力する */
/* 「前の文字」<= ASCII 表上での前 */
/* => 「Y」が表示される */
putchar ( '\n' );
putchar ( 'A' + 32 ); /* ASCII コード表から、小文字(a)になる */
putchar ( '\n' );
putchar ( 'z' - 32 ); /* ASCII コード表から、大文字(Z)になる */
putchar ( '\n' );
putchar ( 'A' + ( 'a' - 'A' ) );
/* 'A' + ( 'a' - 'A' ) = 'A' + 'a' - 'A'
= 'A' - 'A' + 'a'
= 0 + 'a'
= 'a'
*/
putchar ( 'P' + ( 'a' - 'A' ) ); /* 'p' */
/*
'P' + ( 'a' - 'A' ) = 'P' + ( 'p' - 'P' )
= 'p'
何故なら
ASCII 表から、同じ種類の小文字から大文字をひくと、
常に 32 になるので
'a' - 'A' = 32 = 'p' - 'P'
*/
/*
'P' を 'p' に変更する ( 大文字を小文字に変換する )
ためには、32 ( = 'a' - 'A' ) を加えればればよい
「大文字を小文字する」という「情報処理」が、
「32 を加える」という「計算」で実現可能
<= この性質は ASCII コード表の性質
*/
putchar ( '\n' );
return 0;
}
/*
文字
ASCII Code 表にのっているもの ( 1 byte で表現 )
数字 ( 0-9 ), 英字 ( a-z, A-Z ), 記号 ( ", ', .. )
=> 表に載っていないものは、
この講義では、扱わない
「'(シングルクォート)」で挟んで、文字を表す
例: 'A' <= 「A」という文字を表し、対応する ASCII Code は 65
出力は putchar 関数を使う
*/
#include <stdio.h>
int main(void) {
putchar ( '0' + 0 ); /* putchar ( 0 + '0' ) */
putchar ( '0' + 1 ); /* putchar ( 1 + '0' ) */
putchar ( '0' + 2 );
putchar ( '0' + 3 );
putchar ( '0' + 4 );
putchar ( '0' + 5 );
putchar ( '\n' );
return 0;
}
/*
文字
ASCII Code 表にのっているもの ( 1 byte で表現 )
数字 ( 0-9 ), 英字 ( a-z, A-Z ), 記号 ( ", ', .. )
=> 表に載っていないものは、
この講義では、扱わない
「'(シングルクォート)」で挟んで、文字を表す
例: 'A' <= 「A」という文字を表し、対応する ASCII Code は 65
出力は putchar 関数を使う
*/
#include <stdio.h>
int main(void) {
putchar ( ( '2' - '0' ) + ( '3' - '0' ) + '0' );
/*
'2' - '0' => ( '0' + 2 ) - '0' => 2
'3' - '0' => 3
( '2' - '0' ) + ( '3' - '0' )
=> 2 + 3 => 5
( '2' - '0' ) + ( '3' - '0' ) + '0'
=> 5 + '0' => '5'
*/
putchar ( '\n' );
return 0;
}
#include <stdio.h>
int main(void) {
putchar( "Hello, World\n"[0] ); /* 先頭の文字 0 番目 */
/* 0123 */ /* 'H' */
putchar ( '\n' );
putchar( "Hello, World\n"[3] ); /* 先頭の文字 3 番目 */
/* 0123 */ /* 'l' */
putchar ( '\n' );
/*
X[n] <-> *(X + n)
"Hello, World\n"[3] = *("Hello, World\n" + 3 )
= *((("Hello, World\n"+1)+1)+1)
= *(("ello, World\n"+1)+1)
= *("llo, World\n"+1)
= *"lo, World\n"
= 'l'
*/
return 0;
}
#include <stdio.h>
#include <string.h>
/*
文字列の文字を個々に処理するには、
+1 と * と、再帰を利用すればよい
*/
/*
例: myprintf をつくってみる
=> 文字列を指定して、それを画面に出力するが、
その時に、printf ではなく putchar で行う
*/
/*
考え方(わかりやすい具体的な例で、やってみる )
"abc" を出力したい
!! 全体を、分割して、簡単ものと残りにわける
myprintf ( "abc" ) => 画面に 「abc」と表示して欲しい
!! printf がつかえるなら printf ( "abc" ) で OK
!! printf を使わずに、putchar でやりたい..
「abc」=> 「a」+「bc」 ( 先頭と残りにわける )
「a」=> putchar できる
「bc」=> 文字列
myprintf ( 再帰呼び出しをすればよい )
!! 簡単なものは => 直接表現
!! 残りは => 再帰で表現
myprintf ( "abc" );
puchar ( 'a' )
myprintf ( "bc" );
!! 実行する命令の中の値を、
!! 引数から計算するようにする
myprintf ( "abc" );
puchar ( *"abc" )
myprintf ( "abc" + 1 );
!! 共通な値は、変数にする
myprintf ( str );
puchar ( *str )
myprintf ( str + 1 );
!! 変数の値が、空文字列の時とそうでない時に分ける
if ( !strcmp ( str, "" ) ) {
なにもしない
} else {
puchar ( *str )
myprintf ( str + 1 );
}
*/
void myprintf ( char *str ) {
if ( !strcmp ( str, "" ) ) {
/* Do Nothing */
} else {
putchar ( *str );
myprintf ( str + 1 );
}
}
int main(void) {
myprintf ( "Hello, World\n" );
return 0;
}
#include <stdio.h>
#include <string.h>
/*
文字列の文字を個々に処理するには、
+1 と * と、再帰を利用すればよい
*/
/*
例: lowerprintf をつくってみる
=> 英大文字からなる文字列を指定して、
それを英小文字に変換して出力する。
*/
void lowerprintf ( char *str ) {
if ( !strcmp ( str, "" ) ) {
/* Do Nothing */
} else {
putchar ( *str + ( 'a' - 'A' ) );
/* myprintf では、そのまま出力 */
/* lowerprintf では、小文字に変換する */
/* => 32 = 'a' - 'A' を加えればよい */
lowerprintf ( str + 1 );
}
}
int main(void) {
lowerprintf ( "ABCDEF" ); /* 英大文字だけからなる文字列 */
putchar ( '\n' );
lowerprintf ( "01234" ); /* 残念ながら、数大文字がでるわけではない */
putchar ( '\n' );
return 0;
}
#include <stdio.h>
/*
ここに func の関数定義があればよいのだが..
func の関数宣言は別のソースコードファイルで行われている
=> func を利用するために、
分割コンパイル
func が定義されているソースファイルのコンパイル
それからできるオブジェクトとのリンク
を行う
ワーニングを減らすために、関数定義の代わりに、
extern 宣言をする
*/
extern void func(void);
int main(void) {
func(); /* 自分で作成した関数 func を呼び出す */
return 0;
}
#include <stdio.h>
/*
関数 func の定義だけのソースファイルを作った
*/
void func(void) {
printf ( "関数 func が呼び出さされました\n" );
}
#include <stdio.h>
extern void func(void); /* 警告(ワーニング)を抑制するために extern 宣言する */
int main(void) {
func();
func();
func();
return 0;
}
前回(2021/05/21)の内容
複雑な数学パズルを、再帰を用いて解決する
順接/条件分岐/再帰の万能性の現れ
=> プログラムの万能性
計算の結果が、現実に反映さえられる仕組みがあれば、
「計算の結果で、すべての事ができる」という意味で、
計算機(で表現できるプログラム)は、万能性を持つ
<= 現実でできない事は、計算機でもできない
再帰的に問題を解くパズル
ハノイの塔
砂漠の旅人
=> 前回の課題は、後でやる
「数学」と「アルゴリズム」
数学的な「ものの考え方」が問題を解く鍵(アルゴリズム)になる
=> おいおい紹介したい
文字と文字列
文字とは : ASCII Code 表に記載されたもの(キーボードから入力可能な半角文字)
文字列とは : 文字の 0 個以上の並び
文字の表現 : 「'(シングルクォート)」で「一文字」を挟む
文字列の表現 : 「"(ダブルクォート)」で「文字の並び」を挟む
文字の出力 : putchar 関数を利用する
文字列の出力 : printf 関数を利用する
文字の計算 : +1/-1 すると、ASCII Code 表の一つ後、一つ前の文字になる
文字列の計算 : +1 すると、先頭の文字が削られ、長さが短くなる
文字列から文字を取り出す方法
文字列の頭に「*(アスタリスク)」を付けると、先頭の文字が取り出せる
文字列の後ろに「[N]」(N=0?)を付けると、N+1 番目の文字が取り出せる
文字列[N] <-> *(文字列 + N)
空文字列と空文字(NULL 文字 : '\0' )
空文字列 : ""
*"" <= 空文字列の先頭の文字 => NULL 文字
実は、長さ N の文字列は、N + 1 個の文字からなっている
例 : "abc" = { 'a', 'b', 'c', '\0' }
=> 文字列の、最後の文字は、常に NULL 文字 ('\0')
"" = { '\0' }
*"" => '\0'
空文字列("")かどうかを判定するには、
その先頭(*をつけた結果)が、NULL文字('\0')かどうかで判定できる
p-008.c => myprinf を作った
=> 文字列の中文字を、いっこずつ処理する手段になっている
例: myprintf は、個々の文字を、単に出力する
この考え方を応用すれば、色々な事ができる
例: 指定された文字列(英大文字からなる)を小文字に変換して出す
[分割コンパイル]
関数の定義を複数のファイルに分けて、個々にコンパイルし、
リンクによって、一つ実行ファイルを作るという方式
!! 一つのファイルに、すべての関数定義を記述してもよい
!! => もし、同じ関数を、異なるプログラムで使いたい場合
!! もし、プログラムを一つのファイル内で利用するならば、
!! 同じ関数を、複数のファイルに記述する必要がある
分割コンパイルを利用する事により、
一つ関数(定義)を、複数のプログラムで共有できる
[ポイント]
同じ関数の定義を、色々なプログラムで共有する場合には、
その関数の定義を一つのソースコードに分離し、
分割コンパイルし、あとでリンクでつなぐ事が望ましい
!! printf/putchar のような「ライブラリ関数」も、
!! 実は、別に記述されていて、リンク時に繋がれている
!! !! <= コンパイルとリンクが異なる作業である理由
==
12345 <= たくさんのものを処理
1 2345 <= 先頭と、残りに分ける
個別に処理する
12345
/ |
1 2345
/ |
2 345
/ |
3 45
/|
4 5
最初に先頭を処理して、
後から残りを処理する
処理(1)
1 の結果
処理(2345)
2345 の結果
12345 <- [1]
/ |
1 2345 <- [3]
[2] / |
2 345 <- [5]
[4] / |
3 45 <- [7]
[6] /|
4 5
[8] [9]
結果 : [2], [4], [6], [8], [9]
1 2 3 4 5 <= 正順
最初に残りを処理して、
後から先頭を処理
処理(2345)
2345 の結果
処理(1)
1 の結果
12345 <- [1]
/ |
1 2345 <- [2]
[9] / |
2 345 <- [3]
[8] / |
3 45 <- [4]
[7] /|
4 5 <- [5]
[6] [5]
結果 : [5], [6], [7], [8], [9]
5 4 3 2 1 <= 逆順
全体を分けて、
頭と残りの二つにする
処理の対象を
頭が先で、残りを後と処理すると
結果的に、頭からひとつずつになる(正順)
し、
残りを先で、頭を後に処理すると
結果的に、尻からひとつずつになる(逆順)
という性質がある(事が証明できる)ので、それを利用している
課題プログラム内の「/*名前:ここ*/」の部分を書き換え「/*この部分を完成させなさい*/」の部分にプログラムを追加して、プログラムを完成させます。
Download : 20210528-01.c
/*
* 20210528-01-QQQQ.c
* 与えられた文字列の文字を二度ずつ出力する関数を作成する
*/
#include <stdio.h>
#include <strings.h>
/*
* double_print
* 与えられた文字列(message)の文字を二度ずつ出力する
*/
void double_print ( char *message ) {
if ( !strcmp ( message, "" ) ) { /* 空文字列だった */
/* なにもする必要はない */
} else {
putchar ( *message ); /* 取り敢えず、一つ分は出す */
/*
** この部分を完成させなさい
*/
double_print ( message + 1 ); /* 再帰呼出しをする */
}
}
/*
* main
*/
int main ( void ) {
double_print ( "abc" );
printf ( "\n" );
double_print ( "1234567" );
printf ( "\n" );
return 0;
}
$ ./20210528-01-QQQQ.exe aabbcc 11223344556677 $
Download : 20210528-02.c
/*
* 20210528-02-QQQQ.c
* 与えられた文字列の文字を逆順に出力する関数を作る
*/
#include <stdio.h>
#include <strings.h>
/*
* reverse_print
* 与えられた文字列(message)の文字を逆順に出力する
*/
void reverse_print ( char *message ) {
if ( !strcmp ( message, "" ) ) { /* 空文字列だった */
/* なにもする必要はない */
} else {
/* ここで再帰呼出しを行うのだが... */
/*
** この部分を完成させなさい
*/
}
}
/*
* main
*/
int main ( void ) {
reverse_print ( "abc" );
printf ( "\n" );
reverse_print ( "1234567" );
printf ( "\n" );
return 0;
}
$ ./20210528-02-QQQQ.exe cba 7654321 $