/*
* CDATE FILENAME
*
* 自然数の階乗を返す関数
*/
#include <stdio.h>
#include "s_print.h" /* s_print_int を利用するので.. */
/*
* int factrial ( int n )
* int n : 階乗を計算する自然数
* 返り値 : n! ( n の階乗 )
*/
n! = n * (n-1) * (n-2) * ... * 2 * 1
= n * { (n-1) * (n-2) * ... * 2 * 1 }
= n * (n-1)!
再帰
0! = 1
終了条件 : n が 0 になった時に終わり
int factrial ( int n ) {
if ( n <= 0 ) { /* 0!, 負の数の階乗は、取り敢えず 1 にする */
return 1; /* 特に 「0! = 1」に注意 */
} else { /* n が正の時は、「n! = n * (n-1)!」となるので.. */
/*
** この部分を完成させなさい
*/
return n * factrial ... ;
}
}
/*
* main
*/
int main( void )
{
s_print_int ( 3 );
s_print_string ( " の階乗の値は " );
s_print_int ( factrial ( 3 ) );
s_print_string ( " になります。\n" );
s_print_int ( 5 );
s_print_string ( " の階乗の値は " );
s_print_int ( factrial ( 5 ) );
s_print_string ( " になります。\n" );
return 0;
}
/*
* CDATE FILENAME
*
* 二つの整数の最大公約数を返す
*/
#include <stdio.h>
#include "s_print.h" /* s_print_int を利用するので.. */
/*
* int euclid ( int a, int b )
* int a : 非負の整数
* int b : 非負の整数
* 返り値 : a と b の最大公約数を返す
*/
int euclid ( int a, int b ) {
if ( b == 0 ) { /* 任意の数 a と 0 の最大公約数 (a,0) は a となる */
return a;
} else { /* b が 0 でない時 (a,b) = (b,a%b) となる */
/*
** この部分を完成させなさい
*/
return euclid ( b, ... );
}
}
/*
* main
*/
int main( void )
{
s_print_int ( 12 );
s_print_string ( " と、 " );
s_print_int ( 18 );
s_print_string ( " の最大公約数は " );
s_print_int ( euclid( 12, 18 ) );
s_print_string ( " です。\n" );
s_print_int ( 1111 );
s_print_string ( " と、 " );
s_print_int ( 111111 );
s_print_string ( " の最大公約数は " );
s_print_int ( euclid( 1111, 111111 ) );
s_print_string ( " です。\n" );
return 0;
}
ユークリッドの互除法
自然数 m,n が与えられたときに、m,n の最大公約数を求める手続(アルゴリズム)
次のステップで考える
1. m,n の大きい方を小さい方(ここでは、m > nとする)で割り、その余りを r とする
2. もし r が 0 なら、割った方(小さい方)が答 (最大公約数)
3. そうでなければ、n (小さい方)と r の最大公約数を求める。
# はじめから、再帰的に定義されている
a%b は、a を b で割った余り(r)になる
/*
* CDATE FILENAME
*
* 数当てを行う
*/
#include <stdio.h>
#include <time.h>
#include "s_print.h" /* s_print_int を利用するので.. */
#include "s_input.h" /* s_input_int を利用するので.. */
/*
* prompt
*/
int prompt(void) {
s_print_string ( "私が選んだ数を予想して入力してください : " );
return s_input_int(); /* キーボードから整数値を一つ読み込む(先読み) */
}
/*
*/
void game ( int input, int answer ) {
if ( input == answer ) {
s_print_string ( "お見事です。あたりました。\n" );
} else {
if ( input > answer ) {
/**BEGIN**/
s_print_string ( "その数は大きすぎます。\n" );
/**END**/
} else {
s_print_string ( "その数は小さすぎます。\n" );
}
game( prompt(), answer );
}
}
/*
* main
*/
int main( void )
{
time_t time;
ctime(&time);
srand ( time.utime );
s_print_int ( rand() );
s_print_string ( "私が考えた 1 〜 100 数を予想して当ててみてください。\n" );
game ( prompt(), (rand()%100) + 1 );
return 0;
}
/*
方針
問題は、乱数で生成する -> rand 関数を利用する
(rand()%100) + 1
rand() : 0 〜 3 万まで乱数
(rand()%100) : 0 〜 99 まで乱数
(rand()%100)+1 : 1 〜 100 まで乱数
人間に答を予想してもらって、その予想した整数値を入力し、
その結果を出力する
あたるまで、繰返し ( インプットループ )
ヒントとしては、大小関係を教える
*/
/*
* CDATE FILENAME
*
* 与えられた自然数の素因数を出力する
*
* 12 は..
*
*
*
*
*
*
*/
#include <stdio.h>
#include "s_print.h" /* s_print_int を利用するので.. */
/*
* void print_prime_factor_sequence ( int n, int p )
* 機能 : p 以上の n の素因数を小さい順に並べで表示する
* 条件 : n には p 未満の素因数を含まれていないものとする
* int n : p 未満の素因数を含まれていない自然数
* 返り値 : なし
*/
void print_prime_factor_sequence ( int n, int p ) {
if ( p > n ) { /* もう n には p 以上の素因数を含まない */
/* 何もしなくてよい */
/* 本来、ここにくるのは n = 1 の時だが、念の為 */
} else if ( n % p == 0 ) { /* n が p を素因数として含む */
s_print_char ( ' ' ); /* 隙間を空け */
s_print_int ( p ); /* 素因数を表示し */
/* もう一度 p の要素があるかもしれないので、そこから試す [再帰] */
n が p で割り切れるので、
n / p の素因数分解をするので
print_prime_factor_sequence ( n/p, 2 );
でもよいのだが...
すでに、p 未満の数では割り切れない事がわかっているから..
print_prime_factor_sequence ( n/p, ... );
/*
** この部分を完成させなさい
*/
} else { /* n が p を素因数として含まない */
/* 本来は p の次の素数を試すべきだが.. */
/* その代りに p + 1 を試す (のは無駄だが、正く動く) [再帰] */
/*
** この部分を完成させなさい
*/
print_prime_factor_sequence ( n, p + 1 );
}
}
/*
* void print_prime_factor_of ( int n )
* 機能 : n の素因数を出力する
* int n : 素因数を表示したい自然数
* 返り値 : なし
*/
void print_prime_factor_of ( int n ) {
if ( n < 1 ) { /* 与えらた数が自然数ではない */
s_print_int ( n );
s_print_string ( "は、自然数ではありません\n" );
} else if ( n == 1 ) { /* 与えられた数が 1 の場合 */
s_print_int ( n );
s_print_string ( "の素因数はありません\n" );
} else {
s_print_int ( n );
s_print_string ( "の素因数分解は" );
/*
** この部分を完成させなさい
*/
print_prime_factor_sequence ( n, ... ); /* ... の所は最初の素数 */
s_print_string ( " となります。\n" );
}
}
/*
* main
*/
int main( void )
{
print_prime_factor_of ( 12 );
return 0;
}
/*
print_prime_factor_of ( 12 );
-> 12 = 2^2 * 3^1
2 2 3
素因数は、どうやって求めるか ?
小さい方の素数から順にわってみる
割りきれたら、素因数として出力する
!!! 素数を作る必要がありそう...
-> (計算時間は無駄になるが..) 2 以上の自然数でわっていってよい
例 15 の場合 [A]
15 を 2 ( 最初の素数 )で、割ってみる
割り切れない
15 を 3 ( 2 の次の素数 ) で、割ってみる
割り切れ、商は 5 になる。
3 をプリント
5 を 3 ( 2 の次の素数 ) で、割ってみる
割り切れない
5 を 5 ( 3 の次の素数 ) で、割ってみる
割り切れ、商は 1 になる。
5 をプリント
1 は、これ以上、素因数をふくまないので、終わり
結果として、 3 5 が表示される
例 15 の場合 [B]
15 を 2 ( 最初の素数 )で、割ってみる
割り切れない
15 を 3 ( 2 の次の素数 ) で、割ってみる
割り切れ、商は 5 になる。
3 をプリント
5 を 3 ( 2 の次の素数 ) で、割ってみる
割り切れない
5 を 4 ( 3 の次の自然数 ) で、割ってみる
割り切れない
5 を 5 ( 4 の次の自然数 ) で、割ってみる
割り切れ、商は 1 になる。
5 をプリント
1 は、これ以上、素因数をふくまないので、終わり
結果として、 3 5 が表示される
! 本来なら、小さい方の素数から割るのが正しい(定義通り)
! しかし、小さい方の自然数から割っても、同じ結果がえられる
! 無駄な事をするので時間が余分にかかる
! その代わりに、「分かり易く」なっている
!! この二つの異るやり方が、同じ結果になる事は、
!! 「数学的に証明する」
!! 必要がある(できる)
*/
#include <stdio.h>
#include "s_print.h"
/*
関数の作り方
基本は、プログラムの一部に名前をつける
関数定義
関数の頭部＋関数の体部
関数の体部：名前をつけたいプログラムの断片
関数の頭部：関数の名前＋関数の型
関数の型：どんな引数をもち、どんな値を返すか
具体例:
二つの整数値を引数にして、その和を値として返す関数
前回の課題
*/
int add ( int a, int b ) {
/*
add ; 関数の名前
add の前の int は、add 返す値の型
今回の場合は、int が指定されているので、整数値を返す
add の後ろの ( int a, int b ) は add の引数の型
引数は、二つあって、共に整数値を指定
*/
return a + b;
/* 関数で名前をつけている部分
「return 式」で、式の値を関数の値として返す
*/
}
int main(void)
{
s_print_int ( add ( 1, 3 ) );
/*
add ( 1, 3 ) で、「1+3=4」が計算され、4 が値
として返るので、画面に、4が表示される
*/
return 0;
}
/*
* 整数の絶対値を計算する関数
*/
int abs ( int x ) {
/* x が非負なら、xの値を、そうでなければ、符号かえた値を返す */
if ( x >= 0 ) { /* x が非負 */
return x; /* x の値をそのまま返す */
} else { /* そうでない場合は、x が負の数なので... */
return x * (-1); /* -1 をかけると、符号がかわる */
/* -x としても同じ意味 */
}
}
/*
* 整数の符号返す
* 正の時は 1
* 負の時は -1
* 零の時は 0
*/
int sign ( int x ) {
if ( x > 0 ) { /* まず、正かどうかを調べる */
return 1; /* 正だったら 1 を返す */
} else { /* 零か、負 */
if ( x < 0 ) { /* 次に、負かどうかを調べる */
return -1; /* 負の場合は -1 を返す */
} else { /* ここにくるのは、零の時のみ */
return 0;
}
}
/* ここにくる事はない */
}
int sign2 ( int x ) {
if ( x > 0 ) {
return 1;
} else if ( x < 0 ) { /* else-if 形式 */
return -1;
} else {
return 0;
}
}
/* else-if の例 */
/* トランプの役札の判定 (絵札 : 1, 10, 11(J), 12(Q), 13(K) */
/* 役札の場合は 1 を、そうでない場合は 0 を返す */
int yakufuda ( int fuda ) {
if ( fuda == 1 ) { /* A なので、役札 */
return 1;
} else if ( fuda == 10 ) { /* 10 なので、役札 */
return 1;
} else if ( fuda == 11 ) { /* 11 なので、役札 */
return 1;
} else if ( fuda == 12 ) { /* 12 なので、役札 */
return 1;
} else if ( fuda == 13 ) { /* 13 なので、役札 */
return 1;
} else { /* 以上で、絵札は尽したので、残るは.. */
return 0; /* 絵札ではない */
}
}
/* 参考 */
int yakufuda2 ( int fuda ) {
if ( fuda == 1 ) { /* A なので、役札 */
return 1;
} else {
if ( fuda == 10 ) { /* 10 なので、役札 */
return 1;
} else {
if ( fuda == 11 ) { /* 11 なので、役札 */
return 1;
} else {
if ( fuda == 12 ) { /* 12 なので、役札 */
return 1;
} else {
if ( fuda == 13 ) { /* 13 なので、役札 */
return 1;
} else { /* 以上で、絵札は尽したので、残るは.. */
return 0; /* 絵札ではない */
}
}
}
}
}
}
#include <stdio.h>
/*
myprintf ( "abc" );
-> 画面に「abc」が出力される
*/
void myprintf ( char *string ) {
if ( *string == '\0' ) {
/* 文字列は全て出力したので、もうやることはない */
} else {
putchar ( *string ); /* 文字列の先頭の一文字を出力 */
myprintf ( string + 1 ); /* 残りは、再帰呼出で.. */
}
}
/*
myprintf ( "abc" );
# myprintf という関数が呼び出されるので、
# その定義が利用される
->
string : "abc"
myprintf ( string )
->
string : "abc"
if ( *string == '\0' ) {
} else {
putchar ( *string );
myprintf ( string + 1 );
}
->
string : "abc" "abc" : { 'a', 'b', 'c', '\0' }
if ( *"abc" == '\0' ) { *"abc" : 'a'
} else {
putchar ( *"abc" );
myprintf ( "abc" + 1 );
}
->
putchar ( *"abc" ); : a が出力
myprintf ( "bc" ); : ここで、もし bc が出力されるなら、上 a と併せて
: 目的の abc 出力ができる事になる
<<ポイント>>
再帰呼出を利用する事によって、
同じ命令を(必要な回数だけ)繰り返す事ができる
例 : 上記の場合は putchar が何度も呼び出される
*/
パターン
X を繰り返す関数 loopX を作るには、
loopX() {
if ( ) { 終了条件
} else {
X;
loopX();
}
}
#include <stdio.h>
#include "s_print.h"
/*
1 から、引数 n までの整数の二乗和を計算する関数
squreSum ( n ) = 1^2 + 2^2 + .. + n^2
考え方
squreSum ( n )
= 1^2 + 2^2 + .. + (n-1)^2 + n^2
= (1^2 + 2^2 + .. + (n-1)^2 ) + n^2
= squreSum ( n-1 ) + n^2
再帰を利用する(足し算の「繰返し」なので、「再帰」)
後は、終了条件 ( n が 0 の時は、直接計算できる )
squreSum ( 0 ) = 0
関数の型
引数として、一つの整数値 (n)をとり、結果として整数値を返す
*/
int squreSum ( int n ) {
if ( n <= 0 ) {
return 0;
}else{
return squreSum ( n - 1 ) + (n*n);
}
}
int main(void) {
s_print_int ( squreSum ( 5 ) ); /* 5^2 + 4^2 + 3^2 + 2^2 + 1^2 = 55 ? */
return 0;
}
#include <stdio.h>
/*
入力ループ
すこしずつ入力をしながら処理をして、すこしずつ出力を作る
入力 -(データ)--------> *
|
人間 処理(計算) プログラム
v
出力 <-(データ)--------- *
一つ入力、一つ処理、一つ出力
上記のパターンを連続的に、繰り返したい
「入力された一行(改行まで)文字列の小文字を全て大文字する」
プログラムを、
文字の入力、処理、出力の繰返し
で実現したい。
*/
void toUpperLoop ( char ch ) {
if ( ch == '@' ) { /* 改行だったら */
/* 一行分処理し終ったので、その改行を出力して、終わり */
putchar ( ch );
} else { /* 小文字 ( 'a' <~ ch <= 'z' ) を大文字にして出力する作業必要 */
if ( ch < 'a' ) { /* 小文字でない */
putchar ( ch ); /* そのまま出す */
} else if ( 'z' < ch ) { /* 小文字でない */
putchar ( ch ); /* そのまま出す */
} else { /* ここにくるのは、 'a' <= ch <= 'z' なので、小文字 */
putchar ( ch - 'a' + 'A' );
}
toUpperLoop ( getchar() ); /* 次文字を読みだして、再帰 */
}
}
int main(void){
toUpperLoop ( getchar() ); /* 次文字を読みだ(先読み)して、関数を呼ぶ */
return 0;
}
/*
inputLoop ( char ch ) {
if ( ) {
} else {
inputLoop ( getchar() );
}
}
int main(void) {
inputLoop ( getchar() );
}
*/
#include <stdio.h>
#include <stdlib.h> /* rand 関数を使うために.. */
#include "s_print.h"
int main ( void ) {
s_print_string ( "1 回数目 : " );
s_print_int ( rand() ); /* rand() は乱数関数 : 呼び出す度に、異る乱数値を返す */
s_print_newline();
s_print_string ( "2 回数目 : " );
s_print_int ( rand() );
s_print_newline();
s_print_string ( "3 回数目 : " );
s_print_int ( rand() );
s_print_newline();
return 0;
}
#include <stdio.h>
#include <stdlib.h> /* rand 関数を使うために.. */
#include "s_print.h"
void printRadomNumberLoop ( char ch ) {
if ( ch == '@' ) {
printf ( "終了\n" );
} else {
s_print_int ( rand() );
s_print_newline();
printRadomNumberLoop ( getchar() );
}
}
int main ( void ) {
printRadomNumberLoop ( getchar() );
return 0;
}
/*
* CDATE FILENAME
*
* 数当てを行う
*/
#include <stdio.h>
#include "s_print.h" /* s_print_int を利用するので.. */
#include "s_input.h" /* s_input_int を利用するので.. */
/*
* prompt
*/
int prompt(void) {
s_print_string ( "私が選んだ数を予想して入力してください : " );
return s_input_int(); /* キーボードから整数値を一つ読み込む(先読み) */
}
/*
*/
void game ( int input, int answer ) {
if ( input == answer ) {
s_print_string ( "お見事です。あたりました。\n" );
} else {
if ( input > answer ) {
/* ここを完成しなさい */
} else {
s_print_string ( "その数は小さすぎます。\n" );
}
game( prompt(), answer );
}
}
/*
* main
*/
int main( void )
{
s_print_string ( "私が考えた 1 〜 100 数を予想して当ててみてください。\n" );
game ( prompt(), (rand()%100) + 1 );
return 0;
}
/*
方針
問題は、乱数で生成する -> rand 関数を利用する
(rand()%100) + 1
rand() : 0 〜 3 万まで乱数
(rand()%100) : 0 〜 99 まで乱数
(rand()%100)+1 : 1 〜 100 まで乱数
人間に答を予想してもらって、その予想した整数値を入力し、
その結果を出力する
あたるまで、繰返し ( インプットループ )
ヒントとしては、大小関係を教える
*/
123ABCxyz$$$ 123ABCxyz$$$ 123ABCxyz$$$ 123ABCxyz$$$ @
else 節の内容が空っぽの時は、「else {} 」となるが、その場合は、省略可能
if ( x > 0 ) {
printf ( "正\n" );
} else {
/* 空っぽ */
}
の場合は、
if ( x > 0 ) {
printf ( "正\n" );
}
だけで良い。
<<次回>>
srand の話をする
123ABCXYZ$$$ 123ABCXYZ$$$ 123ABCXYZ$$$ 123ABCXYZ$$$ @
課題プログラム内の「/*名前:ここ*/」の部分を書き換え「/*この部分を完成させなさい*/」の部分にプログラムを追加して、プログラムを完成させます。
Download : 20150612-01.c ( SJIS 版 )
/*
* CDATE FILENAME
*
* 数当てを行う
*/
#include <stdio.h>
#include "s_print.h" /* s_print_int を利用するので.. */
#include "s_input.h" /* s_input_int を利用するので.. */
/*
* prompt
* メッセージを出力し、キーボードから整数値を読み込んで、
* その値を返す関数
*/
int prompt(void) {
s_print_string ( "私が選んだ数を予想して入力してください : " );
return s_input_int();
}
/*
*/
void game ( int input, int answer ) {
if ( input == answer ) { /* 入力と答えが一致した */
s_print_string ( "お見事です。あたりました。\n" );
} else {
if ( input > answer ) { /* 入力が、答えより大きい */
/*
** この部分を完成させなさい
*/
} else { /* 入力が、答えより小さい */
s_print_string ( "その数は小さすぎます。\n" );
}
/* 未だ、答えが、当っていないので、ゲームを続ける.. */
/*
** この部分を完成させなさい
*/
}
}
/*
* main
*/
int main( void )
{
s_print_string ( "私が考えた 1 〜 100 数を予想して当ててみてください。\n" );
game ( prompt(), (rand()%100) + 1 );
return 0;
}
50 75 83 90 85 84
$ ./20150612-01-QQQQ.exe 私が考えた 1 〜 100 数を予想して当ててみてください。 私が選んだ数を予想して入力してください : 50 その数は小さすぎます。 私が選んだ数を予想して入力してください : 75 その数は小さすぎます。 私が選んだ数を予想して入力してください : 83 その数は小さすぎます。 私が選んだ数を予想して入力してください : 90 その数は大きすぎます。 私が選んだ数を予想して入力してください : 85 その数は大きすぎます。 私が選んだ数を予想して入力してください : 84 お見事です。あたりました。 $
Download : 20150612-02.c ( SJIS 版 )
/*
* CDATE FILENAME
*
* 与えられた自然数の素因数を出力する
*
* 12 は..
*
*
*
*
*
*
*/
#include <stdio.h>
#include "s_print.h" /* s_print_int を利用するので.. */
/*
* void print_prime_factor_sequence ( int n, int p )
* 機能 : p 以上の n の素因数を小さい順に並べで表示する
* 条件 : n には p 未満の素因数を含まれていないものとする
* int n : p 未満の素因数を含まれていない自然数
* 返り値 : なし
*/
void print_prime_factor_sequence ( int n, int p ) {
if ( p > n ) { /* もう n には p 以上の素因数を含まない */
/* 何もしなくてよい */
/* 本来、ここにくるのは n = 1 の時だが、念の為 */
} else if ( n % p == 0 ) { /* n が p を素因数として含む */
s_print_char ( ' ' ); /* 隙間を空け */
s_print_int ( p ); /* 素因数を表示し */
/* もう一度 p の要素があるかもしれないので、そこから試す [再帰] */
/*
** この部分を完成させなさい
*/
} else { /* n が p を素因数として含まない */
/* 本来は p の次の素数を試すべきだが.. */
/* その代りに p + 1 を試す (のは無駄だが、正く動く) [再帰] */
/*
** この部分を完成させなさい
*/
}
}
/*
* void print_prime_factor_of ( int n )
* 機能 : n の素因数を出力する
* int n : 素因数を表示したい自然数
* 返り値 : なし
*/
void print_prime_factor_of ( int n ) {
if ( n < 1 ) { /* 与えらた数が自然数ではない */
s_print_int ( n );
s_print_string ( "は、自然数ではありません\n" );
} else if ( n == 1 ) { /* 与えられた数が 1 の場合 */
s_print_int ( n );
s_print_string ( "の素因数はありません\n" );
} else {
s_print_int ( n );
s_print_string ( "の素因数分解は" );
/*
** この部分を完成させなさい
*/
s_print_string ( " となります。\n" );
}
}
/*
* main
*/
int main( void )
{
print_prime_factor_of ( 12 );
return 0;
}
abc123
$ ./20150612-02-QQQQ.exe 12の素因数分解は 2 2 3 となります。 $