跳马问题
跳马问题
日拱一卒 发表于4年前
跳马问题
  • 发表于 4年前
  • 阅读 33
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

摘要: 半张象棋棋盘,一马从左下角跳到右上角,只能往右跳,不能往左跳,输出所有跳步步骤。
问题:

半张象棋棋盘,一马从左下角跳到右上角,只能往右跳,不能往左跳,输出所有跳步步骤。


算法1:逆向递归
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int x, y;
	struct node *nextStep;
}stepNode;

stepNode *q;
stepNode* arrProcess[100];
int count = 0;

int func(int, int, stepNode*);

void main(){
	int destX, destY;
	int i, flag;
	stepNode *p;

	printf("请输入要到达点的坐标(0<x<9, 0<y<5):");
	scanf("%d%d", &destX, &destY);
	flag = func(destX, destY, NULL);
	if(flag == 0){
		printf("亲,跳不到点(%d,%d)哟!\n", destX, destY);
	}else{
		printf("共有%d种走法\n", count);
		for(i=0; i<count; i++){
			printf("第%d中方法:\n", i+1);
			for(p=arrProcess[i]; p!=NULL; p=p->nextStep) printf("(%d,%d)\t", p->x, p->y);
			printf("\n");
		}
	}
}

int func(int x, int y, stepNode *p){
	
	int flag1, flag2, flag3, flag4;

	if(x<0 || x>8 || y<0 || y>4) return 0;

	q = (stepNode*)malloc(sizeof(stepNode));
	q->x = x;
	q->y = y;
	q->nextStep = p;
	p = q;
	
	if(x==0 && y==0){
		arrProcess[count++] = q;
		return 1;
	}

	flag1 = func(x-1, y-2, p);
	flag2 = func(x-2, y-1, p);
	flag3 = func(x-2, y+1, p);
	flag4 = func(x-1, y+2, p);
	if(flag1+flag2+flag3+flag4 == 0){
		free(p);
		return 0;
	}else{
		return 1;
	}
}


算法2:正向递归
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int x, y;
	struct node *p1, *p2, *p3, *p4;
	int n1, n2, n3, n4;
}stepNode;

int destX, destY, count;
stepNode *head;

int func(int, int, stepNode **);
void showProcess();

void main(){
	printf("请输入要到达点的坐标(0<x<9, 0<y<5):");
	scanf("%d%d", &destX, &destY);
	count = func(0, 0, &head);
	showProcess();
}

int func(int x, int y, stepNode **p){
	int n;

	*p = (stepNode *)malloc(sizeof(stepNode));
	(*p)->x = x; (*p)->y = y;
	if(x<0 || x>8 || y<0 || y>4 || x>destX){
		n=0;
	}else if(x==destX && y==destY){
		(*p)->p1 = NULL;
		(*p)->p2 = NULL;
		(*p)->p3 = NULL;
		(*p)->p4 = NULL;
		n = 1;
	}else{
		(*p)->n1 = func(x+1, y+2, &((*p)->p1));
		(*p)->n2 = func(x+2, y+1, &((*p)->p2));
		(*p)->n3 = func(x+2, y-1, &((*p)->p3));
		(*p)->n4 = func(x+1, y-2, &((*p)->p4));
		n = (*p)->n1 + (*p)->n2 +  (*p)->n3 + (*p)->n4;
	}
	if(n==0){free (*p); *p = NULL;}
	return n;
}

void showProcess(){
	int i;
	stepNode *p;
	if(count == 0){
		printf("亲,跳不到点(%d,%d)哟!\n", destX, destY);
		return;
	}
	
	printf("共有%d种走法\n", count);
	for(i=0; i<count; i++){
		printf("第%d中走法:\n", i+1);
		p = head;
		while(p!=NULL){
			printf("(%d,%d)  ", p->x, p->y);
			if(p->n1 != 0){p->n1-=1; p=p->p1;}
			else if(p->n2 != 0){p->n2-=1; p=p->p2;}
			else if(p->n3 != 0){p->n3-=1; p=p->p3;}
			else {p=p->p4; p->n4-=1;} 
		}
		printf("\n");
	}
}

调试环境:VC++6.0

标签: C语言
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 15
博文 59
码字总数 24558
×
日拱一卒
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: