-
Floyd-Warshall算法描述
1)適用范圍：
a)APSP(All Pairs Shortest Paths)
b)稠密圖效果最佳
c)邊權可正可負
2)算法描述：
a)初始化：dis[u,v]=w[u,v]
b)For k:=1 to n
For i:=1 to n
For j:=1 to n
If dis[i,j]>dis[i,k]+dis[k,j] Then
Dis[I,j]:=dis[I,k]+dis[k,j]
c)算法結束：dis即為所有點對的最短路徑矩陣
3)算法小結：此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行|V|次Dijkstra算法。時間復雜度O(n^3)。
考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個判斷I,j是否有通路的矩陣。更簡單的，我們可以把dis設成boolean類型，則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍色部分，可以更直觀地得到I,j的連通情況。
標簽：
Floyd-Warshall
Shortest
Pairs
Paths
上傳時間：
2013-12-01
上傳用戶：dyctj
-
用C++中的MFC編程實現正軸等角割圓柱投影，實現以下要求：
取克拉索夫斯基橢球
(1)制圖區域： Bs=0°, BN=25°
LE=105°, LE=125°
(2)經緯線間隔： ΔB=ΔL=5°
(3)制圖比例尺： 1:M0=1:1000 000
(4)標準緯線： Bk=±15°
計算經緯網格點的 x, y,m,n, p
標簽：
MFC
編程實現
正
投影
上傳時間：
2013-12-29
上傳用戶：himbly
-
用C語言解決約瑟夫環問題,約瑟夫環問題描述:設編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有一個正整數密碼（可用隨機數產生）。開始時任意給出一個報數上限值m，從第一個人開始順時針方向自1起順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數，報到新m值的人出列；如此下去，直到所有人全部出列為止。要求設計一個程序模擬此過程，并給出出列人的編號序列。
標簽：
gt
C語言
方向
上傳時間：
2014-11-21
上傳用戶：yepeng139
-
每組輸入是兩個整數n和k。(1 <= n <= 50, 1 <= k <= n)
對于每組輸入，請輸出四行。
第一行： 將n劃分成若干正整數之和的劃分數。
第二行： 將n劃分成最大數不超過k的劃分數。
第三行： 將n劃分成若干奇正整數之和的劃分數。
第四行： 將n劃分成若干不同整數之和的劃分數。
標簽：
lt
輸入
50
整數
上傳時間：
2016-03-07
上傳用戶：腳趾頭
-
Ex3-23 親兄弟問題
« 問題描述：
給定n 個整數0 1 1 , , , n- a a a 組成的序列。序列中元素i a 的親兄弟元素k a 定義為：
min{ | } k i j n j j i a = a a ³ a
< <
。
親兄弟問題要求給定序列中每個元素的親兄弟元素的位置。元素i a 的親兄弟元素為k a
時，稱k 為元素i a 的親兄弟元素的位置。當元素i a 沒有親兄弟元素時，約定其親兄弟元素
的位置為-1。
例如，當n=10，整數序列為6，1，4，3，6，2，4，7，3，5 時，相應的親兄弟元素位
置序列為：4，2，4，4，7，6，7，-1，9，-1。
« 編程任務：
對于給定的n個整數0 1 1 , , , n- a a a 組成的序列，試用抽象數據類型棧，設計一個O(n)
時間算法，計算相應的親兄弟元素位置序列。
« 數據輸入：
由文件input.txt提供輸入數據。文件的第1 行有1 個正整數n，表示給定給n個整數。
第2 行是0 1 1 , , , n- a a a 。
« 結果輸出:
程序運行結束時，將計算出的與給定序列相應的親兄弟元素位置序列輸出到output.txt
中。
輸入文件示例 輸出文件示例
input.txt
10
4 2 4 4 7 6 7 -1 9 -1
output.txt
6 1 4 3 6 2 4 7 3 5
標簽：
61516
laquo
min
序列
上傳時間：
2013-12-17
上傳用戶：shizhanincc
-
Ex8-4 匯點問題
« 問題描述：
采用鄰接矩陣表示一個具有n 個頂點的圖時，大多數關于圖的算法時間復雜性為
O(n2 )，但也有例外。例如，即使采用鄰接矩陣表示一個有向圖G，確定G 是否含有一個
匯（即入度為n-1，出度為0 的頂點），只需要O(n)計算時間。試寫出其算法。
« 編程任務：
對于給定的有n個頂點的圖G 的鄰接矩陣，各頂點依次編號為1，2，…，n。試設計一
個O(n)時間算法，計算圖G 的匯點。
« 數據輸入：
由文件input.txt提供輸入數據。文件的第1 行有1 個正整數n，表示圖G 中頂點個數。
第2 行起每行n個數，共n行，給出圖G 的鄰接矩陣。
« 結果輸出:
程序運行結束時，將計算出的匯點編號輸出到output.txt中。當圖G 沒有匯點時輸出0。
輸入文件示例 輸出文件示例
input.txt
5
0 0 1 1 1
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1
0 1 1 0 0
output.txt
3
標簽：
laquo
Ex
矩陣表示
上傳時間：
2013-12-25
上傳用戶：yyyyyyyyyy
-
算法實現題1-5 最大間隙問題
« 問題描述：
最大間隙問題：給定n 個實數x , , xn 1 2 ，求這n 個數在實軸上相鄰2 個數之間的最
大差值。假設對任何實數的下取整函數耗時O(1)，設計解最大間隙問題的線性時間算法。
« 編程任務：
對于給定的n 個實數n x , x , , x 1 2 ，編程計算它們的最大間隙。
« 數據輸入：
輸入數據由文件名為input.txt的文本文件提供。文件的第1 行有1 個正整數n。接下來
的1 行中有n個實數n x , x , , x 1 2 。
« 結果輸出:
程序運行結束時，將找到的最大間隙輸出到文件output.txt中。
輸入文件示例 輸出文件示例
input.txt
5
2.3 3.1 7.5 1.5 6.3
output.txt
3.2
標簽：
laquo
61516
xn
算法
上傳時間：
2016-05-28
上傳用戶：咔樂塢
-
Ex4-22 單射函數問題
« 問題描述：
設函數f將點集S = {0,1, , n -1}映射為f (S) = { f (i) | iÎ S} Í S 。單射函數問題要
從S中選取最大子集X Í S 使f (X )是單射函數。
例如，當n=7， f (S) = {1,0,0,2,2,3,6} Í S 時， X = {0,1,6} Í S 是所求的最大子集。
« 編程任務：
對于給定的點集S = {0,1, , n -1}上函數f，試用抽象數據類型隊列，設計一個O(n)時
間算法，計算f的最大單射子集。
« 數據輸入：
由文件input.txt 提供輸入數據。文件的第1 行有1 個正整數n，表示給定的點集
S = {0,1, , n -1}。第2 行是f (i)的值，0 £ i < n。
« 結果輸出:
程序運行結束時，將計算出的f的最大單射子集的大小輸出到output.txt中。
輸入文件示例 輸出文件示例
input.txt
7
1 0 0 2 2 3 6
output.txt
3
標簽：
Iacute
61516
laquo
Icirc
上傳時間：
2016-05-28
上傳用戶：tyler
-
離散01串問題
« 問題描述：
(n,k)01 串定義為：長度為n 的01 串，其中不含k 個連續的相同子串。對于給定的正
整數n 和k，計算(n,k)01 串的個數。
« 編程任務：
對于給定的正整數n和k，計算(n,k)01串的個數。
標簽：
laquo
01
離散
定義
上傳時間：
2016-07-15
上傳用戶：fredguo
-
問題描述
設有n種不同面值的硬幣，各硬幣的面值存于數組T[1:n]中。現要用這些面值的硬幣來找錢，可以實用的各種面值的硬幣個數不限。當只用硬幣面值T[1],T[2],…,T[i]時，可找出錢數j的最少硬幣個數記為C(i,j)。若只用這些硬幣面值，找不出錢數j時，記C(i,j)=∞。
編程任務
設計一個動態規劃算法，對1≤j≤L，計算出所有的C( n,j )。算法中只允許實用一個長度為L的數組。用L和n作為變量來表示算法的計算時間復雜性
數據輸入
由文件input.txt提供輸入數據。文件的第1行中有1個正整數n（n<=13），表示有n種硬幣可選。接下來的一行是每種硬幣的面值。由用戶輸入待找錢數j。
結果輸出
程序運行結束時，將計算出的所需最少硬幣個數輸出到文件output.txt中。
標簽：
上傳時間：
2016-07-28
上傳用戶：yangbo69
