Задачи за тренинг
Задача 10а. [8.2.2]
Трима братя наследили N парцела земя с лица S1,
S2,…, SN,
съответно, и решили да си ги поделят по братски. Помогнете им да
направят това по най-справедливия начин. Критерий за справедливост е
стойността на функцията |x1 - x2|
+ |x1 - x3|
+ |x2 - x3 |,
където x1, x2 и x3
са сумите от площите на парцелте на тримата братя.
Вход:
На входа се задава числото N,
(1 < N < 100) - брой на парцелите земя и още N числа - лицата на парчетата
Si < 100, цели числа. Входът съдържа много примери.
Изход:
За всеки пример на нов ред се отпечатват 3 числа като ненарастваща
редица - получената земя на всеки от братята .
Пример:
3
1 1 1
7
4 1 1 1 2 2 9
Решение на примера:
1 1 1
9 6 5
Идея за решение: Давате на първия брат някакво
подмножество от парцели (пълно изчерпване) и останалите парцели
разделяте на две по алгоритъма за Братска подялба
[8.2.2].
За втория пример разделянето е 9, 2+2+1+1=6, 4+1=5.
Задача
10b. [8.2.7] lns3.c
Да
се напише програма за намиране на най-дългата ненамаляваща
подредица.
Вход:
На входа се задава числото n
- брой на елемнтите на
редицата и след това стойностите на самите елементи - цели
числа в интервала [-10, 105]. Входът съдържа много
примери.
Изход:
За всеки пример на отделен ред се отпечатва цяло число - дължината
на най-дългата ненамаляваща подредица.
Пример:
6
6 6 6 2 2 7
6
1 1 1 1 1 2
15
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
3
4 3 2
Решение на примера:
4
6
8
1
Редиците са: 6 6 6 7;
1 1 1 1 1 2; 1 2 2 2 2 2
2 2 (има и друга); 4.