Условие: Номер 15

Задача 15. Пусть A - множество из N натуральных чисел. Ваша программа должна определить, существует ли по крайней мере одно подмножество B множества A, имеющие cледующее свойство (*) для любых X,Y,Z из B, X<>Y<>Z<>X, X+Y+Z <=е {t: t из B\{X,Y,Z}}, тут B\{X,Y,Z} означает 'множество B без элементов X,Y и Z'. В случае положительного ответа программа должна найти подмножество B, удовлетворяющее условию (*) и состоящее из максимально возможного числа элементов.

  Решение задачи: Номер 15

Решение задачи 15. Без потери общности предположим, что элементы массива A упорядочены в возрастающем порядке (в множестве нет дублирующихся элементов, поэтому массив A упорядочен именно в возрастающем, а не только в неубывающем порядке). Если это не так, то добавляем в программу подпpогpамму сортировки. Если свойство (*) выполняется для подмножества B, то оно выполняется и для трех наибольших по величине элементов B. Обратно, из выполнимости (*) для трех максимальных элементов B следует выполнимость (*) и для B. Мы будем включать в B в порядке их возрастания элементы из A и проверять для трех максимальных выполнение (*). Программа на Pascal будет выглядеть следующим образом: const m=20; {максимальный размер массива A} var A:array[1..m] of word; {описание массива A} n,s,s3,k,:word; {s -- сумма от 1-ого до i-ого элементов массива A s3 - сумма a(i+1)+a(i+2)+a(i+3) n - размерность массива A k - индекс такого элемента массива A, что для a(1), ... ,a(k) выполняется свойство (*)} begin readln(n); for i:=1 to n do readln(a[i]); k:=0; for i:=1 to n-3 do begin s:=s+a[i]; s3:=a[i+1]+a[i+2]+a[i+3]; if s3<=s then k:=i+3; end; if k=0 then writeln('Решения нет') else for i:=1 to k do write(a[i]); end.

Назад