Задача на паскале: Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна.

[Rhc]

Сообщение от Аватар

Количество способов разбивки С(1,n)+C(2,n)+..+C(n mod 2,n). Если и ошибся, то думаю не кардинально. Здесь C(i,n)=n!/((n-i)!*i!). А теперь представте 100 предметов и C(50,100)=100!/(50!*50!). 100! это число примерно со 158 цифрами. Сколько лет потребуется компьютеру для расчета всех способов разбивки? (или вернее миллионов лет)

(50,100)=100!/(50!*50!)
это
100891344545564193334812497256 случаев.
Я не думаю, что дольше 30 секунд должно считать...
Точнее не так :-D Максимальное время за которое должно высчитывать - 30 секунд.

Код первой косячной программы:

uses crt;
  var a: array[1..101] of integer;
  i,N,sum1,sum2,raz: integer;
  f: boolean;
  c: integer;


begin
clrscr;
Readln (N);

For i:=1 to N do begin
Read (a[i]);
end;

repeat
  f:=false;
  for i:=1 to N-1 do
  begin
    if a[i]>a[i+1] then
    begin
      f:=true;
      c:=a[i];a[i]:=a[i+1];a[i+1]:=c;
    end;
  end;
until not f;

For i:=1 to N do begin
If (i div 2)=0 then
sum2:=sum2+a[i]
else
sum1:=sum1+a[i];
end;

raz:=abs(sum2-sum1);

WriteLn (raz);

Readln (N);
end.

[Poma][a]

Я не думаю, что дольше 30 секунд должно считать...

Вы не правы... На более-менее мощной машине мы можем сделать около 20-50 млн. операций за секунду.. Так что тут будет огромное время..

[Rhc]

Сообщение от Poma][a

Вы не правы... На более-менее мощной машине мы можем сделать около 20-50 млн. операций за секунду.. Так что тут будет огромное время..

А если программа отправляется на сервер и в условии сказано, что не более 30 секунд?)

[Poma][a]

Аватар разговариает про общую формулу..
У Вас всё гораздо прозаичнее..
у Вас N предметов..
Каждый может быть или в 1-ой или во 2-ой группе
Всего 2^N вариантов.. (кажется)..

[Rhc]

Сообщение от Poma][a

Аватар разговариает про общую формулу..
У Вас всё гораздо прозаичнее..
у Вас N предметов..
Каждый может быть или в 1-ой или во 2-ой группе
Всего 2^N вариантов.. (кажется)..

Нет, он прав.
У нас 100 элементов (Берём максимум, чтоб понимать с чем имеем дело),
а второй массив, в который буду влетать возможные варианты - 50.
Чтобы подсчитать количество возможных случаев используется формула:

C(i,n)=n!/((n-i)!*i!)

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

[Аватар]

Всего 2^N вариантов.. (кажется)..

Вот именно, что кажется. Думаю что не так.
В группе 1 предмет - С(1,n)
В группе 2 предмета - С(2,n)
...
В группе n div 2 предметов - С(n div 2,n)

[Rhc]

Ну ладно, разобрались. Как теперь сделать код для такого
перебора?

[Poma][a]

Вот именно, что кажется. Думаю что не так.
В группе 1 предмет - С(1,n)
В группе 2 предмета - С(2,n)
...
В группе n div 2 предметов - С(n div 2,n)

Причем тут сочетания?
Да мы можем выбрать 2 предмета из N С(2, n) способами
Но причем это тут?

Ладно..
Не проверял..

uses Math;

var
	a : array [1..100] of Integer;
	n, m : Integer;
procedure P(k, s1, s2 : Integer);
begin
	if k = n+1 then begin
		m := Min(m, Abs(s1-s2));
		Exit
	end;
		
	P(k+1, s1+a[k], s2);
	P(k+1, s1, s2+a[k])
end;

var
	i : Integer;
	
begin
	ReadLn(n);
	m := MaxInt;
	for i := 1 to n do
		Read(a[i]);
		
	P(1, 0, 0);
	WriteLn(m)
end.

[Rhc]

Сообщение от Poma][a

Причем тут сочетания?
Да мы можем выбрать 2 предмета из N С(2, n) способами
Но причем это тут?

Ладно..
Не проверял..

uses Math;

var
	a : array [1..100] of Integer;
	n, m : Integer;
procedure P(k, s1, s2 : Integer);
begin
	if k = n+1 then begin
		m := Min(m, Abs(s1-s2));
		Exit
	end;
		
	P(k+1, s1+a[k], s2);
	P(k+1, s1, s2+a[k])
end;

var
	i : Integer;
	
begin
	ReadLn(n);
	m := MaxInt;
	for i := 1 to n do
		Read(a[i]);
		
	P(1, 0, 0);
	WriteLn(m)
end.

Ничего себе, работает! А можно комментарии к ней?

[Poma][a]

Ничего себе, работает! А можно комментарии к ней?

Неа............