导航:首页 > 源码编译 > 妙趣横生的算法c语言实现

妙趣横生的算法c语言实现

发布时间:2022-12-19 20:01:49

❶ 求数据结构课程设计 马踏棋盘 C语言

没看见你说的是非递归的。

其实我也不懂,碰巧知道答案,在51CTO上下的。 不能插图。
9.3 马踏棋盘(1)
【题目要求】
国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中,按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次,最终使得"马"走遍棋盘的64个方格。编写一个C程序,实现马踏棋盘操作,要求用1~64这64个数字标注马移动的路径,也就是按照求出的行走路线,将数字1,2,……64依次填入棋盘的方格中,并输出。
国际象棋中,"马"的移动规则如图9-4所示。

图9-4 "马"的移动规则
如图9-4所示,图中实心的圆圈代表"马"的位置,它下一步可移动到图中空心圆圈标注的8个位置上,该规则叫做"马走日"。但是如果"马"位于棋盘的边界附近,它下一步可移动到的位置就不一定有8个了,因为要保证"马"每一步都走在棋盘中。
【题目分析】
马踏棋盘的问题其实就是要将1,2,…,64填入到一个8*8的矩阵中,要求相邻的两个数按照"马"的移动规则放置在矩阵中。例如数字a放置在矩阵的(i,j)位置上,数字a+1只能放置在矩阵的(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)之中的一个位置上。将矩阵填满并输出。这样在矩阵中从1,2…遍历到64,就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵,在该矩阵中填有1,2…64这64个数字,相邻数字之间遵照"马走日"的规则。
解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索的思想。因为"马"每走一步都是盲目的,它并不能判断当前的走步一定正确,而只能保证当前这步是可走的。"马"走的每一步棋都是从它当前位置出发,向下一步的8个位置中的1个行走(在它下一步有8个位置可走的情况下)。因此"马"当前所走的路径并不一定正确,因为它可能还有剩下的可选路径没有尝试,如图9-5所示。

图9-5 "马"的可选路径
如图9-5所示,假设最开始"马"位于棋盘的(0,0)的位置,接下来"马"有两处位置可走,即(1,2)和(2,1)。这时"马"是无法确定走2的位置最终是正确的,还是走3的位置最终是正确的。因此"马"只能任意先从一个路径走下去(例如从2的位置)。如果这条路是正确的,那当然是幸运的,如果不正确,则"马"要退回到第一步,继续从3的位置走下去。以后"马"走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程,同时也是一种具有重复性操作的递归过程。可以用一棵"探索树"来描述该深度优先搜索过程,如图9-6所示。

