经典游戏问题算法集(页 1) - 数据结构与算法 - 编程论坛

sunnvya 发表于 2006-3-28 20:28

经典游戏问题算法集

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"); } } } ---------------------------------------------------------------------------------------------------------------------------------------------------- 
[align=right][color=#000066][此贴子已经被作者于2006-3-29 18:06:09编辑过][/color][/align]

sunnvya 发表于 2006-3-28 20:29

4.八皇后问题公式解 #include <stdio.h> #include <stdlib.h>
#define MAXSIZE 30 #define MARK 'Q'
void initial(void); void display(void); void class_1(void); void class_2(void); void class_3(void); void class_4(void);
int n; /* input board size */ char board[MAXSIZE+1][MAXSIZE+1]; /* the chess board */
void main(void) { void (*funct[])() = { class_1, class_2, /* functions */ class_4, class_3, /* of four */ class_1, class_2 /* classes */ }; char line[100];
 printf("\nOne Solution for N Queens' Problem"); printf("\n=================================="); printf("\n\nBoard Size Please (N > 3) --> "); gets(line); n = atoi(line);
 if (n > 3) { initial(); /* initial the chess board */ (*funct[n % 6])(); /* call appropriate funct. */ display(); /* print result */ } else printf("\nIllegal Board Size."); }
 /* ------------------------------------------------------ */ /* FUNCTION initial : */ /* Initialize the chess board to blank. */ /* ------------------------------------------------------ */
void initial(void) { int i, j;
 for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) board[i][j] = ' '; }
 /* ------------------------------------------------------ */ /* FUNCTION display : */ /* Function to display the chess board. */ /* ------------------------------------------------------ */
#define DRAWGRID(N) { int i; \ printf("\n+"); \ for (i = 1; i <= N; i++) \ printf("-+"); \ }
 #define DRAWLINE(N, r) { int i; \ printf("\n|"); \ for (i = 1; i <= N; i++) \ printf("%c|", board[r][i]);\ }
void display(void) { int r;
 DRAWGRID(n); for (r = 1; r <= n; r++) { DRAWLINE(n, r); DRAWGRID(n); } }
 /* ------------------------------------------------------ */ /* FUNCTION class_1 : */ /* Solution for n mod 6 == 0 or 4. */ /* ------------------------------------------------------ */
void class_1(void) { int i;
 for (i = 1; i <= n/2; i++) board[2*i][i] = board[2*i-1][n/2+i] = MARK; }
 /* ------------------------------------------------------ */ /* FUNCTION class_2 : */ /* Solution for n mod 6 == 1 or 5. */ /* ------------------------------------------------------ */
void class_2(void) { int i;
 for (i = 1; i <= (n-1)/2; i++) board[2*i][i] = MARK; for (i = 1; i <= (n+1)/2; i++) board[2*i-1][(n-1)/2+i] = MARK; }
 /* ------------------------------------------------------ */ /* FUNCTION class_3 : */ /* Solution for n mod 6 == 3. */ /* ------------------------------------------------------ */
void class_3(void) { int i;
 for (i = 1; i <= (n-3)/2; i++) board[2*i+2][i] = board[2*i+3][(n-1)/2+i] = MARK; board[1][n-1] = board[2][(n-2)/2] = board[3][n] = MARK; }
 /* ------------------------------------------------------ */ /* FUNCTION class_4 : */ /* Solution for n mod 6 = 2. */ /* ------------------------------------------------------ */
void class_4(void) { int i;
 if (n > 8) { for (i = 1; i <= 3; i++) board[2*i-1][n/2-2+i] = MARK; board[2][n] = board[4][1] = board[6][n-1] = MARK; for (i = 1; i <= n/2 - 3; i++) board[2*i+5][i+1] = board[2*i+6][n/2+1+i] = MARK; } else { for (i = 1; i <= 4; i++) board[2*i][i] = MARK; board[1][6] = board[3][5] = MARK; board[5][8] = board[7][7] = MARK; } } 
