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
本附錄介紹一些新的A P I函數(shù)，有了這些函數(shù)，便可在自己的計(jì)算機(jī)上對(duì)I P協(xié)議統(tǒng)計(jì)情況
進(jìn)行查詢和管理。它們有助于獲得下面的能力：
■ I p c o n f i g . e x e（或適用于微軟Windows 95的Wi n i p c f g . e x e）：顯示I P配置信息，允許釋放
和更新D H C P分配的I P地址。
■ N e t s t a t . e x e：顯示T C P連接表、U D P監(jiān)聽者表以及I P協(xié)議統(tǒng)計(jì)情況。
■ R o u t e . e x e：顯示并處理網(wǎng)絡(luò)路由表。
■ A r p . e x e：顯示并修改供“地址解析協(xié)議”（A R P）使用的I P到物理地址翻譯表。
