Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [С] Найти все суммы элементов массива

Автор: AlexSam 14.1.2007, 15:22

Добрый день. Застрял на такой вот задаче. Надо в массиве чисел перебрать все возможные суммы его элементов (ну и если сумма равна некоторому числу , то вывести номера элементов составляющих данную сумму). Помогите пожалуйста.

Автор: Rodman 14.1.2007, 19:59

давай уточним...

типа того

Код


сумма равна 555
из 1+6+9
из 6+10
из 8+9

сумма равна 559
из 1+6+7
из 6+11
из 8+19

а то какое то скользкое задание...

???

Автор: AlexSam 15.1.2007, 00:58

Прости, я что-то не совсем догнал. Ну например есть массив с элементами :

Код


| 1 | 2 | 3 | 4 | 5 |

и надо собрать сумму равную 7 , то надо чтобы вернуло номера чисел 1,2,4 так как их сумма дает 7 (ну или номера чисел 2 и 5 по аналогичной причине)

Добавлено @ 01:05
Да господа, только не смейтесь- нашел маленький код который работает как надо, но хоть убейте не понимаю алгоритма smile

Код


int main()
{
    int num[] = {4,3,2,1,0};//исходный массив
    const int n = 8;
    const int m = 7;//искомая сумма

        int way[8];
    for (int i = 0; i <= m; ++i)
        way[i] = 0;

    way[0] = 1;

    for (int i = 0; i < n; ++i)
        for (int j = m; j > 0; --j)
            if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
                way[j] = num[i];

    if (!way[m])
        printf("No body!\n");
    else
    {
        printf("Ok, this is :\n");
        for (int i = m; i != 0; i -= way[i])
            printf("\t%d\n", way[i]);
    }

    delete[] way;
        getch();
    return 0;
}