Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.12.2006, 11:23
незарегистрированный

 
Сообщений: n/a

помогите!
здравствуйте! простите меня за мою наглость, но не могли бы вы написать алгоритм решющий задачу:«максимальный результат»
задано алгебраическое выражение, состоящее из неотрицательных вещественных чисел и знаков операций +, - и *. необходимо расставить в этом выражении скобки так, чтобы его значение стало максимально возможным.
требуется написать программу для решения поставленной задачи.
технические требования:
входной файл Input.txt:
выходной файл Output.txt:
ограничение времени:10 секунд.
формат входных данных:
в первой строке входного файла Input.txt записано исходное выражение длиной не более 250 символов. внутри чисел пробелы не допускаются. выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 106.
формат выходных данных.
выходной файл Output.txt должен содержать две строки. в первой строке должно находиться максимально возможное после расстановки скобок значение полученного выражения, а во второй строке – само это выражение. если вариантов решения задачи несколько, нужно выдать любой из них.
пример файла входных дачных:
1 + 2 – 3.0 * 4
пример файла выходных данных
0
((1 + 2) – 3.0) * 4
  #2  
Старый 05.12.2006, 12:05
Новичок

Отправить личное сообщение для Dummy Посмотреть профиль Найти все сообщения от Dummy
 
Регистрация: 01.12.2006
Сообщений: 3

синтаксический разбор + динамическое программирование
  #3  
Старый 25.04.2007, 15:22
незарегистрированный

 
Сообщений: n/a

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}

type extended = double;
const nmax=50;
max:extended=1.7e300;

type from=record
k,s1,s2:byte;
end;

var ma,mi:array[1..nmax,1..nmax] of extended; { [**ç*«®, ¤«¨**] }
z:array[1..nmax] of byte; { 0 + 1 * }
x:array[1..nmax,1..nmax,1..2] of from;
n:integer;
s:string;
us:byte;

procedure del_spaces;
begin
while (s[us]=' ') and (us<=length(s)) do inc(us);
end;

function read_cislo:extended;
var pp:string;
i:integer;
j:extended;
begin
del_spaces;
pp:='';
while s[us] in ['0'..'9','.'] do begin
pp:=pp+s[us];
inc(us);
end;
val(pp,j,i);
read_cislo:=j;
end;

function read_znak:byte;
begin
del_spaces;
if us>length(s) then read_znak:=10
else begin
if s[us]='+' then read_znak:=0 else
if s[us]='*' then read_znak:=1
else read_znak:=2;
inc(us);
end;
end;





procedure init;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(s);
us:=1;
n:=0;
repeat
inc(n);
ma[n,1]:=read_cislo;
mi[n,1]:=ma[n,1];
z[n]:=read_znak;
until z[n]=10;
close(input);
end;

procedure scet;
var i,j,k:integer;
e:extended;
begin
for i:=2 to n do
for j:=1 to n+1-i do begin
ma[j,i]:=-max;
mi[j,i]:=max;
for k:=1 to i-1 do begin
{ if z[j+k-1]=0 then e:=m[j,k]+m[j+k,i-k]
else e:=m[j,k]*m[j+k,i-k];
if e>m[j,i] then begin m[j,i]:=e;x[j,i]:=k; end;}
case z[j+k-1] of
0:e:=ma[j,k]+ma[j+k,i-k];
1:e:=ma[j,k]*ma[j+k,i-k];
2:e:=ma[j,k]-ma[j+k,i-k];
end;
if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
x[j,i,1].s1:=1;x[j,i,1].s2:=1;end;
if e<mi[j,i] then begin mi[j,i]:=e;x[j,i,2].k:=k;
x[j,i,2].s1:=1;x[j,i,2].s2:=1;end;
case z[j+k-1] of
0:e:=mi[j,k]+ma[j+k,i-k];
1:e:=mi[j,k]*ma[j+k,i-k];
2:e:=mi[j,k]-ma[j+k,i-k];
end;
if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
x[j,i,1].s1:=2;x[j,i,1].s2:=1;end;
if e<mi[j,i] then begin mi[j,i]:=e;x[j,i,2].k:=k;
x[j,i,2].s1:=2;x[j,i,2].s2:=1;end;
case z[j+k-1] of
0:e:=ma[j,k]+mi[j+k,i-k];
1:e:=ma[j,k]*mi[j+k,i-k];
2:e:=ma[j,k]-mi[j+k,i-k];
end;
if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
x[j,i,1].s1:=1;x[j,i,1].s2:=2;end;
if e<mi[j,i] then begin mi[j,i]:=e;x[j,i,2].k:=k;
x[j,i,2].s1:=1;x[j,i,2].s2:=2;end;
case z[j+k-1] of
0:e:=mi[j,k]+mi[j+k,i-k];
1:e:=mi[j,k]*mi[j+k,i-k];
2:e:=mi[j,k]-mi[j+k,i-k];
end;
if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
x[j,i,1].s1:=2;x[j,i,1].s2:=2;end;
if e<mi[j,i] then begin mi[j,i]:=e;x[j,i,2].k:=k;
x[j,i,2].s1:=2;x[j,i,2].s2:=2;end;

end;
end;
writeln(ma[1,n]);
end;

procedure rec(q,w,r:integer);
begin
if w=1 then begin
if r=1 then write(ma[q,w]) else write(mi[q,w]);
exit;
end;
write('(');
rec(q,x[q,w,r].k,x[q,w,r].s1);
case z[q+x[q,w,r].k-1] of
0:write('+');
1:write('*');
2:write('-');
end;
rec(q+x[q,w,r].k,w-x[q,w,r].k,x[q,w,r].s2);
write(')');
end;


procedure outter;
begin
rec(1,n,1);
writeln;
end;



begin
init;
scet;
outter;
close(output);
end.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра