Текущий архив: 2003.02.27;
Скачать: CL | DM;
Вниз
задачка Найти похожие ветки
← →
Друмлин (2003-02-10 18:01) [0]Help,plz! Не знаю даже с какого конца подойти:
Дана последовательность цифр длины N (1001>N>19). Надо расставить между ними знаки "+" "-" "*" и скобки так, чтобы получившееся выражение равнялось 0. Ограничение по времени: 10 секунд.
пример> исходная последовательность: 348193115789
после расстановки знаков: (3+4+8+1+9)*(3+1+1-5)*(7+8+9)=0
← →
Cr@sh © (2003-02-10 18:10) [1]Делай так чтоб в любой скобке был ноль, вот и все...
← →
AM (2003-02-10 18:10) [2]Тебе просто нужно сделать множитель равный = 0, например в твоем примере можно было сделать проще:
(3+4+8+1+9+3)*(1-1)*(5+7+8+9)=0 :)
← →
Cr@sh © (2003-02-10 18:10) [3](3+4-8+1)*(9+3+1+1+5+7+8+9+)=0
← →
Друмлин (2003-02-10 18:27) [4]ну ето же только пример =)
предлагаете перебор??
← →
Sha © (2003-02-11 09:59) [5]2 Друмлин (10.02.03 18:27)
А чем плох хороший перебор?
Скорее всего и не потребуется перебирать все 20 цифр.
А для непереборного алгоритм, который первым приходит в голову, надо около 30 цифр, что противоречит условиям задачи.
← →
uw © (2003-02-11 11:53) [6]Чем же вам не понравилось предложение AM (10.02.03 18:10)?
← →
Igorek © (2003-02-11 12:13) [7]Задачка не так проста если нужен эфективный алгоритм нахождения подпоследовательности, сводимой к нулю. В "Жемчужинах программирования" есть похожий пример и шустрый алгоритм.
← →
Sha © (2003-02-11 12:43) [8]> uw © (11.02.03 11:53)
> Чем же вам не понравилось предложение AM (10.02.03 18:10)?
А где там алгоритм?
← →
uw © (2003-02-11 12:51) [9]Я решил, что цифры можно переставлять, теперь мне это предложение тоже не нравится.
← →
Sha © (2003-02-11 17:00) [10]2 Друмлин (10.02.03 18:01)
Держи решение:
var
a: array of byte;
sgn, first, last: integer;
function ZeroSum(i1, i2: integer): boolean;
var
i, j, k, minus, sum: integer;
begin;
Result:=false;
Minus:=1; for i:=1 to i2-i1 do Minus:=Minus shl 1;
for k:=0 to Minus-1 do begin;
sum:=0;
j:=k;
for i:=i2 downto i1 do begin;
if odd(j) then dec(sum,a[i]) else inc(sum,a[i]);
j:=j shr 1;
end;
if sum=0 then begin;
first:=i1; last:=i2; sgn:=k; Result:=true; break;
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i, j, h: integer;
s: string;
label
Done;
begin;
s:=Edit1.Text;
h:=Length(s)-1;
for i:=1 to 1+h do if (s[i]<"0") or (s[i]>"9") then h:=-1;
if h<=19 then begin;
Edit2.Text:="неверные данные"; exit;
end;
SetLength(a,h+1);
for i:=0 to h do a[i]:=byte(s[1+i])-byte("0");
first:=-1;
for j:=0 to h do // длина
for i:=0 to h-j do // нач положение
if ZeroSum(i,i+j) then goto Done;
Done:
if first<0 then s:="нет решения"
else begin;
s:=s+")";
for i:=h downto last+1 do Insert("+",s,1+i);
if last<h then Insert(")x(",s,2+last);
j:=sgn;
for i:=last downto first do begin;
if odd(j) then Insert("-",s,1+i) else Insert("+",s,1+i);
j:=j shr 1;
end;
if 0<first then Insert(")x(",s,1+first);
for i:=first-1 downto 0 do Insert("+",s,1+i);
s:="("+s;
end;
Edit2.Text:=s;
end;
← →
Sha © (2003-02-11 17:20) [11]Да, для порядка перед последним end добаиь строчку:
a:=nil;
Страницы: 1 вся ветка
Текущий архив: 2003.02.27;
Скачать: CL | DM;
Память: 0.49 MB
Время: 0.026 c
