Радиотелескоп пытается получать и анализировать сигналы из космоса. Различные шумы переводятся в последовательность вещественных неотрицательных чисел, заданных с точностью до 1 знака после десятичной точки. При анализе этих данных потребовалось выбрать такое непустое подмножество сигналов (в него может войти как один сигнал, так и все), произведение значений которого будет максимальным. Определите, какие сигналы войдут в это подмножество. На паскале напишите.
program RadioTelescope; const maxN = 1000; // максимальное количество сигналов Eps = 1e-9; // погрешность вычислений var n, i, j: integer; signals: array[1..maxN] of real; dp: array[1..maxN] of real; chosenSignals: array[1..maxN] of boolean; function Max(a, b: real): real; begin if a > b then Max := a else Max := b; end; begin // Ввод количества сигналов readln(n); // Ввод сигналов for i := 1 to n do readln(signals[i]); // Инициализация массива dp dp[1] := signals[1]; chosenSignals[1] := true; // Вычисление подмножества с максимальным произведением значений for i := 2 to n do begin dp[i] := signals[i]; chosenSignals[i] := true; for j := 1 to i - 1 do begin if (dp[j] * signals[i] > dp[i]) and (dp[j] * signals[i] - dp[i] > Eps) then begin dp[i] := dp[j] * signals[i]; chosenSignals[i] := true; end; end; end; // Вывод результирующего подмножества for i := 1 to n do if chosenSignals[i] then writeln(signals[i]:0:1); end.
Программа на Паскале:
program RadioTelescope;const
maxN = 1000; // максимальное количество сигналов
Eps = 1e-9; // погрешность вычислений
var
n, i, j: integer;
signals: array[1..maxN] of real;
dp: array[1..maxN] of real;
chosenSignals: array[1..maxN] of boolean;
function Max(a, b: real): real;
begin
if a > b then
Max := a
else
Max := b;
end;
begin
// Ввод количества сигналов
readln(n);
// Ввод сигналов
for i := 1 to n do
readln(signals[i]);
// Инициализация массива dp
dp[1] := signals[1];
chosenSignals[1] := true;
// Вычисление подмножества с максимальным произведением значений
for i := 2 to n do
begin
dp[i] := signals[i];
chosenSignals[i] := true;
for j := 1 to i - 1 do
begin
if (dp[j] * signals[i] > dp[i]) and (dp[j] * signals[i] - dp[i] > Eps) then
begin
dp[i] := dp[j] * signals[i];
chosenSignals[i] := true;
end;
end;
end;
// Вывод результирующего подмножества
for i := 1 to n do
if chosenSignals[i] then
writeln(signals[i]:0:1);
end.