КвантоФорум :: Интересная задача (1/1)

Welcome, Guest

TOPIC: Интересная задача

Интересная задача 21 Авг 2024 04:21 #1

alexlaw
OFFLINE
Дьяк
Posts: 199
Thank you received: 10
Karma: 1

Попалась на глаза задача -
В выражении 1+2*3+4*5+6*7+8*9+10 расставить две пары скобок так, чтобы значение выражения стало равным 537
Задача для программистов, т.к. ни какого логического решения нет.
Мне пришел в голову алгоритм решения и я его реализовал и провел полный анализ выражения 1+2*3+4*5+6*7+8*9+10
Хотелось услышать у кого какие идеи по поводу алгоритма решения

Reply Quote

Интересная задача 21 Авг 2024 06:00 #2

Andralex
OFFLINE
Боярин
на уровне 2 разряда
Posts: 2763
Thank you received: 74
Karma: 17

1+2*3+4*5+6*7+8*9+10

Нечто похожее печатали давным давно в журнале "Наука и Жизнь". Там в задачках было расставить знаки +/-Х между цифрами.

На первый взгляд, если есть две пары скобок, то они могут быть как вложенные так и последовательные. А дальше комбинаторика с полным перебором всевозможных расстановок скобок в позициях.

(1 + 2) * (3 + 4) * 5 + 6 * 7 + 8 * 9 + 10
(1 + 2) * (3 + 4 * 5) + 6 * 7 + 8 * 9 + 10
(1 + 2) * (3 + 4 * 5 + 6) * 7 + 8 * 9 + 10
и т.д.

(1 + (2 * 3) + 4) * 5 + 6 * 7 + 8 * 9 + 10
(1 + (2 * 3) + 4 * 5) + 6 * 7 + 8 * 9 + 10
(1 + (2 * 3) + 4 * 5 + 6) * 7 + 8 * 9 + 10
и т.д.

P.S. Для подсчёта выражения проще использовать функцию JS.eval()

...не мы первые, не мы последние...

Reply Quote

Интересная задача 21 Авг 2024 06:13 #3

Vladimirovich NOW ONLINE Инквизитор Posts: 108571 Thank you received: 2170 Karma: 107	На всякий случай добавлю ссылку на параллельную тему алгоритмические задачки
	Каждому - своё. Reply Quote

Интересная задача 21 Авг 2024 06:40 #4

alexlaw
OFFLINE
Дьяк
Posts: 199
Thank you received: 10
Karma: 1

Andralex wrote:

А дальше комбинаторика с полным перебором всевозможных расстановок скобок в позициях

Пошел другим путем, реализовал другой алгоритм.
В двух словах алгоритм такой.
1. Поставить одну пару скобок
первый цикл
- парсим строку задачи слева на право
- вставляем ( в первую позицию строки задачи
- или если попали на символ + или *, то вставляем ( на позицию за этим символом
- после каждой итерации или перед ней восстанавливаем строку до состояния входа в цикл
второй цикл
- парсим строку задачи справа на лево
- вставляем ) в крайнюю позицию строки задачи
- или если попали на символ + или *, то вставляем ) в позицию этого символом
после каждой итерации второго цикла должна получиться одна пара скобок
- находим и вычисляем значение в скобках , чтобы в дальнейшем заменить выражение в скобках этим значением
- после каждой итерации или перед ней восстанавливаем строку до состояния входа в цикл

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

Табл. после получения всех вариантов расстановки одной пары скобок для исходной строки задачи 1+2*3+4*5+6*7+8*9+10

Warning: Spoiler! [ Click to expand ]

Reply Quote

Интересная задача 21 Авг 2024 06:45 #5

alexlaw
OFFLINE
Дьяк
Posts: 199
Thank you received: 10
Karma: 1

После анализа получил все возможные варианты ответов для исходного условия
ответ кол-во

Warning: Spoiler! [ Click to expand ]

Reply Quote

Интересная задача 21 Авг 2024 07:24 #6

alexlaw
OFFLINE
Дьяк
Posts: 199
Thank you received: 10
Karma: 1

Andralex wrote:

P.S. Для подсчёта выражения проще использовать функцию JS.eval()

В делфи тоже есть аналогичная возможность

//uses ComObj
function Eval_test(Str_eval:string):string;
var
sc: Variant;
begin
  result:='';
  SC:=CreateOLEObject('ScriptControl');
    try
    SC.Language:='VBScript';
    SC.Timeout:=-1;
    SC.AllowUI:=True;
    result:=VarToStr(SC.Eval(Str_eval));
    except
    on E : Exception do
      ShowMessage(E.ClassName+' поднята ошибка, с сообщением : '+E.Message);
    end;
    SC:=Unassigned;

end;

Reply Quote

Университет

Математика. Матрица

Интересная задача

TOPIC: Интересная задача

Интересная задача 21 Авг 2024 04:21 #1

Интересная задача 21 Авг 2024 06:00 #2

Интересная задача 21 Авг 2024 06:13 #3

Интересная задача 21 Авг 2024 06:40 #4

Интересная задача 21 Авг 2024 06:45 #5

Интересная задача 21 Авг 2024 07:24 #6

Научно-шахматный клуб КвантоФорум