Пожалуйста помогите разобраться с задачей!

← →
terdaw (2006-03-26 16:42) [0]

Пожалуйста помогите разобраться с задачей! В первой строке дано число D, во второй строке записаны 4 натуральных числа 0 < K1 < K2 < K3 < K4 <= 15000. Нужно узнать сколькими способами можно получить число D, складывая или вычитая эти числа.
пример:
400
100 300 700 1500

ответ: 3

← →
Palladin © (2006-03-26 16:53) [1]

перебором например

← →
TUser © (2006-03-27 09:11) [2]

Бесконечным количеством способов. При такой постановке задачи.

Если же оговорить, что каждое число можно использовать только один раз, - тогда задача решается так.
Числа из второй строкизапишем в массив A[0..n-1]. Для каждой префиксной подпоследовательности (т.е. 0-0, 0-1, ..., 0-n-1) будем хранить список чисел, которые из них можно получить, и число способов, которыми можно получить такое число. Для подпоследовательности 0-0 такой список очевиден. Для каждой последующей его легко получить из списка для предыдущей. В конце ты получаешь список всех чисел, которые могут быть получены из данной последовательности, и указано по скольку раз. Требуется найти число из первой строчки.

← →
TUser © (2006-03-27 09:15) [3]

Опс, не заметил. Думал, что может быть произвольное кол-во чисел. А так - перебором, с учетом оговорки из [2].

← →
terdaw (2006-03-27 14:11) [4]

Ну помогите же решить задачу!!! Нужно делать перебором, а как это перебором? Объясните пожалуйста!
Ещё раз задача:
В первой строке дано число D, во второй строке записаны 4 натуральных числа 0 < K1 < K2 < K3 < K4 <= 15000. Нужно узнать сколькими способами можно получить число D, складывая или вычитая эти числа.
пример:
400
100 300 700 1500

ответ: 3

← →
terdaw (2006-03-27 14:13) [5]

ой.. не туда написал

← →
oldman © (2006-03-27 17:14) [6]

четыре числа: a, b, c, d
a+b+c+d
a+b+c-d
a+b-c+d
a+b-c-d
a-b+c+d
a-b+c-d
a-b-c-d
-a+b+c+d
-a+b+c-d
-a+b-c+d
-a+b-c-d
-a-b+c+d
-a-b+c-d
-a-b-c-d

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

← →
oldman © (2006-03-27 17:24) [7]

В условии забыто "каждое число используется только один раз" !!!
А то 300+700+300-100-100-100-100-100-100-100-100-100 тоже =400
:))))))))))

← →
Lamer@fools.ua © (2006-03-27 17:26) [8]

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

А должно быть 16.

забыл

a-b-c+d
-a-b-c+d

> Ну помогите же решить задачу!!! Нужно делать перебором,
> а как это перебором? Объясните пожалуйста!

Не орех. конечно, но тоже попахивает...
Вам не надоело решать задачки 9-го класса предмет "Инфолрматика"???

Может еще быть, что допускается использовать не все числа. Тогда результатов будет 3^4 = 81.

← →
terdaw (2006-03-27 20:12) [12]

да! так и надо!

Пожалуйста помогите разобраться с задачей! Найти похожие ветки