В начале 80-х, в студенчестве приобрёл первый советский программируемый калькулятор БЗ-21. Первая серьёзная задача, которую я на нём запрограммировал и решил, была про волка козу и капусту, которых лодочник должен в целости переправить на другой берег. Расчёт по программе длился около суток. Решение было найдено. Предлагаю составить протягиваемую формулу, которая обеспечит проверку возможности решения задачи, т.е. есть ли у задачи решение. Моя формула 142 символа. Вторая задача про миссионеров и людоедов. Решение более длинное, но формула та же самая. 149 символов. Исходные данные можно модифицировать, расширять и перемещать. В разумных пределах. При небольшой модификации исходных данных длина формул 106 и 113 символов. В формуле предусмотреть, чтобы ходы не зациклились и корректно работало направление перемещения лодки. Срок - до 15.08.2016.
[p.s.]С помощью дополнительных формул и текстовых таблиц у меня есть пошаговое словесное описание решения задачи. Типа: Перевёз козу, вернулся, ... В разных ячейках и пока не структурированно. В выходные ещё подумаю.
В начале 80-х, в студенчестве приобрёл первый советский программируемый калькулятор БЗ-21. Первая серьёзная задача, которую я на нём запрограммировал и решил, была про волка козу и капусту, которых лодочник должен в целости переправить на другой берег. Расчёт по программе длился около суток. Решение было найдено. Предлагаю составить протягиваемую формулу, которая обеспечит проверку возможности решения задачи, т.е. есть ли у задачи решение. Моя формула 142 символа. Вторая задача про миссионеров и людоедов. Решение более длинное, но формула та же самая. 149 символов. Исходные данные можно модифицировать, расширять и перемещать. В разумных пределах. При небольшой модификации исходных данных длина формул 106 и 113 символов. В формуле предусмотреть, чтобы ходы не зациклились и корректно работало направление перемещения лодки. Срок - до 15.08.2016.
[p.s.]С помощью дополнительных формул и текстовых таблиц у меня есть пошаговое словесное описание решения задачи. Типа: Перевёз козу, вернулся, ... В разных ячейках и пока не структурированно. В выходные ещё подумаю.Светлый
Вне конкурса. Задачу можно решать следующим образом: имеется 16 возможных состояний из 4х элементов (лодочник, волк, коза, капуста, 2^4 = 16) из которых 10 допустимых состояний и 6 недопустимых (волк+коза, коза+капуста, волк+коза+капуста, каждое состояние без лодочника, умножим на два, т.к. два берега) Возможно 20 вариантов перехода из одного состояния в другое. Составляем граф, где состояния - это вершины графа, а переходы - это ребра графа с весом равным единице Находим кратчайший путь из состояния 1111 (все на одном берегу) в состояние 0000 (все на другом берегу) алгоритмом Дейкстры (или Левита или Форда-Беллмана) Если путь найден - то решение есть и будет найдено кратчайшее решение.
Стоит ли ломать голову и решать все на формулах а не макросом?
Вне конкурса. Задачу можно решать следующим образом: имеется 16 возможных состояний из 4х элементов (лодочник, волк, коза, капуста, 2^4 = 16) из которых 10 допустимых состояний и 6 недопустимых (волк+коза, коза+капуста, волк+коза+капуста, каждое состояние без лодочника, умножим на два, т.к. два берега) Возможно 20 вариантов перехода из одного состояния в другое. Составляем граф, где состояния - это вершины графа, а переходы - это ребра графа с весом равным единице Находим кратчайший путь из состояния 1111 (все на одном берегу) в состояние 0000 (все на другом берегу) алгоритмом Дейкстры (или Левита или Форда-Беллмана) Если путь найден - то решение есть и будет найдено кратчайшее решение.
Стоит ли ломать голову и решать все на формулах а не макросом?MCH
Лен, я понимаю, что в донном разделе нужно "поломать голову". Но как-то не укладывается в голове, реализация алгоритма Дейкстры формулами, без использования вспомогательных ячеек
Лен, я понимаю, что в донном разделе нужно "поломать голову". Но как-то не укладывается в голове, реализация алгоритма Дейкстры формулами, без использования вспомогательных ячеекMCH
реализация алгоритма Декстры формулами, без использования вспомогательных ячеек
Никто ведь не предлагает полностью реализовать алгоритм Декстры. Достаточно выяснить, есть ли путь к решению. Для самого решения конечно потребуются ещё формулы и, возможно, дополнительные ячейки.
реализация алгоритма Декстры формулами, без использования вспомогательных ячеек
Никто ведь не предлагает полностью реализовать алгоритм Декстры. Достаточно выяснить, есть ли путь к решению. Для самого решения конечно потребуются ещё формулы и, возможно, дополнительные ячейки.Светлый
Пока решение вижу с помощью динамического программирования. Все можно реализовать на формулах, не используя макросы. При этом придется задействовать дополнительные ячейки
Пока решение вижу с помощью динамического программирования. Все можно реализовать на формулах, не используя макросы. При этом придется задействовать дополнительные ячейкиMCH
При этом придется задействовать дополнительные ячейки
В моём решении никаких дополнительных ячеек не используется. Формула записывается в светло-зелёные ячейки столбца A и протягивается вниз. Ячейка с целевым результатом =0 подсвечивается ярко-зелёным. Это означает, что решение есть. Каких-то проблем не вижу. Если задача кажется очень сложной, могу дать наводящие подсказки. [p.s.]Откровенно говоря, я думал что профи форума, как всегда, быстро найдут более простое решение. Мне ещё многому можно поучиться у Вас.
При этом придется задействовать дополнительные ячейки
В моём решении никаких дополнительных ячеек не используется. Формула записывается в светло-зелёные ячейки столбца A и протягивается вниз. Ячейка с целевым результатом =0 подсвечивается ярко-зелёным. Это означает, что решение есть. Каких-то проблем не вижу. Если задача кажется очень сложной, могу дать наводящие подсказки. [p.s.]Откровенно говоря, я думал что профи форума, как всегда, быстро найдут более простое решение. Мне ещё многому можно поучиться у Вас.Светлый
Как я понимаю, у сильных формулистов совсем нет времени, а кто ещё не так опытен испытывает трудности с формулировкой алгоритма решения. Даю подсказку. Чтобы получить новое состояние, надо к уже имеющимся состояниям (первоначально одно исходное) прибавить или вычесть ход в зависимости от того, на каком берегу лодка. Можно удвоить список ходов, добавив в него отрицательные, тогда формула изменится. Естественно, надо проверять новые состояния на допустимость и на уникальность, чтобы не произошло зацикливание. После нескольких прибавлений (вычитаний) может получиться целевое состояние =0. Чего мы и добивались. Откликнитесь. Здесь совсем не нужны алгоритмы Декстры. Задачка простая. Я уже оформил формулами словесное описание решения японской задачи, написанной в Excel, про переправу на плоте полицейского, преступника, папы, мамы, двух мальчиков и двух девочек. Можно найти в интернете по названию файла Japanese-IQ-Test_rus.xls. Основная проблема была в том, как разделить все состояния на допустимые и недопустимые, а не в ходе решения. Формулы для разных задач одинаковые, только разные диапазоны и исходные данные.
Как я понимаю, у сильных формулистов совсем нет времени, а кто ещё не так опытен испытывает трудности с формулировкой алгоритма решения. Даю подсказку. Чтобы получить новое состояние, надо к уже имеющимся состояниям (первоначально одно исходное) прибавить или вычесть ход в зависимости от того, на каком берегу лодка. Можно удвоить список ходов, добавив в него отрицательные, тогда формула изменится. Естественно, надо проверять новые состояния на допустимость и на уникальность, чтобы не произошло зацикливание. После нескольких прибавлений (вычитаний) может получиться целевое состояние =0. Чего мы и добивались. Откликнитесь. Здесь совсем не нужны алгоритмы Декстры. Задачка простая. Я уже оформил формулами словесное описание решения японской задачи, написанной в Excel, про переправу на плоте полицейского, преступника, папы, мамы, двух мальчиков и двух девочек. Можно найти в интернете по названию файла Japanese-IQ-Test_rus.xls. Основная проблема была в том, как разделить все состояния на допустимые и недопустимые, а не в ходе решения. Формулы для разных задач одинаковые, только разные диапазоны и исходные данные.Светлый
мы ищем кратчайшее решение (за 7 ходов) или количество ходов может быть существенно больше (например за счет генератора случайных чисел или последовательный перебор), но приводящее к нулю?
мы ищем кратчайшее решение (за 7 ходов) или количество ходов может быть существенно больше (например за счет генератора случайных чисел или последовательный перебор), но приводящее к нулю?MCH
По условию задачи не надо искать кратчайшее решение. Надо выяснить, ЕСТЬ ЛИ решение. По получившемуся списку состояний другими формулами можно выбрать прямую последовательность ходов. Эта последовательность, скорее всего, будет кратчайшая. Это определяет сам алгоритм нахождения новых состояний. Сейчас моя формула 104 символа. Я отказался от использования недопустимых ситуаций и убрал их из столбца A. Формулы, которые создают описательную последовательность решения 125 и 143 символа, но я их не оптимизировал. И в условиях задачи их нет. [offtop]Этот алгоритм я многократно использовал для решения различных головоломок на Delphi. Он обеспечивает кратчайшие решения задач. При нескольких вариантах находятся самые короткие, потом всё длиннее. В Excel, в силу невозможности или сильного усложнения манипулированием выбора из нескольких вариантов, решение может оказаться не оптимальным.
По условию задачи не надо искать кратчайшее решение. Надо выяснить, ЕСТЬ ЛИ решение. По получившемуся списку состояний другими формулами можно выбрать прямую последовательность ходов. Эта последовательность, скорее всего, будет кратчайшая. Это определяет сам алгоритм нахождения новых состояний. Сейчас моя формула 104 символа. Я отказался от использования недопустимых ситуаций и убрал их из столбца A. Формулы, которые создают описательную последовательность решения 125 и 143 символа, но я их не оптимизировал. И в условиях задачи их нет. [offtop]Этот алгоритм я многократно использовал для решения различных головоломок на Delphi. Он обеспечивает кратчайшие решения задач. При нескольких вариантах находятся самые короткие, потом всё длиннее. В Excel, в силу невозможности или сильного усложнения манипулированием выбора из нескольких вариантов, решение может оказаться не оптимальным.Светлый
Программировать проще, чем писать стихи.
Сообщение отредактировал Светлый - Четверг, 11.08.2016, 09:52
К сожалению времени на решение задачи нет, поэтому выкладываю то, что есть. Решение не подходит под условие задачи, тем не менее, при указанной организации данных производится последовательный перебор всех возможных комбинаций, пока не найдется решение.
PS: Все же остаюсь при своем мнении, подобные задачи лучше сводить к графам, и решать их уже известными алгоритмами по поиску кратчайших путей
К сожалению времени на решение задачи нет, поэтому выкладываю то, что есть. Решение не подходит под условие задачи, тем не менее, при указанной организации данных производится последовательный перебор всех возможных комбинаций, пока не найдется решение.
PS: Все же остаюсь при своем мнении, подобные задачи лучше сводить к графам, и решать их уже известными алгоритмами по поиску кратчайших путейMCH
Да, у Вас заранее просчитаны все возможные ходы из всех возможных состояний и эти данные занесены в дополнительную таблицу. Сходимость у Вашего алгоритма есть, но одни и те же состояния просчитываются по несколько раз. Для более длинной задачи это может оказаться проблемой. И я пока с ходу не представляю, как построить обратную цепочку ходов для описания решения.
Абсолютно согласен. Для каждого класса задач свой приоритетный метод решения, тем более, что уже есть готовые программные пакеты. Моя задача чисто для спортивного интереса. Предыдущая моя задача про связную область очень близко перекликается с этой. Это вторая подсказка. Ну кто-нибудь ещё откликнитесь! Почему MCH за всех отдувается?
MCH, работа проделана колоссальная, особенно с учётом дефицита времени!
Да, у Вас заранее просчитаны все возможные ходы из всех возможных состояний и эти данные занесены в дополнительную таблицу. Сходимость у Вашего алгоритма есть, но одни и те же состояния просчитываются по несколько раз. Для более длинной задачи это может оказаться проблемой. И я пока с ходу не представляю, как построить обратную цепочку ходов для описания решения.
Абсолютно согласен. Для каждого класса задач свой приоритетный метод решения, тем более, что уже есть готовые программные пакеты. Моя задача чисто для спортивного интереса. Предыдущая моя задача про связную область очень близко перекликается с этой. Это вторая подсказка. Ну кто-нибудь ещё откликнитесь! Почему MCH за всех отдувается?Светлый
Программировать проще, чем писать стихи.
Сообщение отредактировал Светлый - Пятница, 12.08.2016, 20:09
И я пока с ходу не представляю, как построить обратную цепочку ходов для описания решения.
Разобрался. От начального состояния до целевого все ходы идут подряд. Очень интересное решение. С моей формулой посложнее эту цепочку построить.Светлый
Т.е. Ваше решение не дает путь от начальной до конечной точки? оно только информирует, есть ли решение?
В данном случае применимо динамическое программирование, определяем за сколько наименьшее количество ходов можем попасть в каждое состояние. Макросом решать значительно проще чем формулами. Если не нужно восстанавливать путь от начальной до целевой точки, а только определить решается ли задача или нет, то и работы будет значительно меньше. Кстати, алгоритм Дейкстры упомянутый выше, как раз и решает задачу динамическим программированием. Применительно к данной задаче алгоритм решения можно реализовать значительно проще, чем алгоритм Дейкстры.
Т.е. Ваше решение не дает путь от начальной до конечной точки? оно только информирует, есть ли решение?
В данном случае применимо динамическое программирование, определяем за сколько наименьшее количество ходов можем попасть в каждое состояние. Макросом решать значительно проще чем формулами. Если не нужно восстанавливать путь от начальной до целевой точки, а только определить решается ли задача или нет, то и работы будет значительно меньше. Кстати, алгоритм Дейкстры упомянутый выше, как раз и решает задачу динамическим программированием. Применительно к данной задаче алгоритм решения можно реализовать значительно проще, чем алгоритм Дейкстры.MCH
Выкладываю решение. Если в формуле заменить НАИБОЛЬШЕЕ на НАИМЕНЬШЕЕ, то последовательность ходов может измениться, но решение всё равно будет найдено. MCH, у Вас на этом форуме большой авторитет. Лично я с восхищением изучал Ваши решения. У меня к Вам просьба: не пишите сразу, что решение предложенной задачи невозможно. Некоторые Вам безоговорочно верят и даже не пытаются что-то придумать. Хотя в задании сказано, что решение есть и конкретно указана длина этого решения в символах. Только этим я могу объяснить столь низкую активность в МШ. Как-то не верится, что задача всем показалась совершенно неинтересной или неимоверно сложной. Многим из постоянных участников МШ, судя по их другим решениям, задачка вполне по плечу. [p.s.]Хотелось бы лично от отказавшихся узнать причину, почему они не стали участвовать. Может быть, я непонятно поставил задачу?
Выкладываю решение. Если в формуле заменить НАИБОЛЬШЕЕ на НАИМЕНЬШЕЕ, то последовательность ходов может измениться, но решение всё равно будет найдено. MCH, у Вас на этом форуме большой авторитет. Лично я с восхищением изучал Ваши решения. У меня к Вам просьба: не пишите сразу, что решение предложенной задачи невозможно. Некоторые Вам безоговорочно верят и даже не пытаются что-то придумать. Хотя в задании сказано, что решение есть и конкретно указана длина этого решения в символах. Только этим я могу объяснить столь низкую активность в МШ. Как-то не верится, что задача всем показалась совершенно неинтересной или неимоверно сложной. Многим из постоянных участников МШ, судя по их другим решениям, задачка вполне по плечу. [p.s.]Хотелось бы лично от отказавшихся узнать причину, почему они не стали участвовать. Может быть, я непонятно поставил задачу?Светлый
честно? потому что вообще ни черта не понятно. в файле адская структура данных и ни разу не откомментирована - что используем, что нет, а главное нет того, что надо-то? в обычных темах при таком подходе игнорят, особо скучающие переспрашивают. сейчас, видимо, я сильно скучаю, потому и пишу - хотя для Питера дождь обычное дело как выражался один мой препод "я не знаю как начать думать, чтобы ответить на этот вопрос" причём подсказку читал - только оскорбился - ежу понятная истина, лучше бы предложили альтернативы, авось студентам не на чем тренироваться. Поддерживаю тёзку (MCH) - если есть продуманный подход, зачем изобретать велосипед? - многоэтажные формулы с текстовыми функциями взамен регулярок тому пример
Цитата
почему они не стали участвовать
честно? потому что вообще ни черта не понятно. в файле адская структура данных и ни разу не откомментирована - что используем, что нет, а главное нет того, что надо-то? в обычных темах при таком подходе игнорят, особо скучающие переспрашивают. сейчас, видимо, я сильно скучаю, потому и пишу - хотя для Питера дождь обычное дело как выражался один мой препод "я не знаю как начать думать, чтобы ответить на этот вопрос" причём подсказку читал - только оскорбился - ежу понятная истина, лучше бы предложили альтернативы, авось студентам не на чем тренироваться. Поддерживаю тёзку (MCH) - если есть продуманный подход, зачем изобретать велосипед? - многоэтажные формулы с текстовыми функциями взамен регулярок тому примерbuchlotnik
Сообщение отредактировал buchlotnik - Суббота, 20.08.2016, 19:13
времени катастрафисски не было и моск не хотел думать слепил формулу для минимального количества ходов (вроде работает), немассивная, не использует доп. ячейки, 432 символа уверен, что можно сократить в файле 15 = 1111 (Волк Коза Капуста Лодочник)
времени катастрафисски не было и моск не хотел думать слепил формулу для минимального количества ходов (вроде работает), немассивная, не использует доп. ячейки, 432 символа уверен, что можно сократить в файле 15 = 1111 (Волк Коза Капуста Лодочник)
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
[/offtop]
