VPF::[С] Найти все суммы элементов массива

AlexSam

Дата 14.1.2007, 15:22 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 84
Регистрация: 24.9.2005

Репутация: нет
Всего: нет

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

Rodman

Дата 14.1.2007, 19:59 (ссылка)

(нет голосов)

Загрузка ...

CIO

Профиль
Группа: Участник
Сообщений: 6144
Регистрация: 7.5.2006
Где: Ukraine ⇛ Kyiv ci ty

Репутация: 26
Всего: 122

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

типа того

Код


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

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

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

???

--------------------

CRM с функцией АвтоОбзвона

Лотереи мира

AlexSam

Дата 15.1.2007, 00:58 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 84
Регистрация: 24.9.2005

Репутация: нет
Всего: нет

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

Код


| 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;
}

Это сообщение отредактировал(а) AlexSam - 15.1.2007, 01:08

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »