рекурсия- расстановка знаков Опции

[Екатерина7]

помогите, пожалуйста, разобраться с задачей

Для заданного набора целых чисел без знака расставить между ними арифметические знаки сложения, деления, и умножения так, чтобы результат вычисления полученного арифметического выражения был минимальным. Число знаков умножения в этом выражении должно быть равным или на 2 больше, чем знаков сложения, а знаков сложения- равно или на 1 больше, чем знаков деления. В наборе должно быть не менее четырех чисел, а в полученном выражении должны присутствовать все три арифметических знака.

(умножение и деление имеют приоритет перед операциями сложения и вычитания, деление производится с остатком)



Сообщение отредактировано: Екатерина7 - 23.11.2009 18:16

[Lapp]

Да. Достаточно было указать на три вызова процедуры Count, которые производятся изнутри самой процедуры. Видишь их? один для +, второй для *, третий для /. Смысл слова "рекурсия" именно в этом и состоит. Как "ре-монт" - это "повторный монтаж", так и "ре-курсия" - это "повторный заход".

Дальше, сам отвечу на свой вопрос. Массив Oper (вместе с OperMin) служит одной-единственной цели: распечатать расставленные знаки в конце. Для самой функциональности, то есть для отыскания нужной комбинации знаков, он не нужен. Это я хотел от тебя услышать.

Похоже, что интереса к задаче у тебя так и не появилось. Мне начинает надоедать вытягивать из тебя по слову. Похоже, что мне это нужно больше тебя.. Когда уже в России научатся (и захотят) учиться?..

Лови решение этой задачи.

const
  m=10;  {размер цепочки чисел}

type
  tNum= LongInt;

var
  n,Ad,Mu,Di: integer;
  Arg: array[1..m]of tNum;
  Oper,MinOper: array[2..m]of char;
  Sum,Res,Min: tNum;
  Start: boolean;

procedure Count;
var
  a,Sum0,Res0: tNum;
begin
  if n=m then begin
    if (Di>0) and ((Mu=Ad)or(Mu-Ad=2)) and ((Ad=Di)or(Ad-Di=1)) then begin
      Sum:=Sum+Res;
      if Start or(Sum<Min) then begin
        Min:=Sum;
        MinOper:=Oper;
        Start:=false
      end
    end
  end
  else begin
    Sum0:=Sum;
    Res0:=Res;
    Inc(n);
    a:=Arg[n];

    Oper[n]:='+';
    Inc(Ad);
    Sum:=Sum+Res;
    Res:=a;
    Count;
    Sum:=Sum0;
    Dec(Ad);

    Oper[n]:='*';
    Inc(Mu);
    Res:=Res0*a;
    Count;
    Dec(Mu);

    Oper[n]:='/';
    Inc(Di);
    Res:=Res0 div a;
    Count;
    Dec(Di);

    Dec(n);
  end
end;

var
  i: integer;

begin
  Randomize;
  for i:=1 to m do Arg[i]:=Random(m)+1;
  Start:=true;
  Res:=Arg[1];
  Sum:=0;
  Ad:=0;
  Mu:=0;
  Di:=0;
  n:=1;
  Count;
  Write(Min:10,' =   ');
  for i:=1 to m do begin
    if i>1 then Write(' ',MinOper[i],' ');
    Write(Arg[i]);
  end;
  WriteLn;
  ReadLn
end.

На TP не проверял, только на FPC.
Разбирайся. Спрашивай.

[Екатерина7]

спасибо большое!!!

[Екатерина7]

несовсем пойму, как она выполняется..точнее вообще не пойму.. непонятно, как выражения считаются. проверяю вручную, не получается..