[align=right][color=#000066][此贴子已经被作者于2006-3-29 18:06:52编辑过][/color][/align]

sunnvya 发表于 2006-3-28 20:30

5.八皇后问题递归解 #include <stdio.h> #include <stdlib.h>
#define MAXSIZE 20 /* max. board size */ #define DIAG_SIZE 39 /* max. # of diagonals */ #define OCCUPIED 0 #define EMPTY 1
void initial(void); void display(void); void try(int);
int pos[MAXSIZE+1]; /* pos[j]=i means Q is (i,j)*/ int in_row[MAXSIZE+1]; /* in_row[i] true->row occ. */ int diag[DIAG_SIZE+1]; /* diag[i] or back_diag[i] */ int back_diag[DIAG_SIZE+1]; /* = true -> occupied. */ int n; /* input board size */ int count = 0; /* # of solutions counter */
void main(void) { int i, j; char line[100];
 printf("\nAll Possible Solutions of N Queens' Problem"); printf("\n==========================================="); printf("\n\nBoard Size (N > 3) --> "); gets(line); n = atoi(line);
 initial(); try(1); /* starting from column 1 */ printf("\n\nThere are %d solutions in total.", count); }
 /* ------------------------------------------------------ */ /* FUNCTION initial : */ /* Function to initial the chess board. */ /* ------------------------------------------------------ */
void initial(void) { int i;
 for (i = 1; i <= n; i++) in_row[i] = EMPTY; for (i = 1; i <= 2*n - 1; i++) diag[i] = back_diag[i] = EMPTY;
 printf("\nSolutions are represented the row # in a column"); printf("\n\n #"); for (i = 1; i <= n; i++) printf("%3d", i); printf("\n---"); for (i = 1; i <= n; i++) printf(" --"); }
 /* ------------------------------------------------------ */ /* FUNCTION display : */ /* Function to display a single solution. */ /* ------------------------------------------------------ */
void display(void) { int i;
 printf("\n%3d", count); for (i = 1; i <= n; i++) printf("%3d", pos[i]); }
 /* ------------------------------------------------------ */ /* FUNCTION try : */ /* Given a column number, this function tries to put */ /* a queen on some row of that column until all possible */ /* rows are attampted. */ /* ------------------------------------------------------ */
#define SAVE(r,c) (in_row[r] && back_diag[r+c-1] && diag[n-(c-r)]) #define SET(r,c) { pos[c] = r; \ in_row[r] = OCCUPIED; \ back_diag[r+c-1] = OCCUPIED; \ diag[n-(c-r)] = OCCUPIED; \ } #define RESET(r,c) { in_row[r] = EMPTY; \ back_diag[r+c-1] = EMPTY; \ diag[n-(c-r)] = EMPTY; \ } void try(int column) { int row;
 for (row = 1; row <= n; row++) /* for each row */ if (SAVE(row, column)) { /* is it save ? */ SET(row, column); /* YES, make a record*/ if (column < n) /* all columns tried?*/ try(column+1); /* NO, try next col. */ else { count++; /* OR, we found a sol*/ display(); /* display it. */ } RESET(row, column); /* restore and back. */ } } 
[align=right][color=#000066][此贴子已经被作者于2006-3-29 18:08:17编辑过][/color][/align]

sunnvya 发表于 2006-3-29 18:02

6.武士巡逻问题
#include <stdio.h> #include <stdlib.h>
#define MAXSIZE 10 /* max. board size */ #define MAX_STACK 100 /* stack size = board-size^2*/ #define SUCCESS 1 /* return value for a succ. */ #define FAILURE 0 /* for a failure. */ #define EMPTY -1 /* value to indicate empty */
/* ----------------- external variables ----------------- */
int board[MAXSIZE+1][MAXSIZE+1]; /* chess board */ int n; /* working board size */ int offset_x[] = { 2, 1, -1, -2, -2, -1, 1, 2}; int offset_y[] = { 1, 2, 2, 1, -1, -2, -2, -1};
int path_x[MAX_STACK+1]; /* stack for x coordinate */ int path_y[MAX_STACK+1]; /* stack for y coordinate */ int direction[MAX_STACK+1]; /* stack for direction */ int top; /* stack pointer */
/* ----------------- function prototype ----------------- */
void initial(void); void display(void); int try(int, int);
/* -------------------- main program -------------------- */
void main(void) { int row, column; char line[100];
 printf("\nRecursive Knight Tour Problem"); printf("\n============================="); printf("\n\nBoard Size ----> "); gets(line); n = atoi(line); printf( "Start Row -----> "); gets(line); row = atoi(line); printf( "Start Column --> "); gets(line); column = atoi(line); initial(); if (try(row, column) == FAILURE) printf("\nNO SOLUTION AT ALL."); else display(); }
 /* ------------------------------------------------------ */ /* FUNCTION initial : */ /* initialize the chess board to EMPTY. */ /* ------------------------------------------------------ */
void initial(void) { int i, j;
 for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) board[i][j] = EMPTY; }
 /* ------------------------------------------------------ */ /* FUNCTION display : */ /* display to chess board. */ /* ------------------------------------------------------ */
