/******************************************************************************
Ｃマガジン電脳クラブ（２００３年８月号出題）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 基準値（原点） /*
#define N1 1 /* 基準値より大きい最小の数 /*
/* ===== 変更すれば、いろいろなパターンに対応できる。（ここから） ==== /*
#define N6 6 /* N7 - N1 /*
#define N7 7 /* 格子の辺の長さ /*
#define N13 13 /* 曲がる回数 /*
#define N14 14 /* N13 + N1 /*
#define SX 2 /* スタートのＸ座標 /*
#define SY 0 /* スタートのＹ座標 /*
#define EX 6 /* ゴールのＸ座標 /*
#define EY 2 /* ゴールのＹ座標 /*
/* ===== 変更すれば、いろいろなパターンに対応できる。（ここまで） ==== /*
typedef struct {
int x;
int y;
} XY; /* ＸＹ座標 /*
int checkX[N7][N6]; /* 区間を通過したかのチェックフラグ（Ｘ方向） /*
int checkY[N6][N7]; /* 区間を通過したかのチェックフラグ（Ｙ方向） /*
int checkP[N7][N7]; /* 座標を通過した回数 /*
int maxLen = - N1; /* 最大長さ /*
int maxPoint; /* 最大座標数 /*
XY r1[N14]; /* 曲がった座標 /*
XY r2[N14]; /* 最大長さにおける曲がった座標 /*
void subY(int , int , int , int , int); /* プロトタイプ宣言 /*
/******************************************************************************
機能：解答例を表示する。
引数：なし
戻り値：なし
*****************************************************************************/*
void disp(void)
{
int x , y; /* ループの制御変数 /*
int i; /* ループの制御変数 /*
int p1[N7][N7]; /* 各座標の到達順番 /*
for(y = N0 ; y < N7 ; y++) {
for(x = N0 ; x < N7 ; x++) p1[y][x] = - N1; /* 初期化（未到達） /*
}
for(i = N0 ; i < N14 ; i++) p1[r2[i].y][r2[i].x] = i;
p1[EY][EX] = N14;
printf("+--+--+--+--+--+--+--+\n");
for(y = N0 ; y < N7 ; y++) {
printf("|");
for(x = N0 ; x < N7 ; x++) {
if (p1[y][x] == - N1) printf(" |"); /* 左端 /*
else if(p1[y][x] == N0) printf(" S|"); /* スタート /*
else if(p1[y][x] == N14) printf(" E|"); /* ゴール /*
else printf("%2d|" , p1[y][x]);
}
printf("\n");
printf("+--+--+--+--+--+--+--+\n");
}
}
/******************************************************************************
機能：縦方向から横方向へ曲がる。
引数：
x1 : 前回曲がったＸ座標
y1 : 前回曲がったＹ座標
len : スタートから前回曲がった座標までの長さ
point : スタートから前回曲がった座標までに通過した座標
n : 前回までに曲がった回数
戻り値：なし
*****************************************************************************/*
void subX(int x1 , int y1 , int len , int point , int n)
{
int x2 , x3; /* ループの制御変数 /*
int i; /* ループの制御変数 /*
int np = N0; /* 初めて通る座標の数 /*
int n1; /* 次の回数 /*
if(len < maxLen - N6 * (N14 - n)) return; /* 最大長に到達できない /*
if(n <= N13 && x1 == EX && y1 == EY && (EY == N0 || EY == N6)) return;
if(n > N13) {
if(x1 == EX && y1 == EY) { /* ゴールに到達 /*
if(len > maxLen || (len == maxLen && point > maxPoint)) {
maxLen = len;
maxPoint = point;
for(i = N0 ; i < N14 ; i++) {
r2[i].x = r1[i].x;
r2[i].y = r1[i].y;
}
}
}
return;
}
r1[n].x = x1;
r1[n].y = y1;
n1 = n + N1;
for(x2 = x1 - N1 ; x2 >= N0 ; x2--) { /* 左方向へ /*
if(checkX[y1][x2] == ON) break; /* 通過済 /*
checkX[y1][x2] = ON; /* 通過済にする /*
if(checkP[y1][x2] == N0) np++; /* 初めて通るなら通過数を加算する /*
checkP[y1][x2]++; /* 通過数を加算する /*
subY(x2 , y1 , len + abs(x2 - x1) , point + np , n1); /* 次の角へ /*
}
for(x3 = x1 - N1 ; x3 > x2 ; x3--) {
checkX[y1][x3] = OFF; /* 未通過に戻す /*
checkP[y1][x3]--; /* 通過数を戻す /*
}
np = N0;
for(x2 = x1 + N1 ; x2 < N7 ; x2++) { /* 右方向へ /*
if(checkX[y1][x2 - N1] == ON) break; /* 通過済 /*
checkX[y1][x2 - N1] = ON; /* 通過済にする /*
if(checkP[y1][x2] == N0) np++; /* 初めて通るなら通過数を加算する /*
checkP[y1][x2]++; /* 通過数を加算する /*
subY(x2 , y1 , len + abs(x2 - x1) , point + np , n1); /* 次の角へ /*
}
for(x3 = x1 + N1 ; x3 < x2 ; x3++) {
checkX[y1][x3 - N1] = OFF; /* 未通過に戻す /*
checkP[y1][x3]--; /* 通過数を戻す /*
}
}
/******************************************************************************
機能：横方向から縦方向へ曲がる。
引数：
x1 : 前回曲がったＸ座標
y1 : 前回曲がったＹ座標
len : スタートから前回曲がった座標までの長さ
point : スタートから前回曲がった座標までに通過した座標
n : 前回までに曲がった回数
戻り値：なし
*****************************************************************************/*
void subY(int x1 , int y1 , int len , int point , int n)
{
int y2 , y3; /* ループの制御変数 /*
int i; /* ループの制御変数 /*
int np = N0;
int n1;
if(len < maxLen - N6 * (N14 - n)) return; /* 最大長に到達できない /*
if(n <= N13 && x1 == EX && y1 == EY && (EX == N0 || EX == N6)) return;
if(n > N13) {
if(x1 == EX && y1 == EY) { /* ゴールに到達 /*
if(len > maxLen || (len == maxLen && point > maxPoint)) {
maxLen = len;
maxPoint = point;
for(i = N0 ; i < N14 ; i++) {
r2[i].x = r1[i].x;
r2[i].y = r1[i].y;
}
}
}
return;
}
r1[n].x = x1;
r1[n].y = y1;
n1 = n + N1;
for(y2 = y1 - N1 ; y2 >= N0 ; y2--) { /* 上方向へ /*
if(checkY[y2][x1] == ON) break; /* 通過済 /*
checkY[y2][x1] = ON; /* 通過済にする /*
if(checkP[y2][x1] == N0) np++; /* 初めて通るなら通過数を加算する /*
checkP[y2][x1]++; /* 通過数を加算する /*
subX(x1 , y2 , len + abs(y2 - y1) , point + np , n1); /* 次の角へ /*
}
for(y3 = y1 - N1 ; y3 > y2 ; y3--) {
checkY[y3][x1] = OFF; /* 未通過に戻す /*
checkP[y3][x1]--; /* 通過数を戻す /*
}
np = N0;
for(y2 = y1 + N1 ; y2 < N7 ; y2++) { /* 下方向へ /*
if(checkY[y2 - N1][x1] == ON) break; /* 通過済 /*
checkY[y2 - N1][x1] = ON; /* 通過済にする /*
if(checkP[y2][x1] == N0) np++; /* 初めて通るなら通過数を加算する /*
checkP[y2][x1]++; /* 通過数を加算する /*
subX(x1 , y2 , len + abs(y2 - y1) , point + np , n1); /* 次の角へ /*
}
for(y3 = y1 + N1 ; y3 < y2 ; y3++) {
checkY[y3 - N1][x1] = OFF; /* 未通過に戻す /*
checkP[y3][x1]--; /* 通過数を戻す /*
}
}
/******************************************************************************
機能：メイン
引数：１
戻り値：なし
*****************************************************************************/*
int main(void)
{
int i , j; /* ループの制御変数 /*
for(i = N0 ; i < N7 ; i++) { /* 初期化 /*
for(j = N0 ; j < N7 ; j++) {
if(j < N6) checkX[i][j] = checkY[j][i] = OFF;
checkP[i][j] = N0;
}
}
if(SY == N0 || SY == N6) subY(SX , SY , N0 , N0 , N0); /* 上、下辺から /*
else subX(SX , SY , N0 , N0 , N0); /* 左、右辺から /*
printf("長さ = %dcm 座標数 = %d\n" , maxLen , maxPoint);
disp(); /* 解答例表示 /*
return(EXIT_SUCCESS);
}
|
第151回（10月）２組の５乗数の和
|
|
/******************************************************************************
Ｃマガジン２００３年７月号電脳クラブ出題（２組の５乗数の和）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N0 0 /* 原点 /*
#define N1 1 /* ０より大きい最小の数 /*
#define N2 2 /* N1 + N1 /*
#define N3 3 /* 足し合わせる５乗数の数 /*
#define N5 5 /* ５乗数の５ /*
#define N32 32 /* unsigned int が表現できるビット数 /*
#define N84 84 /* ５乗してintでおさまる最大の整数 /*
#define N85 85 /* N84 + N1 /*
#define F1 "%d = %d^5 + %d^5 + %d^5 = %d^5 + %d^5 + %d^5\n" /* 解答表示用 /*
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
int a0 , a1 , a2; /* １組目 /*
int b0 , b1 , b2; /* ２組目 /*
int n = N3; /* １組目の数の和 /*
unsigned int s0 , s1 , s2; /* １組目の５乗数の和 /*
unsigned int t0 , t1; /* ２組目の５乗数の和 /*
unsigned int st; /* b2の５乗の最大値 /*
int n2; /* a1の最大値 /*
int n3; /* a0の最大値 /*
int m2; /* b1の最大値 /*
int i; /* ループの制御変数 /*
int n84;
unsigned int *gojo; /* ５乗の数 /*
n84 = (int)pow(pow((double)N2 , (double)N32) , ((double)N1 / (double)N5));
gojo = (int *)malloc(sizeof(int) * (n84 + N1));
if(gojo == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(i = N1 ; i <= n84 ; i++) gojo[i] = i * i * i * i * i;
while(N1) { /* 正解が見つかるまで繰り返す /*
n3 = n / N3; /* a0の最大値 /*
for(a0 = N1 ; a0 <= n3 ; a0++) { /* １組目１個目 /*
s0 = gojo[a0]; /* a0の５乗 /*
n2 = (n - a0) / N2; /* a1の最大値 /*
if(n2 > n84) continue;
for(a1 = a0 ; a1 <= n2 ; a1++) { /* １組目２個目 /*
s1 = gojo[a1] + s0; /* a0の５乗＋a1の５乗 /*
a2 = n - a0 - a1; /* １組目３個目 /*
if(a2 > n84) continue;
s2 = gojo[a2] + s1; /* １組目の５乗数の和 /*
for(b0 = N1 ; b0 < n3 ; b0++) { /* ２組目１個目 /*
t0 = gojo[b0]; /* b0の５乗 /*
b2 = n - b0; /* ２組目３個目の最大値 /*
m2 = b2 / N2; /* b1の最大値 /*
if(b2 > n84) b2 = n84; /* unsigned intの範囲内におさめる /*
for(b1 = b0 ; b1 <= m2 ; b1++) { /* ２組目２個目 /*
if(a0 == b0 && a1 == b1) continue; /* １組目＝２組目 /*
t1 = gojo[b1] + t0; /* b0の５乗＋b1の５乗 /*
st = s2 - t1; /* b2の５乗の最大値 /*
while(gojo[b2] > st && b2 > N0) b2--; /* b2を求める /*
if(b2 < N1) break; /* b2が負（見つからない） /*
if(s2 == t1 + gojo[b2]) { /* 正解の場合、解表示＆終了 /*
printf(F1 , s2 , a0 , a1 , a2 , b0 , b1 , b2);
return(EXIT_SUCCESS);
}
}
}
}
}
n++; /* 解が見つからない場合、カウントアップ /*
}
}
|
第150回（9月）正三角形はいくつ？
|
|
/******************************************************************************
Ｃマガジン２００３年６月号出題（正三角形はいくつ？）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define N0 0 /* 基準値としてのゼロ /*
#define N1 1 /* ゼロより大きい最小の数 /*
#define N3 3 /* 底辺の長さが１の正三角形の高さの２倍の２乗の値 /*
#define N37 37 /* 座標の数 /*
typedef struct {
int x; /* Ｘ座標 /*
int y; /* Ｙ座標 /*
} XY;
XY xy[N37]; /* ドットの座標 /*
int nXy = N0; /* 座標の数（３７になる） /*
int main(void)
{
char *ban[] = {
" *" ,
" * *" ,
"* * * * * * *" ,
" * * * * * *" ,
" * * * * *" ,
" * * * * * *" ,
"* * * * * * *" ,
" * *" ,
" *"
};
int x , y; /* ループの制御変数、三角形の頂点間のＸ、Ｙ座標上の距離/*
int s , s2; /* 三角形の辺の長さ /*
int i0 , i1 , i2; /* ループの制御変数 /*
int count = N0; /* 解答 /*
for(y = N0 ; y < sizeof(ban) / sizeof(ban[N0]) ; y++) {
for(x = N0 ; x < (signed int)strlen(ban[y]) ; x++) {
if(*(ban[y] + x) == '*') { /* ドットがあった場合 /*
xy[nXy].x = x; /* Ｘ座標 /*
xy[nXy++].y = y; /* Ｙ座標 /*
}
}
}
for(i0 = N0 ; i0 < nXy ; i0++) { /* １点め /*
for(i1 = i0 + N1 ; i1 < nXy ; i1++) { /* ２点め /*
x = xy[i0].x - xy[i1].x;
y = xy[i0].y - xy[i1].y;
s = x * x + N3 * y * y; /* １辺めの距離の２乗 /*
for(i2 = i1 + N1 ; i2 < nXy ; i2++) { /* ３点め /*
x = xy[i0].x - xy[i2].x;
y = xy[i0].y - xy[i2].y;
s2 = x * x + N3 * y * y; /* ２辺めの距離の２乗 /*
if(s != s2) continue; /* １辺めと２辺めの長さが異なる場合 /*
x = xy[i1].x - xy[i2].x;
y = xy[i1].y - xy[i2].y;
s2 = x * x + N3 * y * y; /* ３辺めの距離の２乗 /*
if(s == s2) count++; /* ２辺めと３辺めの長さが同じ場合 /*
}
}
}
printf("解答 : %d\n" , count);
return(EXIT_SUCCESS);
}
|
第149回（8月）マッチ方陣
|
|
/******************************************************************************
Ｃマガジン２００３年５月号電脳倶楽部出題（マッチ方陣）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 原点 /*
#define N1 1 /* 最小単位 /*
#define N2 2 /* 斜め方向の和を求める数 /*
#define N3 3 /* 横始＋横終＋縦 /*
#define N4 4 /* 縦横各方向の和を求める数 /*
#define N7 7 /* 鏡像チェックパターンの数
（Ｘ反転、Ｙ反転、ＸＹ反転、ＸＹ入替、同Ｘ反転、同Ｙ反転、同ＸＹ反転） /*
#define N9 9 /* N10 - N1 /*
#define N10 10 /* 盤の縦横の大きさ /*
#define M3 3 /* 横方向マッチのＹ座標の数、縦方向マッチのＸ座標の数 /*
#define M4 4 /* 横方向マッチのＸ座標の数、縦方向マッチのＹ座標の数 /*
typedef struct {
int matchX[M4][M3]; /* 横マッチの方向（OFF:←、ON:→） /*
int matchY[M3][M4]; /* 縦マッチの方向（OFF:↑、ON:↓） /*
} MATCH;
MATCH *storeM;
int nStore = N0; /* 既出パターンの数 /*
int sumX[N4]; /* Ｘ方向の合計 /*
int sumY[N4]; /* Ｙ方向の合計 /*
int sumN0 , sumN1; /* 斜め方向の合計（sumN0:＼、sumN1:／） /*
/******************************************************************************
機能：盤表示
引数：
ban : 盤
戻り値：なし
*****************************************************************************/*
void disp(int ban[][N10])
{
int x , y; /* ループの制御変数 /*
int t1; /* 角の値 /*
static char *n1[] = {"０" , "１" , "２" , "３" , "４"};
static char *n2[] = {"→" , "←"};
static char *n3[] = {"↓" , "↑"};
printf("----- %d ----\n" , nStore);
for(y = N0 ; y < N10 ; y+= N3) {
for(x = N0 ; x < N10 ; x += N3) { /* 横方向マッチ表示 /*
t1 = N0;
if(x > N0) t1 += ban[y][x - N1];
if(x < N9) t1 += ban[y][x + N1];
if(y < N9) t1 += ban[y + N1][x];
if(y > N0) t1 += ban[y - N1][x];
printf("%s" , n1[t1]);
if(x == N9) printf("\n");
else printf("%s" , n2[ban[y][x + N1]]);
}
if(y == N9) break;
for(x = 0 ; x < N10 ; x += N3) { /* 縦方向マッチ表示 /*
printf("%s" , n3[ban[y + N1][x]]);
if(x == N9) printf("\n");
else printf(" ");
}
}
}
/******************************************************************************
機能：マッチを盤に展開する。
引数：
ban : 盤
mtach : マッチ
戻り値：なし
*****************************************************************************/*
void convBan(int ban[][N10] , MATCH match)
{
int x , y;
for(y = N0 ; y < N10 ; y++) {
for(x = N0 ; x < N10 ; x++) ban[y][x] = OFF;
}
for(y = N0 ; y < M4 ; y++) {
for(x = N0 ; x < M3 ; x++) {
ban[y * N3][x * N3 + 1] = ON - match.matchX[y][x];
ban[y * N3][x * N3 + 2] = match.matchX[y][x];
}
}
for(x = N0 ; x < M4 ; x++) {
for(y = N0 ; y < M3 ; y++) {
ban[y * N3 + 1][x * N3] = ON - match.matchY[y][x];
ban[y * N3 + 2][x * N3] = match.matchY[y][x];
}
}
}
/******************************************************************************
機能：鏡像チェック
引数：
mtach : マッチ
戻り値：OFF:新パターン、ON:既出パターン
*****************************************************************************/*
int check(MATCH match)
{
int ban[N10][N10]; /* 盤 /*
int banS[N10][N10];
int i , j;
int x , y;
int x2 , y2;
static int d1[N7][2] = {1,2,0,3,1,3,2,0,3,0,2,1,3,1}; /* チェックパターン /*
int xy[4];
convBan(ban , match);
for(i = N0 ; i < nStore ; i++) {
convBan(banS , storeM[i]);
for(j = N0 ; j < N7 ; j++) {
for(xy[2] = N0 , xy[3] = N9 ; xy[2] < N10 ; xy[2]++ , xy[3]--) {
for(xy[0] = N0 , xy[1] = N9 ; xy[0] < N10 ; xy[0]++ , xy[1]--) {
x2 = xy[d1[j][N0]];
y2 = xy[d1[j][N1]];
if(banS[xy[2]][xy[0]] != ban[y2][x2]) break;
}
if(xy[0] != N10) break;
}
if(xy[2] == N10) return(ON);
}
}
storeM = (MATCH *)realloc(storeM , sizeof(MATCH) * (nStore + 1));
if(storeM == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(y = 0 ; y < 4 ; y++) {
for(x = 0 ; x < 3 ; x++) {
storeM[nStore].matchX[y][x] = match.matchX[y][x];
storeM[nStore].matchY[x][y] = match.matchY[x][y];
}
}
nStore++;
disp(ban);
return(OFF);
}
void subX(MATCH , int , int); /* プロトタイプ宣言 /*
/******************************************************************************
機能：Ｙ（縦）方向のマッチを置く
引数：
mtach : マッチ
x : マッチを置くＸ座標
y : マッチを置くＹ座標
戻り値：なし
*****************************************************************************/*
void subY(MATCH match , int x , int y)
{
if(x == 4) { /* ４本置いたら次（横方向、または終わり）へ /*
if(y > 0 && sumX[N0] != sumX[y]) return; /* 合計値不一致 /*
subX(match , 0 , y + N1);
return;
}
match.matchY[y][x] = OFF; /* マッチを置く（↑） /*
sumX[y]++; /* 横方向の和 /*
if(x == y) sumN0++; /* 斜め方向の和 /*
if(x + y == 3) sumN1++; /* 逆斜め方向の和 /*
subY(match , x + N1 , y);
if(x == y) sumN0--;
if(x + y == 3) sumN1--;
sumX[y]--;
match.matchY[y][x] = ON; /* マッチを置く（↓） /*
sumX[y + 1]++; /* 横方向の和 /*
if(x == y + 1) sumN0++; /* 斜め方向の和 /*
if(x + y == 2) sumN1++; /* 逆斜め方向の和 /*
subY(match , x + N1 , y);
if(x == y + 1) sumN0--;
if(x + y == 2) sumN1--;
sumX[y + N1]--;
}
/******************************************************************************
機能：Ｘ（横）方向のマッチを置く
引数：
mtach : マッチ
x : マッチを置くＸ座標
y : マッチを置くＹ座標
戻り値：なし
*****************************************************************************/*
void subX(MATCH match , int x , int y)
{
if(y == 3) { /* ３本置いたら次（縦方向、または終わり）へ /*
if(x == 1 && sumX[0] != sumY[0]) return;
if(x == 2 && sumX[0] != sumY[1]) return;
}
if(x == 3) {
if(y < 3) {
subY(match , N0 , y);
return;
}
else {
if(sumX[0] != sumX[3]) return; /* 合計値不一致 /*
if(sumX[0] != sumY[2]) return; /* 合計値不一致 /*
if(sumX[0] != sumY[3]) return; /* 合計値不一致 /*
if(sumX[N0] + 3 != sumN0) return; /* 合計値不一致 /*
if(sumX[N0] + 3 != sumN1) return; /* 合計値不一致 /*
if(check(match) == ON) return; /* 既出パターン /*
return;
}
}
match.matchX[y][x] = OFF; /* マッチを置く（←） /*
sumY[x]++; /* 縦方向の和 /*
if(x == y) sumN0++; /* 斜め方向の和 /*
if(x + y == 3) sumN1++; /* 逆斜め方向の和 /*
subX(match , x + N1 , y);
if(x == y) sumN0--;
if(x + y == 3) sumN1--;
sumY[x]--;
match.matchX[y][x] = ON; /* マッチを置く（→） /*
sumY[x + N1]++; /* 縦方向の和 /*
if(x + N1 == y) sumN0++; /* 斜め方向の和 /*
if(x + y == 2) sumN1++; /* 逆斜め方向の和 /*
subX(match , x + N1 , y);
if(x + N1 == y) sumN0--;
if(x + y == 2) sumN1--;
sumY[x + N1]--;
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
MATCH match;
int i;
match.matchX[0][0] = OFF; /* コンパイルで警告発生の予防 /*
sumN0 = sumN1 = N0;
for(i = N0 ; i < N4 ; i++) sumX[i] = sumY[i] = N0;
storeM = (MATCH *)malloc(sizeof(MATCH));
if(storeM == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
subX(match , 0 , 0);
printf("解答：%d通り\n" , nStore);
free(storeM);
return(EXIT_SUCCESS);
}
|
第148回（7月）スライディング・スリー
|
|
/******************************************************************************
Ｃマガジン２００３年４月号出題（スライディング・スリー）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NON 0 /* コマが置いてない状態 /*
#define N0 0 /* 原点 /*
#define N1 1 /* 最小の単位 /*
#define N2 2 /* →を表示するＹ座標 /*
#define N3 3 /* 手数 /*
#define N4 4 /* N5 - N1 /*
#define N5 5 /* 盤の大きさ /*
#define NB 5 /* 個数 /*
#define LEN 2 /* 文字列の長さ /*
typedef struct {
int x; /* Ｘ座標 /*
int y; /* Ｙ座標 /*
} XY;
typedef struct {
int b1[N5][N5]; /* 盤 /*
XY xy[NB]; /* コマの各座標 /*
} BAN; /* 盤の定義 /*
int rireki[2][N5][N5]; /* 履歴 /*
static char *shoki[] = { /* 初期状態 /*
"□□□□□" ,
"□□Ａ□Ｂ" ,
"□□□ＣＤ" ,
"□□□□□" ,
"□□Ｅ□□" };
static char *g2[] = {"□" , "Ａ" , "Ｂ" , "Ｃ" , "Ｄ" , "Ｅ"}; /* コマの記号 /*
/******************************************************************************
機能：題意を満たすかをチェックして、満たすなら表示する。
引数：
ban : 盤
戻り値：なし
*****************************************************************************/*
void disp(BAN *ban)
{
int x , y; /* ループの制御変数 /*
int s1; /* その列に置いてあるコマの数 /*
static int count = N0; /* 解の番号 /*
for(y = N0 ; y < N5 ; y++) { /* 縦列チェック /*
s1 = N0;
for(x = N0 ; x < N5 ; x++) {
if(ban->b1[y][x] != NON) s1++;
if(s1 > N1) return; /* ２個以上は不可 /*
}
}
for(x = N0 ; x < N5 ; x++) { /* 横列チェック /*
s1 = N0;
for(y = N0 ; y < N5 ; y++) {
if(ban->b1[y][x] != NON) s1++;
if(s1 > N1) return; /* ２個以上は不可 /*
}
}
s1 = N0;
for(x = N0 ; x < N5 ; x++) { /* 対角線チェック /*
if(ban->b1[x][x] != NON) s1++;
if(s1 > N1) return; /* ２個以上は不可 /*
}
s1 = N0;
for(x = N0 ; x < N5 ; x++) { /* 対角線チェック /*
if(ban->b1[N4 - x][x] != NON) s1++;
if(s1 > N1) return; /* ２個以上は不可 /*
}
printf("−−−−− %d −−−−−\n" , ++count); /* 解の表示 /*
for(y = N0 ; y < N5 ; y++) {
printf("%s" , shoki[y]); /* 初期状態 /*
if(y == N2) printf(" → ");
else printf(" ");
for(x = N0 ; x < N5 ; x++) printf("%s" , g2[rireki[N0][y][x]]); /*1手/*
if(y == N2) printf(" → ");
else printf(" ");
for(x = N0 ; x < N5 ; x++) printf("%s" , g2[rireki[N1][y][x]]); /*2手/*
if(y == N2) printf(" → ");
else printf(" ");
for(x = N0 ; x < N5 ; x++) printf("%s" , g2[ban->b1[y][x]]); /* 最終 /*
printf("\n");
}
}
/******************************************************************************
機能：再帰関数
引数：
ban : 盤
n : ここまでの手の数
戻り値：なし
*****************************************************************************/*
void sub(BAN *ban , int n)
{
int i;
int x , y;
int dx , dy; /* Ｘ、Ｙの移動方向への増分 /*
int x2 , y2;
if(n == N3) { /* ３回動かした場合 /*
disp(ban);
return;
}
if(n > N0) { /* １回以上動かした場合、状態を記録する /*
for(y = N0 ; y < N5 ; y++) {
for(x = N0 ; x < N5 ; x++) rireki[n - N1][y][x] = ban->b1[y][x];
}
}
for(i = N0 ; i < N5 ; i++) {
x = ban->xy[i].x;
y = ban->xy[i].y;
for(dy = - N1 ; dy <= N1 ; dy++) { /* コマを動かすＹ方向の増分 /*
for(dx = - N1 ; dx <= N1 ; dx++) { /* 同Ｘ方向の増分 /*
if(dx == N0 && dy == N0) continue;
x2 = x + dx;
y2 = y + dy;
while(N1) {
if(ban->b1[y2][x2] != N0) break; /* 既にコマがある /*
if(x2 < N0 || x2 > N4) break; /* 盤外 /*
if(y2 < N0 || y2 > N4) break; /* 盤外 /*
ban->xy[i].x = x2; /* コマを動かす /*
ban->xy[i].y = y2;
ban->b1[y][x] = NON; /* 移動前の場所をクリア /*
ban->b1[y2][x2] = i + N1; /* 移動後の場所にコマを置く /*
sub(ban , n + N1); /* 次の手へ /*
ban->b1[y][x] = i + N1; /* コマを元に戻す /*
ban->b1[y2][x2] = NON;
ban->xy[i].x = x;
ban->xy[i].y = y;
x2 += dx;
y2 += dy;
}
}
}
}
}
/******************************************************************************
機能：初期化処理（初期状態のセット）
引数：
ban : 盤
戻り値：なし
*****************************************************************************/*
void init(BAN *ban)
{
int x , y; /* ループの制御変数 /*
int n = N0;
int i;
for(y = N0 ; y < N5 ; y++) { /* 盤の各位置に何が置いてあるか調べる /*
for(x = N0 ; x < N5 ; x++) {
for(i = N0 ; i < sizeof(g2) / sizeof(g2[N0]) ; i++) {
if(strncmp(shoki[y] + x * LEN , g2[i] , LEN) == N0) {
ban->b1[y][x] = i;
break;
}
}
if(ban->b1[y][x] != NON) {
ban->xy[n].x = x; /* コマが置いてある場合、その座標を記録 /*
ban->xy[n++].y = y;
}
}
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
BAN ban; /* 盤 /*
init(&ban); /* 初期化処理 /*
sub(&ban , N0);
return(EXIT_SUCCESS);
}
|
第147回（6月）リバース・スーバリ
|
|
/******************************************************************************
Ｃマガジン電脳クラブ２００３年３月出題 リバース・スーバリ
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define CMAGAZINE "CMAGAZINE" /* 初期状態 /*
#define LEN 9 /* 文字列の長さ /*
#define SHOKI -1 /* 初期手の前の手。ありえないので−１ /*
#define N0 0 /* 原点としての０ /*
#define N1 1 /* 最小の単位の数 /*
#define N2 2 /* N3 - 1 /*
#define N3 3 /* １回にリバースできる最小の個数 /*
#define N7 7 /* 反転する通りの数 /*
#define A 'A' /* アルファベット大文字の最初の文字 /*
typedef struct {
char c1[LEN]; /* 文字列 /*
int f1[LEN]; /* 反転フラグ OFF:反転してない、ON:してる /*
} TEXT;
int max; /* 試みる回数の最大値 /*
int *q1; /* 各回の履歴 /*
char enizagamc[LEN]; /* 最終の文字列 /*
static int fRev[] = {
/*A B C D E F G H I J K L M N /*
OFF,ON ,ON ,ON ,ON ,ON ,ON ,OFF,OFF,ON ,ON ,ON ,OFF,ON ,
/*O P Q R S T U V W X Y Z /*
OFF,ON ,ON ,ON ,ON ,OFF,OFF,OFF,OFF,OFF,OFF,ON
}; /* 反転してもOKかどうかのフラグ OFF:OK、ON:NG /*
/******************************************************************************
機能：文字列をリバースする。
引数：
(1) t1 : リバース後の文字列
(2) t0 : リバース前の文字列
(3) n : リバース位置
戻り値：なし
*****************************************************************************/*
void rev(TEXT *t1 , TEXT t0 , int n)
{
int n2 , n3;
int i; /* ループの制御変数 /*
n2 = n + N2;
n3 = n + N3;
for(i = N0 ; i < n3 ; i++) { /* 左側（反転して移動） /*
t1->c1[i] = t0.c1[n2 - i];
t1->f1[i] = ON - t0.f1[n2 - i];
}
for(i = n3 ; i < LEN ; i++) { /* 右側（反転せず移動） /*
t1->c1[i] = t0.c1[i];
t1->f1[i] = t0.f1[i];
}
}
/******************************************************************************
機能：正解例を表示する。
引数：
(1) q1 : 各回のリバース位置の履歴
戻り値：なし
*****************************************************************************/*
void disp(int q1[])
{
int i , j; /* ループの制御変数 /*
TEXT t0 , t1;
strncpy(t0.c1 , CMAGAZINE , LEN);
for(i = N0 ; i < LEN ; i++) t0.f1[i] = OFF;
for(i = N0 ; i < max ; i++) {
printf("----- %d回目 -----\n" , i + N1);
printf("%d個リバース\n" , q1[i] + N3);
rev(&t1 , t0 , q1[i]);
for(j = N0 ; j < LEN ; j++) printf("%c" , t1.c1[j]);
printf("\n");
for(j = N0 ; j < LEN ; j++) {
if (fRev[t1.c1[j] - 'A'] == OFF) printf(" ");
else if(t1.f1[j] == ON) printf("*");
else printf(" ");
}
printf("\n");
for(j = N0 ; j < LEN ; j++) {
t0.c1[j] = t1.c1[j];
t0.f1[j] = t1.f1[j];
}
}
}
/******************************************************************************
機能：終了パターンかどうかの判定を行う。
引数：
(1) text : チェック対象のテキスト
戻り値：OFF:まだ、ON:終了パターン
*****************************************************************************/*
int check(TEXT text)
{
int i; /* ループの制御変数 /*
if(strncmp(text.c1 , enizagamc , LEN) != N0) return(OFF);
for(i = N0 ; i < LEN ; i++) {
if(fRev[text.c1[i] - A] == OFF) continue; /* 反転チェック対象外文字 /*
if(text.f1[i] == ON) return(OFF); /* 文字が反転している /*
}
return(ON);
}
/******************************************************************************
機能：再帰関数
引数：
(1) t0 : 現時点のテキスト
(2) mae : 前回のリバース位置
(3) n : 何回目か
戻り値：なし
*****************************************************************************/*
void sub(TEXT t0 , int mae , int n)
{
int i; /* ループの制御変数 /*
TEXT t1; /* リバース後のテキスト /*
if(n == max) return; /* 最大回数に達したが、解が見つからない /*
for(i = N0 ; i < N7 ; i++) {
if(mae == i) continue;
q1[n] = i;
rev(&t1 , t0 , i);
if(check(t1) == ON) { /* 正解 /*
printf("正解:%d回\n" , max);
disp(q1);
free(q1);
exit(EXIT_SUCCESS);
}
sub(t1 , i , n + N1);
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：1
*****************************************************************************/*
int main(void)
{
int i; /* ループの制御変数 /*
TEXT text;
for(i = N0 ; i < LEN ; i++) enizagamc[i] = *(CMAGAZINE + LEN - i - N1);
strncpy(text.c1 , CMAGAZINE , LEN);
for(i = N0 ; i < LEN ; i++) text.f1[i] = OFF;
max = N1;
while(N1) {
q1 = (int *)malloc(sizeof(int) * max);
if(q1 == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sub(text , SHOKI , N0);
max++;
free(q1);
}
}
|
第146回（5月）逆さ電卓数字
|
|
/******************************************************************************
Ｃマガジン２００３年２月号出題 逆さ電卓数字
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define N0 0 /* 原点 /*
#define N1 1 /* 最小の単位 /*
#define N7 7 /* 使える数字の個数(0,1,2,5,6,8,9) /*
#define N10 10 /* １０進数 /*
#define N100 100 /* N10 * N10 /*
#define N252 252 /* ３桁の電卓数字の個数(6 * 7 * 6) /*
#define N299 299 /* A + B = C - D Aの上限 (999(C) - 101(A)) / 2 = 499 → 299 /*
#define N699 699 /* 同Bの上限 999(C) - 101(D) - 101(A) = 797 → 699 /*
int an1[N252]; /* ３桁の数字 /*
int ar1[N252]; /* その反転 /*
static int bn1[N7] = {0,1,2,5,6,8,9}; /* 使える数字 /*
static int br1[N7] = {0,1,2,5,9,8,6}; /* その反転 /*
int count = 0; /* 解答 /*
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
int i0 , i1 , i2 , i3; /* ループの制御変数 /*
int sn1; /* A+B /*
int sr1; /* A(反転)+B(反転) /*
int n = N0;
int maxA; /* Aの上限の添え字の値 /*
int maxB; /* Bの上限の添え字の値 /*
for(i0 = N1 ; i0 < N7 ; i0++) {
for(i1 = N0 ; i1 < N7 ; i1++) {
for(i2 = N1 ; i2 < N7 ; i2++) {
an1[n] = bn1[i0] * N100 + bn1[i1] * N10 + bn1[i2];
if (an1[n] == N299) maxA = n;
else if(an1[n] == N699) maxB = n;
ar1[n++] = br1[i2] * N100 + br1[i1] * N10 + br1[i0];
}
}
}
for(i0 = N0 ; i0 <= maxA ; i0++) {
for(i1 = i0 ; i1 <= maxB ; i1++) {
sn1 = an1[i0] + an1[i1];
sr1 = ar1[i0] + ar1[i1];
i3 = 0;
for(i2 = i1 ; i2 < N252 ; i2++) {
while(an1[i2] - an1[i3] > sn1) i3++;
if(sn1 != an1[i2] - an1[i3]) continue;
if(sr1 != ar1[i3] - ar1[i2]) continue;
count++;
}
}
}
printf("%d\n" , count); /* 解答を表示する /*
return(EXIT_SUCCESS);
}
|
第145回（4月）素数団 正解
|
|
/******************************************************************************
Ｃマガジン２００３年１月号出題 素数団
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define N0 0 /* 原点としての０ /*
#define N1 1 /* 最小の単位の数 /*
#define N2 2 /* １＋１ /*
#define SOSU3 3 /* 最小の奇数の素数 /*
#define NKAZU 10 /* 相異なる数の個数 /*
int p1[NKAZU]; /* 0,2,2+4,2+4+6,2+4+6+8,... /*
int *sosu1; /* 素数列 /*
int *sosu2; /* 素数の２乗値の列 /*
int nSosu = N0; /* 素数列に格納した素数の数 /*
/******************************************************************************
機能：初期化処理
引数：なし
戻り値：なし
*****************************************************************************/*
void init(void)
{
int i;
int n = N2;
p1[N0] = N0;
for(i = N1 ; i < NKAZU ; i++) {
p1[i] = p1[i - N1] + n;
n += N2;
}
sosu1 = (int *)malloc(sizeof(int));
if(sosu1 == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sosu2 = (int *)malloc(sizeof(int));
if(sosu2 == NULL) {
free(sosu1);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sosu1[nSosu] = SOSU3;
sosu2[nSosu++] = SOSU3 * SOSU3;
}
/******************************************************************************
機能：３〜sum10までの数が素数かどうかをチェックするのに必要な素数列を生成する。
引数：
sum10 １０個の数の合計値
戻り値：なし
*****************************************************************************/*
void initSosu(int sum10)
{
int j;
int s;
s = sosu1[nSosu - N1];
while(sosu2[nSosu - N1] < sum10) {
s++;
for(j = N0 ; j < nSosu ; j++) {
if((s % sosu1[j]) == 0) break;
}
if(j != nSosu) continue;
sosu1 = (int *)realloc(sosu1 , sizeof(int) * (nSosu + N1));
if(sosu1 == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sosu2 = (int *)realloc(sosu2 , sizeof(int) * (nSosu + N1));
if(sosu2 == NULL) {
free(sosu1);
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sosu1[nSosu] = s;
sosu2[nSosu++] = s * s;
}
}
/******************************************************************************
機能：素数かどうかチェックする。
引数：
n 素数かどうかチェックする対象の数
戻り値：OFF:非素数、ON:素数
*****************************************************************************/*
int check(int n)
{
int i = N0;
while(sosu2[i] <= n) {
if((n % sosu1[i]) == N0) return(OFF);
i++;
}
return(ON);
}
/******************************************************************************
機能：９、１０個目の数を設定する。
引数：
f1 正解がみつかっているかどうかのフラグ
sum10 １０個の数の合計値
kazu １０個の数を格納する
sum ここまでの合計値
戻り値：OFF:正解が見つかってない、1:正解が見つかった
*****************************************************************************/*
int sub10(int f1 , int sum10 , int kazu[] , int sum[])
{
int j;
kazu[NKAZU - N1] = sum10 - sum[NKAZU - N2];
if(kazu[NKAZU - N1] <= kazu[NKAZU - N2]) return(f1);
for(j = N0 ; j < NKAZU ; j++) {
if(check(sum10 - kazu[j]) == OFF) return(f1);
}
if(j < NKAZU) return(f1);
if(f1 == OFF) printf("%d\n" , sum10);
for(j = N0 ; j < NKAZU ; j++) printf("%3d " , kazu[j]);
printf("\n");
return(ON);
}
/******************************************************************************
機能：１〜８個目までの数の値を設定する。
引数：
f1 正解がみつかっているかどうかのフラグ
sum10 １０個の数の合計値
kazu １０個の数を格納する
sum ここまでの合計値
n 値を設定する数の順番（０オリジン）
戻り値：OFF:正解が見つかってない、1:正解が見つかった
*****************************************************************************/*
int sub(int f1 , int sum10 , int kazu[] , int sum[] , int n)
{
int t1; /* まだ値が設定されてない数の個数 /*
t1 = NKAZU - n - N1;
for(kazu[n] = kazu[n - N1] + N2 ; kazu[n] < sum10 ; kazu[n] += N2) {
sum[n] = sum[n - N1] + kazu[n];
if(sum[n] + kazu[n] * t1 + p1[t1] > sum10) break;
if(n == NKAZU - N2) f1 = sub10(f1 , sum10 , kazu , sum);
else f1 = sub(f1 , sum10 , kazu , sum , n + N1);
}
return(f1);
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
int kazu[NKAZU]; /* １０個の数を格納する /*
int sum[NKAZU]; /* 値が決まる都度、それまでの合計値を格納する /*
int f1 = OFF; /* 解答が見つかったかどうかのフラグ /*
int sum10; /* １０個の数の合計値 /*
init(); /* 初期化 /*
sum10 = (N1 + (N2 * NKAZU - N1)) * NKAZU / N2; /* １０個の和の最小値 /*
while(f1 == OFF){ /* 正解が見つかるまでループする /*
initSosu(sum10); /* 3〜sum10が素数かどうかチェックするための初期化 /*
for(kazu[N0] = N1 ; kazu[N0] < sum10 ; kazu[N0] += N2) {
sum[N0] = kazu[N0];
f1 = sub(f1 , sum10 , kazu , sum , N1);
}
sum10 += N2; /* 見つからなかったら合計値を＋２する /*
}
free(sosu1);
free(sosu2);
return(EXIT_SUCCESS);
}
|
第143回（2月）８コイーンプロブレム
|
|
/******************************************************************************
Ｃマガジン２００２年１１月号 ８コイーンプロブレム
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define NON 0 /* コインが置いてない状態 /*
#define COIN_10 1 /* １０円玉が置いてある状態 /*
#define COIN_100 2 /* １００円玉が置いてある状態 /*
#define N0 0 /* 基準値 /*
#define N1 1 /* 最小の単位の数 /*
#define N5 5 /* 盤の縦、横の大きさ /*
#define C2 2 /* 置く１００円玉の数−１ /*
#define C4 4 /* 置く１０円の数−１ /*
#define DP N1 /* 正方向 /*
#define DO N0 /* 方向なし /*
#define DM -N1 /* 負方向 /*
typedef struct {
int ban[N5][N5];
} PAT; /* 既出パターン格納用構造体定義 /*
typedef struct {
int x;
int y;
} XY; /* 座標の構造体定義 /*
typedef struct {
XY x;
XY y;
} XYM;
typedef struct {
XY xy[N5][N5];
} MZ; /* 鏡像変換後の座標の構造体定義 /*
int count = N0; /* 解答。初期値は０ /*
PAT *pat = NULL; /* 既出パターン /*
int nPat = N0; /* 既出パターンの数 /*
int n7; /* 鏡像チェックパターンの数（＝７） /*
int n4; /* N5 - 1 /*
int n9; /* Ｎ５×２−１（＝９） （中心１、負方向４、正方向４）/*
MZ *mz1; /* 鏡像変換後の座標 /*
/******************************************************************************
機能：解答例表示
引数：
(1) ban 盤
戻り値：なし
*****************************************************************************/*
void disp(int ban[][N5])
{
int x , y; /* ループの制御変数 /*
static char *coin[] = {"--" , "100" , "10"}; /* 表示する文字列 /*
printf("解答例(%d)\n" , count + N1);
for(y = N0 ; y < N5 ; y++) {
for(x = N0 ; x < N5 ; x++) printf("%4s" , coin[ban[y][x]]);
printf("\n");
}
}
/******************************************************************************
機能：初期化処理
引数：
(1) ban 盤
戻り値：なし
*****************************************************************************/*
void init(int ban[][N5])
{
static XYM xy[] = { /* 鏡像チェックのための座標軸移動データ /*
DM , DO , DO , DP , /* Ｘ反転 /*
DP , DO , DO , DM , /* Ｙ反転 /*
DM , DO , DO , DM , /* Ｘ、Ｙともに反転 /*
DO , DP , DP , DO , /* ＸＹ入替 /*
DO , DP , DM , DO , /* ＸＹ入れ替えて、Ｘ反転 /*
DO , DM , DP , DO , /* ＸＹ入れ替えて、Ｙ反転 /*
DO , DM , DM , DO}; /* ＸＹ入れ替えて、Ｘ、Ｙともに反転 /*
int i , x , y; /* ループの制御変数 /*
n4 = N5 - 1;
n7 = sizeof(xy) / sizeof(xy[0]);
n9 = N5 + N5 - N1;
mz1 = (MZ *)malloc(sizeof(MZ) * n7);
if(mz1 == NULL) { /* メモリ確保ができなかった場合 /*
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
pat = (PAT *)malloc(sizeof(PAT)); /* 既出パターン用メモリ確保 /*
if(pat == NULL) { /* メモリ確保ができなかった場合 /*
free(mz1);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(i = N0 ; i < n7 ; i ++) {
for(y = N0 ; y < N5 ; y++) {
for(x = N0 ; x < N5 ; x++) {
mz1[i].xy[y][x].x = x * xy[i].x.x+ y * xy[i].x.y;
if(xy[i].x.x == DM || xy[i].x.y == DM) mz1[i].xy[y][x].x += n4;
mz1[i].xy[y][x].y = x * xy[i].y.x + y * xy[i].y.y;
if(xy[i].y.x == DM || xy[i].y.y == DM) mz1[i].xy[y][x].y += n4;
}
}
}
for(y = N0 ; y < N5 ; y++) {
for(x = N0 ; x < N5 ; x++) ban[y][x] = NON; /* 盤の初期化 /*
}
}
/******************************************************************************
機能：１０円玉を置けるかどうかのチェック（縦横斜めチェック）
引数：
(1) ban 盤
(2) x １０円玉を置く場所のＸ座標
(3) y １０円玉を置く場所のＹ座標
戻り値：ON:置ける、OFF:置けない
*****************************************************************************/*
int check10(int ban[][N5] , int x , int y)
{
int i; /* ループの制御変数 /*
int x1 , y1; /* 斜め方向の座標 /*
for(i = N0 ; i < N5 ; i++) {
if(ban[y][i] == COIN_100) return(OFF); /* 横 /*
if(ban[i][x] == COIN_100) return(OFF); /* 縦 /*
}
x1 = x - n4; /* 斜め(Ｘ負Ｙ負→Ｘ正Ｙ正) /*
y1 = y - n4;
for(i = N0 ; i < n9 ; i++) {
if(x1 >= N5) break;
if(y1 >= N5) break;
if(x1 >= N0 && y1 >= N0) {
if(ban[y1][x1] == COIN_100) return(OFF);
}
x1++;
y1++;
}
x1 = x - n4; /* 斜め(Ｘ負Ｙ正→Ｘ正Ｙ負) /*
y1 = y + n4;
for(i = 0 ; i < n9 ; i++) {
if(x1 >= N5) break;
if(y1 < N0) break;
if(x1 >= N0 && y1 < N5) {
if(ban[y1][x1] == COIN_100) return(OFF);
}
x1++;
y1--;
}
return(ON);
}
/******************************************************************************
機能：鏡像チェック
引数：
(1) ban 盤
戻り値：ON:初めてのパターン、OFF:既出パターン
*****************************************************************************/*
int checkMirror(int ban[][N5])
{
int x , y;
int i , j; /* ループの制御変数 /*
for(i = N0 ; i < nPat ; i++) {
for(j = N0 ; j < n7 ; j++) {
for(y = N0 ; y < N5 ; y++) {
for(x = N0 ; x < N5 ; x++) {
if(ban[y][x] !=
pat[i].ban[mz1[j].xy[y][x].y][mz1[j].xy[y][x].x])
break;
}
if(x < N5) break;
}
if(y == N5) return(OFF); /* 既出パターンならOFF /*
}
}
pat = (PAT *)realloc(pat , sizeof(PAT) * (nPat + N1));
if(pat == NULL) { /* メモリ確保ができなかった場合 /*
free(mz1);
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(y = N0 ; y < N5 ; y++) {
for(x = N0 ; x < N5 ; x++) pat[nPat].ban[y][x] = ban[y][x];
}
nPat++;
return(ON);
}
/******************************************************************************
機能：１０円玉を置く（再帰呼び出し）
引数：
(1) ban 盤
(2) x 一個前の１０円玉を置いた場所のＸ座標
(3) y 一個前の１０円玉を置いた場所のＹ座標
(4) n 過去に置いた１０円玉の個数
戻り値：なし
*****************************************************************************/*
void sub_10(int ban[][N5] , int x , int y , int n)
{
if(checkMirror(ban) == OFF) return; /* 既出パターンなら探索中止 /*
y += (x / N5);
x %= N5;
while(y < N5) {
while(x < N5) {
if(ban[y][x] == NON && check10(ban , x , y) == ON) {
ban[y][x] = COIN_10; /* １０円玉を置く /*
if(n < C4) sub_10(ban , x + N1 , y , n + N1);
else {
disp(ban); /* 解答例表示 /*
count++; /* カウントアップ /*
}
ban[y][x] = NON; /* １０円玉を取り除く /*
}
x++;
}
x = N0;
y++;
}
}
/******************************************************************************
機能：１００玉を置く（再帰呼び出し）
引数：
(1) ban 盤
(2) x 一個前の１００円玉を置いた場所のＸ座標
(3) y 一個前の１００円玉を置いた場所のＹ座標
(4) n 過去に置いた１００玉の個数
戻り値：なし
*****************************************************************************/*
void sub_100(int ban[][N5] , int x , int y , int n)
{
if(checkMirror(ban) == OFF) return; /* 既出パターンなら探索中止 /*
y += (x / N5);
x %= N5;
while(y < N5) {
while(x < N5) {
if(ban[y][x] == NON) {
ban[y][x] = COIN_100; /* １００円玉を置く /*
if(n < C2) sub_100(ban , x + N1 , y , n + N1);
else sub_10(ban , N0 , N0 , N0);
ban[y][x] = NON; /* １００円玉を取り除く /*
}
x++;
}
x = N0;
y++;
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：１
*****************************************************************************/*
int main(void)
{
int ban[N5][N5]; /* 盤 /*
init(ban); /* 初期化 /*
sub_100(ban , N0 , N0 , N0);
free(pat); /* メモリ開放 /*
free(mz1);
printf("解答：%d通り\n" , count);
return(EXIT_SUCCESS);
}
|
第142回（1月）割り算の得意な金庫
|
|
/******************************************************************************
Ｃマガジン２００２年１０月号出題（割り算の得意な金庫）
*****************************************************************************/*
#include <stdio.h>
#include <stdlib.h>
#define OFF 0 /* オフ /*
#define ON 1 /* オン /*
#define NDIAL 5 /* ダイアルの数 /*
#define N0 0 /* 原点 /*
#define N1 1 /* 最小単位 /*
#define N2 2 /* 割る数の初期値 /*
#define N9 9 /* １桁の数の最大値 /*
#define N10 10 /* １０進法の１０ /*
int d4 = N1; /* ダイアルの数の桁数の最小値 /*
int d5 = N1; /* ダイアルの数の桁数の最大値＋１ /*
typedef struct {
unsigned char *fSumi; /* チェック済フラグ /*
} SUMI;
SUMI *sumi; /* チェック済フラグ /*
int maxN = N2; /* 正解 /*
/******************************************************************************
機能：探索関数(ダイヤルを一つ回す)
引数：
(1) dial[] (INPUT) 各ダイヤルの番号
(2) n (INPUT) 現在のＮ
(3) dval (INPUT) ダイヤルのＤ値
戻り値：なし
*****************************************************************************/*
void sub(int dial[] , int n , int dval)
{
int n2; /* ダイヤルを１つ回転後のＮ /*
int i; /* ループの制御変数 /*
int dial2[NDIAL]; /* 一つ回転後のダイアル /*
int b1; /* Ｄ値を求める際のダイヤルごとの乗数 /*
b1 = d4;
for(i = N0 ; i < NDIAL ; i++) dial2[i] = dial[i];
if((dval % n) != N0) return;
if(n > maxN) {
maxN = n;
sumi = (SUMI *)realloc(sumi , sizeof(SUMI) * (maxN + N1));
if(sumi == NULL) {
fprintf(stderr , "realloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
sumi[n].fSumi = (unsigned char *)malloc(sizeof(unsigned char) * d5);
if(sumi[n].fSumi == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(i = N0 ; i < d5 ; i++) sumi[maxN].fSumi[i] = OFF;
}
if(sumi[n].fSumi[dval] == ON) return;
sumi[n].fSumi[dval] = ON;
n2 = n + N1;
for(i = N0 ; i < NDIAL ; i++) {
dial2[i] = (dial[i] + N9) % N10; /* ダイヤルを負の方向に回す /*
if(dial[i] == N0) sub(dial2 , n2 , dval + N9 * b1);
else sub(dial2 , n2 , dval - b1);
dial2[i] = (dial[i] + N1) % N10; /* ダイヤルを正の方向に回す /*
if(dial[i] == N9) sub(dial2 , n2 , dval - N9 * b1);
else sub(dial2 , n2 , dval + b1);
dial2[i] = dial[i];
b1 /= N10;
}
}
/******************************************************************************
機能：スタート時点の番号設定
引数：
(1) dial[] (INPUT) 各ダイヤルの番号
(2) n (INPUT) 設定するダイヤルの順番の番号
(3) dval (INPUT) ダイヤルのＤ値
戻り値：なし
*****************************************************************************/*
void initD(int dial[] , int n , int dval)
{
int dval2; /* 一つダイヤル設定後のＤ値 /*
for(dial[n] = N0 ; dial[n] < N10 ; dial[n]++) {
dval2 = dial[n] + dval * N10;
if(n < NDIAL - N1) initD(dial , n + N1 , dval2);
else sub(dial , N2 , dval2);
}
}
/******************************************************************************
機能：メイン
引数：なし
戻り値：1
*****************************************************************************/*
int main(void)
{
int i , j; /* ループの制御変数 /*
int dial[NDIAL]; /* 各ダイヤルの番号 /*
for(i = 1 ; i < NDIAL ; i++) d4 *= N10;
d5 = d4 * N10;
sumi = (SUMI *)malloc(sizeof(SUMI) * (maxN + N1));
if(sumi == NULL) {
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(i = N0 ; i < maxN + N1 ; i++) {
sumi[i].fSumi = (unsigned char *)malloc(sizeof(unsigned char) * d5);
if(sumi == NULL) {
free(sumi);
fprintf(stderr , "malloc error at %d\n" , __LINE__);
exit(EXIT_FAILURE);
}
for(j = N0 ; j < d5 ; j++) sumi[i].fSumi[j] = OFF;
}
initD(dial , N0 , N0);
for(i = N0 ; i < maxN + N1 ; i++) free(sumi[i].fSumi);
free(sumi);
printf("解答：N=%d\n" , maxN);
return(EXIT_SUCCESS);
}
| | | | | | | | | |