图9-6 深度优先搜索过程
"马"的行走过程实际上就是一个深度探索的过程。如图9-6所示,"探索树"的根结点为"马"在棋盘中的初始位置(这里用4*4的棋盘示意)。接下来"马"有两种行走方式,于是根结点派生出两个分支。而再往下一步行走,根结点的两个孩子又能够分别派生出其他不同的"行走路线"分支,如此派生下去,就得到了"马"的所有可能的走步状态。可以想见,该探索树的叶子结点只可能有两种状态:一是该结点不能再派生出其他的"走步"分支了,也就是"马"走不通了;二是棋盘中的每个方格都被走到,即"马"踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。
如何才能通过搜索这棵探索树找到这条马踏棋盘的行走路径呢?可以采用深度优先搜索的方法以先序的方式访问树中的各个结点,直到访问到叶结点。如果叶结点是第二种情况的叶结点,则搜索过程可以结束,因为找到了马踏棋盘的行走路径;如果叶结点为第一种情况的叶结点,即走不通了,则需要返回到上一层的结点,顺着该结点的下一条分支继续进行深度优先搜索下去。
因此在设计"马踏棋盘"的算法时可以借鉴前面讲过的图的深度优先遍历算法和二叉树的先序遍历算法。但是在这里并不需要真正地构建这样一棵探索树,我们只需要借用探索树的思想。在实际的操作过程中,所谓的探索树实际就是深度优先搜索的探索路径,每个结点实际就是当前的棋盘状态,而所谓的叶结点要么就是在当前棋盘状态下,"马"无法再进行下一步行走;要么就是马踏棋盘成功。该算法描述可如下:
int TravelChess Board (int x,int y,int tag)
{
chess[x][y] = tag;
if(tag == 64) { return 1;}
找到"马"的下一个行走坐标(x1,y1),如果找到返回flag=1,否则返回flag=0;
while(flag ){
if(TravelChessBoard (x1,y1,tag+1))return 1; /*递归调用TravelChess , 从x1,y1向下搜索;如果从 x1,y1往下马踏棋盘成功,返回1*/
else
继续找到"马"的下一个行走坐标(x1,y1),如果找到返回flag=1,否则返回flag=0;
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
9.3 马踏棋盘(2)
http://book.51cto.com 2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)
摘要:《妙趣横生的算法(C语言实现)》第9章综合题,,本章将列举一些经典的综合题编程实例。这些题目生动有趣,同时具有一定的难度,因此作者尽量做到讲解深入浅出,把问题讲透彻,讲清楚。同时希望读者能从中得到启发,启迪思维,提高自身的编程水平。本节为大家介绍马踏棋盘。
标签:妙趣横生 C语言实现 妙趣横生的算法(C语言实现)

Oracle帮您准确洞察各个物流环节
9.3 马踏棋盘(2)
该算法中通过函数TravelChess()递归地搜索"马"的每一种走法。其中参数x,y指定 "马" 当前走到棋盘中的位置,tag是标记变量,每走一个棋盘方格,tag自动增1,它标识着马踏棋盘的行走路线。
算法首先将当前"马"处在棋盘中的位置上添加标记tag,然后判断tag是否等于64,如果等于64,说明这是马踏棋盘的最后一步,因此搜索成功,程序应当结束,返回1。否则,找到"马"下一步可以走到的位置(x1,y1),如果找到这个位置坐标,flag置1,否则flag置0。
下面在flag为1的条件下(即找到x1,y1),递归地调用函数TravelChess()。也就是从x1,y1指定的棋盘中的位置继续向下深度搜索。如果从x1,y1向下搜索成功,即程序一直执行下去,直到tag等于64返回1,那就说明"马"已经踏遍棋盘(马踏棋盘的过程是:先走到棋盘的(x,y)位置,再从(x1,y1)向下深度搜索,走遍全棋盘),于是搜索结束,返回1;否则继续找到"马"的下一个可以行走的坐标(x1,y1),如果找到这个位置坐标,flag置1,并从(x1,y1)向下重复上述的递归搜索,否则flag置0,本次递归结束。
如果找遍当前位置(x,y)的下一个坐标(x1,y1)(一般情况是8种),但是从(x1,y1)向下继续深度优先搜索都不能成功地"马踏棋盘"(此时flag等于0),则表明当前所处的状态并不处于马踏棋盘的"行走路径"上,也就是说"马"本不应该走到(x,y)的位置上,因此将chess[x][y]置0,表明棋盘中该位置未被走过(擦掉足迹),同时返回0,程序退到上一层的探索状态。
这里应当知道,所谓当前位置(x,y)的下一个坐标(x1,y1)是指"马"下一步可以走到的地方,用坐标(x1,y1)返回。在探索树中它处在(x,y)所在的结点的子结点中,如图9-7所示。

图9-7 (x,y)的下一个坐标(x1,y1)
当前位置(x,y)的下一个坐标(x1,y1)的可选个数由当前棋盘的局面决定。一般情况下是有8种可走的位置(如图9-7所示),但是如果"马"位于棋盘的边缘(如图9-7所示的探索树的根结点)或者8个可选位置中有的已被"马"前面的足迹所占据,在这两种情况下(x1,y1)的可选个数就不是8个了。
上述搜索算法相当于先序遍历探索树,只不过它不一定是将探索树完整地遍历,而是当tag等于64时,也就是棋盘被全部"踏遍"时就停止继续搜索了。
下面给出完整的程序清单供读者参考。
程序清单9-3
/*--------------------------------- 9-3.c --------------------------*/
#include "stdio.h"
#define X 8
#define Y 8
int chess[X][Y];

int nextxy(int *x,int *y,int count) /*找到基于x、y位置的下一个可走的位置*/
{
switch(count)
{
case 0: if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0) {*x =*x+2;*y = *y-1;return 1; } break;
case 1: if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0) {*x = *x+2; *y = *y+1 ;
return 1;}break;
case 2: if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0) {*x = *x+1; *y = *y-2; return 1;} break;
case 3: if(*x+1<=X-1 && *y+2<=Y-1 &&chess[*x+1][*y+2]==0) {*x = *x+1; *y = *y+2;
return 1;}break;
case 4: if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0) {*x = *x-2; *y = *y-1; return 1;} break;
case 5: if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0){*x = *x-2; *y = *y+1; return 1;} break;
case 6:if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0) {*x = *x-1; *y = *y-2;return 1;}break;
case 7: if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0) {*x = *x-1; *y = *y+2;
return 1;}break;
default: break ;
}
return 0;
}