#define DRAWGRID(N) { int i; \ printf("\n+"); \ for (i = 1; i <= N; i++) \ printf("--+"); \ }
 #define DRAWLINE(N, r) { int i; \ printf("\n|"); \ for (i = 1; i <= N; i++) \ printf("%2d|",board[r][i]);\ }
 void display(void) { int r;
 printf("\n\nHere is One Possible Solution :\n"); DRAWGRID(n); for (r = 1; r <= n; r++) { DRAWLINE(n,r); DRAWGRID(n); } }
 /* ------------------------------------------------------ */ /* FUNCTION try : */ /* The main non-recursive backtrack working routine. */ /* ------------------------------------------------------ */
#define YES 1 #define NO 0 #define BOARD(x,y) (1<=x) && (x<=n) && (1<=y) && (y<=n) #define CHECK(x,y) board[x][y] == EMPTY #define PUSH(x,y) { top++; \ path_x[top] = x; path_y[top] = y; \ direction[top] = 0; \ board[x][y] = top; \ }
int try(int x, int y) { int new_x, new_y; int found;
 top = -1; /* initial to empty */ PUSH(x, y); /* push first pos. and dir. */ while (top < n*n-1) { /* loop until the board full*/ found = NO; while (direction[top] < 8) { /* try all 8 pos. */ new_x = path_x[top] + offset_x[direction[top]]; new_y = path_y[top] + offset_y[direction[top]]; if (BOARD(new_x,new_y) && CHECK(new_x,new_y)) { PUSH(new_x, new_y); /* a new pos. PUSH*/ found = YES; /* set flag */ break; /* try next pos. */ } else direction[top]++; /* OR try next dir*/ } if (!found) /* if no new pos. is found */ if (top > 0) { /* do we have prev. item? */ board[path_x[top]][path_y[top]] = EMPTY; direction[--top]++; /* YES, backtrack */ } else return FAILURE; /* otherwise, FAILURE */ } return SUCCESS; /* all pos. visited. DONE */ }

sunnvya 发表于 2006-3-29 18:03

7.环游世界问题
#include <stdio.h>
#define MAXSIZE 30 /* no more than 30 vertices */ #define ALWAYS 1 #define SUCCESS 1 #define FAILURE 0 #define YES 1 #define NO 0
/* ------------------------------------------------------ */ /* FUNCTION read_in : */ /* Read in the number of vertices and the edges. Then */ /* build up the adjacenct matrix. NOTE that because the */ /* graph is undirected, an edga (s,t) will represent two */ /* 'edges' in the graph, namely (s,t) and (t,s). This */ /* function reflects this fact by set two entries. */ /* ------------------------------------------------------ */
void read_in(int connected[][MAXSIZE], int *n) { int i, j;
 scanf("%d", n); /* read in the number of VTX*/ for (i = 0; i < *n; i++) /* clear the adjacent matrix*/ for (j = 0; j < *n; j++) connected[i][j] = NO;
 scanf("%d%d", &i, &j); /* read in first edge */ while (i != 0 && j != 0) { /* end ? */ connected[i-1][j-1] = YES; /* NO, setup two */ connected[j-1][i-1] = YES; /* symmetric edges */ scanf("%d%d", &i, &j); /* read next one */ } for (i = 0; i < *n; i++) /* clear diagonal */ connected[i][i] = NO; }
