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

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

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

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

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



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

[мисс_граффити]

Екатерина, перенести тему в "Задачи на заказ"? Или Вы попробуете что-нибудь сделать и задать конкретные вопросы?

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

Екатерина, перенести тему в "Задачи на заказ"? Или Вы попробуете что-нибудь сделать и задать конкретные вопросы?

а сколько примерно будет стоить одна программа?

[Lapp]

Согласия на перенос, как я понял, не поступало... Переношу в Задачи.

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

По первой задаче: при выполнении операций нужно ли соблюдать правило, что умножение и деление имеют приоритет перед сложением?

Вторая задача тоже интересная.

Ты все же определись с тем, хочешь ли ты решать сама (с помощью Форума - лично я с удовольствием включусь в обсуждение, задачи приятные), или ты хочешь заплатить. Цена нефиксирована, как договоритесь (если кто-то возьмется). Если же все же ты предпочтешь первый вариант, то я буду настаивать на разделении темы на две (правила раздела Задачи, п.6). Оставь в этой теме, скажем, первую задачу, а во второй запость вторую. И позаботься о хороших названиях (Правила Форума, п.4).

[Гость]

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

[Гость]

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

Соображения и опыт могли бы появиться.
Ну, хозяин - барин..

[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

[Unconnected]

Присваивание логической переменной значения false.

Задача навскидку курса 2-3, и не знать булевых переменных? О_о

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

[Lapp]

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

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

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

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

[Гость]

массив Oper- массив знаков. так?

[Гость]

рекурсия используется в самом конце программы? честно, затрудняюсь сказать для чего она нужна..

[Lapp]

массив Oper- массив знаков. так?

Так. Вопрос был, для чего он используется.

рекурсия используется в самом конце программы? честно, затрудняюсь сказать для чего она нужна..

Нет не в конце. Посмотри внимательно, пожалуйста. В программе есть три места, где применяется рекурсия.

Катя, ты забыла пароль? Его нужно восстановить?

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

нет, спасибо, не нужно восстанавливать..

Добавлено через 1 мин.
здесь применяется:
Oper[n]:='+';
Inc(Ad);
Res:=Res0+a;
Count;
Dec(Ad);
?

[Unconnected]

Ну как бы да, применяется здесь... Т.е. процедура вызывает себя из себя же.

[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]

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