最快通路演算法
A. dijkstra的matlab程序看不懂，求解！
clear;
clc;
M=10000;%無窮遠距離
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';%a66鄰接矩陣，無向圖
pb(1:length(a))=0;pb(1)=1;%存放p,t標號信息
index1=1;%存放標號頂點順序
index2=ones(1,length(a));%存放始點到第i點最短通路中第i頂點前一頂點的序號
d(1:length(a))=M;d(1)=0;%存放由始點到第i點最短通路的值
temp=1;%算c1到其它點的最短路
while sum(pb)<length(a)
tb=find(pb==0);%找到標號為0的所有點
d(tb)=min(d(tb),d(temp)+a(temp,tb));%計算標號為0的點的最短路,其餘已算過,再算結果還是一樣
tmpb=find(d(tb)==min(d(tb)));%tmpb存儲標號為0的點中最短路最短的點的tb值，即在find過程中的第幾個
temp=tb(tmpb(1));%這個第幾個在d中的真正位置
pb(temp)=1;%把這個點標號為1
index1=[index1,temp];%存放標號頂點順序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2%判斷這個點前面是否有點
index=index(1);
end
index2(temp)=index;%記下這個點前面的點的標號
end
d, index1, index2
B. 圖論的基本概念有哪些
圖論基本概念
重要定義：
有向圖：每條邊都是有向邊的圖。
無向圖：每條邊都是無向邊的圖。
混合圖：既有有向邊又有無向邊的圖。
自迴路：一條邊的兩端重合。
重數：兩頂點間若有幾條邊，稱這些邊為平行邊，兩頂點a,b間平行邊的條數成為（a,b）的重數。
多重圖：含有平行邊的圖。
簡單圖：不含平行邊和自迴路的圖。
注意！一條無向邊可以用一對方向相反的有向邊代替，因此一個無向圖可以用這種方法轉化為一個有向圖。
定向圖：如果對無向圖G的每條無向邊指定一個方向由此得到的有向圖D。稱為的G定向圖.
底圖：如果把一個有向圖的每一條有向邊的方向都去掉，得無向圖G稱為的D底圖。
逆圖：把一個有向圖D的每條邊都反向由此得到的圖稱為D的逆圖。
賦權圖：每條邊都賦上了值。
出度：與頂點相連的邊數稱為該定點的度數，以該定點為始邊的邊數為出度。 入度：以該定點為終邊的邊數為入度。
特殊！度數為零的定點稱為孤立點。度數為一的點為懸掛點。
無向完全圖：在階無向圖中如果任何兩點都有一條邊關連則稱此圖是無向完全圖。Kn
完全有向圖：在階有向圖中如果任意兩點都有方向相反的有向邊相連則稱此圖為完全有向圖。
竟賽圖：階圖中如果其底圖是無向完全圖，則程此有向完全圖是竟塞圖。
注意！n階有向完全圖的邊數為n的平方；無向完全圖的邊數為n(n-1)/2。
下面介召圖兩種操作：①刪邊：刪去圖中的某一條邊但仍保留邊的端點。
②刪點：刪去圖中某一點以及與這點相連的所有邊。
子圖：刪去一條邊或一點剩下的圖。
生成子圖：只刪邊不刪點。
主子圖：圖中刪去一點所得的子圖稱的主子圖。
補圖：設為階間單無向圖，在中添加一些邊後，可使成為階完全圖；由這些添加邊和的個頂點構成的圖稱為的補圖。
重要定理：
定理5.1.1 設圖G是具有n個頂點m條邊的有向圖，其中點集V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理5.1.2 設圖G是具有n個頂點m條邊的無向圖，其中點集V={v,v,v,……,v}
deg(vi)=2m
推論 在無向圖中，度數為積數的頂點個數為偶數。
通路和富權圖的最短通路
1通路和迴路
基本概念：
通路的長度：通路中邊的條數。
迴路：如果通路中始點與終點相同。
簡單通路：如果通路中各邊都不相同。
基本通路：如果通路中各頂點都不相同。顯然（基本通路一定是簡單通路，但簡單通路不一定是基本通路）
可達：在圖G中如果存在一條v到d通路則稱從v到d是可達。
連通：在無向圖中如果任意兩點是可達的，否則是不連通的。
強連通：在有向圖中如果任意兩點是互可達的。
單向連通：在有向圖中如果存在任意兩點的通路。
弱連通：在有向圖中如果其底圖是連通的。
權：在圖的點或邊上表明某種信息的數。
賦權圖：含有權的圖。
賦權圖的最短通路問題的演算法：先求出到某一點的最短通路，然後利用這個結果再去確定到另一點的最短通路，如此繼續下去，直到找到到的最短通路為止。
指標：設V是圖的點集，T是V的子集，且T含有z但不含a，則稱T為目標集。在目標集T中任取一個點t，由a到t但不通過目標集T中其它點所有通路中，個邊權和的最小者稱為點t關與T的指標記作DT(t)。
圖和矩陣
住意兩個的區別：A·A 中元素的意義：當且僅當a 和a 都是1時，a a =1而a 和a 都為1意味著圖G中有邊(v ,v )和(v ,v )。於是可得如下結論：從頂點v 和v 引出的邊，如果共同終止於一些頂點，則這些終止頂點的數目就是b 的值；特別對於b ，其值就是v 的出度。
A ·A中元素的意義：當且僅當a 和a 都為1時，a a =1，這意味著圖中有邊(v ,v )和(v ,v )。於是的得如下結論：從某些點引出的邊，如果同時終止於v 和v ，則這樣的頂點數就是的值。特別對於b ，其值就是的v 入度。
冪A 中元素的意義：當m=1時，a 中的元素=1，說明存在一條邊(v ,v )，或者說從v 到v 存在一條長度為一的通路。
A 中元素a 表示從v 到v 的長度為m的所有通路的數目。
歐拉圖
主要定義：
如果圖中存在一條通過圖中個邊一次且僅一次的迴路，則稱此迴路為歐拉迴路，具有歐拉迴路的圖稱為歐拉圖。
如果圖中存在一條通過圖中各邊一次且僅一次的通路，則稱此迴路為歐拉通路，具有歐拉通路的圖稱為半歐拉圖。
主要定理：一個無向連通圖是歐拉圖的充要條件是圖中各點的度數為偶數。
一個無向連通圖是半歐拉圖的充要條件是圖中至多有兩個奇數度點。
設圖G是有向連通圖，圖G是歐拉圖的充要條件是圖中每個頂點的入度和出度相等。
設圖G是有向連通圖，圖G是半歐拉圖的充要條件是至多有兩個頂點，其中一個頂點入度比它的出度大1，另一個頂點入度比它的出度少1；而其他頂點的入度和出度相等。
哈密頓圖
主要定義：如果圖G中存在一條通過圖G中各個頂點一次且僅一次的迴路，則稱此迴路為圖的哈密頓迴路；具有哈密頓迴路的圖稱為哈密頓圖。
如果圖G中存在一條通過圖G中各個頂點一次且僅一次的迴路，則稱此迴路為圖的哈密頓迴路；具有哈密頓迴路的圖稱為哈密頓圖。
主要定理：設圖G是哈密頓圖，如果從G中刪去個p頂點得到圖G』，則圖G』的連通分支數小於等於p。
設圖G是具有n個頂點的無向簡單圖，如果G中任意兩個不同頂點的度數之和大於等於n-1，則具有哈密頓通路，即G是半哈密頓圖。
設圖G是具有n個頂點的無向簡單圖，如果G中任意兩個不同頂點的度數之和大於等於n，則G具有哈密頓迴路，即G是哈密頓圖。
C. 網路流理論的常用演算法
1、augment path，直譯為「增廣路」，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個演算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個演算法必然會結束。
尋找通路的時候可以用DFS，BFS最短路等演算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上一個數量級。
增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個復雜得多的演算法，就是預推進演算法。
2、push label，直譯為「預推進」演算法。
[等待完善]
D. 鏈路狀態路由演算法的演算法工作原理
鏈路狀態選路演算法的工作原理如下
（1）在參與鏈路狀態選路的路由器集合中，每個路由器都需要通過某種機制來了解自己所連接的鏈路及其狀態。
（2）各路由器都能夠將其所連接的鏈路的狀態信息通知給網路中的所有其他路由器，這些鏈路信息包括鏈路狀態、費用以及鏈路兩端的路由器等。
（3）鏈路狀態信息的通過鏈路狀態分組（LSP）來向整個網路發布。一個LSP通常包含源路由器的標識符、相鄰路由器的標識符，以及而知之間鏈路的費用。每一個LSP都將被網路中的所有的路由器接收，並用於建立網路整體的統一拓撲資料庫。由於網路中所有的路由器都發送LSP，經過一段時間以後，每一個路由器都保持了一張完整的網路拓撲圖，再在這個拓撲圖上，利用最短通路演算法（例如Dijkstra演算法等），路由器就可以計算出從任何源點到任何目的地的最佳通路。
這樣，每一個路由器都能夠利用通路最短的原則建立一個以本路由器為根、分支到所有其他路由器的生成樹，依據這個生成樹就可以很容易地計算出本路由器的路由表。
E. 用遞歸演算法找出迷宮中所有可行的路徑
回溯啊、、、
int ans[1000][2],t=0； //ans數組里存的是每一步的解
void dfs(int x,int y)
{
if (x==x0&&y==y0) {print();return ;} //x0 y0是出口坐標 print（）是輸出一個合法解的函數 這個很 簡單你自己寫吧
然後是枚舉下一步可以到達的點 因為我不知道走的規則所以寫不出來 只能先假設xx yy是x、y能到達的一個點吧 你可以用for循環枚舉能到的點
for (xx.....)
for (yy....)
if (xx,yy滿足條件）
{
t++;
ans[t][0]=xx;
ans[t][1]=yy;
dfs(xx,yy)
t--;
}
}
F. 求用C++Dijkastra演算法解決最短通路問題
#include<string.h>
#defineN1010
#definenull0
longmap[N][N],v[N];
voiddijkstra(longn,longs,longt){
longq[N],i,j,k,flag=1;
memset(v,0x7f,sizeof(v));
memset(q,1,sizeof(q));
v[s]=0;
for(k=0;k<n;k++){
for(j=1;j<=n&&q[j]==0;j++);
if(j>n)break;
for(i=j+1;i<=n;i++)
if(q[i]&&v[i]<v[j])j=i;
q[j]=0;
for(i=1;i<=n;i++)
if(j!=i&&map[j][i]!=null&&v[j]+map[j][i]<v[i])
v[i]=v[j]+map[j][i];
}
}
來自北理工某大神模板
G. 最短路徑
// dijsktra.cpp : 定義控制台應用程序的入口點。
//
#include "stdafx.h"
#define N 12
#include <iostream>
using namespace std;
const static int soure[N][N] =
{
/*
這填鄰接矩陣
*/
};
int min(int arr[N],bool bj[])
{
int tmp = 999;
int temp = 0;
for(int i=0; i<N; i++)
{
if((arr[i]<tmp)&&(bj[i]==true))
{
tmp = arr[i];
temp = i;
}
}
return temp;
}
class dijsktra
{
private:
int dist[N][N];
int path[N][N];
int final[N][N];
bool flag[N];
public:
void Doing()
{
for(int i=0; i<N; i++)
{
int temp = 0;
for(int j=0; j<N; j++)
{
flag[j] = true;
}
for(int j=0; j<N; j++)
{
dist[i][j] = soure[i][j];
path[i][j] = i;
}
flag[i] = false;
temp = min(dist[i],flag);
flag[temp] = false;
for(int j=1; j<N; j++)
{
for(int k=0; k<N; k++)
{
if((flag[k] == true)&&((soure[temp][k]+dist[i][temp])<dist[i][k]))
{
dist[i][k] = soure[temp][k]+dist[i][temp];
path[i][k] = temp;
}
}
temp = min(dist[i],flag);
flag[temp] = false;
}
}
}
void print()
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<dist[i][j]<<","<<path[i][j]<<" ";
}
cout<<endl;
}
}
void l_print()
{
int i,j;
cout<<"請輸入i,j的值:";
cin>>i>>j;
cout<<"最短路徑長度為："<<dist[i][j]<<endl;
cout<<"路徑為";
int temp = j;
while(path[i][temp]!=i)
{
cout<<temp<<"<-";
temp = path[i][temp];
}
cout<<temp<<"<-";
cout<<i<<endl;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
dijsktra test;
test.Doing();
test.print();
test.l_print();
system("pause");
return 0;
}
H. 最短路徑演算法應用在哪些方面
網路通路， 凡事可以使用圖作為模型的問題都基本可以用到，比如游戲地圖的尋找，交通路線的尋找，這種最短路徑都可以用。
I. 離散數學是學什麼的
第l章 基礎：邏輯、集合和函數
1．1 邏輯
1．1．1 引言
1．1．2 命題
1．1．3 翻譯語言的句子
1．1．4 布爾檢索
l. 1．5 邏輯運算和位運算練習
1．2 命題等價
1. 2．1 引言
1．2．2 邏輯等價練習
1．3 謂詞和量詞
1．3．1 引言
1．3．2 量詞
1．3．3 翻譯語句為邏輯表達式
1．3．4 選自Lewis Carroll的例子(選讀)
1．3．5 綁定變數
1．3．6 否定練習
1．4 集合
1．4．1 引言
1．4．2 冪集合
1．4．3 笛卡兒積練習
1．5 集合運算
1．5．1 引言
1．5．2 集合相等
1．5．3 擴展的並集和交集
1．5．4 集合的計算機表示練習
1．6 函數
1．6．1 引言
1．6．2 一對一函數和映上函數
1．6．3 反函數和函數組合
1．6．4 函數的圖像
1．6．5 幾個重要的函數練習
1．7 序列與求和
1．7．1 引言
1．7．2 序列
1．7．3 特殊的整數序列
1．7．4 求和
1．7．5 基數(選讀)練習
1．8 函數增長
1．8．1 引言
1．8．2 大O符號
1．8．3 函數組合的增長
1．8．4 大Ω和大Ξ符號
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第2章 基礎：演算法、整數和矩陣
2．1 演算法
2．1．1 引言
2．1．2 搜索演算法練習
2．2 演算法的復雜性
2．2．1 引言練習
2．3 整數和除法
2．3．1 引言
2．3．2 除法
2．3．3 素數
2．3．4 除法演算法
2．3．5 最大公約數和最小公倍數
2．3．6 模運算
2. 3．7 同餘應用
2．3．8 密碼學練習
2．4 整數和演算法
2．4．1 引言
2．4．2 歐幾里德演算法
2．4．3 整數表示
2．4．4 整數運算演算法練習
2．5 數論應用
2．5．1 引言
2．5．2 若干有用的結果
2．5．3 線性同餘
2．5．4 中國余數定理
2．5. 5 大整數的計算機算術運算
2．5．6 偽素數
2．5．7 公鑰密碼學
2．5．8 RSA加密
2．5．9 RSA解密
2．5．10 用RSA作公鑰系統練習
2．6 矩陣
2．6．1 引言
2．6．2 矩陣運算
2．6．3 矩陣乘法運算
2．6．4 矩陣的轉置和冪
2．6．5 0-1矩陣練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第3章 數學推理
3．1 證明方法
3．1．1 引言
3．1．2推理規則
3．1．3 謬誤
3．1．4 帶量詞命題的推理規則
3．1．5 證明定理的方法
3．1．6 定理與量詞
3．1．7 停機問題
3．1．8 關於證明的一些評注練習
3．2 數學歸納法
3．2．1 引言
3．2．2 良序性
3．2．3 數學歸納法
3．2．4 數學歸納法證明的例子
3．2．5 數學歸納法的第二原理練習
3．3 遞歸定義
3．3．1 引言
3．3．2 遞歸地定義函數
3．3．3 遞歸地定義集合練習
3．4 遞歸演算法
3．4．1 引言
3．4．2 遞歸與迭代練習
3．5 程序正確性
3．5．1 引言
3．5．2 程序驗證
3．5．3 推理規則
3．5．4 條件語句
3．5．5 循環不變數
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第4章 計數
4．1 計數的基礎
4．1．1 引言
4．1．2 基本的計數原則
4．1．3 容斥原理
4．1．4 樹圖練習
4．2 鴿巢原理
4．2．1 引言
4．2．2 推廣的鴿巢原理
4．2．3 巧妙使用鴿巢原理練習
4．3 排列與組合
4．3．1 引言
4．3．2 排列
4．3．3 組合
4．3．4 二項式系數
4．3．5 二項式定理練習
4．4 離散概率
4．4．1 引言
4．4．2 有限概率
4．4．3 事件組合的概率
4．4．4 概率的推理練習
4．5 概率論
4．5．1 引言
4．5．2 概率賦值
4．5．3 事件的組合
4．5．4 條件概率
4．5．5 獨立性
4．5．6 伯努利實驗與二項式分布
4．5．7 隨機變數
4．5．8 期望值
4．5．9 獨立隨機變數
4．5．10 方差
4．5．11 切比雪夫不等式
4．5．12 平均狀態下的計算復雜性練習
4．6 一般性的排列和組合
4．6．1 引言
4．6．2 有重復的排列
4．6．3 有重復的組合
4．6．4 具有不可區別物體的集合的排列
4．6．5 把物體放入盒子練習
4. 7 生成排列和組合
4．7．1 引言
4．7．2 生成排列
4．7．3 生成組合
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第5章 高級計數技術
5．1 遞推關系
5．1．1 引言
5．1．2 遞推關系
5．1．3 用遞推關系構造模型練習
5．2求解遞推關系
5．2．1 引言
5．2．2 求解常系數線性齊次遞推關系
5．2．3 常系數線性非齊次的遞推關系練習
5．3分而治之關系
5．3．1 引言
5．3．2 分而治之關系練習
5．4 生成函數
5．4．1 引言
5．4．2 關於冪級數的有用的事實
5．4．3 計數問題與生成函數
5．4．4 使用生成函數求解遞推關系
5．4．5 使用生成函數證明恆等式練習
5．5 容斥
5．5．1 引言
5．5．2 容斥原理練習
5．6 容斥原理的應用
5．6．1 引言
5．6．2 容斥原理的另一種形式
5．6．3伊拉脫森篩
5．6．4 映上函數的個數
5．6．5 錯位排列
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第6章 關系
6．1 關系及其性質
6．1．1 引言
6．1．2 函數作為關系
6．1．3 集合上的關系
6．1．4 關系的性質
6．1．5 關系的組合練習
6．2 n元關系及其應用
6．2．1 引言
6. 2．2 n元關系
6．2．3 資料庫和關系練習
6．3 關系的表示
6．3．1 引言
6．3．2 用矩陣表示關系
6．3．3 用圖表示關系練習
6．4 關系的閉包
6．4．1 引言
6．4．2 閉包
6．4．3 有向圖的路徑
6．4．4 傳遞閉包
6．4．5 沃舍爾演算法練習
6．5 等價關系
6．5．1 引言
6．5．2 等價關系
6．5．3 等價類
6．5．4 等價類與劃分練習
6．6 偏序
6．6．1 引言
6．6．2 字典順序
6．6．3 哈斯圖
6. 6．4 極大元素與極小元素
6．6．5 格
6．6．6 拓撲排序
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第7章 圖
7．1 圖的介紹
7．1．1 圖的種類
7．1．2 圖模型練習
7．2 圖的術語
7．2．1 引言
7．2．2 基本術語
7．2．3 一些特殊的簡單圖
7．2．4 偶圖
7．2．5 特殊類型的圖的一些應用
7．2．6 從舊圖到新圖練習
7．3 圖的表示和圖的同構
7．3．1 引言
7．3．2 圖的表示
7．3．3 相鄰矩陣
7．3．4 關聯矩陣
7．3．5 圖的同構練習
7. 4 連通性
7．4．1 引言
7．4．2 通路
7．4．3 無向圖連通性
7．4．4 有向圖中的連通性
7．4．5 通路與同構
7．4．6 統計頂點之間的通路練習
7．5 歐拉通路與哈密頓通路
7．5．1 引言
7．5．2 歐拉迴路和歐拉通路的充要條件
7．5．3 哈密頓通路和迴路練習
7．6 最短通路問題
7．6．1 引言
7．6．2 一個最短通路演算法
7．6．3 旅行推銷員問題練習
7．7 平面性圖
7．7．1 引言
7．7．2 歐拉公式
7．7．3 庫拉圖斯基定理練習
7．8 圖著色
7．8．1 引言
7．8．2 圖著色的應用
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第8章 樹
8．1 介紹樹
8．1．1 樹作為模型
8．1．2 樹的性質練習
8．2 樹的應用
8．2．1 引言
8．2．2 二叉搜索樹
8．2．3 決策樹
8．2．4 前綴碼練習
8．3 樹的遍歷
8．3．1 引言
8．3．2 通用地址系統
8．3．3 遍歷演算法
8．3．4 中綴、前綴和後綴記法練習
8．4 樹與排序
8．4．1 引言
8．4．2 排序的復雜性
8．4．3 冒泡排序
8．4．4 歸並排序練習
8．5 生成樹
8．5．1 引言
8．5．2 一些構造生成樹的演算法
8．5．3 回溯練習
8．6 最小生成樹
8．6．1 引言
8．6．2 最小生成樹演算法
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第9章 布爾代數
9．1 布爾函數
9．1．1 引言
9．1．2 布爾表達式和布爾函數
9．1．3 布爾代數中的恆等式
9．1．4 對偶性
9．1．5 布爾代數的抽象定義練習
9．2 布爾函數的表示
9．2．1 積之和展開式
9．2．2 函數完備性練習
9．3 邏輯門電路
9．3．1 引言
9．3. 2 門的組合
9．3．3 電路的例子
9．3．4 加法器練習
9．4 電路的極小化
9．4．1 引言
9．4．2 卡諾圖
9．4．3 無需在意條件
9．4．4 奎因-莫可拉斯基方法
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
第10章 計算模型
10．1 語言和文法
10．1．1 引言
10．1．2 短語結構文法
10．1．3 短語結構文法的類型
10．1．4 派生樹
10．1．5 巴科斯-諾爾範式練習
10．2 帶輸出的有限狀態機
10．2．1 引言
10．2．2 帶輸出的有限狀態機練習
10．3 不帶輸出的有限狀態機
10．3．1 引言
10．3．2 串的集合
10．3．3 有限狀態自動機練習
10．4 語言的識別
10．4．1 引言
10．4．2 正則集合
10．4．3 克萊因定理
10．4．4 正則集合和正則文法
10．4．5 一個不能由有限狀態自動機識別語言
10．4．6 一些更強大的機器練習
10．5 圖靈機
10．5．1 引言
10．5．2 圖靈機的定義
10．5．3 用圖靈機識別集合
10．5．4 用圖靈機計算函數
10．5．5 不同類型的圖靈機
10. 5．6 丘奇-圖靈論題
練習
關鍵術語和結果
復習題
補充練習
計算機題目
計算和研究
寫作題目
附錄A 指數函數和對數函數
附錄B 偽代碼
奇數練習題答案
推薦讀物 如果想成為真正的程序員，學好離散數學是很重要的，但剛學時也有點難度。
J. 迷宮數組 最短路徑演算法 我， 我， 我給分60！
//對角線也可以走：如從1,3到2,4最短路徑為根號2
//如果對角線不想，兩個for循環條件判斷稍微修改下：
//代碼如下：
//輸出-1 表示找不到路徑
/*
給個數組，0表示通路，1表示阻礙，然後給任意兩個0的坐標，可以找到它們之間的最短路徑並列印出來
比如說數組是 1 0 0 0 1
1 1 1 0 1
1 1 0 0 1
1 0 0 0 1
1 0 1 1 1
然後我就可以找到第一行第二個數和第五行第二個數之間的最短路徑了
*/
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <stdio.h>
#define M 5
#define N 5
typedef struct coordinate{
short int x;
short int y;
} COORDINATE;
COORDINATE path[M*N];//全局變數，存儲已訪問結點
float getminpath(COORDINATE *,COORDINATE *,char [][N],COORDINATE *);
void main()
{
memset(path,0,sizeof(COORDINATE)*M*N);
char maze[M][N]={
'\1','\0','\0','\0','\1',
'\1','\1','\1','\0','\1',
'\1','\1','\0','\0','\1',
'\1','\0','\0','\0','\1',
'\1','\0','\1','\1','\1',
};
COORDINATE a,b;
float dis;
do{
system("cls");
printf("請輸入起點坐標：\n如1,2為第一行第二個數\n");
printf("取值范圍1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&a.x,&a.y);
printf("請輸入終點坐標：\n如5,2為第五行第二個數\n");
printf("取值范圍1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&b.x,&b.y);
a.x--;
a.y--;
b.x--;
b.y--;
dis=getminpath(&a,&b,maze,path);
printf("最短路徑為：%f\n",dis);
system("pause");
} while(getchar()!=EOF);
}
float getminpath(COORDINATE *from,COORDINATE *to,char maze[][5],COORDINATE *visited)
//從from結點到to結點可以分成兩步，1.從from到from的相鄰結點。2.再到to結點，這就是一個遞歸的過程
//將已訪問結點存放入visited中
{
COORDINATE *nearpt=(COORDINATE*)malloc(sizeof(COORDINATE)*1);
memset(nearpt,0,sizeof(COORDINATE));
int i,j;
float min=0;//存儲最短路徑的值
COORDINATE *pvisit;//遍歷已訪問結點的指針
char reflag;//相鄰結點是否 「已訪問」 的flag
float dis=-1;//距離
if(from==0||to==0||maze==0)
{
return -1;
}
else
{
if(from->x==to->x&&from->y==to->y)//坐標相同，表示已到達
{
dis=0;
}
else
{
for(i=-1;i<=1;i++)
{
for(j=-1;j<=1;j++)
{
if(i==0&&j==0)
{
continue;
}
nearpt->x=from->x+i;
nearpt->y=from->y+j;
if(nearpt->x<0||nearpt->x>M-1||nearpt->y<0||nearpt->y>N-1)//越界
{
continue;
}
if(maze[nearpt->x][nearpt->y]!='\0')//非零為障礙，繼續下一次循環
{
continue;
}
reflag='\0';//初值為'\0'，表示未訪問過
for(pvisit=path;pvisit<visited;pvisit++)//搜索已訪問結點
{
if(pvisit->x==nearpt->x&&pvisit->y==nearpt->y)
{
reflag='\1';//該結點已經訪問過了
break;
}
}
if(reflag=='\1')
{
continue;
}
else
{
visited->x=from->x;//將from結點加入已訪問結點數組中
visited->y=from->y;
dis=getminpath(nearpt,to,maze,visited+1);//遞歸
if(dis>=0)
{
dis+=sqrt((nearpt->x-from->x)*(nearpt->x-from->x)+(nearpt->y-from->y)*(nearpt->y-from->y));
// printf("%d,%d到%d,%d\t距離：%3f\n",from->x,from->y,to->x,to->y,dis);
if(min==0)//第一次，還沒將dis的值賦給m過
{
min=dis;
}
else
{
if(dis<min)
{
min=dis;
}
else
{
}
}
}
visited->x=0;//清除from結點
visited->y=0;
}
}
}
}
}
free(nearpt);
if(min>0)
{
return min;
}
else
{
return dis;
}
}