存在N个二元集A={a,b},a>b且a,b∈N+(正整数);定义A的范围M为区间[a,b],又定义A的长度L=b-a;

存在N个二元集A={a,b},a>b且a,b∈N+(正整数);定义A的范围M为区间[a,b],又定义A的长度L=b-a;N个二元集A之间满足条件:任意二元集A (i) 中元素a(i),b(i)都不在其他集合A(j)范围M中,也就是说任意A之间无交集,找一个算法得到剩下的集合长度和的最大值.
例如三个二元集A1,A2,A3;
A1={6,10},L1=10-6=4;
A2={1,9},L2=8;
A3={8,11},L3=3;
A1与A2与A3具有交集,为了无交集,且使得L最大,只留下A2,max=L2=8
newskey 1年前 已收到1个回答 举报

loveayumizidane 幼苗

共回答了16个问题采纳率:81.3% 举报

自己转换成语言吧,so easy,就是写起来麻烦点.
(1)先看A1 依次和A2 .An做比较,比如和A2比较,分两种情况:
如果a(1) 大于b(2),分两种情况:
如果b(1)小于a(2),那么A(2)包含A(1),排除,跳出循环到第(2)步.
如果b(1) 大于a(2),分两种情况:
如果a(1)小于a(2),则有交集,跳出循环到第(2)步.
如果a(1)大于a(2),则不可能有交集,再与A3比较.
如果a(1) 小于b(2),分两种情况:
如果b(1)大于b(2),那么不是包含,就是有交集,跳出循环到第(2)步.
如果b(1)小于b(2),分两种情况:
如果b(1)小于a(1),那么没有交集,再与A3比较.
如果b(1)大于a(1),则有交集,跳出循环到第(2)步.
依上面的方法和A3比较
...
如果循环直到最后都没有交集,那么记录A(1)的L(k1)
(2) 把上面的集合A(i)换成A(i+1),重复循环比较A(i+2).A(n)即可
(3)把L(k1)+L(k2) +...给出即可.

1年前 追问

2

newskey 举报

不对,你想得太简单了,A(2)包含A(1)不一定能排除

举报 loveayumizidane

你说的不对,我也有地方没说对。 任意二元集A (i) 中元素a(i),b(i)都不在其他集合A(j)范围M中 而A(2)包含A(1) 说明A (1) 中元素a(1),b(1)很显然在集合A(2)范围中 但是A(1)包含A(2) 仍然可以继续与A3比较,不能跳出循环 。这一点我写错了 。
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.455 s. - webmaster@yulucn.com