/* ------------------------------------------------------ */ /* FUNCTION hamilton : */ /* Given the adjacent matrix connected[], the number */ /* of vertices and the start vertex, this function finds */ /* a Hamilton Cycle and stores it in cycle[]. */ /* ------------------------------------------------------ */
int hamilton(int connected[][MAXSIZE], int cycle[], int n, int start) { int *visited; /* visited marks */ int top, i;
 visited = (int *) malloc(sizeof(int)*n); /* get mem. */ for (i = 0; i < n; i++) /* clear marks to NO */ visited[i] = NO; visited[start] = YES; /* but the start has visited*/
 cycle[0] = start; /* the cycle has 'start' */ cycle[1] = 0; /* next in cycle is VTX 0 */ top = 1; /* the top working element */
 while (ALWAYS) { /* loop until done */ for (i = cycle[top]; i < n; i++) /* find next */ if (connected[cycle[top-1]][i] && !visited[i]) break; if (i < n) { /* all neighbors tried? */ cycle[top] = i;/* NO, a new vertex in cycle*/ visited[cycle[top]] = YES; if (top == n-1 && connected[cycle[top]][start]) { free(visited); /* if all visited ... */ return SUCCESS;/* return SUCCES */ } else /* otherwise, advance. */ cycle[++top] = 0; } else { /* next not found ..... */ visited[cycle[--top]] = NO; /* backtrack */ if (top == 0) { /* return to the start VTX?*/ free(visited); /* YES, failed. */ return FAILURE; } cycle[top]++; /* NO, move to neighbr */ } } }
/* ------------------------------------------------------ */ /* FUNCTION display : */ /* Display the found cycle. */ /* ------------------------------------------------------ */
void display(int cycle[], int n) { int i; printf("\n\nA Hamilton Cycle is Listed as Follows :"); printf("\n\n%d", cycle[0]+1); for (i = 1; i < n; i++) printf("->%d", cycle[i]+1); printf("->%d", cycle[0]+1); }
 /* ------------------------------------------------------ */
void main(void) { int connected[MAXSIZE][MAXSIZE]; int cycle[MAXSIZE]; int n;
 printf("\nHamilton Cycle Program"); printf("\n======================"); read_in(connected, &n); if (hamilton(connected, cycle, n, 0) == SUCCESS) display(cycle, n); else printf("\n\nNO Hamilton Cycle at all."); }

sunnvya 发表于 2006-3-29 18:03

8.一笔画问题 #include <stdio.h> #include <stdlib.h>
#define MAXSIZE 20 #define ALWAYS 1 #define YES 1 #define NO 0 #define SUCCESS 1 #define FAIL -1
/* ------------------------------------------------------ */ /* types and external variables */ /* ------------------------------------------------------ */
typedef struct node Node; /* trail node (linked list) */
struct node { /* a node consists of ... */ int vertex; /* a vertex number field */ Node *next; /* and a next node ptr */ };
int connect[MAXSIZE][MAXSIZE]; /* the connection matrix */ int deg[MAXSIZE]; /* degree array */ int n; /* number of vertices */ Node *trail; /* pointer to Euler trail */
/* ------------------------------------------------------ */ /* function prototypes */ /* ------------------------------------------------------ */
void read_in(void); Node *euler(void); int prepare(Node **, Node **); int find_next(Node **); void find_trail(int, Node **, Node **); void display(void);
/* ------------------------------------------------------ */
void main(void) { printf("\nEuler Trail Program"); printf("\n===================\n");
 read_in(); /* get data */ trail = euler(); /* compute Euler Trail */ display(); /* display result */ } /* ------------------------------------------------------ */ /* FUNCTION read_in : */ /* This function reads in the connection matrix and */ /* then compute the degree array. */ /* ------------------------------------------------------ */
void read_in(void) { int i, j; char line[100];
 gets(line); /* get in number of vertices*/ n = atoi(line); for (i = 0; i < n; i++) { /* clear the connection mtx*/ deg[i] = 0; for (j = 0; j < n; j++) connect[i][j] = 0; } gets(line); /* get 1st line of edge set */ sscanf(line, "%d%d", &i, &j); while (i != 0 && j != 0) { /* end of file ? */ if (i != j) { /* a loop ? */ connect[i-1][j-1]++; /* increase edge cnt*/ connect[j-1][i-1]++; deg[i-1]++; /* increase degree count */ deg[j-1]++; } else /* ignore all self loops */ printf("\n*** ERROR *** A loop found. Data ignored"); gets(line); /* get next edge */ sscanf(line, "%d%d", &i, &j); } }
