妙趣橫生的演算法c語言實現

❶ 求數據結構課程設計 馬踏棋盤 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

❽ 我才接觸C語言，想找一本可以關於數據結構入門等一些很基礎的書，希

您好，根據您的情況，向您推薦
《妙趣橫生的演算法：C語言實現》
這本書上的題目不難，而且很有趣，是培養初學者演算法思想的好書，裡面沒有像別的書一樣長篇大論的講理論，而是通過一個又一個有趣的編程挑戰來讓讀者學到知識。

在對這本書有一個基本的學習後，還是建議您選擇一本專門講數據結構的教材進行深入學習，這樣才能對理論有更深入的認識