阅读:1473回复:14
有关数据分配的算法?
有一段数据,需要分散保存在n个人手中,要求其中任意m个人(m<n)都可凑出完整的数据,但每个人手中都没有完整的数据。
问:每个人手中最少保存多少数据? 能叙述一下算法吗?当然不需在证明了! |
|
沙发#
发布于:2002-05-13 17:47
将数据分成均等的n份,第一个人获得全部数据抽去第一份之后的其它数据,第二个人获得全部数据抽去第二份之后的其它数据。。。。。。第n个人获得全部数据抽去第n份之后的其它数据。
|
|
|
板凳#
发布于:2002-05-13 17:52
也不一定要均分,分成n份就可以。
|
|
|
地板#
发布于:2002-05-13 17:58
任何一个人所缺的那份数据其他任何一个人都有,但没有一个人拥有全部数据。
|
|
|
地下室#
发布于:2002-05-13 18:17
这类题目很有趣,能多找些来吗?
|
|
|
5楼#
发布于:2002-05-13 19:22
好,佩服。
|
|
6楼#
发布于:2002-05-13 21:50
找本算法数据结构看看吧!编程久了就知道数据结构的作用了,开始编程的时候根本就不考虑数据结构和算法,因为写的都是小东西
|
|
7楼#
发布于:2002-05-14 08:51
将数据分成均等的n份,第一个人获得全部数据抽去第一份之后的其它数据,第二个人获得全部数据抽去第二份之后的其它数据。。。。。。第n个人获得全部数据抽去第n份之后的其它数据。 可能我没说清楚,当少于m个人(也是任意的人)时,是不能溱出完整的数据。这一点很重要,因为只有这样才能保证数据的安全。 我想建立一个数学公式来计算,然后通过找可导点来取得极值,但不知如何去建立? To:guardee,这好象与数据结构无关吧!这是个纯数学问题。 这也不来考大家,而是我现在遇到的一个需求。 再叙述一次: 有一段数据,需要分散保存在n个人手中,要求只有其中任意m个人(m<n)都可凑出完整的数据,但每个人手中都没有完整的数据,且少于m个人时是不能凑出完整数据的。 问:每个人手中最少保存多少数据? |
|
8楼#
发布于:2002-05-14 08:56
这么说算法中必须代入m,让我想想看。
|
|
|
9楼#
发布于:2002-05-14 09:10
分成m份不行吗。
哈哈,我的数据结构很差,不要笑话我。 :D |
|
10楼#
发布于:2002-05-14 11:34
用集合的方法可以实现。
下午要考试,晚上把完整的算法给你。 |
|
|
11楼#
发布于:2002-05-15 13:32
在n个人中任选m个人共有n!/m!种选法。
将所有数据分成m×n份,每一份数据称为一个基本元素xi。 将m×n个基本元素分成n等份,每份m个元素,并将这m个元素构成的集合称为原始成员集合。共有n个原始集合S1,S2,。。。。,Sn。 将S1,S2,。。。,Sn放入初态集SET_START。 将S1,S2,。。。,Sn放入终态集SET_END。 从S1,S2,。。。,Sn中任选m个集合作为元素构成一个新集Gi,共有n!/m!个不同的Gi,以n!/m!个Gi为元素构成分组集SET_GROUP。 定义一个集合称为临时头集SET_TEMP_HEAD。 定义一个集合称为临时尾集SET_TEMP_TAIL。 定义一个集合称为分组集SET_GROUP。 1。 SET_GROUP为空吗?若空转14。 2。 置SET_TEMP_HEAD及SET_TEMP_TAIL为空。 3。 从SET_GROUP中任选一个元素Gi,从SET_END中取出所有与Gi中的元素同名的元素放入SET_TEMP_HEAD中,从SET_START中取出所有与Gi中的所有元素都不同名的元素放入SET_TEMP_TAIL中,然后将Gi从SET_GROUP中删除。 4。 SET_TEMP_TAIL为空吗?若空转12。 5。 从SET_TEMP_TAIL任取一个元素TSi。 6。 TSi为空吗?若不空转8。 7。 将TSi从SET_TEMP_TAIL删除,转4。 8。 从TSi中任取一元素x。 9。 若x在SET_TEMP_HEAD中的某个元素中出现,转11。 10。若x在SET_TEMP_HEAD中的所有元素中都不出现,将x放入某个HSi中,其中HSi是SET_TEMP_HEAD的元素,且HSi中不含TSi最初拥有的任何元素。 11。将x从TSi中删除,转6。 12。令SET_TEMP_HEAD中的元素替代SET_END中的同名元素。 13。转1。 14。SET_END中的元素即所求的解。 这个算法要求数据长度至少为m×n个单元。 |
|
|
12楼#
发布于:2002-05-15 13:34
因为又做了些修改,所以发迟了。
|
|
|
13楼#
发布于:2002-05-17 08:51
我要好好想一下,先给分吧!
|
|
14楼#
发布于:2002-05-17 12:57
多谢给分!我的专家分终于有了0的突破。
|
|
|