/* ------------------------------------------------------ */ /* FUNCTION euler : */ /* This is the main working routine of this program. */ /* It calls prepare() to initialize various data field and*/ /* some checks. Then compute the Euler Trail loop by loop*/ /* ------------------------------------------------------ */
Node *euler(void) { Node *current; /* processing cursor */ Node *head, *tail; /* bound a partial trail */ Node *p1, *p2; /* working pointer variables*/ int VTX;
 if (prepare(&head, &tail) == FAIL) /* prepare data */ return NULL; /* if fail, return NULL */
 current = tail; /* start from the tail */ while (ALWAYS) if ((VTX = find_next(&current)) != FAIL) { find_trail(VTX, &p1, &p2); p2->next = current->next; /* join the trail*/ current->next = p1; current = p1; /* step to next node */ } else break; return head; /* return the trail list */ }
/* ------------------------------------------------------ */ /* FUNCTION prepare : */ /* This function checks to see if there are more two */ /* odd degree vertices. It reject a graph with more than */ /* two odd degree vertices. Then it builds a preliminary */ /* trail list consisting of one node (if all vertices are */ /* even), or two nodes (for the two odd degree vertices). */ /* ------------------------------------------------------ */
int prepare(Node **first, Node **last) { Node *p1, *p2; int no, odd_no, i; int odd[2];
 for (no = odd_no = i = 0; i < n; i++) /* test odd deg*/ if (deg[i] % 2 != 0) { odd_no++; if (no < 2) odd[no++] = i; } if (odd_no > 2) { /* more than two odd deg VTX*/ printf("\n*** ERROR *** too many odd degree vertices."); return FAIL; } if (odd_no == 2) { /* exactly two odd VTX */ p1 = (Node *) malloc(sizeof(Node)); /* get mem. */ p2 = (Node *) malloc(sizeof(Node)); connect[odd[0]][odd[1]]--; /* just remove this */ connect[odd[1]][odd[0]]--; /* odd degree edge */ deg[odd[0]]--; deg[odd[1]]--; p1->vertex = odd[0]; /* these two vertices are */ p1->next = p2; /* the must for first step */ p2->vertex = odd[1]; /* thus put them into the */ p2->next = NULL; /* trail list */ *first = p1; /* return this list */ *last = p2; } else { /* all vertices are even */ p1 = (Node *) malloc(sizeof(Node)); /* get mem. */ p1->vertex = 0; /* it is the only one node */ p1->next = NULL; /* in the trail list */ *first = *last = p1;/* return the trail list */ } return SUCCESS; }
/* ------------------------------------------------------ */ /* FUNCTION find_next : */ /* Given a pointer to some vertex which has already */ /* been put into trail list, this function scans the trail*/ /* list in order to find a vertex with non-zero degree. */ /* ------------------------------------------------------ */
int find_next(Node **p) { for (;(*p)!=NULL && deg[(*p)->vertex]==0; (*p)=(*p)->next) ; return ((*p) == NULL) ? FAIL : (*p)->vertex; }
/* ------------------------------------------------------ */ /* FUNCTION find_trail : */ /* Given a vertex, this function computes a trail */ /* starting from the given vertex and returns the trail */ /* list found. */ /* ------------------------------------------------------ */
void find_trail(int start, Node **head, Node **tail) { Node *first, *last, *ptr; int p, i, done;
 first = last = NULL; /* no node in list currently*/ p = start; /* p is a moving vertex */ done = NO; while (ALWAYS) { for (i = 0; i < n && !connect[p][i]; i++) ; /* find a VTX adjacent to p */ if (i < n) { /* p->i is possible */ connect[p][i]--, connect[i][p]--; deg[p]--, deg[i]--; ptr = (Node *) malloc(sizeof(Node)); ptr->vertex = i; /* make node and put */ ptr->next = NULL; /* it into the trail */ if (first == NULL) first = last = ptr; else { last->next = ptr; last = ptr; } p = i; /* step to the next */ } else /* if can not proceed, stop */ break; } *head = first; /* return the trail list */ *tail = last; }
