文档章节

跳马问题

日拱一卒
 日拱一卒
发布于 2014/05/29 18:39
字数 583
阅读 35
收藏 0
问题:

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


算法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

© 著作权归作者所有

共有 人打赏支持
日拱一卒
粉丝 15
博文 63
码字总数 24558
作品 0
沈阳
其他

暂无文章

TypeScript基础入门之JSX(二)

转发 TypeScript基础入门之JSX(二) 属性类型检查 键入检查属性的第一步是确定元素属性类型。 内在元素和基于价值的元素之间略有不同。 对于内部元素,它是JSX.IntrinsicElements上的属性类型...

durban
20分钟前
0
0
AVA中CAS-ABA的问题解决方案AtomicStampedReference

了解CAS(Compare-And-Swap) CAS即对比交换,它在保证数据原子性的前提下尽可能的减少了锁的使用,很多编程语言或者系统实现上都大量的使用了CAS。 JAVA中CAS的实现 JAVA中的cas主要使用的是...

码代码的小司机
22分钟前
0
0
Android JNI开发系列(十三) JNI异常处理

JNI 异常处理 JNI异常与JAVA处理异常的区别 JAVA 有异常处理机制,而JNI没有 如果JAVA中异常没有捕获,后面的代码不会执行,JNI会执行 JAVA编译时的异常,是在方法显示的声明了某一个异常,编...

蔡小鹏
36分钟前
2
0
简单介绍Java 的JAR包、EAR包、WAR包区别

WAR包 WAR(Web Archive file)网络应用程序文件,是与平台无关的文件格式,它允许将许多文件组合成一个压缩文件。War专用于Web方面。大部分的JAVA WEB工程,都是打成WAR包进行发布的。 War是...

Linux就该这么学
今天
1
0
Qt那些事0.0.7

在帮助文档(Overview - QML and C++ Integration)中随缘遇到一张图,是关于C++对象与QML整合介绍的,值得标记下来,虽然大部分功能也有所涉猎,但是还是留个记号,万一哪天我失忆了还想写Q...

Ev4n
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部