资 源 简 介
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