/* ------------------------------------------------------ */ /* FUNCTION display : */ /* Simple routine. It display the Euler Trail. */ /* ------------------------------------------------------ */
void display(void) { Node *ptr = trail; int i = 0;
 if (trail == NULL) return; printf("\nAn Euler Trail has been Found :\n"); for ( ; ptr->next != NULL; ptr = ptr->next, i++) { if (i % 15 == 0) printf("\n"); printf("%2d->", ptr->vertex+1); } if (i % 15 == 0) printf("\n"); /* the last item */ printf("%2d", ptr->vertex+1); }

sunnvya 发表于 2006-3-29 18:04

9.非递归河内之塔问题
#include <stdio.h> #include <stdlib.h>
#define MAX_DISK 31
int which_disk(unsigned long *);
void main(void) { int number_of_disk; /* the number of disks */ int pin[MAX_DISK+1]; /* locations of disks */ int dir[2]; /* directions; 0=pos,1=neg */ int disk; /* disk to be moved */ int next; /* next position of 'disk' */ int index; /* direction subscript */ unsigned long number_of_moves; /* number of moves */ unsigned long counter; /* counter for Gray Code */ unsigned long i; /* working */ char line[100]; /* input line */
 printf("\nIterative Towers of Hanoi Program"); printf("\n================================="); printf("\n\nHow many disks (<=31) ? "); gets(line);
 number_of_disk = atoi(line); number_of_moves = (0x01UL << number_of_disk) - 1; counter = 0; /* counter for Gray Code */
 if (number_of_disk & 0x01) /* setup direction */ dir[0] = 0, dir[1] = 1; else dir[0] = 1, dir[1] = 0;
 for (i = 1; i <= number_of_disk; i++) /* set up loc. */ pin[i] = 1;
 printf("\n Step Disk # From To"); printf("\n -----------------------------");
 for (i = 1; i <= number_of_moves; i++) { disk = which_disk(&counter); /* get disk # */ index = disk & 0x01; /* compute direction index*/ next = (pin[disk] + dir[index]) % 3 + 1; printf("\n%6lu%8d%10d%8d", i, disk, pin[disk], next); pin[disk] = next; } }
 /* ------------------------------------------------------ */ /* FUNCTION which_disk : */ /* Given the previous counter value, this function */ /* computes the only one bit changed from 0 to 1 by adding*/ /* one. This value corresponding to Gray Code. */ /* ------------------------------------------------------ */
int which_disk(unsigned long *counter) { unsigned long a, b, c; int i;
 a = *counter; *counter = b = a + 1; for (c = a^b, i = 0; c != 0; c >>= 1, i++) ; return i; }

sunnvya 发表于 2006-3-29 18:04

10.生命游戏
#include <stdio.h> #include <stdlib.h>
#define MAXSIZE 50 /* board size */ #define OCCUPIED 1 /* occupied flag */ #define UNOCCUPIED 0 #define YES 1 #define NO 0
char cell[MAXSIZE][MAXSIZE]; /* the board */ char workcopy[MAXSIZE][MAXSIZE]; /* a working copy */ int row; /* No. of rows you want */ int column; /* no. of columns you want */ int generations; /* maximum no. of generation*/
/* ------------------------------------------------------ */ /* FUNCTION read_in : */ /* This function reads in the number of generations, */ /* the number of rows, the number of columns and finally */ /* the initial configuration (the generation 0). Then put*/ /* your configuration to the center of the board. */ /* ------------------------------------------------------ */
void read_in(void) { int max_row, max_col; /* max # of row and col. */ int col_gap, row_gap; /* incremnet of row and col */ int i, j; char line[100];
 gets(line); /* read in gens, row and col*/ sscanf(line, "%d%d%d", &generations, &row, &column); for (i = 0; i < row; i++)/* clear the board */ for (j = 0; j < column; j++) cell[i][j] = UNOCCUPIED; max_col = 0; /* read in the config. */ for (max_row = 0; gets(line) != NULL; max_row++) { for (i = 0; line[i] != '\0'; i++) if (line[i] != ' ') cell[max_row][i] = OCCUPIED; max_col = (max_col < i) ? i : max_col; } row_gap = (row - max_row)/2; /* the moving gap */ col_gap = (column - max_col)/2; for (i = max_row + row_gap - 1; i >= row_gap; i--) { for (j = max_col + col_gap - 1; j >= col_gap; j--) cell[i][j] = cell[i-row_gap][j-col_gap]; for ( ; j >= 0; j--) cell[i][j] = UNOCCUPIED; } for ( ; i >= 0; i--) for (j = 0; j < column; j++) cell[i][j] = UNOCCUPIED; }
