By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
431,965 Members | 2,043 Online
Bytes IT Community
+ 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
Share this Question
Share on Google+
3 Replies


Tig201
100+
P: 103
This is a rough idea but hopefully it will help
Expand|Select|Wrap|Line Numbers
  1. Private Sub Form_Load()
  2.   Dim lst(6) As Integer, Cnt1 As Integer, Cnt2 As Integer
  3.   Dim No As Integer, NoNew As Integer
  4.  
  5.   No = 16
  6.   lst(1) = 2
  7.   lst(2) = 5
  8.   lst(3) = 7
  9.   lst(4) = 9
  10.   lst(5) = 13
  11.   lst(6) = 15
  12.  
  13.   For Cnt1 = 1 To UBound(lst) Step 1
  14.     NoNew = No - lst(Cnt1)
  15.     For Cnt2 = Cnt1 + 1 To UBound(lst) Step 1
  16.       If NoNew = lst(Cnt2) Then
  17.         MsgBox (lst(Cnt1) & "+" & lst(Cnt2) & "=" & No)
  18.         Cnt2 = UBound(lst)
  19.         Cnt1 = UBound(lst)
  20.       End If
  21.     Next Cnt2
  22.   Next Cnt1
  23. End Sub
  24.  
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

Post your reply

Sign in to post your reply or Sign up for a free account.