求效率最高的算法!?
在VB中,从一个数组arr[100]中查找满足条件 Abs((a*c)/(b*d))-p <0.00001(误差范围)的四个元素a,b,c,d,其中变量p由文本框输入的值决定。求效率最高的算法。。请高手指教!!!
[解决办法]
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,差得不是很多,自己修改一下语法
没有过滤重复的情况。
瞬间出结果