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

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

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

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

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



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

[Lapp]

Остается открытым вопрос про приоритеты операций. Нужно его учитывать или нет? Пожалуйста, уточни. Решения отличаются довольно сильно.

Решение без приоритетов несложное. Собственно, вот оно..

const
  m=10;

type
  tNum= double;

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


procedure Count;
var
  a,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)) and (Start or(Res<Min)) then begin
      Min:=Res;
      MinOper:=Oper;
      Start:=false
    end
  end
  else begin
    Res0:=Res;
    a:=Arg[n];
    Inc(n);

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

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

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

    Dec(n)
  end
end;

var
  i: integer;

begin
  Randomize;
  for i:=1 to m do Arg[i]:=Random*2;
  Start:=true;
  Res:=Arg[1];
  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]:5:2);
  end;
  WriteLn;
  ReadLn
end.

Я его слишком придирчиво не проверял (не на чем, не считать же на бумажке)). Нашедшему существенную ошибку - плюс в репу)).
Катя, спрашивай, что неясно.

Его можно в принципе переделать и на приоритеты..

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

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


Добавлено через 5 мин.
еще несовсем понятно эта строчка Res,Min: tNum;
и вот это Dec(Ad);

Добавлено через 1 мин.
Dec(Ad);- это результат операции какой-то?

[Lapp]

я же вроде там в скобочках дописала..

Извиняюсь, не заглянул наверх (лучше говорить по ходу темы)

еще несовсем понятно эта строчка Res,Min: tNum;
и вот это Dec(Ad);
Dec(Ad);- это результат операции какой-то?

Res - это сам результат выполнения операций. В самом начале он равен первому числу, потом "накапливается" по мере выполнения.
Min - это минимальный из всех Res, то есть то, что мы ищем. Мы его обновляем по мере встечи более маленьких значений Res.

Dec(x) - это операция уменьшения x на 1, то есть эквивалентно записи: x:=x-1

Спрашивай дальше.

Если приоритет нужно учитывать, решение нужно дорабатывать. Подумай, как. Я тоже )).

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

спасибо огромное тебе!!!! подумаю над решением и вопросами..

[Гость]

а что такое Start?
например, Start:=false

[Lapp]

а что такое Start?
например, Start:=false

Start - логическая переменная, с помощью которой мы инициализируем Min жизненным значением, а не среднепотолочным. При самой первой встрече допустимой комбинации знаков мы заносим ее в Min (чтобы потом уточнять), а переменную Start сбрасываем в ложь.

Как я и полагал, учет приоритета операций потребовал вполне ощутимыз изменений, но далеко не катастрофических. Прога остается вполне узнаваемой. Кстати, в том варианте (выше), действительно есть ошибки - но все, прием заявок на плюс в репу закончен)).

Общая логика проги сохранилась. Екатерина, ты можешь приблизительно прокомментировать, что там к чему? Хотя бы сказать, где там использована рекурсия - можешь? И зачем.
Или вот такой совсем конкретный вопрос: какой цели служит массив Oper?