Math problem

[ETAkoG1T]

I need help with finding a way to get the 2 numbers with the highest sum out of 3 values.
Example:
the numbers 9 4 7
It is easy to see that 9 + 7 is the largest sum but how do I do this with a loop?

Preferably an algorithm that works with larger numbers. I am able to do it manually with 3 numbers but with larger numbers it is really inconvenient and I want to be able to solve some bigger problems.

[coder777]

simply sort the numbers and add the two highest

[ETAkoG1T]

That makes sense. Do you know any sorting algorithms without using one of the libraries?

[coder777]

there are plenty of algorithms:

http://en.wikipedia.org/wiki/Sorting_algorithm

[3qX21hU5]

Preferably an algorithm that works with larger numbers. I am able to do it manually with 3 numbers but with larger numbers it is really inconvenient and I want to be able to solve some bigger problems.

3 Numbers you will have no problem with having a efficient sort algorithm, but depending on how large of numbers you are dealing with you might have to use a large number library.


Also you could always use std::sort() in the algorithm header but if you want/need to make your own function you can look into a bubblesort which should work just fine since you are only using 3 numbers.



Or even simpler just create a loop that checks which 2 numbers are the highest.

[Duthomhas]

For really large numbers:

Given two strings of digits representing numbers, like "12345", the larger number will be one of:

1) longer

2) the same length where the first different digit is larger

Examples:

"12345" > "123" (because the first is longer)

"4719" > "4709" (because the first different digit is larger -- '1' > '0')


To add the numbers, you only need to carry a single digit, just like in grade-school math. (Start at the ends of the strings, though.)

Good luck!

[keskiverto]

So, for a more generalized problem there is a list with N elements, and you want to use M largest ones.

Sorting is one method, but if M is tiny or very close to N, then it might be more efficient to find the largest ones or remove the smallest ones, respectively.

[dreyan]

So, for a more generalized problem there is a list with N elements, and you want to use M largest ones.

Sorting is one method, but if M is tiny or very close to N, then it might be more efficient to find the largest ones or remove the smallest ones, respectively.

Clearly if he is unable to do this on his own then efficiency isn't something he should be worrying about.


Sort the numbers with a sorting algorithm of your choice and add the two largest.

[MiiNiPaa]

dreyan wrote:

sorting algorithm of your choice

I recommend Bogosort!

[JLBorges]

> So, for a more generalized problem there is a list with N elements, and you want to use M largest ones.

The standard way to do this is:

Use a linear time selection algorithm ( the quick select algorithm or the median of medians algorithm) of to select the M^th largest - (N-M)^th smallest - element. And then partition the sequence with this as the pivot.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

[MiiNiPaa]

JLBorges wrote:

Use a linear time selection algorithm ( the quick select algorithm or the median of medians algorithm) of to select the Mth largest - (N-M)th smallest - element. And then partition the sequence with this as the pivot.

In C++ you can use nth_element(): http://en.cppreference.com/w/cpp/algorithm/nth_element

[JLBorges]

> In C++ you can use nth_element()

Yes. The usual implementation is a quick select.
Followed by std::partition()

[MiiNiPaa]

JLBorges wrote:

Followed by std::partition()

If he needs only to sum largest/smallest numbers, he does not need partition.

Partially sorts the range [first, last) in ascending order so that all elements in the range [first, nth) are less than those in the range [nth, last).
Complexity
Linear in std::distance(first, last) on average.

[JLBorges]

> he does not need partition.

Right. Thanks.