Recursion with for loop

[VladasX]

I was given a task to find the biggest number by this formula:
number = (smallest_number / sum_of numbers) * 100
The difficulty is that the amount of numbers used in sum is specified and is different from total amount of numbers.
For example:
There are 5 numbers and the sum uses only 2 numbers.
The numbers are:
300
500
100
150
800
The result should be: 40.00
Because (100 / (100 + 150)) * 100 = 40

I thought of using recursions, but the problem is I get an answer 0 everytime I compile my code (maybe because several functions return different numbers back).

void Recursion (int total, int needed, int numbers[], double &result, 
double temp, int start, int cycle, int order[])
{
    if (needed != 0) order[needed - 1] = numbers[start];
    else if (needed == 0)
    {
        double smallest = 1000, sum = 0;
        for (int i = 0; i < needed; i++)
        {
            if (numbers[order[i]] < smallest) smallest = numbers[order[i]];
            sum += numbers[order[i]];
        }
        temp = (smallest / sum) * 100;
        if (temp > result) result = temp;
    }
    else for (int i = start; i < cycle; i++)
        Recursion(total,needed - 1,numbers,result,temp,i + 1,cycle,order);
}

[TheIdeasMan]

I was given a task to find the biggest number by this formula:
number = (smallest_number / sum_of numbers) * 100

I am confused by this, with the numbers you give the answer is 0.185? How is this related to finding the largest number?

The difficulty is that the amount of numbers used in sum is specified and is different from total amount of numbers.
For example:
There are 5 numbers and the sum uses only 2 numbers.

Which two numbers? The smallest ones? How is that related to finding the largest number?

If you can find the smallest number, you can just as easily find the largest one.

Why do you think recursion will help here?

Because (100 / 100 + 150) * 100 = 40

Maybe you meant (100 / (100 + 150)) * 100 = 40 ?

The way you have it now is equal to 15100 because of BEDMAS.

When finding the smallest number, initially set smallest to the first number in the array, not to some arbitrarily large value.

So I am rather confused about the methodology. When we get that sorted, then you could please provide a minimally working program that shows the problem. That is a program with a main() and a call to you function, something we can compile and run with cpp.sh using the gear icon at the top right of the code snippet.

[VladasX]

Maybe you meant (100 / (100 + 150)) * 100 = 40 ?

Yes.

Which two numbers? The smallest ones? How is that related to finding the largest number?

Any 2 numbers from the given list. So it could be 300 and 800 or 500 and 150.
This is related because by formula if we take 300 and 800:
(300 / (300 + 800)) * 100 = 27.27
And if we take 500 and 150:
(150 / (500 + 150)) * 100 = 23.07

When finding the smallest number, initially set smallest to the first number in the array, not to some arbitrarily large value.

Because the numbers in the tests won't be larger than 1000.

When we get that sorted, then you could please provide a minimally working program that shows the problem.

#include <iostream>

using namespace std;

void Recursion (int total, int needed, int numbers[], double &result,
double temp, int start, int cycle, int order[]);

int main()
{
    int total = 5;
    int needed = 2;
    int numbers[5] = {300, 500, 100, 150, 800};
    double result = 0;
    double temp;
    int start = 0;
    int cycle = total - needed + 1;
    int order[2];
    Recursion(total,needed,numbers,result,temp,start,cycle,order);
    cout << result;
    return 0;
}

void Recursion (int total, int needed, int numbers[], double &result,
double temp, int start, int cycle, int order[])
{
    if (needed != 0) order[needed - 1] = numbers[start];
    else if (needed == 0)
    {
        double smallest = 1000, sum = 0;
        for (int i = 0; i < needed; i++)
        {
            if (numbers[order[i]] < smallest) smallest = numbers[order[i]];
            sum += numbers[order[i]];
        }
        temp = (smallest / sum) * 100;
        if (temp > result) result = temp;
    }
    else for (int i = start; i < cycle; i++)
        Recursion(total,needed - 1,numbers,result,temp,i + 1,cycle,order);
}

[dhayden]

Recognize that this is a combinatorics problem. Given N numbers and some value 1<=K<=N, you need to find all combinations of K numbers and chose the minimum value of the formula.

So if you can figure out how to find the combinations, you're pretty much home free.

[VladasX]

I know that, but I can't figure it out.

[TheIdeasMan]

It seems I am the odd one out here, but I still don't get how this works. Maybe you could post a link to the actual question verbatim? I know it's just for my benefit, apologies :+)

What I don't understand:

I was given a task to find the biggest number by this formula:
number = (smallest_number / sum_of numbers) * 100

Any 2 numbers from the given list. So it could be 300 and 800 or 500 and 150.
This is related because by formula if we take 300 and 800:
(300 / (300 + 800)) * 100 = 27.27
And if we take 500 and 150:
(150 / (500 + 150)) * 100 = 23.07

How are the values of 27.27 and 23.07 related to the largest value of 800?

The biggest number of what? The whole array; any N numbers; the largest sum of N numbers?

In my mind "The biggest number" could be construed as being a bit vague.

dhayden mentioned combinations and a minimum value, forgive me for being dense, but how is that related to a biggest number?

Because the numbers in the tests won't be larger than 1000.

And if that number changes, you have to change your code. Better to have a Smallest function that does what it says, and not have to alter your code, and you can avoid a magic number :+)

Regards

[jgg2002]

Is it necessary that you must do this with recursion?

[dhayden]

dhayden mentioned combinations and a minimum value, forgive me for being dense, but how is that related to a biggest number?

The problem statement is to find the largest of (smallest_number / sum_of numbers) * 100
But I may misunderstand the problem statement. Let me describe what I think it is:

You are given a set NUM of N numbers and some smaller value K.

Let S be a subset of K numbers from the set NUM.  You can compute
X = min(S) / sum(S) * 100.
In other words X is the minimum value in S, divided by the sum of all values in S, times 100.

Find the maximum value of X, considering all possible subsets S.

The thing that seems odd to me is that iterating over the combinations of a set is not a beginner project. So it makes me think that I'm missing something here.

I agree with TheIdeasMan. Please post the exact text of the assignment (or a translation if it isn't in English).