431,965 Members | 2,043 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 431,965 IT Pros & Developers. It's quick & easy.

# efficient algorithm

 P: 13 Hey I'm looking for a solution to the belowe question. Any recommendations on how to write this algorithm??? Thanks: You are given a sequence s of numbers, in increasing order, for example: s = 2, 5, 7, 9, 13, 15. You are also given a number n, say n = 16. You have to try to find two numbers x and y from s, such that x+y = n, if such numbers exist. In this example, you could take x = 7 and y = 9. However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this. Apr 18 '07 #1
3 Replies

 100+ P: 103 This is a rough idea but hopefully it will help Expand|Select|Wrap|Line Numbers Private Sub Form_Load()   Dim lst(6) As Integer, Cnt1 As Integer, Cnt2 As Integer   Dim No As Integer, NoNew As Integer     No = 16   lst(1) = 2   lst(2) = 5   lst(3) = 7   lst(4) = 9   lst(5) = 13   lst(6) = 15     For Cnt1 = 1 To UBound(lst) Step 1     NoNew = No - lst(Cnt1)     For Cnt2 = Cnt1 + 1 To UBound(lst) Step 1       If NoNew = lst(Cnt2) Then         MsgBox (lst(Cnt1) & "+" & lst(Cnt2) & "=" & No)         Cnt2 = UBound(lst)         Cnt1 = UBound(lst)       End If     Next Cnt2   Next Cnt1 End Sub   The idea is that you could eliminate the numbers as you go through the list Apr 18 '07 #2

 Expert 5K+ P: 8,434 However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this. I don't think this is possible, unless you add the further constraint that the numbers must be next to each other in the list. (Of course, I'm no mathematician.) Unless you get sneaky and use subtraction instead of addition, but I doubt that's acceptable. Apr 19 '07 #3

 Expert 5K+ P: 8,434 This is a rough idea but hopefully it will help ... Hm... neat little routine. I like it! :) Apr 19 '07 #4 