您的位置：程序门 -> vb -> 基础类

求效率最高的算法！？

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

求效率最高的算法！？[已结贴,结贴人:qiluncjx]

发表于：2007-02-20 22:50:09 楼主

在vb中，从一个数组arr[100]中查找满足条件 abs（（a*c)/（b*d))-p <0.00001（误差范围）的四个元素a,b,c,d，其中变量p由文本框输入的值决定。求效率最高的算法。。请高手指教！！！

发表于：2007-02-20 23:01:431楼得分:0

强调一点：是查找出所有满足条件的四个元素的组合。。。。望高手指教啊！！！

发表于：2007-02-20 23:44:222楼得分:0

好像发现有太多结果了。

发表于：2007-02-20 23:51:283楼得分:0

是啊，我用四个for语句，70个数组元素运行了足足十几分钟啊。。所以上来求助各位大虾啊！！

发表于：2007-02-21 00:02:264楼得分:0

abs 写错位置了吧？那么多的结果
是不是应该这样：
abs（（a*c)/（b*d)-p) <0.00001

发表于：2007-02-21 00:08:085楼得分:0

呵呵，楼上说对了，是写错了。。另外，只要组数中没有重复的数值，那么四个元素之间也应该两两不相等。请大家帮我看看，怎样将算法的复杂度尽可能减小。。。

发表于：2007-02-21 00:26:246楼得分:0

我的初步想法

for a=0 to 99
for b=a+1 to 99
for c=b+1 to 99
for d=c+1 to 99

bb 或者 dd 等于0，不计算（除数不能为0）
四个数相等，不计算

计算、判断

数组中，可能有相同的数，会产生重复的四个数。

发表于：2007-02-21 00:50:497楼得分:0

先排序、过滤重复的，会加快一些。

发表于：2007-02-21 01:09:278楼得分:0

谢谢各位！我的意思不是不允许有重复的数值，而是不允许a,b,c,d四个元素取数组中的同一个数值。例如数组中有20，40，30，60，50，100,120共七个数值，p=0.25,则可以有
a=20,b=40,c=30,d=60
a=20,b=40,c=50,d=100
a=30,b=60,c=50,d=100
a=20,b=40,c=60,d=120
而不允许存在
a=20,b=40,c=20,d=40
a=20,b=20,c=30,d=12
之类的组合存在

发表于：2007-02-21 15:07:399楼得分:0

我的想法是把式子化为（a/c)*（b/d)，则不管怎么样都是两个数相除的结果。所以先计算任意a,b他们a/b的值，把（a,b,a/b)作为结构记录下来，这样需要5000个空间，复杂度on2。然后对a/b值排序。复杂度nlgn n=n2，最后再顺序试探，大概可以把复杂度降到n2lgn。

再进一步优化的话可以把第一步的存储改为哈希表，或类似结构。

发表于：2007-02-21 19:02:1510楼得分:0

楼上说的我看不大懂啊，可能的话给出代码好吗？？多谢了！

发表于：2007-02-21 22:53:2811楼得分:10

public class form1

structure recorditem
dim ratio as double
dim indexa as integer
dim indexb as integer
end structure

private sub form1_load（byval sender as system.object, byval e as system.eventargs) handles mybase.load
dim data（100) as integer
dim records（5050) as recorditem
dim x as integer, y as integer, n as integer
dim value as double

for x = 0 to 99
data（x) = rnd（) * 100 + 1
next x

n = 0
' 程序开始
for x = 0 to 99
for y = x to 99
records（n).ratio = data（x) / data（y)
records（n).indexa = x
records（n).indexb = y
n = n + 1
next y
next x

' 排序
mergesort（records, 0, 5049)

y = -1
n = 0
' 搜索第一对可能值
while y = -1
for x = n to 5049
if records（n).ratio * records（x).ratio > 1 then
y = x
exit while
end if
next x
n = n + 1
end while

' 搜不到的概率很小，万一失败需要倒过来实现

for x = n to 5049
value = records（x).ratio * records（y).ratio - 1
if value < 0 then
y = y + 1
continue for
elseif value < 0.00001 then
msgbox（str（data（records（x).indexa)) + "* " + str（data（records（y).indexa)) + "/ " + str（data（records（x).indexb)) + "/ " + str（data（records（y).indexb)))
else
y = y - 1
if y < x then exit for
end if
next x

end sub

public sub mergesort（byref items（) as recorditem, byval from as integer, byval endto as integer)
dim item as recorditem
dim n as integer, m as integer, k as integer

if endto - from <= 1 then
if items（from).ratio > items（endto).ratio then
item = items（from)
items（from) = items（endto)
items（endto) = item
end if
else
n = from + int（（endto - from) / 2)
' 分治
mergesort（items, from, n)
mergesort（items, n + 1, endto)
m = from
k = n + 1
' 合并
while m <= n and k <= endto
if items（m).ratio > items（k).ratio then
item = items（m)
items（m) = items（k)
items（k) = item
k = k + 1
end if
m = m + 1
end while
end if
end sub
end class

不好意思手边只有vb2005，差得不是很多，自己修改一下语法
没有过滤重复的情况。

瞬间出结果

发表于：2007-02-22 00:32:1112楼得分:0

不好意思我把p看成1了，呵呵~你改一下吧

发表于：2007-02-22 00:43:4813楼得分:0

太感谢了。。。

发表于：2007-02-26 10:44:4514楼得分:0

100 combine 4

http://community.csdn.net/expert/topic/5305/5305770.xml?temp=.6581385

发表于：2007-02-26 14:08:1915楼得分:0

很显然，一看就是在计算挂轮吧！

发表于：2007-02-26 15:25:4816楼得分:0

收了```

发表于：2007-02-26 16:51:1317楼得分:0

mark

发表于：2007-02-27 10:52:0818楼得分:0

是啊，就是计算挂轮的。。

发表于：2007-02-27 22:13:4519楼得分:0

敢问,什么是挂轮?

发表于：2007-02-28 09:02:0820楼得分:0

楼主用百度搜一下“雁山齿轮软件下载”，那个软件是我做的，里面有计算挂轮的模块，看适不适合你！

下一篇：对象变量或 with 块变量没有设置（错误 91）
上一篇：报表分组后如何打印

其他资讯