#include <stdio.h>
enum
{
plus = 0, minus, divide, multiply
};
union ops
{
struct
{
unsigned char op1 : 2;
unsigned char op2 : 2;
unsigned char op3 : 2;
unsigned char op4 : 2;
};
unsigned char ptr;
};
int f(int a, int b, unsigned char op)
{
int result;
switch (op)
{
case plus :
result = a + b;
break;
case minus :
result = a - b;
break;
case divide :
if (!b)
result = -1;
else
result = a / b;
break;
case multiply :
result = a * b;
break;
}
return result;
}
char get_symbol(unsigned char op)
{
char result;
switch (op)
{
case plus :
result = '+';
break;
case minus :
result = '-';
break;
case divide :
result = '/';
break;
case multiply :
result = '*';
break;
}
return result;
}
int main( void )
{
ops op;
op.ptr = 255;
int a[5] = {2, 5, 12, 2, 9};
do
{
int result_1 = f(a[2], a[3], op.op1); // (12?2)
int result_2 = f(result_1, a[4], op.op2); // ((12?2)?9)
int result_3 = f(a[0], a[1], op.op3); // (2?5)
int result = f(result_3, result_2, op.op4); // (2?5)?((12?2)?9)=190
if (result == 190)
break;
}
while (op.ptr--);
printf("(%i%c%i)%c((%i%c%i)%c%i)=190\n", a[0], get_symbol(op.op3),
a[1], get_symbol(op.op4), a[2], get_symbol(op.op1),
a[3], get_symbol(op.op2), a[4]);
return 0;
}
Разработка алгоритма
Добрый день.
Помогите пожалуйста разработать алгоритм решения нижеизложенной задачи.
Есть выражение типа (2?5)?((12?2)?9)=190, нужно найти какие арифметический операции требуется поставить вместо знаков впроса, чтобы получилось 190, ответ: (2*5)*((12-2)+9)=190
Помогите пожалуйста разработать алгоритм решения нижеизложенной задачи.
Есть выражение типа (2?5)?((12?2)?9)=190, нужно найти какие арифметический операции требуется поставить вместо знаков впроса, чтобы получилось 190, ответ: (2*5)*((12-2)+9)=190
Самое очевидное решение таково.
Обозначить эти операции как однобайтовые переменные, благо операций всего 4, по порядку вхождения в строку. Потом разобрать строку, используя обратную польскую запись , и затем перебирать все возможные комбинации операций. Для выражения такого порядка "сложности" полный перебор сойдет вполне.
Обозначить эти операции как однобайтовые переменные, благо операций всего 4, по порядку вхождения в строку. Потом разобрать строку, используя обратную польскую запись , и затем перебирать все возможные комбинации операций. Для выражения такого порядка "сложности" полный перебор сойдет вполне.
Как вариант (алгоритм виден, надеюсь):
Жутко корявый код. ;)
Код:
Жутко корявый код. ;)
Цитата: platon
Добрый день.
Помогите пожалуйста разработать алгоритм решения нижеизложенной задачи.
Есть выражение типа (2?5)?((12?2)?9)=190, нужно найти какие арифметический операции требуется поставить вместо знаков впроса, чтобы получилось 190, ответ: (2*5)*((12-2)+9)=190
Помогите пожалуйста разработать алгоритм решения нижеизложенной задачи.
Есть выражение типа (2?5)?((12?2)?9)=190, нужно найти какие арифметический операции требуется поставить вместо знаков впроса, чтобы получилось 190, ответ: (2*5)*((12-2)+9)=190
Автор, не надо писать мне в личку причину, по которой ты разместил тут вопрос. Я не буду твои сообщения тут цитировать, но замечу тебя вот что.
1 - Если это олимпиадная задача, как ты говоришь, то в них существуют всегда (по крайне мере на нормальных олимпиадах) четкие и строгие условия, ограничения по времени выполнения, по размеру исполняемого кода, по размерности валидных данных, и т.п. Ты их тут выложил? Нет. Ты просто попросил помочь, я предложил решение, может, не лучшее, но рабочее, а Lerkin так на код расщедрился:).
Если же тебя интересует "более сложный случай", и то выложи более сложное условие.
2 - На олимпиадах задачи не оценивают по тривиальности/ нетривиальности решения ( в последнее время). Задача может быть решенной, если она проходит предложенный автором задачи набор тестов, или нерешенной в противном случае.
Я не понемаю почему изменяются значения битовых полей, и почему цикл do\while выполняется 255 раз, обьясните пожалуйста
знаков действий всего 4 : "+","-","*","/"
перебираем рекурсией , вставляя в пример .
если получается тождество - выход,
иначе - облом ) .
вот и весь алгоритм .
перебираем рекурсией , вставляя в пример .
если получается тождество - выход,
иначе - облом ) .
вот и весь алгоритм .
Эээ.. рекурсия... А, это похоже не про метод Lerkina.
Цитата:
Я не понемаю почему изменяются значения битовых полей, и почему цикл do\while выполняется 255 раз, обьясните пожалуйста
Вариантов перебора 256, если учитывать что каждая из операций может присутствовать не только один раз.
Начинаем со всех перемножений. Деление у нас представлено состоянием 11.
255 - это (11 11 11 11)b. Вычитаем единицу, получаем (11 11 11 10)b. Стало быть первых три перемножения и одно деления. И так далее до четырех сложений (00 00 00 00)b. Если нашли что искали - выход.
А битовые поля меняются потому чтоструктура данных представленна как union, и данные могут быть представленны либо как одно поле unsigned char, либо как набор битовых полей (с размером набора таким же), фактически имея один физический участок памяти.
в выражении может быть произвольное кол-во операций !
platon привёл только пример .
platon привёл только пример .
Ага. И операций произвольное количество, и операторов.
Посмотрев задание, я подумал, что это для олимпиады (и автор подтвердил мою догадку, правда довольно странным способом:)). Данный вариант решения - для КОНКРЕТНОГО примера. Для олимпиады, обычно, большего и не требуется. Т.к. я потратил на написание этого примера около 4-5 мин., что соответствует требованиям таких мероприятий.
А потом: критикуешь - предлагай. Примерчик только я и выложил, от тебя пока - одни символы кириллицы ;)
P.S. Вообще, уже в Студенам надо перенести...
Посмотрев задание, я подумал, что это для олимпиады (и автор подтвердил мою догадку, правда довольно странным способом:)). Данный вариант решения - для КОНКРЕТНОГО примера. Для олимпиады, обычно, большего и не требуется. Т.к. я потратил на написание этого примера около 4-5 мин., что соответствует требованиям таких мероприятий.
А потом: критикуешь - предлагай. Примерчик только я и выложил, от тебя пока - одни символы кириллицы ;)
P.S. Вообще, уже в Студенам надо перенести...
если чел выступает на олимпиадах , то код накарябать сам могёт .
просили алгоритм - даём . )
просили алгоритм - даём . )
Цитата: koderAlex
если чел выступает на олимпиадах , то код накарябать сам могёт .
просили алгоритм - даём . )
просили алгоритм - даём . )
Меня, кстати, тоже это удивляет. Люди участвуют в олимпиадах по программированию, но не способны создать или разобрать самый примитивный код.
Ну, а в плане демонстрации кода - так это для примера реализации того, или иного алгоритма. Имхо, словесное описание - не всегда раскрывает суть задумки.
товарищи вам по 28 и 29 лет - вы учились давно. щас прогульщикам дают такие задачки в качестве долга.
а нам он её подсунул в качестве аванса ? :)