Драгоценные камни (Stone pile 1005).

You have a number of stones with known weights W1…Wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Исходные данные.

Input contains the number of stones N (1 ≤ N ≤ 20) and weights of the stones W1…Wn (1 ≤ Wi ≤ 100000) delimited by white space (either space characters or new lines).

Результат.

Your program should output a number representing the minimal possible weight difference between stone piles.

Вольный перевод: нужно поделить камни на две кучи с минимальной разницей весов.

Идея алгоритма, который часто предлагают школьники: считываем числа в массив, сортируем его, по одному большому камню кладем в кучи. Просматриваем остальные камни и кладем очередной камень в ту кучу, в которой в этот момент вес камней меньше. Пишем программу, тестируем.

Var a: array[1..20] of integer;

n,i,j,k:integer;

Begin

Readln(n);

For i:=1 to n do readln(a[i]);

For i:=n-1 downto 1 do

For j:=1 to i do

If a[j]>a[j+1] then Begin

    k:=a[j];

    a[j]:=a[j+1];

    a[j+1]:=k;

End;

j:=0;

k:=0;

For i:=n downto 1 do

If j<k then j:=j+a[i] else k:=k+a[i];

Write(abs(j-k));

Readln

End.

Протестируйте программу, меняя число и веса камней. Все ваши тесты проходят?

Придумайте тесты, которые «не пройдут». Не придумали?

Вот один из них: 5 камней (8, 7, 6, 4, 3). Результат программы 2. Суммы 8+4+3=15 и 7+6=13, разница 2. А правильный результат: 8+6=14 и 7+4+3=14, разница и соответственно ответ 0.

Ниже приведено решение Павла Семушина (Самарский лицей информационных технологий) методом динамического программирования. Возможно только с целыми весами камней. Для вещественных весов пришлось бы делать полный перебор. Размер вспомогательного массива определяется значениями весов камней (современные компиляторы допускают такие размеры массивов).

Var

  a: array[1..20] of integer;

  b: array[0..100000] of integer;

{допустимый размер для компилятора на сайте}

  n, i, j, k, s: integer;

Begin

Readln(n);

  s:=0;

  For i:=1 to n do Begin

   Readln(a[i]);

   s:=s+a[i];

End;

  k:=s div 2;

  For i:=k downto 0 do

  If i>=a[1] then b[i]:=a[1] else b[i]:=0;

  For i:=2 to n do

  For j:=k downto 1 do

    If (j>=a[i]) and (a[i]+b[j-a[i]]>b[j]) then b[j]:=a[i]+b[j-a[i]];

  Write(abs(s-2*b[k]));

End.

Протестируйте эту программу. Теперь даже ваши самые «трудные» тесты пройдут!

Процедуры и функции.

Как написать хорошую программу.

Пока вы дочитали до этого раздела, вам встретились и процедуры и функции, в том числе и рекурсивные. Вам пришлось заглядывать в рекомендованную литературу? Или было все понятно?

Не приводя подробного описания процедур и функций, обращаем ваше внимание на следующие моменты:

§ Процедура или функция определяет некоторый законченный блок действий;

§ Каждая процедура или функция должна иметь одну точку входа и одну точку выхода;

§ Взаимодействие с вызывающей программой должно, по возможности, осуществляться только через параметры.

§ Создание таких блоков существенно облегчает задачу программирования и отладки, вы можете каждый из них проверить отдельно, а затем соединить их в правильной последовательности.

Рекурсивные процедуры

Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и дает более короткий текст программы, но при выполнении может вызвать переполнение стека. Подробное описание и много замечательных примеров вы найдете в работе[2]. Ограничимся несколькими полезными примерами [2].

N- ая степень числа

Function p(x, n:integer): longint;

Begin

  If n=0 then p:=1 else p:=x*p (x, n-1)+1;

End;

Begin

Writeln (p (2, 8));

End.

Перевод десятичного числа в двоичную систему

Заменив делитель 2 на другой (<10), получим перевод в любую другую систему счисления с основанием меньшим 10.

Procedure Rec (n: integer);

Begin

If n > 1 then rec (n div 2);

 Write (n mod 2);

End;

Begin

Rec (25);

End.

N-ое число Фибоначчи

Числа Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21,…Первые два числа 1, 1. Каждое следующее число равно сумме двух предыдущих.

Function f (n:integer):integer;

Begin

If n<=2 then f:=1

else f:=f(n-1) + f(n-2);

End;

Begin

Write(f(11));

Readln

End.