求一个高效算法:已知n个数,取其中的m个数(m100,m=10,如果穷举,那计算机要算爆了),
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/08/29 06:05:33
求一个高效算法:已知n个数,取其中的m个数(m100,m=10,如果穷举,那计算机要算爆了),
你是要找出所有的符合要求的组合,还是只需要一个就可以?
再问: 需要找出所有符合要求的组合。
再答: 楼主熟悉普通的从N个数中找出所有M个数的算法吗?你这个情况仅仅需要在其之上加一个条件判断即可,每次不是单纯线形的寻找下一个数,而是判断如果下一个数与当前选出的离它最近的数之差是否大于t。 随手写了个测试了一下,核心方法如下,仅供参考: a是总数集合,你需要事先排序,这是一个可以有效减少比较次数的办法 n是a的数量 m是组合数量 b是输出结果 M是m的一个copy 这是c#写的,把输出函数换掉后,应该是几种常用语言通用的了 public void combine(int[] a, int n, int m, int[] b, int M) { int i, j; for (i = n; i >= m; i--) { b[m - 1] = i - 1; if (m > 1) combine(a, i - 1, m - 1, b, M); else { int c = M - 1; for (j = M - 1; j >= 0; j--) if (j == M - 1) Console.Write(a[b[j]]); else if (a[b[j+1]] - a[b[j]] >= t) // 这里就是添加的判断 Console.Write(a[b[j]]); Console.Write("\n"); } } } 而既然你要找出所有符合的组合,计算量基本就确定了,因为C(n,m)这个算法已经有很多人论证过了,楼上所说的那种情况的确会发生,我建议你结合一些算法之外的策略来避免,比如从控制输入上面来辅助,这段代码我没整理的太仔细,输出了一些空组合,但其中所有m个数的组合应该就是你想要的,你可以自己过滤一下
再问: 需要找出所有符合要求的组合。
再答: 楼主熟悉普通的从N个数中找出所有M个数的算法吗?你这个情况仅仅需要在其之上加一个条件判断即可,每次不是单纯线形的寻找下一个数,而是判断如果下一个数与当前选出的离它最近的数之差是否大于t。 随手写了个测试了一下,核心方法如下,仅供参考: a是总数集合,你需要事先排序,这是一个可以有效减少比较次数的办法 n是a的数量 m是组合数量 b是输出结果 M是m的一个copy 这是c#写的,把输出函数换掉后,应该是几种常用语言通用的了 public void combine(int[] a, int n, int m, int[] b, int M) { int i, j; for (i = n; i >= m; i--) { b[m - 1] = i - 1; if (m > 1) combine(a, i - 1, m - 1, b, M); else { int c = M - 1; for (j = M - 1; j >= 0; j--) if (j == M - 1) Console.Write(a[b[j]]); else if (a[b[j+1]] - a[b[j]] >= t) // 这里就是添加的判断 Console.Write(a[b[j]]); Console.Write("\n"); } } } 而既然你要找出所有符合的组合,计算量基本就确定了,因为C(n,m)这个算法已经有很多人论证过了,楼上所说的那种情况的确会发生,我建议你结合一些算法之外的策略来避免,比如从控制输入上面来辅助,这段代码我没整理的太仔细,输出了一些空组合,但其中所有m个数的组合应该就是你想要的,你可以自己过滤一下
求一个算法:N个数,用其中M个任意组合相加等于一个已知数X.得出这M个数是哪些数.
从一个包含m个数的整型数组中挑出n个数要求这n个数大于等于其他数,其中m>n,m个数各不相同.
求1 java算法 一个数组中m个数(连续的) 需要分成n组 求这n组的所有组合方式
m个数的平均数为A,N个数的平均数为B,P个数的平均数为C.求(M+N+P)个数的平均数是多少?
已知集合M={m∈N|6-m∈N},则集合M中元素的个数是?
已知集合M={x∈N|8-x∈N},则M中元素的个数是( )
matlab求n个数中取m个的全组合.
设计一个计算10个数的平均数的算法
1.满足|mn|+|m-n|=1的整数对(m,n)的个数是?
已知集合M={x|x^2=4},集合N=={x|ax=1},若N真包含于M,则实数a的所有可能的取值的个数是( )个
C++编程帮忙挑挑错用穷举法求最大公约数:穷举法求最大公约数方法为:对两个正整数m和n,从r=n(设n是两个数中较小的数
已知集合M={(x,y)|y=x^2},N={(x,y)|y=2^x},求M∩N的元素个数为