/* ------------------------------------------------------ */ /* FUNCTION display : */ /* Display the board. */ /* ------------------------------------------------------ */
#define DRAW_BOARDER(n) { int i; \ printf("\n+"); \ for (i = 0; i < n; i++) \ printf("-"); \ printf("+"); \ } void display(int gen_no) { int i, j;
 if (gen_no == 0) printf("\n\nInitial Generation :\n"); else printf("\n\nGeneration %d :\n", gen_no);
 DRAW_BOARDER(column); for (i = 0; i < row; i++) { printf("\n|"); for (j = 0; j < column; j++) printf("%c", (cell[i][j] == OCCUPIED) ? '*' : ' '); printf("|"); } DRAW_BOARDER(column); }
/* ------------------------------------------------------ */ /* FUNCTION game_of_life : */ /* This is the main function of Game of Life. */ /* ------------------------------------------------------ */
void game_of_life(void) { int stable; /* stable flag */ int iter; /* iteration count */ int top, bottom, left, right; /* neighborhood bound */ int neighbors; /* # of neighbors */ int cell_count; /* # of cells count */ int done; int i, j, p, q;
 display(0); /* display initial config. */ done = NO; for (iter = 1; iter <= generations && !done; iter++) { memmove(workcopy, cell, MAXSIZE*MAXSIZE); /*copy*/ stable = YES; /* assume it is in stable */ cell_count = 0; /* # of survived cells = 0 */ for (i = 0; i < row; i++) { /* scan each cell...*/ top = (i == 0) ? 0 : i - 1; bottom = (i == row - 1) ? row-1 : i + 1; for (j = 0; j < column; j++) { left = (j == 0) ? 0 : j - 1; right = (j == column - 1) ? column-1 : j + 1;
 /* compute number of neighbors */
 neighbors = 0; for (p = top; p <= bottom; p++) for (q = left; q <= right; q++) neighbors += workcopy[p][q]; neighbors -= workcopy[i][j];
 /* determine life or dead */
 if (workcopy[i][j] == OCCUPIED) if (neighbors == 2 || neighbors == 3) { cell[i][j] = OCCUPIED; cell_count++; } else cell[i][j] = UNOCCUPIED; else if (neighbors == 3) { cell[i][j] = OCCUPIED; cell_count++; } else cell[i][j] = UNOCCUPIED; stable = stable && (workcopy[i][j] == cell[i][j]); } } if (cell_count == 0) { printf("\n\nAll cells die out."); done = YES; } else if (stable) { printf("\n\nSystem enters a stable state."); done = YES; } else display(iter); } }
/* ------------------------------------------------------ */
void main(void) { read_in(); game_of_life(); }

foolish 发表于 2006-3-29 18:12

强啊

Adminstrator 发表于 2006-4-2 20:22

[em14]

shiyingkong 发表于 2006-4-3 14:51

厉害..还看不懂..呵呵

山娃学电脑 发表于 2006-4-6 09:51

[em17]

sky351732466 发表于 2006-4-6 10:46

楼主好强啊,不过我们都看不懂[em03]

ap0406220 发表于 2006-4-7 20:14

楼主的数据结构学得一定很好 那几个算法都很难的,我看不懂,强啊!

luoxian_2003 发表于 2006-4-12 16:11

请问一下atoi()是什么意思?[em03]

canbe 发表于 2006-4-12 19:36

为什么用VC编译会出错??[em09]

sunnvya 发表于 2006-4-13 16:04

有错自己可以调试

qzt040613 发表于 2006-4-13 20:38

下次打包行不行啊！

谁伴我闯荡 发表于 2006-4-15 20:02

[em01]好劲啊！

hmilyalex 发表于 2006-4-21 14:08

[em17]我靠，太强了

页: [1] 2 3 4 5 6 7

编程论坛's Archiver

经典游戏问题算法集