Copyright© 2004 Sergiu Dumitriu, Marta GÎ rdea, Că tă lin Hriţ cu Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License" All brand names, product names, or trademarks belong to their respective holders.
标签：
Permission
Copyright
259
Dumitriu
上传时间：
2015-04-02
上传用户：jackgao
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