int TravelChessBoard(int x,int y,int tag) /*深度优先搜索地"马踏棋盘"*/
{
int xx1 = x, yy1 = y, flag = 0,a,b ,count = 0 ;
chess[x][y] = tag;
if(tag == X*Y) { return 1;}
flag = nextxy(&x1,&y1,count);
while(flag == 0 && count <7){
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
while(flag ){
if(TravelChessBoard(x1,y1,tag+1))return 1;
xx1 = x;yy1 = y;
countcount = count +1;
flag = nextxy(&x1,&y1,count); /*寻找下一个(x,y)*/
while(flag == 0 && count <7){ /*循环地寻找下一个(x,y)*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
main()
{
int i,j;
for(i=0;i<X;i++)
for(j=0;j<Y;j++)
chess[i][j] = 0;
if(TravelChessBoard(2,0,1)) {
for(i=0;i<X;i++) {
for(j=0;j<Y;j++)
printf("%d ",chess[i][j]);
printf("\n");
}
printf("The horse has travelled the chess borad\n");
}
else
printf("The horse cannot travel the chess board\n");
getche();
}
9.3 马踏棋盘(3)
http://book.51cto.com 2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)
摘要:《妙趣横生的算法(C语言实现)》第9章综合题,,本章将列举一些经典的综合题编程实例。这些题目生动有趣,同时具有一定的难度,因此作者尽量做到讲解深入浅出,把问题讲透彻,讲清楚。同时希望读者能从中得到启发,启迪思维,提高自身的编程水平。本节为大家介绍int nextxy(int *x,int *y,int count)。
标签:妙趣横生 C语言实现 妙趣横生的算法(C语言实现)

Oracle帮您准确洞察各个物流环节
9.3 马踏棋盘(3)
【程序说明】
本程序中应用二维数组chess[8][8]作为8*8的棋盘,"马"每走到棋盘的(i,j)处,就将当前的步数tag赋值给chess[i][j]。为了方便起见,将数组chess设置为外部变量。另外定义字符常量X,Y,它规定棋盘的大小。本程序清单中将X和Y都设置为8。
函数TravelChessBoard()是上述马踏棋盘算法的具体实现。本程序中初始的(x,y)位置为(2,0),说明"马"从chess[8][8]的chess[2][0]位置开始进行"马踏棋盘"的。在函数TravelChessBoard()中要调用函数nextxy()。
int nextxy(int *x,int *y,int count)
函数nextxy()包含3个参数:x和y为传递下来的"马"当前踏到棋盘上的位置,它是指针变量。变量count的作用是标记调用nextxy()过程的次数,根据count值的不同,返回基于(x,y)的下一个不同的坐标,以此来避免返回同一个坐标,真正实现寻找"针对当前位置(x,y)的下一个位置"的目的。函数nextxy()的作用是找到"马"当前的位置(x,y)的下一个可以行走的位置,并通过指针修改x、y的内容,将下一个位置坐标用变量x、y返回。
"寻找(x,y)的下一个位置坐标"的操作通过代码:
xx1 = x; yy1 = y; /*将坐标(x1,y1)初始化为当前访问的坐标 (x,y),因为(x,y)不能被改动*/
flag = nextxy(&x1,&y1,count); /*寻找(x,y)下一个位置坐标(x1,y1)*/
while(flag == 0 && count <7){ /*循环地寻找(x,y)的下一个坐标*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
实现。程序最开始将(x1,y1)初始化为当前坐标(x,y),因为"马"的当前位置坐标(x,y)不能被轻易改动。然后将&x1、&y1作为函数nextxy的参数传递,并通过参数&x1和&y1返回当前坐标(x,y)的第count个下一个坐标(x1,y1)。只有当flag为1时,才表明找到了下一个坐标,于是循环可以停止。但是如果count的值超过了7,则说明无法找到(x,y)的下一个坐标,也就说明棋走不通了。所谓当前位置(x,y)的"下一个位置",如图9-8所示。

(点击查看大图)图9-8 (x,y)的"下一个位置"示意
图中实心的圆圈的坐标为(x,y),它周围的8个空心的圆圈1~8,为当前坐标(x,y)的可选的"下一个"坐标(x1,y1)。每次调用nextxy()都可能得到这8个坐标其中的一个,当参数count为i时,返回圆圈i所处的坐标。这样就保证了不返回同一个坐标。
如果像本程序这样将字符常量X和Y都设置为8,那么程序就执行8*8的马踏棋盘。但是这样一来会非常费时,实践证明应用本程序运算出8*8的马踏棋盘的结果要花几分钟的时间。因此读者在调试程序时可以通过设置X和Y的值减小棋盘的规格,从而更快地得到结果。
本程序的运行结果如图9-9所示。

(点击查看大图)图9-9 程序9-3的运行结果

❷ 学习c语言什么辅导书比较好

强力推荐 销量最好的 谭浩强的《C程序实际》(第三版)作为好多大学的课本 非常好 巨详细

❸ 有哪些适合电脑小白的自学书籍推荐

《数据结构与算法Java版》本书把算法分析与最有效率的Java程序的开发有机地结合起来,深入分析每种算法,内容全面、缜密严格,并细致讲解精心构造程序的方法。

❹ 谁能推荐几本c语言入门的书

对于初学者:
C程序设计<第4版 谭浩强着>
C Primer Plus(第5版)
C大学教程
C语言入门经典(第5版)

进阶篇:
C和指针
C陷阱与缺陷
C语言参考手册(第5版)
妙趣横生的算法(C语言实现 第2版)

高级篇:
C专家编程
图灵程序设计丛书:深入理解C指针
C标准库
.......
希望对你学习C语言有帮助吧。

❺ 编程初学者推荐书籍和论坛有哪些

“客气地说,《C++ Primer》不适合大学C++基础课堂教学,也不适合初学者入门。不客气地说,恐怕你们的大学老师也搞不定《C++ Primer》,更别说拿这本书教学生了。”

摘自某技术论坛的帖子,个人认为《C++ Primer》和《编译原理》就是给新手挖的两个天坑,随便介绍这些书给新手,其实完全是在坑新手。
建议可以看下《妙趣横生的算法》,都是C语言实现的,可以算作是C语言的提高和数据结构+基础算法的入门

❻ 四皇后问题求解

本章内容来自《妙趣横生的算法》一书中。

回溯法是一种非常有效,适用范围相当广泛的算法设计思想。许多复杂的问题,规模较大的问题都可以使用回溯法求解。因此回溯法又有“通用解题方法”的美称。

回溯法的基本思想是:在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度 探索 解空间树。当 探索 到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续 探索 下去;如果该结点不包含问题的解,那就说明以该结点为根结点的子树一定不包含“剪枝”操作。

如果应用回溯法求解问题的所有解,要回溯到解空间树的树根,这样根结点的所有子树都被 探索 到才结束。如果只要求解问题的一个解,问题的最终解,因此要跳过对以该结点为根的子树的系统 探索 ,逐层向其祖先结点回溯。这个过程叫做解空间树的那么在 探索 解空间树时,只要搜索到问题的一个解就可以结束了。

应用回溯法的思想求解四皇后问题

分析:

上面一节中已经详细介绍了回溯法解决四皇后问题的基本过程。在这里将给出具体的算法描述和程序清单。

其实在解决四皇后问题时,并不一定要真的构建出这样一棵解空间树,它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构来真实地创建出一棵解空间树,不过那样会比较浪费空间资源。

运行结果:

❼ 求《妙趣横生的算法(C语言实现第2版)》全文免费下载百度网盘资源,谢谢~

《妙趣横生的算法(C语言实现第2版)》网络网盘pdf最新全集下载:
链接: https://pan..com/s/1CdeYYmFNRuNn8QwWP35gzA

?pwd=namn 提取码: namn
简介:《妙趣横生的算法(C语言实现 第2版)》是深受广大读者好评的《妙趣横生的算法(C语言实现)》一书的全新升级版。本书在第1版的基础上对原书内容做了大量的调整和补充,并将书中的实例代码在Visual Studio 2010环境下重新编译通过,以适应当前技术的发展和阅读需求。本书内容涵盖了算法入门的必备基础知识和大量的趣味算法题、面试题和ACM竞赛题等。通过学习本书内容,可以开阔读者的视野,帮助读者理解算法,提高编程兴趣和能力,并提高C语言编程能力,还可以让读者了解IT面试中的常见算法题及编程竞赛中的相关知识。另外,本书提供了5.5小时配套教学视频和实例源代码,以提高读者的学习效率。

❽ 我才接触C语言,想找一本可以关于数据结构入门等一些很基础的书,希

您好,根据您的情况,向您推荐
《妙趣横生的算法:C语言实现》
这本书上的题目不难,而且很有趣,是培养初学者算法思想的好书,里面没有像别的书一样长篇大论的讲理论,而是通过一个又一个有趣的编程挑战来让读者学到知识。

在对这本书有一个基本的学习后,还是建议您选择一本专门讲数据结构的教材进行深入学习,这样才能对理论有更深入的认识

阅读全文

与妙趣横生的算法c语言实现相关的资料

热点内容
php中括号定义数组 浏览:600
php打印堆栈 浏览:514
华为adb命令行刷机 浏览:963
人像摄影pdf 浏览:755
解压文件密码怎样重新设置手机 浏览:999
高考指南pdf 浏览:693
爬虫python数据存储 浏览:240
u盘怎么取消加密 浏览:429
567除以98的简便算法 浏览:340
pdf手机如何解压 浏览:15
python描述器 浏览:60
战地联盟3解压密码 浏览:805
s型命令 浏览:25
php年薪5年 浏览:71
如何上网上设个人加密账户 浏览:44
linux打开ssh服务 浏览:78
微信位置可以加密吗 浏览:470
算法蛮力法 浏览:438
随机排练命令 浏览:147
python多进程并发 浏览:41