2

Помогите с алгоритмом для программы

Есть массив из n чисел, необходимо создать новый массив, в котором будут выведены все суммы исходного массива.

Например:

На вход:

3
2 3 5

На выход:

2 3 5 5 7 8 10

На вход:

4 
6 7 2 10

На выход:

6 7 2 10 13 8 16 9 17 12 15 23 19 25

Понимаю, что нужно использовать рекурсию, но не знаю, как это сделать

2
  • 1
    Генерируете все выборки длинной от 1 до n из элементов массива, считаете сумму каждой выборки, заносите в массив. 3 июн 2018 в 10:22
  • @VTT как сгенерировать все выборки?
    – user272403
    3 июн 2018 в 14:59

3 ответа 3

1

Один из возможных классических подходов перебора - это использование рекурсии. Вот код, который рекурсивно считает суммы всех возможных комбинаций массива

#include <iostream>
#include <vector>

int sum(std::vector<int>& result, const std::vector<int>& v, int index, int curSum)
{
    if (index < v.size())
    {
        curSum += v[index];
        for (int i = index + 1; i < v.size(); ++i)
        {
            int res = sum(result, v, i, curSum);
            result.push_back(res);
        }
    }
    return curSum;
}

int main()
{
    std::vector<int> v = { 6, 7, 2, 10 };

    std::vector<int> result;

    for (int i = 0; i < v.size(); ++i)
    {
        int res = sum(result, v, i, 0);
        result.push_back(res);
    }

    for (const int s : result)
        std::cout << s << " ";

    std::cout << std::endl;
}

На выходе имеем:

25 15 23 13 18 8 16 6 19 9 17 7 12 2 10

1
  • господин минусующий, будьте добры озвучить свои доводы. 4 июн 2018 в 13:37
0

Выписка возможных выборок имеет сложность экспоненциальную O(2^N). Можно представлять конкретную выборку как массив логических значений true/false. Например как std::vector<bool>. Перебор возможных выборок с помощью рекурсии нагружает стек лишней информацией. Можно перебирать все выборки с помощью собственной процедуры инкремента {0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}. Те , кто дружит с языком C не любят вектора. Они пользуются массивом unsigned int m[(N / (sizeof(unsigned int)*8))+1]. Если аккуратно написать инкремент данного вектора, это даст максимальную скорость.

1
  • Максимальную скорость дас код Грея - не надо будет много считать, только один элемент прибавить или отнять.
    – Mikhajlo
    2 окт 2018 в 18:19
0

Решала подобную задачу реальную для бухгалтерии в Excel. Был список работников с суммами к выдаче зп. Зп была выдана по нескольким ведомостям. От ведомостей остались только итоговые суммы. Нужно было распределить работников по нескольким ведомостям. Вручную это никому в отделе не удалось сделать. Решила в Excel с помощью нулей и единиц. Нечто подобное тому, что на картинке ниже. Кстати автор вопроса забыл в промежуточных суммах указать 18

Удобно эту задачу решать в Excel, вот пример

1
  • Это вообще как к вопросу относится?
    – Qwertiy
    30 апр 2019 в 19:16

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.