軟體課程設計1報告
姓名： 學號：
姓名學號
專業電腦科學與技術
設計題目寫程式求解騎士巡遊問題
指導教師
2010 年 07 月 01 日
中國礦業大學徐海學院課程設計綜合成績表
目錄《constructing roads》解題與演算法分析報告
一、題目描述 5
二、解題思路 8
三、相關演算法介紹 8
四、主要資料結構 8
五、流程圖 9
六、源程式 11
七、時空分析 13
編寫程式求解騎士巡遊問題：在n行n列的棋盤上（如n=5），假設一位騎士（按象棋中「馬走日」的行走法）從初始座標位置(x1，y1)出發，要遍訪（巡遊）棋盤中的每乙個位置一次。請編乙個程式，為騎士求解巡遊「路線圖」（或告訴騎士，從某位置出發時，無法遍訪整個棋盤 — 問題無解）。
輸入輸入n行n列的棋盤的大小（1 <= n <= 12），建立乙個n*n的陣列，陣列[i][j]棋盤,再輸入騎士巡遊的初始位置(i,j)。
輸出例如，當n=5且初始座標位置定為(1，1) — 即最左上角的那個點時，如下是一種巡遊「路線圖」。程式執行後的輸出結果為：
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
（1）「棋盤」可用二維陣列b表示。
（2）編制乙個具有如下原型的遞迴函式solve，用於完成任務：從(i,j)點出發，做第k至第n*n（即n的平方）次的移動 — 將k直到n的平方這些數碼按規則分別擺放到棋盤即陣列b中，若成功則通過引用引數ok返回true，否則返回false。
void solve(int i, int j, int k, bool& ok)；
（3）編制主函式，讓使用者輸入作為巡遊起點的初始座標位置(x1,y1)，在該處擺放「棋子」（數碼）1，而後進行呼叫「solve(x1, y1, 2, ok);」來完成所求任務。
欲處理的初始問題為：從某點(x1,y1)出發，按所給行走規則，作24次移動，遍訪棋盤中沒被訪問過的各點（或發現無路可走）。
可分解化簡為如下兩個子問題（正是形成遞迴函式的基礎）：
① 由點(x1,y1)出發，按所給行走規則作1次移動到達(g,h)（或發現無路可走）；
② 從(g,h)點出發，按所給行走規則，作23次移動，遍訪棋盤中沒被訪問過的各點（或發現無路可走）。
solve函式具體實現時，若由(i,j)點出發已「無路可走」，則將引用引數ok置為false而遞迴出口；否則，先「邁一步」到達(g,h)點，而後再進行遞迴呼叫：solve(g, h, k+1, ok)；以實現從新點(g,h)出發，將k+1直到25這些「棋子」（數碼）分別擺放到棋盤上，若成功則通過引用引數ok返回true（否則返回false）。
遞迴演算法：在函式或子過程的內部，直接或者間接地呼叫自己的演算法。
回溯演算法：問題的每個解都包含n部分，先給出第一部分，再給出第二部分，……直到給出第n部分，這樣就得到了乙個解。若嘗試到某一步時發現已經無法繼續，就返回到前一步，修改已經求出的上一部分，然後再繼續向後求解。
這樣，直到回溯到第一步，並且已經將第一步的所有可能情況都嘗試過之後，即可得出問題的全部解。
全域性性的二維陣列b[ ][ ] ，a[ ][ ]
一維陣列dx[ ]， dy[ ]
main()流程
a[i][j]=true
solve()流程
#include
#include //i/o流控制標頭檔案,setw()的標頭檔案,setw(n) 設域寬為n個字元 #define n 12定義乙個巨集並賦初值
using namespace std;
int b[n][n]; //定義全域性性的二維陣列儲存步數
bool a[n][n]; //記錄某一點是否已經走過
int num=0; //記錄方案數
int dx=;
int dy=; //提供每一步的走法
void solve(int i,int j,int k,bool&ok,int n) //計算走法
else
a[x1][y1]=true;
}} }int main()
cout<<"請輸入起始位置的座標:";
cin>>row>>col;
b[row-1][col-1]=1設定起始點
a[row-1][col-1]=false;
solve (row-1,col-1,2,ok,n); //呼叫函式計算結果
if(!ok)
cout<<"從點("< return 0;
}時間複雜度：
（1）時間頻度
乙個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且乙個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。
乙個演算法中的語句執行次數稱為語句頻度或時間頻度。記為t(n)。
（2）時間複雜度
本題的時間複雜度為o()。
空間複雜度：
本題的空間複雜度為o(n*n)。
C面試問題
c語言面試題大彙總之華為面試題 1 區域性變數能否和全域性變數重名？答 能，區域性會遮蔽全域性。要用全域性變數，需要使用 區域性變數可以與全域性變數同名，在函式內引用這個變數時，會用到同名的區域性變數，而不會用到全域性變數。對於有些編譯器而言，在同乙個函式內可以定義多個同名的區域性變數，比如在兩個迴...
C理論知識問題
再給這個數先左移2次 原來數的4倍，然後，在給這個數字乘以2 原來數的8倍，最後加上存放在暫存器裡面的兩倍就 原來數字的10倍了。這些都是由cpu的指令系統控制的，在做邏輯運算的時候 就是邏輯控制單元 在起作用了，其實就是一些奇怪的加法比如 與運算就會被規定兩個不一樣的數字進行比較結果為0 或運算 ...
C 實習報告
實驗報告 課程名稱 c 程式設計 專業班級電子1041 姓名李巨集平 學號 1004451132 電氣與資訊學院 和諧勤奮求是創新 實驗教學考核和成績評定辦法 1 課內實驗考核成績，嚴格按照該課程教學大綱中明確規定的比重執行。實驗成績不合格者，不能參加課程考試，待補做合格後方能參加考試。2 單獨設立...