当日のOHP資料です。
Download : sample-001.c ( SJIS 版 )
/*
* 2012/11/09 sample-001.c
*
* 一次方程式 ( a x + b = c ) の解を、虱潰し法で解く
* ただし、解は、一桁の自然数
*
*/
#include <stdio.h>
/*
*
*/
#define YES 1
#define NO 0
/*
* a x + b = c ? : 論理式 P に相当する
*/
int check_formula ( int a, int b, int c, int x ) {
if ( a * x + b == c ) { /* 方程式を満すか ? */
return YES;
}
return NO;
}
/*
* 方程式 a x + b = c の解を、x_min 〜 x_max の範囲で探す
* 見付かったら、その値を返す
* もし見付からなかったら、範囲外の数 ( x_max + 1 ) を返す
*/
int solve_formal ( int a, int b, int c, int x_min, int x_max ) {
int x;
for ( x = x_min; x <= x_max; x++ ) { /* x = x_min 〜 x_max */
if ( check_formula ( a, b, c, x ) == YES ) { /* 見付かった */
return x; /* その値を返す */
}
}
/*
* 見付からなかったので..
*/
return x_max + 1; /* 範囲の外である数を返す */
}
/*
* a x + b = c の整数解を求める
*/
int main ( void ) {
int a;
int b;
int c; /* a x + b = c の a, b, c */
int x_min;
int x_max; /* F = { x | x_min <= x <= x_max } */
int x; /* 答の候補 */
/*
* [Input]
*/
/*
* P(x) == (a x + b = c)
*/
printf ( "方程式 a x + b = c の整数解を搜します。\n" );
printf ( " a の値を入力してください : " );
scanf ( "%d", &a );
printf ( " b の値を入力してください : " );
scanf ( "%d", &b );
printf ( " c の値を入力してください : " );
scanf ( "%d", &c );
/*
* F = { x | x_min <= x <= x_max }
*/
printf ( "x の取り得る範囲を指定してください\n" );
printf ( "\t最小値 : " );
scanf ( "%d", &x_min );
printf ( "\t最大値 : " );
scanf ( "%d", &x_max );
/*
* [Process]
*/
/*
* 「 \exists x \in F[P(x)] 」の探索による証明
*/
x = solve_formal ( a, b, c, x_min, x_max );
/*
* [Output]
*/
if ( x > x_max ) {
printf ( "方程式 %d x + %d = %d の解を %d 〜 %d の範囲の整数からは見つける事ができませんでした。\n", a, \
b, c, x_min, x_max );
} else { /* 答が見つかった */
printf ( "方程式 %d x + %d = %d の解は %d です。\n", a, b, c, x );
}
/*
*
*/
return 0;
}
/*
*
*/
2 3 7 -1 8
C:\usr\c>sample-001< sample-001.in 方程式 a x + b = c の整数解を搜します。 a の値を入力してください : 2 b の値を入力してください : 3 c の値を入力してください : 7 x の取り得る範囲を指定してください 最小値 : -1 最大値 : 8 方程式 2 x + 3 = 7 の解は 2 です。 C:\usr\c>
Download : sample-002.c ( SJIS 版 )
/*
* 2012/11/09 sample-002.c
*
* 二つの自然数 m, n の最大公約数 g=gcd(m,n) を求める
*
*/
#include <stdio.h>
/*
*
*/
#define YES 1
#define NO 0
/*
* min(n,m) は m と n の大きくない方を値として返す
*/
int min ( int n, int m ) {
/*
* n と m の大きくない方を返す
*/
if ( n > m ) { /* m が n より小さい */
return m; /* m を返す */
}
/*
* ここでは、n > m でない、つまり、 n <= m となる
*/
return n; /* n を返せばよい ( n == m の時も n でよい ) */
}
/*
* x が m, n の公約数であれば、YES を、そうでなければ NO を返す
*/
int is_common_divisor ( int n, int m, int x ) {
/*
* x は n と m の公約数か ?
*/
if ( n % x != 0 ) { /* n は x で割り切れない */
return NO; /* n の約数でないから、公約数でない */
}
if ( m % x != 0 ) { /* m は x で割り切れない */
return NO; /* m の約数でないから、公約数でない */
}
/* x は n の約数であり、m の約数であるので、公約数 */
return YES;
}
/*
* n, m の最大公約数を返す
*/
int gcd ( int n, int m ) {
/*
* n と m の最大公約数は、n, m の双方より大きくなく、かつ公約数で最大の物
*/
int g; /* 最大公約数の候補 */
/*
* g の取り得る範囲 (F)
* F = { g | 1 <= g <= min(m,n) }
*/
for ( g = min(n,m); g > 1; g-- ) { /* min(m,n) から 2 まで.. */
/*
* P に相当する ( 「最大」という条件は「探す順」で決る )
*/
if ( is_common_divisor ( n, m, g ) == YES ) { /* 公約数だった */
return g; /* 最初に見付かったものが最大 */
}
}
return 1; /* 1 より大きい公約数がない場合は m,n は素 */
}
/*
*
*/
int main ( void ) {
int n;
int m;
int g;
/*
* [Input]
*/
printf ( "二つの自然数 n, m の最大公約数 g = gcd(n,m) を求めます\n" );
printf ( " n の値を入力してください : " );
scanf ( "%d", &n );
printf ( " m の値を入力してください : " );
scanf ( "%d", &m );
/*
* [Process]
*/
g = gcd ( n, m );
/*
* [Output]
*/
printf ( " %d と %d の最大公約数は %d です。\n", n, m, g );
/*
*
*/
return 0;
}
/*
*
*/
12 18
C:\usr\c>sample-002< sample-002.in 二つの自然数 n, m の最大公約数 g = gcd(n,m) を求めます n の値を入力してください : 12 m の値を入力してください : 18 12 と 18 の最大公約数は 6 です。 C:\usr\c>
Download : sample-003.c ( SJIS 版 )
/*
* 2012/11/09 sample-003.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」を解く
*
*/
#include <stdio.h>
/*
*
*/
#define YES 1
#define NO 0
/*
* 答の候補 pi, yo, hi, ko の値が答になっていれば、
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「P」の部分
*
*/
int calc_check ( int pi, int yo, int hi, int ko ) {
int piyo; /* ぴよ */
int hiyoko; /* ひよこ */
/*
* (条件 1) ピとヒは、数値の先頭なので、零にならない
*/
/* 「ぴ」は先頭なので 0 だと駄目 */
if ( pi == 0 ) {
return NO;
}
/* 「ひ」は先頭なので 0 だと駄目 */
if ( hi == 0 ) {
return NO;
}
/*
* (条件 2) ピ、ヨ、ヒ、コは互いに異る
*/
/* 「ぴ」と「ひ」は別 */
if ( pi == hi ) {
return NO;
}
/* 「ぴ」と「よ」は別 */
if ( pi == yo ) {
return NO;
}
/* 「ぴ」と「こ」は別 */
if ( pi == ko ) {
return NO;
}
/* 「ひ」と「よ」は別 */
if ( hi == yo ) {
return NO;
}
/* 「ひ」と「こ」は別 */
if ( hi == ko ) {
return NO;
}
/* 「よ」と「こ」は別 */
if ( yo == ko ) {
return NO;
}
/*
* (条件 3) 「ピ*10+ヨ」+「ピ*10+ヨ」=「ヒ*100+ヨ*10+コ」
*/
piyo = pi * 10 + yo; /* 「ぴよ」を求める */
hiyoko = hi * 100 + yo * 10 + ko; /* 「ひよこ」を求める */
if ( piyo + piyo == hiyoko ) { /* 計算があっていれば */
printf ( "ぴ = %d, ひ = %d, よ = %d, こ = %d\n",
pi, hi, yo, ko );
printf ( "%d + %d = %d\n", piyo, piyo, hiyoko );
/* 答を出力して.. */
return YES; /* YES を返す */
}
return NO; /* そうでなければ NO を返す */
}
/*
* 「こ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「こ」を探す
* 次がなければ NO を返す
*/
int find_ko ( int pi, int hi, int yo, int ko ) {
/* 現在の「こ」は答か */
if ( calc_check ( pi, hi, yo, ko ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( ko < 9 ) { /* 次の候補があれば */
return find_ko ( pi, hi, yo, ko + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
/*
* 「よ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「よ」を探す
* 次がなければ NO を返す
*/
int find_yo ( int pi, int hi, int yo ) {
/* 現在の「よ」は答か */
if ( find_ko ( pi, hi, yo, 0 ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( yo < 9 ) { /* 次の候補があれば */
return find_yo ( pi, hi, yo + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
/*
* 「ひ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「ひ」を探す
* 次がなければ NO を返す
*/
int find_hi ( int pi, int hi ) {
/* 現在の「ひ」は答か */
if ( find_yo ( pi, hi, 0 ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( hi < 9 ) { /* 次の候補があれば */
return find_hi ( pi, hi + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
/*
* 「ぴ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「ぴ」を探す
* 次がなければ NO を返す
*/
int find_pi ( int pi ) {
/* 現在の「ぴ」は答か */
if ( find_hi ( pi, 0 ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( pi < 9 ) { /* 次の候補があれば */
return find_pi ( pi + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
/*
*
*/
int main ( void ) {
/*
*
*/
printf ( "問 : ぴよ + ぴよ = ひよこ\n" ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find_pi ( 0 ) == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
987
C:\usr\c>sample-003< sample-003.in 問 : ぴよ + ぴよ = ひよこ ぴ = 6, ひ = 1, よ = 2, こ = 4 62 + 62 = 124 解けた C:\usr\c>
Download : sample-004-01.c ( SJIS 版 )
/*
* 2012/11/09 sample-004-01.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の条件式
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
* 答の候補 pi, yo, hi, ko の値が答になっていれば、
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「P」の部分
*
*/
int calc_check ( int pi, int yo, int hi, int ko ) {
int piyo; /* ぴよ */
int hiyoko; /* ひよこ */
/*
* (条件 1) ピとヒは、数値の先頭なので、零にならない
*/
/* 「ぴ」は先頭なので 0 だと駄目 */
if ( pi == 0 ) {
return NO;
}
/* 「ひ」は先頭なので 0 だと駄目 */
if ( hi == 0 ) {
return NO;
}
/*
* (条件 2) ピ、ヨ、ヒ、コは互いに異る
*/
/* 「ぴ」と「ひ」は別 */
if ( pi == hi ) {
return NO;
}
/* 「ぴ」と「よ」は別 */
if ( pi == yo ) {
return NO;
}
/* 「ぴ」と「こ」は別 */
if ( pi == ko ) {
return NO;
}
/* 「ひ」と「よ」は別 */
if ( hi == yo ) {
return NO;
}
/* 「ひ」と「こ」は別 */
if ( hi == ko ) {
return NO;
}
/* 「よ」と「こ」は別 */
if ( yo == ko ) {
return NO;
}
/*
* (条件 3) 「ピ*10+ヨ」+「ピ*10+ヨ」=「ヒ*100+ヨ*10+コ」
*/
piyo = pi * 10 + yo; /* 「ぴよ」を求める */
hiyoko = hi * 100 + yo * 10 + ko; /* 「ひよこ」を求める */
if ( piyo + piyo == hiyoko ) { /* 計算があっていれば */
printf ( "ぴ = %d, ひ = %d, よ = %d, こ = %d\n",
pi, hi, yo, ko );
printf ( "%d + %d = %d\n", piyo, piyo, hiyoko );
/* 答を出力して.. */
return YES; /* YES を返す */
}
return NO; /* そうでなければ NO を返す */
}
Download : sample-004-02.c ( SJIS 版 )
/*
* 2012/11/09 sample-004-02.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の「こ」の探索
*
*/
#include "hiyoko.h"
/*
* 「こ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「こ」を探す
* 次がなければ NO を返す
*/
int find_ko ( int pi, int hi, int yo, int ko ) {
/* 現在の「こ」は答か */
if ( calc_check ( pi, hi, yo, ko ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( ko < 9 ) { /* 次の候補があれば */
return find_ko ( pi, hi, yo, ko + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
Download : sample-004-03.c ( SJIS 版 )
/*
* 2012/11/09 sample-004-03.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の「よ」の探索
*
*/
#include "hiyoko.h"
/*
* 「よ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「よ」を探す
* 次がなければ NO を返す
*/
int find_yo ( int pi, int hi, int yo ) {
/* 現在の「よ」は答か */
if ( find_ko ( pi, hi, yo, 0 ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( yo < 9 ) { /* 次の候補があれば */
return find_yo ( pi, hi, yo + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
Download : sample-004-04.c ( SJIS 版 )
/*
* 2012/11/09 sample-004-04.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の「ひ」の探索
*
*/
#include "hiyoko.h"
/*
* 「ひ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「ひ」を探す
* 次がなければ NO を返す
*/
int find_hi ( int pi, int hi ) {
/* 現在の「ひ」は答か */
if ( find_yo ( pi, hi, 0 ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( hi < 9 ) { /* 次の候補があれば */
return find_hi ( pi, hi + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
Download : sample-004-05.c ( SJIS 版 )
/*
* 2012/11/09 sample-004-05.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の「ひ」の探索
*
*/
#include "hiyoko.h"
/*
* 「ぴ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「ぴ」を探す
* 次がなければ NO を返す
*/
int find_pi ( int pi ) {
/* 現在の「ぴ」は答か */
if ( find_hi ( pi, 0 ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( pi < 9 ) { /* 次の候補があれば */
return find_pi ( pi + 1 ); /* 次を try */
}
return NO; /* そうでなければ NO */
}
Download : sample-004.c ( SJIS 版 )
/*
* 2012/11/09 sample-004.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」を解く
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
*
*/
int main ( void ) {
/*
*
*/
printf ( "問 : ぴよ + ぴよ = ひよこ\n" ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find_pi ( 0 ) == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
C:\usr\c>sample-004 問 : ぴよ + ぴよ = ひよこ ぴ = 6, ひ = 1, よ = 2, こ = 4 62 + 62 = 124 解けた C:\usr\c>
Download : hiyoko.h ( SJIS 版 )
/* * 2012/11/09 hiyoko.h */ #define YES 1 #define NO 0 /* * */ extern int calc_check ( int pi, int yo, int hi, int ko ); extern int find_ko ( int pi, int hi, int yo, int ko ); extern int find_yo ( int pi, int hi, int yo ); extern int find_hi ( int pi, int hi ); extern int find_pi ( int pi ); /* * */
Download : makefile.mf
Download : sample-005-01.c ( SJIS 版 )
/*
* 2012/11/09 sample-005-01.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の条件式
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
* 答の候補 pi, yo, hi, ko の値が答になっていれば、
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「P」の部分
*
*/
int calc_check ( int pi, int yo, int hi, int ko ) {
int piyo; /* ぴよ */
int hiyoko; /* ひよこ */
/*
* (条件 1) ピとヒは、数値の先頭なので、零にならない
*/
/* 「ぴ」は先頭なので 0 だと駄目 */
if ( pi == 0 ) {
return NO;
}
/* 「ひ」は先頭なので 0 だと駄目 */
if ( hi == 0 ) {
return NO;
}
/*
* (条件 2) ピ、ヨ、ヒ、コは互いに異る
*/
/* 「ぴ」と「ひ」は別 */
if ( pi == hi ) {
return NO;
}
/* 「ぴ」と「よ」は別 */
if ( pi == yo ) {
return NO;
}
/* 「ぴ」と「こ」は別 */
if ( pi == ko ) {
return NO;
}
/* 「ひ」と「よ」は別 */
if ( hi == yo ) {
return NO;
}
/* 「ひ」と「こ」は別 */
if ( hi == ko ) {
return NO;
}
/* 「よ」と「こ」は別 */
if ( yo == ko ) {
return NO;
}
/*
* (条件 3) 「ピ*10+ヨ」+「ピ*10+ヨ」=「ヒ*100+ヨ*10+コ」
*/
piyo = pi * 10 + yo; /* 「ぴよ」を求める */
hiyoko = hi * 100 + yo * 10 + ko; /* 「ひよこ」を求める */
if ( piyo + piyo == hiyoko ) { /* 計算があっていれば */
printf ( "ぴ = %d, ひ = %d, よ = %d, こ = %d\n",
pi, hi, yo, ko );
printf ( "%d + %d = %d\n", piyo, piyo, hiyoko );
/* 答を出力して.. */
return YES; /* YES を返す */
}
return NO; /* そうでなければ NO を返す */
}
Download : sample-005-02.c ( SJIS 版 )
/*
* 2012/11/09 sample-005-02.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」を for 文で解く
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
* 答の候補 pi, yo, hi, ko の値を for 文で検索し、答えがあれば
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「F」の部分
*
*/
int find ( void ) {
int pi;
int yo;
int hi;
int ko;
for ( pi = 0; pi < 10; pi++ ) {
for ( yo = 0; yo < 10; yo++ ) {
for ( hi = 0; hi < 10; hi++ ) {
for ( ko = 0; ko < 10; ko++ ) {
if ( calc_check ( pi, yo, hi, ko ) == YES ) {
return YES;
}
}
}
}
}
return NO; /* そうでなければ NO を返す */
}
Download : sample-005.c ( SJIS 版 )
/*
* 2012/11/09 sample-005.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」を解く (for 版)
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
*
*/
int main ( void ) {
/*
*
*/
printf ( "問 : ぴよ + ぴよ = ひよこ\n" ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find () == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
C:\usr\c>sample-005 問 : ぴよ + ぴよ = ひよこ ぴ = 6, ひ = 1, よ = 2, こ = 4 62 + 62 = 124 解けた C:\usr\c>
Download : hiyoko.h ( SJIS 版 )
/* * 2012/11/09 hiyoko.h */ #define YES 1 #define NO 0 /* * */ extern int calc_check ( int pi, int yo, int hi, int ko ); extern int find(); /* * */
Download : makefile.mf
Download : sample-006-01.c ( SJIS 版 )
/*
* 2012/11/09 sample-006-01.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」の条件式 (配列版)
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
* 答の候補 pi, yo, hi, ko の値が答になっていれば、
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「P」の部分
*
* ピ : x[PI]
* ヨ : x[YO]
* ヒ : x[HI]
* コ : x[KO]
*
*/
int calc_check ( int x[], int size ) {
int piyo; /* ぴよ */
int hiyoko; /* ひよこ */
int i;
int j;
/*
* (条件 1) ピとヒは、数値の先頭なので、零にならない
*/
/* 「ぴ」は先頭なので 0 だと駄目 */
if ( x[PI] == 0 ) {
return NO;
}
/* 「ひ」は先頭なので 0 だと駄目 */
if ( x[HI] == 0 ) {
return NO;
}
/*
* (条件 2) ピ、ヨ、ヒ、コは互いに異る
*/
for ( i = 0; i < size; i++ ) {
for ( j = i + 1; j < size; j++ ) {
if ( x[i] == x[j] ) {
return NO;
}
}
}
/*
* (条件 3) 「ピ*10+ヨ」+「ピ*10+ヨ」=「ヒ*100+ヨ*10+コ」
*/
piyo = x[PI] * 10 + x[YO]; /* 「ぴよ」を求める */
hiyoko = x[HI] * 100 + x[YO] * 10 + x[KO]; /* 「ひよこ」を求める */
if ( piyo + piyo == hiyoko ) { /* 計算があっていれば */
printf ( "ぴ = %d, ひ = %d, よ = %d, こ = %d\n",
x[PI], x[HI], x[YO], x[KO] );
printf ( "%d + %d = %d\n", piyo, piyo, hiyoko );
/* 答を出力して.. */
return YES; /* YES を返す */
}
return NO; /* そうでなければ NO を返す */
}
Download : sample-006-02.c ( SJIS 版 )
/*
* 2012/11/09 sample-006-02.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」を同一の再帰で解く
*
*/
#include "hiyoko.h"
/*
*
*/
int find_n ( int x[], int k, int size ) {
int i;
if ( k < size ) {
for ( i = 0; i < 10; i++ ) {
x[k] = i;
if ( find_n ( x, k + 1, size ) == YES ) {
return YES;
}
}
} else {
return calc_check ( x, size );
}
return NO;
}
/*
* 答の候補 pi, yo, hi, ko の値を for 文で検索し、答えがあれば
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「F」の部分
*
*/
int find ( void ) {
int x[4];
return find_n ( x, 0, 4 );
}
Download : sample-006.c ( SJIS 版 )
/*
* 2012/11/09 sample-006.c
*
* 覆面算の「ぴよ＋ぴよ＝ひよこ」を解く (for 版)
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
*
*/
int main ( void ) {
/*
*
*/
printf ( "問 : ピヨ + ピヨ = ヒヨコ\n" ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find() == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
C:\usr\c>sample-006 問 : ピヨ + ピヨ = ヒヨコ ぴ = 6, ひ = 1, よ = 2, こ = 4 62 + 62 = 124 解けた C:\usr\c>
Download : hiyoko.h ( SJIS 版 )
/* * 2012/11/09 hiyoko.h */ #define YES 1 #define NO 0 /* * */ #define PI 0 #define YO 1 #define HI 2 #define KO 3 /* * */ extern int calc_check ( int x[], int size ); extern int find(void); /* * */
Download : makefile.mf
Download : sample-007-01.c ( SJIS 版 )
/*
* 2012/11/09 sample-007-01.c
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
* 数の並びから十進数を計算する
*/
int ten ( int a[], int as, int x[] ) {
int i;
int v = 0;
for ( i = 0; i < as; i++ ) {
v = v * 10 + x[a[i]];
}
return v;
}
/*
* 答の候補 x[] が条件を満していれば
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 A+B=C
*
*/
int calc_check (
char n[], int size, /* 文字の名前 */
int a[], int sa, /* 足される数の個々の桁の番号の配列とサイズ */
int b[], int sb, /* 足す数の個々の桁の番号の配列とサイズ */
int c[], int sc, /* 和の数の個々の桁の番号の配列とサイズ */
int x[] /* 答の候補 */
) {
int va; /* 足される数 */
int vb; /* 足す数 */
int vc; /* 和 */
int i;
int j;
/*
* (条件 1) 個々の数の先頭は 0 でない
*/
if ( x[a[0]] == 0 ) {
return NO;
}
if ( x[b[0]] == 0 ) {
return NO;
}
if ( x[c[0]] == 0 ) {
return NO;
}
/*
* (条件 2) x[i] は互いに異る
*/
for ( i = 0; i < size; i++ ) {
for ( j = i + 1; j < size; j++ ) {
if ( x[i] == x[j] ) {
return NO;
}
}
}
va = ten( a, sa, x );
vb = ten( b, sb, x );
vc = ten( c, sc, x );
if ( va + vb == vc ) {
for ( i = 0; i < size; i++ ) {
printf ( "%c = %d", n[i], x[i] );
if ( i < size - 1 ) {
printf ( ", " );
} else {
printf ( "\n" );
}
}
printf ( "%d + %d = %d\n", va, vb, vc );
/* 答を出力して.. */
return YES; /* YES を返す */
}
return NO; /* そうでなければ NO を返す */
}
Download : sample-007-02.c ( SJIS 版 )
/*
* 2012/11/09 sample-007-02.c
*
*/
#include "hiyoko.h"
/*
*
*/
int find_n ( int x[], int k, int size ) {
int i;
int piyo[] = { PI, YO }; /* piyo */
int hiyoko[] = { HI, YO, KO }; /* hiyoko */
if ( k < size ) {
for ( i = 0; i < 10; i++ ) {
x[k] = i;
if ( find_n ( x, k + 1, size ) == YES ) {
return YES;
}
}
} else {
return calc_check ( "pyhk", 4, piyo, 2, piyo, 2, hiyoko, 3, x );
}
return NO;
}
/*
* 答の候補 pi, yo, hi, ko の値を for 文で検索し、答えがあれば
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 (「ピヨ＋ピヨ＝ヒヨコ」) の条件「F」の部分
*
*/
int find ( void ) {
int x[4];
return find_n ( x, 0, 4 );
}
Download : sample-007.c ( SJIS 版 )
/*
* 2012/11/09 sample-007.c
*
* 覆面算の「py＋py＝hyk」を解く
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
*
*/
int main ( void ) {
/*
*
*/
printf ( "問 : py + py = hyk\n" ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find() == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
C:\usr\c>sample-007 問 : py + py = hyk p = 6, y = 2, h = 1, k = 4 62 + 62 = 124 解けた C:\usr\c>
Download : hiyoko.h ( SJIS 版 )
/* * 2012/11/09 hiyoko.h */ #define YES 1 #define NO 0 /* * */ #define PI 0 #define YO 1 #define HI 2 #define KO 3 /* * */ extern int calc_check ( char n[], int size, /* 文字の名前 */ int a[], int sa, /* 足される数の個々の桁の番号の配列とサイズ */ int b[], int sb, /* 足す数の個々の桁の番号の配列とサイズ */ int c[], int sc, /* 和の数の個々の桁の番号の配列とサイズ */ int x[] /* 答の候補 */ ); extern int find(void); /* * */
Download : makefile.mf
Download : sample-008-01.c ( SJIS 版 )
/*
* 2012/11/09 sample-008-01.c
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
* 数の並びから十進数を計算する
*/
int ten ( int a[], int as, int x[] ) {
int i;
int v = 0;
for ( i = 0; i < as; i++ ) {
v = v * 10 + x[a[i]];
}
return v;
}
/*
* 答の候補 x[] が条件を満していれば
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算 A+B=C
*
*/
int calc_check (
char n[], int size, /* 文字の名前 */
int a[], int sa, /* 足される数の個々の桁の番号の配列とサイズ */
int b[], int sb, /* 足す数の個々の桁の番号の配列とサイズ */
int c[], int sc, /* 和の数の個々の桁の番号の配列とサイズ */
int x[] /* 答の候補 */
) {
int va; /* 足される数 */
int vb; /* 足す数 */
int vc; /* 和 */
int i;
int j;
/*
* (条件 1) 個々の数の先頭は 0 でない
*/
if ( x[a[0]] == 0 ) {
return NO;
}
if ( x[b[0]] == 0 ) {
return NO;
}
if ( x[c[0]] == 0 ) {
return NO;
}
/*
* (条件 2) x[i] は互いに異る
*/
for ( i = 0; i < size; i++ ) {
for ( j = i + 1; j < size; j++ ) {
if ( x[i] == x[j] ) {
return NO;
}
}
}
va = ten( a, sa, x );
vb = ten( b, sb, x );
vc = ten( c, sc, x );
if ( va + vb == vc ) {
for ( i = 0; i < size; i++ ) {
printf ( "%c = %d", n[i], x[i] );
if ( i < size - 1 ) {
printf ( ", " );
} else {
printf ( "\n" );
}
}
printf ( "%d + %d = %d\n", va, vb, vc );
/* 答を出力して.. */
return YES; /* YES を返す */
}
return NO; /* そうでなければ NO を返す */
}
Download : sample-008-02.c ( SJIS 版 )
/*
* 2012/11/09 sample-008-02.c
*
*/
#include "hiyoko.h"
/*
*
*/
int find_n (
char name[], int size,
int a[], int sa,
int b[], int sb,
int c[], int sc,
int x[], int k ) {
int i;
if ( k < size ) {
for ( i = 0; i < 10; i++ ) {
x[k] = i;
if ( find_n ( name, size, a, sa, b, sb, c, sc, x, k + 1 ) == YES ) {
return YES;
}
}
} else {
return calc_check ( name, size, a, sa, b, sb, c, sc, x );
}
return NO;
}
/*
* 答の候補を検索し、答えがあれば
* それを出力し、 YES を返す
* そうでなければ NO を返す
*
* 覆面算の条件「F」の部分
*
*/
int find ( char *ta, char *tb, char *tc ) {
char n[10];
int size;
int a[10];
int sa;
int b[10];
int sb;
int c[10];
int sc;
int i;
int j;
int find;
int x[10];
size = 0;
for ( i = 0; ta[i] != EOS; i++ ) {
find = NO;
for ( j = 0; j < size; j++ ) {
if ( n[j] == ta[i] ) {
a[i] = j;
find = YES;
}
}
if ( find == NO ) {
n[size] = ta[i];
a[i] = size;
size = size + 1;
}
}
sa = i;
for ( i = 0; tb[i] != EOS; i++ ) {
find = NO;
for ( j = 0; j < size; j++ ) {
if ( n[j] == tb[i] ) {
b[i] = j;
find = YES;
}
}
if ( find == NO ) {
n[size] = tb[i];
b[i] = size;
size = size + 1;
}
}
sb = i;
for ( i = 0; tc[i] != EOS; i++ ) {
find = NO;
for ( j = 0; j < size; j++ ) {
if ( n[j] == tc[i] ) {
c[i] = j;
find = YES;
}
}
if ( find == NO ) {
n[size] = tc[i];
c[i] = size;
size = size + 1;
}
}
sc = i;
return find_n ( n, size, a, sa, b, sb, c, sc, x, 0 );
}
Download : sample-008.c ( SJIS 版 )
/*
* 2012/11/09 sample-008.c
*
* 覆面算の「py＋py＝hyk」を解く
*
*/
#include <stdio.h>
#include "hiyoko.h"
/*
*
*/
int main ( void ) {
/*
*
*/
char a[SSIZE];
char b[SSIZE];
char c[SSIZE];
/*
*
*/
printf ( "足される数 : " );
scanf ( "%s", a );
printf ( "足す数 : " );
scanf ( "%s", b );
printf ( "和 : " );
scanf ( "%s", c );
/*
*
*/
printf ( "問 : %s + %s = %s\n", a, b, c ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find( a, b, c ) == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
py py hyk
C:\usr\c>sample-008< sample-008.in 足される数 : py 足す数 : py 和 : hyk 問 : py + py = hyk p = 6, y = 2, h = 1, k = 4 62 + 62 = 124 解けた C:\usr\c>
Download : hiyoko.h ( SJIS 版 )
/* * 2012/11/09 hiyoko.h */ #define YES 1 #define NO 0 /* * */ #define EOS '\0' #define SSIZE 100 /* * */ extern int calc_check ( char n[], int size, /* 文字の名前 */ int a[], int sa, /* 足される数の個々の桁の番号の配列とサイズ */ int b[], int sb, /* 足す数の個々の桁の番号の配列とサイズ */ int c[], int sc, /* 和の数の個々の桁の番号の配列とサイズ */ int x[] /* 答の候補 */ ); extern int find ( char *ta, char *tb, char *tc ); /* * */
Download : makefile.mf
Download : 20121116-01.c ( SJIS 版 )
/*
* DATE-DIR-QQQQ.c
*
* ニ次方程式 ( a x^2 + b x + c = 0 ) の解を、虱潰し法で解く
* ただし、解は、一桁の自然数
*
*/
#include <stdio.h>
/*
*
*/
#define YES 1
#define NO 0
/*
* a x^2 + b x + c = 0 ? : 論理式 P に相当する
*/
int check_formula ( int a, int b, int c, int x ) {
/*
** この部分を完成させなさい
*/
return NO;
}
/*
* 方程式 a x^2 + b x + c = 0 の解を、
* x_min 〜 x_max の範囲で探す
* 見付かったら、その値を返す
* もし見付からなかったら、範囲外の数 ( x_max + 1 ) を返す
*/
int solve_formal ( int a, int b, int c, int x_min, int x_max ) {
int x;
for ( x = x_min; x <= x_max; x++ ) { /* x = x_min 〜 x_max */
if ( check_formula ( a, b, c, x ) == YES ) { /* 見付かった */
return x; /* その値を返す */
}
}
/*
* 見付からなかったので..
*/
return x_max + 1; /* 範囲の外である数を返す */
}
/*
* a x^2 + b x + c = 0 の整数解を求める
*/
int main ( void ) {
int a;
int b;
int c; /* a x^2 + b x + c = 0 の a, b, c */
int x_min;
int x_max; /* F = { x | x_min <= x <= x_max } */
int x; /* 答の候補 */
/*
* [Input]
*/
/*
* P(x) == (a x^2 + b x + c = 0)
*/
printf ( "方程式 a x^2 + b x + c = 0 の整数解を搜します。\n" );
printf ( " a の値を入力してください : " );
scanf ( "%d", &a );
printf ( " b の値を入力してください : " );
scanf ( "%d", &b );
printf ( " c の値を入力してください : " );
scanf ( "%d", &c );
/*
* F = { x | x_min <= x <= x_max }
*/
printf ( "x の取り得る範囲を指定してください\n" );
printf ( "\t最小値 : " );
scanf ( "%d", &x_min );
printf ( "\t最大値 : " );
scanf ( "%d", &x_max );
/*
* [Process]
*/
/*
* 「 \exists x \in F[P(x)] 」の探索による証明
*/
x = solve_formal ( a, b, c, x_min, x_max );
/*
* [Output]
*/
if ( x > x_max ) {
printf ( "方程式 %d x^2 + %d x + %d = 0 の解を %d 〜 %d \
の範囲の整数からは見つける事ができませんでした。\n", a, b, c, x_min, x_max );
} else { /* 答が見つかった */
/*
** この部分を完成させなさい
*/
}
/*
*
*/
return 0;
}
/*
*
*/
12 34
C:\usr\c\> 20121116-01
方程式 a x^2 + b x + c = 0 の整数解を搜します。
a の値を入力してください : 12
b の値を入力してください : 34
c の値を入力してください : 1074531517
x の取り得る範囲を指定してください
最小値 : 134516073
最大値 : -1078587784
方程式 12 x^2 + 34 x + 1074531517 = 0 の解を 134516073 〜 -1078587784 \
の範囲の整数からは見つける事ができませんでした。
C:\usr\c\>
Download : 20121109-02.c ( SJIS 版 )
/*
* DATE-DIR-QQQQ.c
*
* 覆面算の「こな＋ここ＝きなこ」を解く
*/
#include <stdio.h>
/*
*
*/
#define YES 1
#define NO 0
/*
* 答の候補 ko, na, ki の値が答になっていれば、
* それを出力し、 YES を返す
* そうでなければ NO を返す
*/
int calc_check ( int ko, int na, int ki ) {
int kona = ko * 10 + na; /* 「こな」を求める */
int koko = ko * 10 + ko; /* 「ここ」を求める */
int kinako = ki * 100 + na * 10 + ko; /* 「きなこ」を求める */
/* 「こ」は先頭なので 0 だと駄目 */
if ( ko == 0 ) {
return NO;
}
/* 「き」は先頭なので 0 だと駄目 */
/*
** この部分を完成させなさい
*/
/* 「こ」と「な」は別 */
if ( ko == na ) {
return NO;
}
/* 「こ」と「き」は別 */
/*
** この部分を完成させなさい
*/
if ( na == ki ) { /* 「な」と「き」は別 */
return NO;
}
if ( kona + koko == kinako ) { /* 計算があっていれば */
/*
** この部分を完成させなさい
*/
/* 答を出力して.. */
return YES; /* 1 を返す */
}
return NO; /* そうでなければ 0 を返す */
}
/*
* 「き」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「き」を探す
* 次がなければ NO を返す
*/
int find_ki ( int ko, int na, int ki ) {
/* 現在の「き」は答か */
if ( calc_check ( ko, na, ki ) == YES ) {
return YES; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
if ( ki < 9 ) { /* 次の候補があれば */
return find_ki ( ko, na, ki + 1 ); /* 次を try */
}
return NO; /* そうでなければ 0 */
}
/*
* 「な」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「な」を探す
* 次がなければ NO を返す
*/
int find_na ( int ko, int na ) {
/* 現在の「な」は答か */
/*
** この部分を完成させなさい
*/
/* そうでないなら.. */
if ( na < 9 ) { /* 次の候補があれば */
return find_na ( ko, na + 1 ); /* 次を try */
}
return NO; /* そうでなければ 0 */
}
/*
* 「こ」の候補を作り、答になっているかどうかを調べる
* 答がみつかったら、YES を返す
* そうでなければ、次の「こ」を探す
* 次がなければ NO を返す
*/
int find_ko ( int ko ) {
/* 現在の「こ」は答か */
if ( find_na ( ko, 0 ) == YES ) {
return 1; /* それなら YES を返して終了 */
}
/* そうでないなら.. */
/*
** この部分を完成させなさい
*/
return NO; /* そうでなければ 0 */
}
/*
*
*/
int main ( void ) {
/*
*
*/
printf ( "問 : こな + ここ = きなこ\n" ); /* 問題の出力 */
/*
*
*/
/* 「こ」の最初の候補として「0」を指定して答を検索 */
if ( find_ko ( 0 ) == YES ) { /* 答がみつかったら */
printf ( "解けた\n" ); /* 「解けた」と出力 */
} else {
printf ( "解けない\n" ); /* 「解けない」と出力 */
}
/*
* 結果の出力
*/
return 0;
}
/*
*
*/
12 34
C:\usr\c\> 20121109-02 問 : こな + ここ = きなこ こ = 5, な = 0, き = 1 50 + 55 = 105 解けた C:\usr\c\>