Написать алгоритм, который используя числа 1, 3, 4, 6, а также умножение, деление, сложение, вычитание и скобки, находит все комбинации для получения числа 24. Разрешается использовать только эти числа и только эти операции. Каждое число должно использоваться только один раз. Операции и скобки можно использовать любое число раз. Нельзя объединять числа как цифры, составляя, например, 36 или 614.
Что-то я ничего, кроме полного перебора не придумал. Вкратце, для всевозможных перестановок данных чисел пытаемся всеми возможными способами расставить скобки и действия между ними. Вот рабочий вариант написаный на python:
from fractions import Fraction
from itertools import permutations
OPS = {"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"/": lambda a, b: a / b,
"*": lambda a, b: a * b}
class Expression:
def __init__(self, value, op = None):
self.value = value
self.op = op
self.left = None
self.right = None
def __str__(self):
if self.left == None:
return str(self.value)
return "(" + str(self.left) + " " + self.op + " " + str(self.right) + ")"
def all_expressions(numbers):
if len(numbers) == 1:
yield Expression(numbers[0])
return
for i in xrange(1, len(numbers)):
for left_expr in all_expressions(numbers[:i]):
for right_expr in all_expressions(numbers[i:]):
for op in OPS:
try: # For 0 division
value = OPS[op](left_expr.value, right_expr.value)
res = Expression(value, op)
res.left = left_expr
res.right = right_expr
yield res
except Exception:
pass
numbers = [Fraction(1), Fraction(3), Fraction(4), Fraction(6)]
for p in permutations(numbers):
for e in all_expressions(p):
if e.value == 24:
print e
Результат всего один:
$ python tp.py
(6 / (1 - (3 / 4)))
Моё решение на Delphi с использованием обратной польской нотации здесь.
Результат: 6/(1-(3/4))=24
Функция Solve:
function TReversePolishNotation.Solve: string;
var
i,j: integer;
Token: string;
arg1,arg2: extended;
arg1infix,arg2infix: string;
tmp: extended;
begin
try
i:=0;
repeat
//идём по польской нотации, пока не натыкаемся на пробел
j:=i+1;
repeat
Inc(i)
until self.FNotation[i]=' ';
//копируем в Token часть до пробела (оператор или аргумент)
Token:=copy(self.FNotation,j,i-j);
//если это не оператор - кладём в стек
if not CharInSet(Token[1],['+','-','*','/']) then begin
FSolveStack.Push(Token);
FInfixStack.Push(Token);
end
//иначе - оператор
else begin
//достаём аргументы в обратном порядке
arg2:=strtofloat(self.FSolveStack.Pop);
arg1:=strtofloat(self.FSolveStack.Pop);
//применяем оператор и кладём результат в стек
case Token[1] of
'+': self.FSolveStack.Push(floattostr(arg1+arg2));
'-': self.FSolveStack.Push(floattostr(arg1-arg2));
'*': self.FSolveStack.Push(floattostr(arg1*arg2));
'/': self.FSolveStack.Push(floattostr(arg1/arg2));
end;
//делаем тоже самое, но без вычисления, для сборки в инфиксную нотацию
arg2infix:=FInfixStack.Pop;
arg1infix:=FInfixStack.Pop;
if not TryStrToFloat(arg2infix,tmp) then
arg2infix:='('+arg2infix+')';
if not TryStrToFloat(arg1infix,tmp) then
arg1infix:='('+arg1infix+')';
FInfixStack.Push(
arg1infix+Token+arg2infix
);
end;
//цикл выполняется до тех пор пока не пройдём по всей польской нотации
until (i>=Length(self.FNotation));
//ответ лежит в стеке
Result:=self.FSolveStack.Pop;
self.InfixNotation:=self.FInfixStack.Pop;
except
Result:='Error';
end;
end;
Надо написать работающий вариант или описание сойдет?
Если сойдет:
Создаем массив массивов всех вариантов расположения чисел.
Сразу уходим в обратную польскую, чтобы о скобках не думать.
Если после операций с тремя числами уже получилось число больше 24, в четвертой не используем + и *(экономия времени)
Полученные верные варианты преобразуем в прямую запись..
Задача тупо переборная. Вот мой вариант реализации. Основной алгоритм:
public static List<ICountable> GetAll(List<ICountable> array)
{
if (array.Count <= 1) return array;
var result = new List<ICountable>();
for (int mask = 1; mask < (1 << array.Count) - 1; mask++)
{
var xParam = new List<ICountable>();
var yParam = new List<ICountable>();
for (int i = 0; i < array.Count; i++) ((mask >> i & 1) == 0 ? xParam : yParam).Add(array[i]);
var xResult = GetAll(xParam);
var yResult = GetAll(yParam);
foreach (OperatorType operatorType in OperatorType.All) foreach (ICountable xx in xResult) foreach (ICountable yy in yResult) result.Add(new Expression(xx, yy, operatorType));
}
return result;
}
Вариант на питоне с расчетом в обратной польской нотации. Упор в коде на хорошую читаемость и легкую расширяемость.
# coding=utf-8
from __future__ import print_function
from itertools import permutations, product
class BinaryOperator(object):
"""
Бинарный оператор
"""
def __init__(self, text, func, priority=1):
self.text = text
self.func = func
self.priority = priority
def __call__(self, left, right):
return self.func(left, right)
def __str__(self):
return self.text
class SimpleMachine(object):
"""
Простейший автомат
"""
def __init__(self):
self.reset()
def reset(self):
self._stack = []
self._infix = []
def infix_add(self, op):
if isinstance(op, BinaryOperator):
arg1, arg2 = self._infix.pop(), self._infix.pop()
to_str = lambda x: '(%s)' % x[0] if x[1] < op.priority else str(x[0])
self._infix.append(('%s %s %s' % (to_str(arg1), op, to_str(arg2)), op.priority))
else:
self._infix.append((op, 10))
def execute(self, expression):
try:
self.reset()
for op in expression:
if isinstance(op, BinaryOperator):
self._stack.append(op(self._stack.pop(), self._stack.pop()))
else:
self._stack.append(float(op))
self.infix_add(op)
except ZeroDivisionError:
self._stack = []
return self._stack[-1] if len(self._stack) else None
@property
def infix(self):
return ' '.join([name for name, priority in self._infix])
def expression_generator(all_operands, all_operators):
"""
Генератор всевозможных выражений
"""
for lists_operands in permutations(all_operands):
for lists_operators in product(all_operators, repeat=len(all_operands) - 1):
result = []
def gen(stack, operands, operators, expect = 0):
if not operands and not operators: return result.append(stack)
if len(operands):
gen(stack + [operands[-1]], operands[:-1], operators, expect + 1)
if expect > 1:
gen(stack + [operators[-1]], operands, operators[:-1], expect - 1)
gen([], lists_operands, lists_operators)
for expr in result:
yield expr
OPERANDS = [1, 3, 4, 6]
OPERATORS = (
BinaryOperator('+', float.__add__, 1),
BinaryOperator('-', float.__sub__, 1),
BinaryOperator('*', float.__mul__, 2),
BinaryOperator('/', float.__div__, 2),
)
if __name__ == '__main__':
machine = SimpleMachine()
for expression in expression_generator(OPERANDS, OPERATORS):
if machine.execute(expression) == 24:
print('24 =', machine.infix)
Условие задачи не совсем корректное. Возможно, стоит его поправить, изменив
"Операции и скобки можно использовать любое число раз"
на "Операции и скобки можно использовать любое значимое число раз".
Не то, чтобы я был слоупоком или занудой, но из текущего условия следует такое решение:
Код на js за который надо сильно пинать :)
var numbers = [1,3,4,6];
var symbol = ["+","-","*","/"];
var MyArray = new Array(0);
var s = "";
for (var i=0; i<numbers.length; i++) {
s=s+numbers[i];
for (var i2=0; i2<symbol.length; i2++) {
s=s+symbol[i2];
for (var i3=0; i3<numbers.length; i3++) {
if (s.indexOf(numbers[i3]+'', 0) != -1) continue;
s=s+numbers[i3];
for (var i4=0; i4<symbol.length; i4++) {
s=s+symbol[i4];
for (var i5=0; i5<numbers.length; i5++) {
if (s.indexOf(numbers[i5]+'', 0) != -1) continue;
s=s+numbers[i5];
for (var i6=0; i6<symbol.length; i6++) {
s=s+symbol[i6];
for (var i7=0; i7<numbers.length; i7++) {
if (s.indexOf(numbers[i7]+'', 0) != -1) continue;
s=s+numbers[i7];
MyArray.push(s);
s = s.slice(0,6);
}
s = s.slice(0,5);
}
s = s.slice(0,4);
}
s = s.slice(0,3);
}
s = s.slice(0,2);
}
s = s.slice(0,1);
}
s = "";
}
var skobkyDvoynue = [
[0, 3],
[2, 5],
[4, 7]
];
var skobkyTroynie = [
[0, 5],
[2, 7]
];
var skobkyDvoynue2_1 = [
[1, 4],
[3, 6],
[5, 8]
];
for (var i8=0; i8<MyArray.length; i8++) {
if (eval(MyArray[i8]) == 24)
document.write(MyArray[i8]+'='+eval(MyArray[i8])+"<br \>");
for (var i10=0; i10<skobkyDvoynue.length; i10++) {
var arr = MyArray[i8].split('');
arr.splice(skobkyDvoynue[i10][0], 0, '(');
arr.splice(skobkyDvoynue[i10][1]+1, 0, ')');
if (eval(arr.join('')) == 24) document.write(arr.join('')+'='+eval(arr.join(''))+"<br \>");
}
for (var i11=0; i11<skobkyTroynie.length; i11++) {
var arr2 = MyArray[i8].split('');
arr2.splice(skobkyTroynie[i11][0], 0, '(');
arr2.splice(skobkyTroynie[i11][1]+1, 0, ')');
if (eval(arr2.join('')) == 24) document.write(arr2.join('')+'='+eval(arr2.join(''))+"<br \>");
for (var i12=0; i12<skobkyDvoynue2_1.length; i12++) {
var arr3 = (arr2.join('')).split('');
arr3.splice(skobkyDvoynue2_1[i12][0], 0, '(');
arr3.splice(skobkyDvoynue2_1[i12][1]+1, 0, ')');
try {
if (eval(arr3.join('')) == 24) document.write(arr3.join('')+'='+eval(arr3.join(''))+"<br \>");
} catch (err) {}
}
}
}
Как организовать в настройках приложения функцию скрыть/показать textviewПытался с помощью SharedPreferences, но так и понял
Хотите улучшить этот вопрос? Update the question so it's on-topic for Stack Overflow на русском
Есть такая задача: найти максимальную последовательность единиц в матрицеПоследовательность может быть как горизонтальной так и вертикальной
Для чего сравнивать this, и любой Object o? В каких случая они могут оказаться равными?