Задача 10a. Дадени са
камъни с тегла x1,
x2,
x3,..., xn
- цели числа. Напишете
програма, която ще ги подреди в две купчини, така че разликата в
тежестите на купчините да е минимална.
Вход:
Първи ред - числото n (1 <
n < 20). Следват n числа (от 1 до 10000), разделени
с интервал. Входът съдържа много примери, наредени един след друг.
Изход:
За всеки пример от входа се извежда едно число - минималната възможна
разлика в теглата на двете купчини.
Примерен вход:
5
5 8 13 27 14
4
2 3 2 3
Решение:
3
0
Задача 10b. Числа на Фибоначи
Да се напише програма за
пресмятане на n-тото
число на Фибоначи със запомняне
на вече пресметнати стойности и използване на формулата:
F(n) = F2(n/2)
+ F2(n/2
- 1), за n четно; F(n) = F(n - 1)
+ F(n -
2),
за n нечетно.
Да се намери най-голямото n,
за което написаната програма пресмята вярно F(n).
(Логаритмична сложност.)