Версия для печати темы

Автор: Екатерина7 23.11.2009 1:10

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

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

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

Автор: мисс_граффити 23.11.2009 2:33

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

Автор: Екатерина7 23.11.2009 2:54

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

Автор: Lapp 23.11.2009 9:09

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

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

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

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

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

Автор: Гость 23.11.2009 16:43

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

Автор: Гость 23.11.2009 17:00

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

Автор: Lapp 23.11.2009 22:51

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

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

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 23.11.2009 23:02

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


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

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

Автор: Lapp 23.11.2009 23:31

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

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

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

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

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

Автор: Екатерина7 23.11.2009 23:42

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

Автор: Гость 24.11.2009 2:09

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

Автор: Unconnected 24.11.2009 2:16

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

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

Автор: Lapp 24.11.2009 10:50

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

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

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

Автор: Гость 24.11.2009 13:35

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

Автор: Гость 24.11.2009 14:00

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

Автор: Lapp 24.11.2009 15:31

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

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

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

Автор: Екатерина7 25.11.2009 3:02

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

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

Автор: Unconnected 25.11.2009 3:18

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

Автор: Lapp 25.11.2009 6:31

Да. Достаточно было указать на три вызова процедуры 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 25.11.2009 18:44

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

Автор: Екатерина7 8.12.2009 1:21

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

Автор: Lapp 8.12.2009 2:41

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

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

Автор: Екатерина7 8.12.2009 14:09

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

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

Автор: volvo 8.12.2009 14:29

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

Автор: Lapp 8.12.2009 22:28

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

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

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

 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 9.12.2009 2:58

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


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

Автор: Lapp 9.12.2009 3:36

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

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

Автор: Екатерина7 9.12.2009 11:36

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

Автор: Lapp 9.12.2009 11:55

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