計(jì)數(shù)排序是一個(gè)非基于比較的線性時(shí)間排序算法。它對(duì)輸入的數(shù)據(jù)有附加的限制條件： 1、輸入的線性表的元素屬于有限偏序集S； 2、設(shè)輸入的線性表的長(zhǎng)度為n，|S|=k（表示集合S中元素的總數(shù)目為k），則k=O(n)。 在這兩個(gè)條件下，計(jì)數(shù)排序的復(fù)雜性為O(n)。 計(jì)數(shù)排序算法的基本思想是對(duì)于給定的輸入序列中的每一個(gè)元素x，確定該序列中值小于x的元素的個(gè)數(shù)。一旦有了這個(gè)信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個(gè)元素的值小于x的值，則x可以直接存放在輸出序列的第18個(gè)位置上。 計(jì)數(shù)排序算法沒有用到元素間的比較，它利用元素的實(shí)際值來確定它們?cè)谳敵鰯?shù)組中的位置。因此，計(jì)數(shù)排序算法不是一個(gè)基于比較的排序算法，從而它的計(jì)算時(shí)間下界不再是Ω(nlogn)。另一方面，計(jì)數(shù)排序算法之所以能取得線性計(jì)算時(shí)間的上界是因?yàn)閷?duì)元素的取值范圍作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到線性時(shí)間的上界。
上傳時(shí)間： 2015-10-30
上傳用戶：chenxichenyue
[問題描述] 將N個(gè)關(guān)鍵字去整數(shù)的記錄進(jìn)行整序， 以使所有關(guān)鍵字為非負(fù)數(shù)的記錄排在關(guān)鍵字為負(fù)數(shù)的記錄之前，要求使用最少的附加空間，且算法的時(shí)間復(fù)雜度為O（N） [輸入] 待排序記錄個(gè)數(shù)，各關(guān)鍵字的值。 [輸出] 關(guān)鍵字從正負(fù)分開，正數(shù)在前 [存儲(chǔ)結(jié)構(gòu)] 待排序記錄順序存儲(chǔ)。 [算法的基本思想] 快速排序算法每次任取一個(gè)記錄的關(guān)鍵字為標(biāo)準(zhǔn)，將其余記錄分為兩組將，N個(gè)關(guān)鍵字去整數(shù)的記錄進(jìn)行整序， 以使所有關(guān)鍵字為非負(fù)數(shù)的記錄排在關(guān)鍵字為負(fù)數(shù)的記錄之前。 #include <iostream> using namespace std #define MAXNUM 100//設(shè)文件的最長(zhǎng)可能長(zhǎng)度 void sort(int* keys, const int len)//排序
上傳時(shí)間： 2014-01-13
上傳用戶：aig85
本書提供用J B u i l d e r開發(fā)數(shù)據(jù)庫應(yīng)用程序、創(chuàng)建分布式應(yīng)用程序以及編寫J a v a B e a n 組件的高級(jí)資料。它包括下列幾個(gè)部分： • 第一部分是“開發(fā)數(shù)據(jù)庫應(yīng)用程序”，它提供關(guān)于使用J b u i l d e r的D a t a E x p r e s s數(shù)據(jù) 庫體系結(jié)構(gòu)的信息，并解釋原始數(shù)據(jù)組件和類之間的相互關(guān)系，以及怎樣使用它 們來創(chuàng)建你的數(shù)據(jù)庫應(yīng)用程序。它還解釋怎樣使用Data Modeler(數(shù)據(jù)模型器)和 Application Generator（應(yīng)用程序生成器）創(chuàng)建數(shù)據(jù)驅(qū)動(dòng)的客戶機(jī)/服務(wù)器應(yīng)用程 序。 • 第二部分是“開發(fā)分布式應(yīng)用程序”，它提供關(guān)于使用ORB Explorer、用J B u i l d e r 創(chuàng)建多級(jí)的分布應(yīng)用程序、調(diào)試分布式應(yīng)用程序、用J a v a定義C O R B A接口以及 使用s e r v l e t等的信息。 • 第三部分是“創(chuàng)建J a v a B e a n”，它解釋怎樣開發(fā)新的J a v a B e a n組件，描述在組件 開發(fā)中涉及的任務(wù), 怎樣使用B e a n s E x p r e s s創(chuàng)建新的J a v a B e a n，以及關(guān)于屬性、 事件、B e a nIn f o類和其他方面的詳細(xì)情況。
標(biāo)簽： 8226 數(shù)據(jù)庫 應(yīng)用程序 分
上傳時(shí)間： 2014-01-03
上傳用戶：wpt
實(shí)現(xiàn)最優(yōu)二叉樹的構(gòu)造；在此基礎(chǔ)上完成哈夫曼編碼器與譯碼器。 假設(shè)報(bào)文中只會(huì)出現(xiàn)如下表所示的字符： 字符 A B C D E F G H I J K L M N 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 字符 O P Q R S T U V W X Y Z ， ． 頻度 63 15 1 48 51 80 23 8 18 1 16 1 6 2 要求完成的系統(tǒng)應(yīng)具備如下的功能： 1．初始化。從終端（文件）讀入字符集的數(shù)據(jù)信息，。建立哈夫曼樹。 2．編碼：利用已建好的哈夫曼樹對(duì)明文文件進(jìn)行編碼，并存入目標(biāo)文件（哈夫曼碼文件）。 3．譯碼：利用已建好的哈夫曼樹對(duì)目標(biāo)文件（哈夫曼碼文件）進(jìn)行編碼，并存入指定的明文文件。 4．輸出哈夫曼編碼文件：輸出每一個(gè)字符的哈夫曼編碼。
上傳時(shí)間： 2014-11-23
上傳用戶：shanml
最大間隙問題：給定n 個(gè)實(shí)數(shù)x , x , , xn 1 2 ，求這n 個(gè)數(shù)在實(shí)軸上相鄰2 個(gè)數(shù)之間的最 大差值。假設(shè)對(duì)任何實(shí)數(shù)的下取整函數(shù)耗時(shí)O(1)，設(shè)計(jì)解最大間隙問題的線性時(shí)間算法。
上傳時(shí)間： 2013-12-25
上傳用戶：123456wh
算法實(shí)現(xiàn)題1-2 連續(xù)和問題 « 問題描述： 給定一個(gè)正整數(shù)n，計(jì)算有多少個(gè)不同的連續(xù)自然數(shù)段，其和恰為n。例如，當(dāng)n=27 時(shí)，有4 個(gè)不同的連續(xù)自然數(shù)段的和恰為27：2+3+4+5+6+7；8+9+10；13+14；27。 « 編程任務(wù)： 給定一個(gè)正整數(shù)n，試設(shè)計(jì)一個(gè)O(n)時(shí)間算法，計(jì)算有多少個(gè)不同的連續(xù)自然數(shù)段的 和恰為n。 « 數(shù)據(jù)輸入： 由文件input.txt提供輸入數(shù)據(jù)。文件的第1 行是正整數(shù)n。 « 結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的和恰為n的連續(xù)自然數(shù)段的個(gè)數(shù)輸出到output.txt中。 輸入文件示例 輸出文件示例 input.txt 27 output.txt 4
上傳時(shí)間： 2016-05-28
上傳用戶：yulg
Ex3-23 親兄弟問題 « 問題描述： 給定n 個(gè)整數(shù)0 1 1 , , , n- a a a 組成的序列。序列中元素i a 的親兄弟元素k a 定義為： min{ | } k i j n j j i a = a a ³ a < < 。 親兄弟問題要求給定序列中每個(gè)元素的親兄弟元素的位置。元素i a 的親兄弟元素為k a 時(shí)，稱k 為元素i a 的親兄弟元素的位置。當(dāng)元素i a 沒有親兄弟元素時(shí)，約定其親兄弟元素 的位置為-1。 例如，當(dāng)n=10，整數(shù)序列為6，1，4，3，6，2，4，7，3，5 時(shí)，相應(yīng)的親兄弟元素位 置序列為：4，2，4，4，7，6，7，-1，9，-1。 « 編程任務(wù)： 對(duì)于給定的n個(gè)整數(shù)0 1 1 , , , n- a a a 組成的序列，試用抽象數(shù)據(jù)類型棧，設(shè)計(jì)一個(gè)O(n) 時(shí)間算法，計(jì)算相應(yīng)的親兄弟元素位置序列。 « 數(shù)據(jù)輸入： 由文件input.txt提供輸入數(shù)據(jù)。文件的第1 行有1 個(gè)正整數(shù)n，表示給定給n個(gè)整數(shù)。 第2 行是0 1 1 , , , n- a a a 。 « 結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的與給定序列相應(yīng)的親兄弟元素位置序列輸出到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
上傳時(shí)間： 2013-12-17
上傳用戶：shizhanincc
Ex8-4 匯點(diǎn)問題 « 問題描述： 采用鄰接矩陣表示一個(gè)具有n 個(gè)頂點(diǎn)的圖時(shí)，大多數(shù)關(guān)于圖的算法時(shí)間復(fù)雜性為 O(n2 )，但也有例外。例如，即使采用鄰接矩陣表示一個(gè)有向圖G，確定G 是否含有一個(gè) 匯（即入度為n-1，出度為0 的頂點(diǎn)），只需要O(n)計(jì)算時(shí)間。試寫出其算法。 « 編程任務(wù)： 對(duì)于給定的有n個(gè)頂點(diǎn)的圖G 的鄰接矩陣，各頂點(diǎn)依次編號(hào)為1，2，…，n。試設(shè)計(jì)一 個(gè)O(n)時(shí)間算法，計(jì)算圖G 的匯點(diǎn)。 « 數(shù)據(jù)輸入： 由文件input.txt提供輸入數(shù)據(jù)。文件的第1 行有1 個(gè)正整數(shù)n，表示圖G 中頂點(diǎn)個(gè)數(shù)。 第2 行起每行n個(gè)數(shù)，共n行，給出圖G 的鄰接矩陣。 « 結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的匯點(diǎn)編號(hào)輸出到output.txt中。當(dāng)圖G 沒有匯點(diǎn)時(shí)輸出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
上傳時(shí)間： 2013-12-25
上傳用戶：yyyyyyyyyy
算法實(shí)現(xiàn)題1-5 最大間隙問題 « 問題描述： 最大間隙問題：給定n 個(gè)實(shí)數(shù)x , , xn 1 2 ，求這n 個(gè)數(shù)在實(shí)軸上相鄰2 個(gè)數(shù)之間的最 大差值。假設(shè)對(duì)任何實(shí)數(shù)的下取整函數(shù)耗時(shí)O(1)，設(shè)計(jì)解最大間隙問題的線性時(shí)間算法。 « 編程任務(wù)： 對(duì)于給定的n 個(gè)實(shí)數(shù)n x , x , , x 1 2 ，編程計(jì)算它們的最大間隙。 « 數(shù)據(jù)輸入： 輸入數(shù)據(jù)由文件名為input.txt的文本文件提供。文件的第1 行有1 個(gè)正整數(shù)n。接下來 的1 行中有n個(gè)實(shí)數(shù)n x , x , , x 1 2 。 « 結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，將找到的最大間隙輸出到文件output.txt中。 輸入文件示例 輸出文件示例 input.txt 5 2.3 3.1 7.5 1.5 6.3 output.txt 3.2
上傳時(shí)間： 2016-05-28
上傳用戶：咔樂塢
Ex4-22 單射函數(shù)問題 « 問題描述： 設(shè)函數(shù)f將點(diǎn)集S = {0,1, , n -1}映射為f (S) = { f (i) | iÎ S} Í S 。單射函數(shù)問題要 從S中選取最大子集X Í S 使f (X )是單射函數(shù)。 例如，當(dāng)n=7， f (S) = {1,0,0,2,2,3,6} Í S 時(shí)， X = {0,1,6} Í S 是所求的最大子集。 « 編程任務(wù)： 對(duì)于給定的點(diǎn)集S = {0,1, , n -1}上函數(shù)f，試用抽象數(shù)據(jù)類型隊(duì)列，設(shè)計(jì)一個(gè)O(n)時(shí) 間算法，計(jì)算f的最大單射子集。 « 數(shù)據(jù)輸入： 由文件input.txt 提供輸入數(shù)據(jù)。文件的第1 行有1 個(gè)正整數(shù)n，表示給定的點(diǎn)集 S = {0,1, , n -1}。第2 行是f (i)的值，0 £ i < n。 « 結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的f的最大單射子集的大小輸出到output.txt中。 輸入文件示例 輸出文件示例 input.txt 7 1 0 0 2 2 3 6 output.txt 3
標(biāo)簽： Iacute 61516 laquo Icirc
上傳時(shí)間： 2016-05-28
上傳用戶：tyler
蟲蟲下載站版權(quán)所有 京ICP備2021023401號(hào)-1
