【アルゴリズム】アルゴリズムの応用(三)
17145 ワード
八皇后問題
八皇后の問題のすべての解を求めます.
インスタンスの解析:
これは非常に古い問題です:どのように1つの8*8の碁盤の上で衝突しないで8つの皇后の駒を置いて、8皇后の問題と呼ばれます.
チェスでは、皇后は任意の直線と任意の45°斜線に沿って移動して別の駒を食べることができるため、いずれの皇后がいる横線、縦線、2本の対角線には他の皇后が存在することはできない.完全で衝突のない八皇后分布を八皇后問題の解と呼ぶ.本例は八皇后のすべての解を解く.
明らかに、碁盤の各行には皇后が1人しかいなければならないので、最初の行から皇后を置いて(8つの位置が置くことができる)、関数自体を再帰的に呼び出して、後ろの駒を置いて、8行目が終わるまで、解を見つけたことを示します.
各行について、皇后を置くことができる位置は8つあり、ループで1つずつ探ることができ、衝突がなければ駒を置き、次の階層の再帰呼び出しを続ける......、競合する場合は、ローの別の場所に移動します.
次はプログラムコードです.
再帰アルゴリズムを使用していますが、非再帰遡及アルゴリズムも使用できます.
ここには一部の関数のみがリストされています
迷宮問題
迷宮から入り口から出口までのすべての通路を見つけます.
インスタンスの解析:
迷路は、図17−6に示すブロックで表され、各ブロックは、チャネル(空白のブロックで表される)または壁(シャドウのあるブロックで表される)で表される.入口から出口までの単純な経路を見つけることが要求される.すなわち、求めた経路で同じチャネルブロックが繰り返し現れない.
迷宮問題を解く簡単な方法は、入り口から出発して、ある方向に沿って検索し、通れば、前進し続けることです.そうでなければ元の道に戻って、可能なすべての通路が検索されるまで方向を変えて検索します.
コンピュータでは図17-7に示す2次元配列maze[m][n]で表すことができ、配列中の要素は0でチャネルを表し、1で壁を表す.いずれかの点maze[i][j]について、可能な動き方向は4つある.遡及法迷路問題解を求める過程は,探索の経路を1つのスタックで保存する.
コアコードは次のとおりです.
式の計算
キーボード入力式については,正当か否かを判断し,正当であれば演算結果を出力する.
説明:
(1)式を空にすることはできません
(2)式に表示できる文字は次のとおりです.
演算子「+」、「-」、「*」、「」;
左右かっこ「(」、「)」;
整数(複数可).
スペースとタブ.
たとえば、入力された式が「20+(3*(4+1)-5)/2-3」の場合、22が出力されます.
インスタンスの解析:
スタックを使用して、接尾辞式を接尾辞式に変換してから、接尾辞式の値を求めます.
1.接尾辞式に変換するには、次の手順に従います.
演算子スタックとして空のスタックを作成し、接尾辞式を順次スキャンします.
①他の文字を読む場合:無視します.その他の文字には、「」、「t」などがあります.
②数字を読めば:出力(書き込み配列)
③左かっこまで読むと:スタックに入る
④右括弧を読むと、スタック内の要素が左括弧に遭遇するまでポップアップ、出力され続け、ポップアップされますが出力されません.
⑤プラスまたはマイナスを読むと、チェックを繰り返し、スタックが空でなく、スタックトップがプラス、マイナス、乗算または除算の場合、スタックトップ要素をポップアップして出力します.読み込んだ演算子(スタックに加算または減算)
⑥乗算または除算を読み取る場合:スタックが空でなく、スタックトップが乗算または除算の場合、スタックトップ要素がポップアップされて出力されます.読み込み演算子(乗算または除算)スタックへの読み込み
接頭辞式のスキャンが完了すると、スタック内の残りの要素がポップアップされ、出力されます.
2.接尾辞式の値を計算するには、次の手順に従います.
空のスタックを作成し、接尾辞式を順次スキャンします.
①数字を読めば:スタックに入る.
②他の文字を読む場合:無視します.その他の文字には、「」、「t」などがあります.
③演算子を読むと、スタックから2つの要素をポップアップして計算し、結果をスタックに入れます.
接尾辞式のスキャンが完了すると、スタックトップ要素が結果になります.
手順は次のとおりです.
この文書は「成鵬致遠」ブログから出ています.この出典http://infohacker.blog.51cto.com/6751239/1171355は必ず保持してください.
八皇后の問題のすべての解を求めます.
インスタンスの解析:
これは非常に古い問題です:どのように1つの8*8の碁盤の上で衝突しないで8つの皇后の駒を置いて、8皇后の問題と呼ばれます.
チェスでは、皇后は任意の直線と任意の45°斜線に沿って移動して別の駒を食べることができるため、いずれの皇后がいる横線、縦線、2本の対角線には他の皇后が存在することはできない.完全で衝突のない八皇后分布を八皇后問題の解と呼ぶ.本例は八皇后のすべての解を解く.
明らかに、碁盤の各行には皇后が1人しかいなければならないので、最初の行から皇后を置いて(8つの位置が置くことができる)、関数自体を再帰的に呼び出して、後ろの駒を置いて、8行目が終わるまで、解を見つけたことを示します.
各行について、皇后を置くことができる位置は8つあり、ループで1つずつ探ることができ、衝突がなければ駒を置き、次の階層の再帰呼び出しを続ける......、競合する場合は、ローの別の場所に移動します.
次はプログラムコードです.
#include <math.h>
#include <stdio.h>
#define MAX 8 // MAX*MAX
int board[MAX];
int count = 0;
void show_result() //
{
int i;
for(i = 0; i < MAX; i++)
printf("(%d,%d),", i+1, board[i]+1); // 1
printf("
");
}
int check_cross(int n) //
{
int i;
for(i = 0; i < n; i++)
if(board[i]==board[n]||(n-i)==abs(board[i]-board[n]))
return 1; // 1
return 0;
}
void put_chess(int n) // n
{
int i;
for(i = 0; i < MAX; i++)
{ // 0~7
board[n] = i; // board[n] ( n)
if(!check_cross(n))
{ //
if(n == MAX-1)
{ // ，
count++;
printf(“%3d: ”, count); //
show_result(); //
if(count%24 == 0)
{ // 24
getch();
clrscr();
}
}
else
put_chess(n+1); // ， ，
}
}
}
int main()
{
clrscr();
puts("The possible placements are:");
put_chess(0);
puts("
Press any key to quit...");
getch();
return 0;
}再帰アルゴリズムを使用していますが、非再帰遡及アルゴリズムも使用できます.
#define TRUE 1
#define FALSE 0
int nQueens_nonrecursive(int *a, int n)
{
int top, i, j, conflict;
if(n <= 0)
return FALSE;
top = -1;
i = 0;
do
{
conflict = FALSE;
/* */
for(j = 0; j < top+1; j++)
if(i==a[j]||top+1-j==i-a[j]||top+1-j==a[j]-i)
conflict = TRUE;
if(conflict == FALSE)
{ //
a[++top] = i; // i
if(top == n-1)
return TRUE; //
i = 0; // 0 ，
}
else
{ //
while(i == n-1 && top >= 0)
i = a[top--];
i++;
}
}
while(i < n);
return FALSE;
}ここには一部の関数のみがリストされています
迷宮問題
迷宮から入り口から出口までのすべての通路を見つけます.
インスタンスの解析:
迷路は、図17−6に示すブロックで表され、各ブロックは、チャネル(空白のブロックで表される)または壁(シャドウのあるブロックで表される)で表される.入口から出口までの単純な経路を見つけることが要求される.すなわち、求めた経路で同じチャネルブロックが繰り返し現れない.
迷宮問題を解く簡単な方法は、入り口から出発して、ある方向に沿って検索し、通れば、前進し続けることです.そうでなければ元の道に戻って、可能なすべての通路が検索されるまで方向を変えて検索します.
コンピュータでは図17-7に示す2次元配列maze[m][n]で表すことができ、配列中の要素は0でチャネルを表し、1で壁を表す.いずれかの点maze[i][j]について、可能な動き方向は4つある.遡及法迷路問題解を求める過程は,探索の経路を1つのスタックで保存する.
コアコードは次のとおりです.
#include <stdio.h>
#include <stdlib.h>
#define M 8 // maze
#define N 11 // maze
typedef struct
{
int x,y,d;
}DataType;
struct SeqStack
{ //
int MAXNUM;
int t; // t<MAXNUM， ，
DataType *s;
};
typedef struct SeqStack *PSeqStack; //
PSeqStack CreateEmptyStack_seq(int n);
void push_seq( PSeqStack pastack, DataType x );
void pop_seq( PSeqStack pastack );
int isEmptyStack_seq(PSeqStack pastack);
DataType top_seq( PSeqStack pastack );
/* maze[x1][y1] maze[x2][y2] ， 1<=x1, x2<=M-2 , 1<=y1, y2<=N-2 */
void mazePath(int** maze, int direction[4][2],int x1,int y1,int x2,int y2,int m,int n)
{
int i,j,k;
int g,h;
PSeqStack st;
DataType element;
st = CreateEmptyStack_seq(m*n);
if(st == NULL)
return;
maze[x1][y1] = 2; // ,
element.x = x1;
element.y = y1;
element.d = -1;
push_seq(st,element); //
while(!isEmptyStack_seq(st))
{ // ,
element = top_seq(st);
pop_seq(st);
i = element.x;
j = element.y;
k = element.d + 1;
while(k <= 3)
{ //
g = i + direction[k][0];
h = j + direction[k][1];
if(g==x2 && h==y2 && maze[g][h]==0)
{ //
printf("The revers path is:
"); //
printf("the node is: %d %d
",g,h);
printf("the node is: %d %d
",i,j);
while(!isEmptyStack_seq(st))
{
element = top_seq(st);
pop_seq(st);
printf("the node is: %d %d
",element.x,element.y);
}
free(st->s);
free(st);
return;
}
if(maze[g][h] == 0)
{ //
maze[g][h] = 2; //
element.x = i;
element.y = j;
element.d = k;
push_seq(st,element); //
i = g; //
j = h;
k = -1;
}
k = k + 1;
}
}
printf("The path has not been found.
");
free(st->s);
free(st);
}
int main()
{
int maze[M][N] ={
{1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,1,1,1,0,0,1},
{1,0,0,0,0,0,1,0,0,1,1},
{1,0,1,1,1,0,0,0,1,1,1},
{1,0,0,0,1,0,1,1,0,1,1},
{1,1,0,0,1,0,1,1,0,0,1},
{1,1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1},
};
int direction[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
mazePath(maze,direction,1,1,6,9,M,N);
return 0;
}式の計算
キーボード入力式については,正当か否かを判断し,正当であれば演算結果を出力する.
説明:
(1)式を空にすることはできません
(2)式に表示できる文字は次のとおりです.
演算子「+」、「-」、「*」、「」;
左右かっこ「(」、「)」;
整数(複数可).
スペースとタブ.
たとえば、入力された式が「20+(3*(4+1)-5)/2-3」の場合、22が出力されます.
インスタンスの解析:
スタックを使用して、接尾辞式を接尾辞式に変換してから、接尾辞式の値を求めます.
1.接尾辞式に変換するには、次の手順に従います.
演算子スタックとして空のスタックを作成し、接尾辞式を順次スキャンします.
①他の文字を読む場合:無視します.その他の文字には、「」、「t」などがあります.
②数字を読めば:出力(書き込み配列)
③左かっこまで読むと:スタックに入る
④右括弧を読むと、スタック内の要素が左括弧に遭遇するまでポップアップ、出力され続け、ポップアップされますが出力されません.
⑤プラスまたはマイナスを読むと、チェックを繰り返し、スタックが空でなく、スタックトップがプラス、マイナス、乗算または除算の場合、スタックトップ要素をポップアップして出力します.読み込んだ演算子(スタックに加算または減算)
⑥乗算または除算を読み取る場合:スタックが空でなく、スタックトップが乗算または除算の場合、スタックトップ要素がポップアップされて出力されます.読み込み演算子(乗算または除算)スタックへの読み込み
接頭辞式のスキャンが完了すると、スタック内の残りの要素がポップアップされ、出力されます.
2.接尾辞式の値を計算するには、次の手順に従います.
空のスタックを作成し、接尾辞式を順次スキャンします.
①数字を読めば:スタックに入る.
②他の文字を読む場合:無視します.その他の文字には、「」、「t」などがあります.
③演算子を読むと、スタックから2つの要素をポップアップして計算し、結果をスタックに入れます.
接尾辞式のスキャンが完了すると、スタックトップ要素が結果になります.
手順は次のとおりです.
#include <stdio.h>
#include <malloc.h>
#define DataType char
#define TRUE 1
#define FALSE 0
#define MAX_SEQSTACK 100
struct SeqStack
{ //
int MAXNUM;
int t; // t<MAXNUM， ，
DataType *s;
};
typedef struct SeqStack *PSeqStack; //
/ 5 13
PSeqStack CreateEmptyStack_seq();
void push_seq(PSeqStack pastack, DataType x);
void pop_seq(PSeqStack pastack);
int isEmptyStack_seq(PSeqStack pastack);
DataType top_seq(PSeqStack pastack);
// ， TRUE
int infixtoSuffix(char *infix, char *suffix)
{
int state_int = FALSE;
/* ，TRUE ，FALSE 。 ， 。*/
char c, c2;
int i, j = 0;
PSeqStack ps = CreateEmptyStack_seq();
if(ps == NULL)
return FALSE;
if(infix[0] == '\0')
{
free(ps->s);
free(ps);
return FALSE;
}
for(i = 0; infix[i] != '\0'; i++)
{
c = infix[i];
switch(c){
case ' ':
case '\t':
case '
':
if(state_int == TRUE) // TRUE FALSE ，
suffix[j++] = ' ';
state_int = FALSE;
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
state_int = TRUE;
suffix[j++] = c; // ，
break;
case '(':
if(state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
push_seq(ps, c);
break;
case ')':
if(state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
c2 = ')';
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
pop_seq(ps);
if(c2 == '(')
break;
suffix[j++] = c2;
} // ， ， ，
if(c2 != '(')
{
free(ps->s);
free(ps);
suffix[j++] = '\0';
return FALSE; // ，
}
break;
case '+':
case '-':
if(state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if(c2=='+' || c2=='-' || c2=='*' || c2=='/')
{
pop_seq(ps);
suffix[j++] = c2;
} // ，
else
break;
}
push_seq(ps,c);
break;
case '*':
case '/':
if(state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if(c2 == '*' || c2 == '/' )
{
pop_seq(ps);
suffix[j++] = c2;
} // ，
else
break;
}
push_seq(ps,c);
break;
default: //
free(ps->s);
free(ps);
suffix[j++] = '\0';
return FALSE;
}
}
if(state_int == TRUE)
suffix[j++] = ' ';
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
pop_seq(ps);
if(c2 == '(')
{
free(ps->s);
free(ps);
suffix[j++] = '\0';
return FALSE;
}
suffix[j++] = c2;
}
free(ps->s);
free(ps);
suffix[j++] = '\0';
return TRUE;
}
/* ， FALSE； TRUE， *presult */
int calculateSuffix(char *suffix, int *presult)
{
int state_int = FALSE;
int num = 0, num1, num2;
int i;
char c;
PSeqStack ps = CreateEmptyStack_seq();
if(ps == NULL)
return FALSE;
for(i = 0; suffix[i] != '\0'; i++)
{
c = suffix[i];
switch(c)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if(state_int == TRUE)
num = num*10 + c - '0';
else
num = c -'0';
state_int = TRUE;
break;
case ' ':
case '\t':
case '
':
if(state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
break;
case '+':
case '-':
case '*':
case '/':
if(state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
if(isEmptyStack_seq(ps))
{
free(ps->s);
free(ps);
return FALSE;
}
num2 = top_seq(ps);
pop_seq(ps);
if(isEmptyStack_seq(ps))
{
free(ps->s);
free(ps);
return FALSE;
}
num1 = top_seq(ps);
pop_seq(ps);
if(c == '+')
push_seq(ps, num1+num2);
if(c == '-')
push_seq(ps, num1-num2);
if(c == '*')
push_seq(ps, num1*num2);
if(c == '/')
{
if(num2 == 0)
{ // 0 FALSE
free(ps->s);
free(ps);
return FALSE;
}
push_seq(ps, num1/num2);
}
break;
default: //
free(ps->s);
free(ps);
return FALSE;
}
}
*presult = top_seq(ps);
pop_seq(ps);
if(!isEmptyStack_seq(ps)) // ，
{
free(ps->s);
free(ps);
return FALSE;
}
free(ps->s);
free(ps);
return TRUE;
}
int main()
{
char infix[80] = "20+(3*(4+1)-5)/2-3";
char suffix[80];
int result;
if(infixtoSuffix(infix,suffix) == TRUE)
{
if(calculateSuffix(suffix,&result) == TRUE)
printf("The Reuslt is: %3d
", result);
else
printf("Error!
");
}
else
printf("Input Error!
");
return 0;
}この文書は「成鵬致遠」ブログから出ています.この出典http://infohacker.blog.51cto.com/6751239/1171355は必ず保持してください.