Thread: C++ Help

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    9

    C++ Help

    I haven't taken a C++ class in over a year and I am asking for some help. I do not want anyone to give me the answer just to walk me through how to answer this.

    Here is the question:

    Design an algorithm for finding the closest 2 numbers in the input list

    so let say I have 5 numbers: 8, 5, 12, 20, and 1. How would I start this? It is supposed to be an unsorted list. I have an idea of how I would do it if the list was sorted, but since its not I do not know where to start. Any help would be greatly appreciated!

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Approach it like a math problem, and you could probably graph it on paper.

    Create a number line and find the smallest difference x.

    Once you do that, you could probably think up a program that does trial and error if not something better.

  3. #3
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    It will be similar in algorithm to how 5 people could all shake hands(ie dude to far left shakes hands with all 4 to the right, dude second from left shakes hands with all 3 to the right, and do on).

    Find the absolute difference between each of the numbers, and remember the smallest difference so far and the two numbers that were subtracted to get that difference.

  4. #4
    printf("Hello Cboard\n"); codeprada's Avatar
    Join Date
    Jan 2011
    Location
    In a little room at the back of your brain
    Posts
    68
    to keep track of the differences you can make an array with size [n - 1] with n being the amount of numbers being tested. so when you calculate 8 - 5, 3 will be the value of the first index and so on until you reach 20 - 1 making 19 being index[3] or the 4th element.
    We shouldn't be quick to criticize unless we can do better.
    Code:
    public function __clone() { die ( "I'm one of a kind" ); }

  5. #5
    Registered User
    Join Date
    Feb 2011
    Posts
    9
    Thank you guys for the replies! I understand how I would do the do the subtraction to get the 2 closest numbers, but the problem I am having is how would I keep track of those numbers? does anyone have an example that I could use to help me out with this problem?

  6. #6
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I'm thinking you would only need an additional pair of variables. Think of it like finding a minimum. The only difference is what you're comparing and what you want to save.

    Quote Originally Posted by codeprada
    to keep track of the differences you can make an array with size [n - 1] with n being the amount of numbers being tested. so when you calculate 8 - 5, 3 will be the value of the first index and so on until you reach 20 - 1 making 19 being index[3] or the 4th element.
    But surely, there could be more than one pair of numbers with a difference of three, and why would you need to save all of the differences, anyway?

  7. #7
    Registered User
    Join Date
    Feb 2011
    Posts
    9

    Unhappy

    Here is what I have so far but if the number is negative then it displays the wrong answer. I know there is probably an easier way to figure this out, but it has been forever since I have worked with C++ and I can not figure it out

    I have the user input 3 numbers:

    Code:
    if (x-y < y-z && x-y < x-z) 
    {
    	cout << "The two closest numbers are: "<< x << " & " << y << endl;
    }
    else if (y-z < x-y && y-z < x-z)
    {
        cout << "The two closest numbers are: "<< y << " & " << z << endl;
    }
    else if (x-z < x-y && x-z < y-z)
    {
    	cout << "The two closest numbers are: "<< x << " & " << z << endl;
    }
    I guess my question is, is there some sort of loop I can do here or a different way to subtract the numbers( 10-6 instead of 6-10)?

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Use the absolute value function.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It is unclear what the result from data like 5, 2, 6, 8 would be. Is the smallest 8 - 6 (next to each other) or (6 - 5). If the latter, you could just sort the data and do it exactly the same way you'd do it if it was the first.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered User
    Join Date
    Feb 2011
    Posts
    9

    Smile Thanks everyone

    Thank you everyone for all the help! I have never been to a forum where people were so quick to respond and I really appreciate it!

Popular pages Recent additions subscribe to a feed