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

[Екатерина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]

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

[Lapp]

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

Кать, ты меня, наконец, снова радуешь . Кроме шуток. Твои предыдущие слова "я разберусь" - расстраивали, а вот теперь чувствуется, что ты уже не витаешь в облаках и находишь силы это признать

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

Покажи, пожалуйста, твои проверки. Что значит "не получается"? Я, например, вручную просто не смогу в большинстве случаев быть уверенным, что я правильно нашел минимум. Или ты хочешь сказать, что вручную тебе удается найти лучший минимум, чем находит программа? Тогда покажи, плз, такой случай. Как только разберемся с этим, я объясню, какой принцип работы проги.
O'kay?

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

смотри,
например 319155=8+2+1+8*10*10*7/9/4/5
вот этого я не понимаю.. как считает.. должно же в результате получиться это число? 319155?

или вот например
46016=1+5+7+5*7*9*1/8/10/8
просто попробовала там посчитать действия и не такой результат..
может я чего-то не допонимаю..

[Lapp]

Гм.. И мне тоже непонятно. Кать, откуда ты берешь эти равенства?

например 319155=8+2+1+8*10*10*7/9/4/5
... или вот например
46016=1+5+7+5*7*9*1/8/10/8

Ты что-то изменила в программе? Покажи, пожалуйста, свой текущий вариант проги.

У меня, например, при запуске получаются такие:

 3 =   1 + 1 / 10 * 9 * 7 * 6 + 2 + 8 / 9 / 3

 7 =   10 * 2 / 4 / 7 * 9 * 2 + 4 + 3 + 5 / 7

 5 =   4 + 6 / 10 + 6 / 10 * 5 * 2 * 6 + 9 / 5

 4 =   7 * 3 / 8 + 2 + 5 * 1 / 7 + 2 * 1 / 8

- на этот раз в BP прогонял для пущей уверенности.
Что я делаю не так? (С)

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

хм... все, нашла ошибку! спасибо! вес правильно получается


Добавлено через 3 мин.
извиняюсь..

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

[Lapp]

хм... все, нашла ошибку

Извини - ошибку в чем? Вроде бы как ошибки-то и не было... ?

Так что, уже понятно, как оно работает? не нужно объяснять?

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

да, ошибка была не у тебя.. все нормально. если не трудно, сможешь объяснить, пожалуйста

Сообщение отредактировано: Екатерина7 - 9.12.2009 7:37

[Lapp]

если не трудно, сможешь объяснить, пожалуйста

Нет проблем. Давай, говори, какое место ты не поняла в процессе разбора. Я постараюсь объяснить.
Точнее, даже так: скажи, что ты поняла. На этой основе продолжим.