Подскажите алгоритм для проставления арифметических скобок между числами?

Форум Программирование Общие вопросы программирования (Dev)

Платформа 1С v8.3

1. DJDUH 17 12.02.16 17:59 Сейчас в теме

Привет.
Ломаю голову над алгоритмом - может кто знает!?

Задачка на логику. Есть n-чисел ( n1, n2, n3, ...., n_мах) и их результат Rez, нужно проставить арифметические операции между ними и скобки, таким образом, что-бы получить результат.

Например: (( n1 + n2 ) * n3 ) / n_мах = Rez.

Как правильно организовать функцию по проставление скобок?

Ответы

Подписаться на ответы Инфостарт бот

Свернуть все

2. dabu-dabu 291 12.02.16 18:18 Сейчас в теме

(1) DJDUH, Для начала неплохо бы научиться письменно высказывать свои мысли.

3. DJDUH 17 12.02.16 18:21 Сейчас в теме

(2) dabu-dabu, Что в описании не понятно?

4. dabu-dabu 291 12.02.16 19:26 Сейчас в теме

(3) DJDUH, Ничего непонятно.
Попробую своими словами: Необходимо сформировать текст формулы (равенства) так чтобы заданные n-чисел с помощью арифметических преобразований равнялись заданному числу Rez.
Например.
Задано: n1=2, n2=3, n3=1,5, n4=7,5, Rez=1.
Должны получить в виде одного из вариантов: (( n1 + n2 ) * n3 ) / n4 = Rez.
Так?
Тогда боюсь только перебором возможных комбинаций, благо их должно быть не так много в случае небольшого количества чисел.

6. CaptainMorgan 13.02.16 08:03 Сейчас в теме

(1) Вы пишите "Ломаю голову над алгоритмом - может кто знает!?"
Занятие похвальное.
"Как правильно организовать функцию по проставление скобок?"
Примерно так:

Функция СрываГоловы(МассивЪ)
    Результат = 0;
    Позиция = 0;
    Для Каждого Ять Из МассивЪ Цикл
        Позиция = Позиция+1;
        Если Позиция=1 Тогда
            А1 = Ять;
        ИначеЕсли Позиция=2 Тогда
            А2 = Ять;
        ИначеЕсли Позиция=3 Тогда
            А3 = Ять;
            Результат = Результат + ((А1+А2)*А3)/МассивЪ.Количество();
            Позиция = 0;
        КонецЕсли;
    КонецЦикла;
    Возврат Результат*0;
КонецФункции

Показать

7. DJDUH 17 15.02.16 18:07 Сейчас в теме

(6) CaptainMorgan, Не совсем то, что мне нужно.

Необходимо расставить арифметические знаки и скобки между числами, для получения результата.

Числа n1, n2, n3, n4 и их результат Rez.
Например:
ВариантN1 = n1 + n2 + n3 + n4;
ВариантN2 = n1 - n2 * n3 / n4;
..............................
ВариантNm = ( n1 / ( n2 - n3 ) ) / n4.

Как написать рекурсию для проставления и операций, и скобок между числами?

8. ildarovich 7865 15.02.16 21:46 Сейчас в теме

(7) DJDUH, вот готовая функция

Функция СписокФормул(От, До)
	Результат = Новый СписокЗначений;
	Если От >= До Тогда
		Результат.Добавить("n" + От);
		Результат.Добавить("(-n" + От + ")")
	Иначе 
		Для Сч = От По До - 1 Цикл
			Для каждого Слева Из СписокФормул(От, Сч) Цикл
				Для каждого Справа Из СписокФормул(Сч + 1, До) Цикл
					Для Оп = 1 По 3 Цикл
						Результат.Добавить("(" + Слева + Сред("+*/", Оп, 1) + Справа + ")")
					КонецЦикла 
				КонецЦикла
			КонецЦикла 	
		КонецЦикла 
	КонецЕсли;
	Возврат Результат
КонецФункции // СписокФормул()

Показать

Она генерирует все формулы для заданного диапазона номеров аргументов. Для 5-ти аргументов получается 36 288 разных формул.
Логика примерно такая: Цепочка аргументов разными способами разбивается на две части: операцией между первым и вторым, вторым и третьим, третьим и четвертым и т.д. аргументами. Варианты формул для левой и правой части цепочки вычисляются рекурсивно. Затем варианты комбинируются, конкатенируясь с тремя (!!!) разными вариантами соединяющих их операций. Скобки обрамляют результат. Когда диапазон номеров аргументов сужается до одного, возвращается два варианта nK и (-nK). Знак "-" представляет некоторую сложность, поскольку минус может быть унарной операцией. Поэтому сделано именно так. Лишние скобки вычислениям не мешают.

Прикрепленные файлы:

9. DJDUH 17 16.02.16 17:09 Сейчас в теме

(8) ildarovich, Реально круто сделано, сам делал!?

10. dj_serega 392 16.02.16 17:12 Сейчас в теме

(9) DJDUH, ildarovich Мего Мозг в этих делах. Посмотрите его публикации.

11. DJDUH 17 16.02.16 17:45 Сейчас в теме

(10) dj_serega, таки Да!

12. DJDUH 17 16.02.16 18:50 Сейчас в теме

(8) ildarovich, У меня почему-то рекурсия делает более миллиона вариантов на от 1 до 4 и вылетает на нехватку памяти!

13. ildarovich 7865 17.02.16 11:08 Сейчас в теме

(12) DJDUH, могу только предположить, что у вас ошибочно расширена область видимости переменных Результат, Сч, Оп в том модуле, в который вы вставляете функцию. Это может быть, например, при наличии В МОДУЛЕ операторов типа Перем Результат или при наличии реквизита с таким именем. Попробуйте вот такой вариант:

Функция СписокФормул(От, До)
    Перем Результат, Сч, Оп; // для безопасности
    Результат = Новый СписокЗначений;
    Если От >= До Тогда
        Результат.Добавить("n" + От);
        Результат.Добавить("( - n" + От + ")")
    Иначе 
        Для Сч = От По До - 1 Цикл
            ПравыеЧасти = СписокФормул(Сч + 1, До); // для скорости
            Для каждого Слева Из СписокФормул(От, Сч) Цикл
                Для каждого Справа Из ПравыеЧасти Цикл
                    Для Оп = 1 По 3 Цикл
                        Результат.Добавить("(" + Слева + " " + Сред("+*/", Оп, 1) + " " + Справа + ")")
                    КонецЦикла 
                КонецЦикла
            КонецЦикла     
        КонецЦикла 
    КонецЕсли;
    Возврат Результат
КонецФункции // СписокФормул()

Показать

Если не получится, пришлите, пожалуйста всю обработку, которой вы тестируете функцию, посмотрю. А я прилагаю ту обработку, которой тестировал я.

Прикрепленные файлы:

СписокФормул.erf

14. DJDUH 17 17.02.16 14:02 Сейчас в теме

(13) ildarovich, Спасибо, всё получилось!
Как и просили прикрепил обработку. Может по оптимизации она и не проходит, но работает)))

Прикрепленные файлы:

СчиталкаДляВлада®.epf

5. pvvpvv 10 13.02.16 04:18 Сейчас в теме

Даже из результата - 2 есть варианты: бесконечно

15. user680895_Nata1061 29.01.17 19:33 Сейчас в теме

Помогите, пожалуйста, написать программу на Делфи для расстановки +-* среди n чисел, чтобы получить известный результат. Скобки не нужны.

Оставьте свое сообщение

E-mail: