经典游戏问题算法集一

作者在 2010-05-25 13:02:01 发布以下内容
经典游戏问题算法集

1.奇数阶魔方阵
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20

void main(void)
{
int matrix[MAXSIZE][MAXSIZE]; /* the magic square */
int count; /* 1..n*n counting */
int row; /* row index */
int column; /* column index */
int order; /* input order */
char line[100];

printf("\nOdd Order Magic Square Generator");
printf("\n================================");
printf("\n\nOrder Please --> ");
gets(line);
order = atoi(line);

if (order > MAXSIZE)
printf("\n*** ERROR *** Order should be <= %d", MAXSIZE);
else if (order % 2 == 0)
printf("\n*** ERROR *** Order must be an odd integer");
else {
row = 0; /* start of from the middle */
column = order/2; /* of the first row. */
for (count = 1; count <= order*order; count++) {
matrix[row][column] = count; /* put next # */
if (count % order == 0) /* move down ? */
row++; /* YES, move down one row */
else { /* compute next indices */
row = (row == 0) ? order - 1 : row - 1;
column = (column == order-1) ? 0 : column + 1;
}
}
printf("\n\nMagic Square of order %d :\n\n", order);
for (row = 0; row < order; row++) {
for (column = 0; column < order; column++)
printf("%4d", matrix[row][column]);
printf("\n");
}
}
}
-------------------------------------------------------------------------------------------------------------------------------------------
2.单偶数阶魔方阵
#define MAXSIZE 30

void singly_even(int [][MAXSIZE], int);
void magic_o(int [][MAXSIZE], int);
void exchange(int [][MAXSIZE], int);

/* ------------------------------------------------------ */
/* FUNCTION singly_even : */
/* This is the driver program. It fills the upper-left*/
/* lower-right, upper-right and lower-left parts by using */
/* odd order magic square routine. Then exchange some */
/* parts in each routine in order to maintain the magic */
/* properties. */
/* ------------------------------------------------------ */

void singly_even(int matrix[][MAXSIZE], int n)
{
int half = n/2;

magic_o(matrix, half);
exchange(matrix, n);
}


/* ------------------------------------------------------ */
/* FUNCTION magic_o : */
/* Odd order magic square routine. It fills the block */
/* bounded by left, right, top and bottom with numbers */
/* starting from 'start'. Otherwise all are the same as */
/* the magic square routine discussed before. */
/* ------------------------------------------------------ */

void magic_o(int matrix[][MAXSIZE], int n)
{
int count; /* fill counting */
int row; /* row index */
int column; /* column index */

row = 0; /* start of from the middle */
column = n/2; /* of the first row. */
for (count = 1; count <= n*n; count++) {
matrix[row][column] = count; /* put # in A */
matrix[row+n][column+n] = count + n*n; /* in B */
matrix[row][column+n] = count + 2*n*n; /* in C */
matrix[row+n][column] = count + 3*n*n; /* in D */
if (count % n == 0) /* move downward ? */
row++; /* YES, move down one row */
else { /* compute next indices */
row = (row == 0) ? n - 1 : row - 1;
column = (column == n-1) ? 0 : column + 1;
}
}
}

#define SWAP(x,y) { int t; t = x; x = y; y = t;}

void exchange(int x[][MAXSIZE], int n)
{
int width = n / 4;
int width1 = width - 1;
int i, j;

for (i = 0; i < n/2; i++)
if (i != width) { /* if not the width-row */
for (j = 0; j < width; j++)
SWAP(x[i][j], x[n/2+i][j]);
for (j = 0; j < width1; j++)
SWAP(x[i][n-1-j], x[n/2+i][n-1-j]);
}
else { /* width-row is special */
for (j = 1; j <= width; j++)
SWAP(x[width][j], x[n/2+width][j]);
for (j = 0; j < width1; j++)
SWAP(x[width][n-1-j], x[n/2+width][n-1-j]);
}
}

/* ------------------------------------------------------ */

#include <stdio.h>
#include <stdlib.h>

void main(void)
{
int matrix[MAXSIZE][MAXSIZE];
int n;
int i, j;
char line[100];

printf("\nSingly-Even Order Magic Square");
printf("\n==============================");
printf("\n\nOrder Please (must be 2*(2k+1)) --> ");
gets(line);
n = atoi(line);

if (n % 2 == 0 && (n/2) % 2 == 1) {
singly_even(matrix, n);
printf("\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%4d", matrix[i][j]);
printf("\n");
}
}
else
printf("\n*** Illegal Order ***");
}
--------------------------------------------------------------------------------------------------------------------------------------------------
3.双偶数阶魔方阵
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 /* square size */
#define MARK -1 /* marker for build up */

void main(void)
{
int square[MAXSIZE][MAXSIZE]; /* the square */
int n; /* order of the magic square*/
int count, inv_count; /* 1 -> n^2 and n^2 -> 1 */
int marker; /* working marker 1,-1,1,-1 */
int i, j;
char line[100];

printf("\nDoubly-Even Magic Square");
printf("\n========================");
printf("\n\nOrder (4*m, m>0) please --> ");
gets(line);
n = atoi(line);
if (n % 4 != 0)
printf("\n*** Illegal Order *****");
else {
marker = MARK; /* mark the upper part */
for (i = 0; i < n/2; i++, marker = -marker)
for (j = 0; j < n/2; j++, marker = -marker)
square[i][j] = square[i][n-1-j] = marker;

count = 1; /* upward counter */
inv_count = n*n; /* downward counter */
for (i = 0; i < n/2; i++)
for (j = 0; j < n; j++)
if (square[i][j] != MARK) { /* marked*/
square[i][j] = count++;
square[n-1-i][n-1-j] = inv_count--;
}
else { /* unmarked */
square[i][j] = inv_count--;
square[n-1-i][n-1-j] = count++;
}
printf("\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%4d", square[i][j]);
printf("\n");
}
}
}

默认分类 | 阅读 780 次
文章评论,共0条
游客请输入验证码
文章分类