Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 54
Хорошая статья, если Вы действительно знаете все языки о которых упомянули - огромный респект :) С выводами спорить не буду, так как незнаком с ИП.
Тяжело пишете. Ну и сравнивать, я думаю, незачем, лучше синтезировать.
Рекурсия совершенно необязательна - есть итеративные способы решения задачи.
Про состояния полезно читать is.ifmo.ru.
Рекурсия совершенно необязательна - есть итеративные способы решения задачи.
Про состояния полезно читать is.ifmo.ru.
Так какая жизнь, так и пишу ( :
По делу. Рекурсия действительно не обязательна - последний вариант это показывает. Но в ФП и ООП рекурсивное решение кажется более естественным, в этом основная мысль. Потому что эти подходы как раз предполагают не синтез решения, а декомпозицию задачи, при этом сразу же. Я же утверждаю, что объекты при проектировании должны не навязываться сверху при проектировании, а возникать при реализации программы, проект которой заключается в описании необходимых преобразований над некими состояними (не автоматными), если в ходе проектирования и программирования этих преобразований будет видно, что возникают некие структуры из данных и алгоритмов, то это прямое указание на модульную декомпозицию, или на классовую, кому как удобнее. Но это следствие того, как происходят преобразования в программе, а не их причина. Не нужно, по моему глубокому убеждению, начинать проектирование с определения модулей и классов. Сами потом появятся.
Эмс... И про автоматы. Те состояния и их изменения, о которых я говорю, это не автоматные состояния и не автоматные изменения. Автомат - это опять же логическая конструкция с постоянными свойствами, которая должна возникать в процессе решения, а не навязываться сверху путём декомпозиции программы на множество этих самых автоматов. Потому что состояния у процессов могут быть потенциально бесконечными, а конечные автоматы с такими объектами оперировать не в состоянии. Нужны как минимум МП-автоматы, но это не панацея. Панацея - это сдвоенные МП-автоматы, которые тъюринг-полные. Которые, кстати, невозможны в рамках подхода иерархических конечных автоматов, которые предлагают авторы указанного Вами сайта.
Но даже если бы были - это же жутко неудобно. Попробуйте в этих автоматах выразить алгоритм пирамидальной сортировки. Конечно, во многих случаях динамика в программе описывается именно конечными автоматами, они очень полезный инструмент. Но во многих случаях они ничем не могут помочь, в преобразованиях данных возникают совсем иные структуры.
По делу. Рекурсия действительно не обязательна - последний вариант это показывает. Но в ФП и ООП рекурсивное решение кажется более естественным, в этом основная мысль. Потому что эти подходы как раз предполагают не синтез решения, а декомпозицию задачи, при этом сразу же. Я же утверждаю, что объекты при проектировании должны не навязываться сверху при проектировании, а возникать при реализации программы, проект которой заключается в описании необходимых преобразований над некими состояними (не автоматными), если в ходе проектирования и программирования этих преобразований будет видно, что возникают некие структуры из данных и алгоритмов, то это прямое указание на модульную декомпозицию, или на классовую, кому как удобнее. Но это следствие того, как происходят преобразования в программе, а не их причина. Не нужно, по моему глубокому убеждению, начинать проектирование с определения модулей и классов. Сами потом появятся.
Эмс... И про автоматы. Те состояния и их изменения, о которых я говорю, это не автоматные состояния и не автоматные изменения. Автомат - это опять же логическая конструкция с постоянными свойствами, которая должна возникать в процессе решения, а не навязываться сверху путём декомпозиции программы на множество этих самых автоматов. Потому что состояния у процессов могут быть потенциально бесконечными, а конечные автоматы с такими объектами оперировать не в состоянии. Нужны как минимум МП-автоматы, но это не панацея. Панацея - это сдвоенные МП-автоматы, которые тъюринг-полные. Которые, кстати, невозможны в рамках подхода иерархических конечных автоматов, которые предлагают авторы указанного Вами сайта.
Но даже если бы были - это же жутко неудобно. Попробуйте в этих автоматах выразить алгоритм пирамидальной сортировки. Конечно, во многих случаях динамика в программе описывается именно конечными автоматами, они очень полезный инструмент. Но во многих случаях они ничем не могут помочь, в преобразованиях данных возникают совсем иные структуры.
А почему ФП и ООП - рекурсия-то?
Неужели нельзя запрограммировать линейно?
Неужели нельзя запрограммировать линейно?
Можно, но линейный вариант не естественнен для этих подходов. Решения принимаются уводящие программу в другую сторону.
Подход программирования - не определяет алгоритм решения задачи.
Другое дело - если вы говорите о возможностях самого языка программирования.
Другое дело - если вы говорите о возможностях самого языка программирования.
Меня вот что настрожило:
Лично я в этот момент прочтения не подумал там ни про какие кружки, а только 3 стека, заполняемых цифрами.
Но теперь объектно ориентированных подход. Сперва надо выделить объекты. Ну с этим всё просто: кружки и стержени, а так же сама башенка...
Лично я в этот момент прочтения не подумал там ни про какие кружки, а только 3 стека, заполняемых цифрами.
гораздо ближе к физической реальности, чем объекты или функции, потому что нет ни объектов, ни функций в природе
Ну знаете, таким нигилизмом можно ведь всё отрицать. Но динамизм присутствует лишь в алгоритмах (типа ханойских башен, сортировки и т.п.), а в большинстве своем все же философская статика. Так что тут однобокий взгляд, но интересный)
Интересно
Во-первых, любую рекурсию можно переписать циклами. Иногда мы при этом получим некоторое преимущество - но далеко не всегда. Это раз.
Во-вторых, я не совсем понял где происходит перекладывание бесконечной ханойской башни?
Т.е. как можно даже в последнем листинге обойтись без определения N и вообще как об этом можно говорить, если изначально заданы списки (надо полагать - конечные)?
Во-третьих, вот это:
Это ничего не доказывает, это вообще какая-то ересь, извините...
Поясните немножко, может я просто что-то неправильно понял?
Во-вторых, я не совсем понял где происходит перекладывание бесконечной ханойской башни?
Т.е. как можно даже в последнем листинге обойтись без определения N и вообще как об этом можно говорить, если изначально заданы списки (надо полагать - конечные)?
Во-третьих, вот это:
а бесконечную башенку обсчитывать можно было бы только в функциональных языка с полностью ленивым исполнением, в рамках самой же lamda-абстракции такое вычисление будет невычислимым. Что ещё раз, кстати, доказывает, что компьютер - это гораздо больше, чем машина Тьюринга.
Это ничего не доказывает, это вообще какая-то ересь, извините...
Поясните немножко, может я просто что-то неправильно понял?
Где именно ересь? В том, что компьютер - больше машины Тьюринга? Так это очевидно: у МТ нет устройства для ввода/вывода, в том числе и для ввода/вывода новых программ, а у компьютера есть.
И на все три пункта. Цель не в том, чтобы сравнить языки по мощности, а в том, чтобы показать, как подходы к проектированию влияют на конечный результат. Там прямо в тексте написано, что линейный вариант с переименованием списков можно реализовать и на Haskell в виде функций над монадами (хоть это и потребует шаманства некоторого), и в виде объектов, но это не первая мысль, которая приходит в голову при построении программ в рамках функциональной и ОО парадигм. Первое, что приходит в голову - это разложение на очевидные объекты, которые мы берём из своего материального или математического представления о программе. Но на деле 'существующим' в процессе вычисления может быть нечто иное.
Без определения N можно просто запустить бесконечный цикл. На каждом шаге, конечно, списки будут конечными, но само вычисление может продолжаться бесконечно долго, конечно, оно будет не менее ресурсоёмким, чем рекурсия - понадобиться постепенное наращивание памяти и так далее. НО хоть какие-то результаты можно будет получать уже во время вычислений, а рекурсия будет просто молча бесконечно долго спускаться к решению.
И на все три пункта. Цель не в том, чтобы сравнить языки по мощности, а в том, чтобы показать, как подходы к проектированию влияют на конечный результат. Там прямо в тексте написано, что линейный вариант с переименованием списков можно реализовать и на Haskell в виде функций над монадами (хоть это и потребует шаманства некоторого), и в виде объектов, но это не первая мысль, которая приходит в голову при построении программ в рамках функциональной и ОО парадигм. Первое, что приходит в голову - это разложение на очевидные объекты, которые мы берём из своего материального или математического представления о программе. Но на деле 'существующим' в процессе вычисления может быть нечто иное.
Без определения N можно просто запустить бесконечный цикл. На каждом шаге, конечно, списки будут конечными, но само вычисление может продолжаться бесконечно долго, конечно, оно будет не менее ресурсоёмким, чем рекурсия - понадобиться постепенное наращивание памяти и так далее. НО хоть какие-то результаты можно будет получать уже во время вычислений, а рекурсия будет просто молча бесконечно долго спускаться к решению.
Хорошо, я понял. По сути могу сказать, что при решении головоломок или олимпиадных задач конечно стоит отказаться от шаблонных парадигм проектирования софта, но на практике при разработке коммерческого ПО подобное "свободное алгоритмическое мышление" не даст ничего, кроме полной неразберихе в коде. Промышленное, если так можно выразится программирование и есть основное применение ООП. ФП - больше поджходит для математического моделирования и прочих научных задач...
А по-поводу машины Тьюринга - все-таки не стоит так - это некорректно. Ну причем тут ввод/вывод?
Абстракция МТ - включает в себя как подмножество и частный урезанный случай - любые существующие на сегодняшний день вычислительные машины. И то что МТ не оснащена ТФТ дисплеем и жестким диском - тут не причем, на то она и математическая модель, а не предмет.
А по-поводу машины Тьюринга - все-таки не стоит так - это некорректно. Ну причем тут ввод/вывод?
Абстракция МТ - включает в себя как подмножество и частный урезанный случай - любые существующие на сегодняшний день вычислительные машины. И то что МТ не оснащена ТФТ дисплеем и жестким диском - тут не причем, на то она и математическая модель, а не предмет.
а ввод не нужен в абстракции МТ - потому что лента - бесконечна! ))
Лента не служит для обмена данными. Это лишь устройство для хранения промежуточных данных во время работы алгоритма.
Но ведь любые данные подбираемые программой на реальной машине с устройств ввода - могут быть помещены на ленту бесконечной длины. Это ведь формализм. Зачем плодить сущности без надобности? Устройства ввода-вывода - следствие ограничений накладываемых физической реализацией и прикладным значением машины - мат.модели все это не нужно.
В формализме МТ нет никакого помещения данных на ленту. Данные выкладываются в начале работы, и впоследствии только машина их может менять. Считываются они по окончании. Во время работы никто не может новые данные классической машине предоставить. В этом суть математической абстракции. Машина со вводом/выводом - это уже совсем другая по своим математическим свойствам конструкция, которая берёт данные из вне во время своей работы.
МТ + очередь обслуживания запросов = это та же МТ,
(очередь - это только ввод, вывод - не влияет на модель)
в ячейках которого как можно было бы полагать изменяются данные, но все это сводится к МТ у которой эти ячейки - выстроены в бесконечную последовательность на линейке ячеек МТ.
Никакими другими грандиозными свойствами эта машина не уделена.
(очередь - это только ввод, вывод - не влияет на модель)
в ячейках которого как можно было бы полагать изменяются данные, но все это сводится к МТ у которой эти ячейки - выстроены в бесконечную последовательность на линейке ячеек МТ.
Никакими другими грандиозными свойствами эта машина не уделена.
Вы не правы, к сожалению. То, что вы описали не сводится к MT. Потому что я вам запросту предоставлю ввод, для которого вы не построите ленту для МТ, однако компьютеры с этим вводом будут работать. Например, пускай на вводе случайная величина. Если вы вы попытаетесь разместить последовательность её значений на ленте, то это (1) результирующая лента не будет случайной величиной и (2) для размещения на ленте потребуется бесконечно много времени.
Компьютер (MT c вводом\выводом) же может с такой последовательностью производить осмысленные операции, например, считать текущее математическое ожидание. А другая машина может этим пользоваться для своей активности, и так далее.
Классическая же МТ даже не сможет начать работать с этим входным потоком, ведь его изначально надо будет разместить на ленте.
Компьютер (MT c вводом\выводом) же может с такой последовательностью производить осмысленные операции, например, считать текущее математическое ожидание. А другая машина может этим пользоваться для своей активности, и так далее.
Классическая же МТ даже не сможет начать работать с этим входным потоком, ведь его изначально надо будет разместить на ленте.
А вот и нет. Отсутсвие ввода/вывода - это серьёзная деталь классической МТ. Математическая модель МТ с регистром ввода/вывода - значительно отличается от классики. Например, среди таких машин нет универсальной машины, а сеть из них является гиперкомпьютером, то есть, способна решать алгоритмически неразрешимые на классической МТ задачи.
Ну, естесственно, математическая модель машины не покрывает сеть машин. )
Речь о том, что из классических МТ сеть даже нельзя собрать. Из МТ с вводом/выводом - можно, и математические свойства у них совсем другие.
Неужели нельзя? А как же многопоточность вычислений?
Можно, но N параллельно работающих классических машин Тьюринга - это то же самое по своей мощности, что и одна классическая машина Тьюринга.
И потом. В обычном компьютере задачи могут во время вычислений обмениваться данными. В классической MT никаких обменов со внешним миром во время работы не предусматривается - это самое важное отличие от машины с вводом/выводом. Это влияет на то, что машина может делать и с какими данными оперировать, и на математические свойства модели (в очередной раз повторяюсь).
И потом. В обычном компьютере задачи могут во время вычислений обмениваться данными. В классической MT никаких обменов со внешним миром во время работы не предусматривается - это самое важное отличие от машины с вводом/выводом. Это влияет на то, что машина может делать и с какими данными оперировать, и на математические свойства модели (в очередной раз повторяюсь).
Ещё одно важное свойство: бесконечно много МТ, работающий параллельно так же вычислительно эквивалентны одной МТ, по той причине, что данные нужно выложить на ленты до начала вычислений. А дальше каждая начнёт мариновать данные по своему усмотрению, и они никак не смогут повлиять на ход вычислений в других машинах.
Бесконечное множество МТ с I/O, способные друг другу сообщать о результатах расчётов - не эквивалентны одной такой машине, и обладают огромной вычислительной мощностью.
Возможно, конечно, представить машину с I/O цепочкой классических машин, которые обрабатывают данные друг за дружкой, но эта цепочка должна быть (1) бесконечной, следовательно (2) эта модель не сводится к классической МТ, обладающей лишь конечным числом состояний.
Бесконечное множество МТ с I/O, способные друг другу сообщать о результатах расчётов - не эквивалентны одной такой машине, и обладают огромной вычислительной мощностью.
Возможно, конечно, представить машину с I/O цепочкой классических машин, которые обрабатывают данные друг за дружкой, но эта цепочка должна быть (1) бесконечной, следовательно (2) эта модель не сводится к классической МТ, обладающей лишь конечным числом состояний.
В любом случае, физический процессор с регистрами и памятью вместо бесконечной ленты - сводится к МТ (даже потранзисторно!!).
Так что сказать "компьютер больше чем МТ" - нельзя.
Так что сказать "компьютер больше чем МТ" - нельзя.
Не сводится. Потому что в процессор способен обрабатывать прерывания, а в память компьютера данные могут записываться устройствами ввода\вывода, во время работы программ. Для МТ это не так.
Ввод данных - это очередь?
На МТ - можно реализовать счетчик?
По счетчику - можно считать адреса?
По адресам - можно прочитать данные?
Данные со счетчиком - образуют очередь?
очередь = ввод данных - волне определима привычными средствами МТ?
Если на какой-то вопрос вы ответили Нет - то значит ваши суждения вышли за рамки определения модели МТ, и то что вы хотите обсудить - это либо теория обслуживания с обратной связью, либо каким-то другим образом включите оператора машины в свою модель.
На МТ - можно реализовать счетчик?
По счетчику - можно считать адреса?
По адресам - можно прочитать данные?
Данные со счетчиком - образуют очередь?
очередь = ввод данных - волне определима привычными средствами МТ?
Если на какой-то вопрос вы ответили Нет - то значит ваши суждения вышли за рамки определения модели МТ, и то что вы хотите обсудить - это либо теория обслуживания с обратной связью, либо каким-то другим образом включите оператора машины в свою модель.
Вы забыли ещё один вопрос задать: как размещаются данные на ленте, которые формируют входящие данные? Математическая модель МТ ТРЕБУЕТ, чтобы ВСЕ данные были размещены ДО начала вычислений. Обычный современный компьютер в этом значительно отличается от классической МТ. Значительно, потому что модели алгоритмов, которые пытаются учесть это свойство, такие как МТ с регистром ввода/вывода, обладают существенно другими математическими свойствами, о которых уже было сказано.
Перечислите свойства.
Конечно, любая модель с обобщением на переменные или попросту вероятностные входящие данные - будет иметь свойства зависимости от самого обобщения.
Но с утверждением, что МТ с вводом и выводом - нечто другое, я не согласен!
Конечно, любая модель с обобщением на переменные или попросту вероятностные входящие данные - будет иметь свойства зависимости от самого обобщения.
Но с утверждением, что МТ с вводом и выводом - нечто другое, я не согласен!
Увидел только одно "свойство":
Я не могу вести полемику в условиях нестрогой определенности этих вещей в твоих словах.
Определи, пожалуйста, термины "мощность", "ввод", "вывод" и "эквивалентность машин"
MT с I/O, способные друг другу сообщать о результатах расчётов - не эквивалентны одной такой машине, и обладают огромной вычислительной мощностью.
Я не могу вести полемику в условиях нестрогой определенности этих вещей в твоих словах.
Определи, пожалуйста, термины "мощность", "ввод", "вывод" и "эквивалентность машин"
А почему по вашему мнению теорема о существовании\не существовании универсальной машины - это не свойство модели?
Понятия мощность и эквивалентность - обычные из математической логики. Хм... Ну. Так и быть, дам определения:
Мощность - это множество задач, для которых существует алгоритм в рамках этой модели. Чем больше задач во множестве, тем модель мощнее.
Для алгоритмов в разных моделях эквивалентность определяется следующим образом: пусть A и B - преобразования над входом, выполняемые двумя алгоритмами соответсвенно. Пусть алгоритмам на вход могут быть поданы данные из множеств IA и IB, а в результате алгоритмы выдают результаты в виде элементов множеств OA и OB, соответсвенно. Если существуют изморофизмы o: OB -> OA и i: IA -> IB, такие, что o(B(i(x)) = A(x), то алгоритмы A и B называются эквивалентными.
МТ с вводом/выводом - это обычная машина Тьюринга с дополнительными регистрами ввода (вывода), в которых в каждый момент времени может присутствовать один из символов алфавита ленты. А множество комманд такой машины, кроме классических, включает так же в себя комманды вида a, S1 -> get (set), S2, где put означает запись на ленту символа из регистра ввода (чтение с ленты буквы и помещение её в региср вывода).
Понятие вычислимости здесь иное. Считается, что такая машина вычисляет функцию (или уже можно говорить об операторах), если в регистр ввода подаётся последовательность букв, кодирующая input задачи, а на выходе получается последовательность, кодирующая output.
Последовательности потенциально могут быть бесконечными, и это ни сколько не противоречит теоретическим возможностям компьютера: например, очень устойчивая база данных.
Понятия мощность и эквивалентность - обычные из математической логики. Хм... Ну. Так и быть, дам определения:
Мощность - это множество задач, для которых существует алгоритм в рамках этой модели. Чем больше задач во множестве, тем модель мощнее.
Для алгоритмов в разных моделях эквивалентность определяется следующим образом: пусть A и B - преобразования над входом, выполняемые двумя алгоритмами соответсвенно. Пусть алгоритмам на вход могут быть поданы данные из множеств IA и IB, а в результате алгоритмы выдают результаты в виде элементов множеств OA и OB, соответсвенно. Если существуют изморофизмы o: OB -> OA и i: IA -> IB, такие, что o(B(i(x)) = A(x), то алгоритмы A и B называются эквивалентными.
МТ с вводом/выводом - это обычная машина Тьюринга с дополнительными регистрами ввода (вывода), в которых в каждый момент времени может присутствовать один из символов алфавита ленты. А множество комманд такой машины, кроме классических, включает так же в себя комманды вида a, S1 -> get (set), S2, где put означает запись на ленту символа из регистра ввода (чтение с ленты буквы и помещение её в региср вывода).
Понятие вычислимости здесь иное. Считается, что такая машина вычисляет функцию (или уже можно говорить об операторах), если в регистр ввода подаётся последовательность букв, кодирующая input задачи, а на выходе получается последовательность, кодирующая output.
Последовательности потенциально могут быть бесконечными, и это ни сколько не противоречит теоретическим возможностям компьютера: например, очень устойчивая база данных.
Вы определили эквивалентность алгоритмов, а не машин, ну да ладно...
Основное твое суждение было таким: МТ и МТ+I/O не эквивалентны, потому что вторая машина - мощнее, так?
Тогда приведите хотя бы одну задачу, алгоритм решения которого может быть построен на второй, но не может быть построен на первой машине.
Основное твое суждение было таким: МТ и МТ+I/O не эквивалентны, потому что вторая машина - мощнее, так?
Тогда приведите хотя бы одну задачу, алгоритм решения которого может быть построен на второй, но не может быть построен на первой машине.
Вы уже такие примеры привели - системы с обратной связью. Сервер какой-нибудь, или, более формальный пример: дана случайная величина x(t) (t - дискретное время), с областью значений {3, 4, 5}, вычислить случайную величину 2x(t).
Вот. Конечно, такую задачу можно решить организовав систему обслуживания, с классической MT в центре, которая умножает конкретное число на два. Но вся система уже не будет эквивалентна МТ в строгом смысле. Хотя бы по той причине, что всевозможных случайных величин континуум, а всевозможных лент у любой МТ - счётное количество.
Вот. Конечно, такую задачу можно решить организовав систему обслуживания, с классической MT в центре, которая умножает конкретное число на два. Но вся система уже не будет эквивалентна МТ в строгом смысле. Хотя бы по той причине, что всевозможных случайных величин континуум, а всевозможных лент у любой МТ - счётное количество.
Так в чем задача-то?
Дана случайная величина x(t) - хорошо.
Распределим по ленте эти случайные величины.
Дальше построим счетчик по этим ячейкам.
Дальше - рализуем суммирование - результирующую ячейку - можете считать выводом, а можно расположить его в другую сторону ленты - тоже со счетчиком....
Задача реализуема с помощью МТ
Дана случайная величина x(t) - хорошо.
Распределим по ленте эти случайные величины.
Дальше построим счетчик по этим ячейкам.
Дальше - рализуем суммирование - результирующую ячейку - можете считать выводом, а можно расположить его в другую сторону ленты - тоже со счетчиком....
Задача реализуема с помощью МТ
Другое дело - если вам нужен генератор этих случайных чисел...
Но это не МТ - генерирует эти числа.
Т.е. тут вы говорите о системе МТ + генератор случайных данных (черный ящик) а не о МТ, способном принимать и отдавать
Но это не МТ - генерирует эти числа.
Т.е. тут вы говорите о системе МТ + генератор случайных данных (черный ящик) а не о МТ, способном принимать и отдавать
Странно. ПОчему у вас есть только объект башня. У вообще присутствует несколько больше типов объектов. Если рассматривать так, то алгоритм у вас будет линейный, а не рекурсивный.
PS У меня такое ощущение, что в к ООП применяете функциональный подход.
PS У меня такое ощущение, что в к ООП применяете функциональный подход.
Хм... А какие ещё объекты, например?
Стержни и кольца. Башенка же у вас состоит из колец. Если вы допустите что башенка состоит из стержня и колец, то это начнет укладываться в линейный алгоритм.
Всего-то: 3 стека, заполняемых цифрами.
Эмс, и какой из этих трёх стеков получается алгоритм, основанный на посылках сообщений друг дружке? И где тот объект, которому надо послать сообщений solve или move, чтобы он выдал объект - решение?
+ еще один класс (фасад) Game и можно добавить класс - ход Step:
Game game(new Stack(10), new Stack(), new Stack());
while (!game.isCompleted)
{
Step step = game.getNextStep();
game.move( step );
}
А дальше? Описание самих методов getnextstep и move в терминах объектов и сообщений, отправляемых им?
getNextStep() - для ханойской башни имеет вполне определенный алгоритм,
нечто похожее на:
a → b
a → c
b → c
a → b
c → a
c → b
a → b
a → c
и т.д. где каждая итерация зависит от текущего состояния.
И даже без информации о предыдущих ходах, этот алгоритм имеет решение.
Ровно так как крестики-нолики.
Рекурсия здесь неуместна...
нечто похожее на:
a → b
a → c
b → c
a → b
c → a
c → b
a → b
a → c
и т.д. где каждая итерация зависит от текущего состояния.
И даже без информации о предыдущих ходах, этот алгоритм имеет решение.
Ровно так как крестики-нолики.
Рекурсия здесь неуместна...
Ещё раз повторю свой запрос: пожалуйста, приведите алгоритм в виде посылок сообщений, учавствующим в предлагаемой модели игры объектам.
По идее, следующее должно стать очевидным. (1) такая опять же априорная модель разбиеня задачи, которая опирается на понятия, существующие в голове программиста, до анализа решения: стержни очень похожи на стек, следовательно, да будет стек в модели - не полная. Для построения эффективного генератора последовательности ходов, по идее, должен понадобиться объект 'самый мелкий кружочек', который должен будет хранить информацию о предыдущем её перемещении.
(2) Такой алгоритм тоже не сможет начать строительство программы ходов для бесконечной башенки, он будет опираться на значения, записанные в стек, а в стек не влезет бесконечная башенка. Можно, конечно, и тут ООП показывает свою приятную сторону, один из стеков сделать таким, что он никогда не пуст и выдаёт (N + 1), когда выполняется pop, а он пуст.
Но этот подход по сравнению с переписыванием программы, которое (подчеркну) достаточно просто возникает при взгляде на то, какие процессы происходят при перемещении кружочков, и требует чуть больше интеллектуальных усилий, что и рекурсивные построения, будет требовать всё более и более длинные ячейки для хранения элементов стека. То есть, понадобится реализовать ещё один объект: число с переменной длинной. Ещё немного головной боли ОО программисту, imho.
P.S. пример с крестиками и ноликами очень хорош: классическая машина Тьюринга не может сыграть в крестики и нолики, а компьютер может.
По идее, следующее должно стать очевидным. (1) такая опять же априорная модель разбиеня задачи, которая опирается на понятия, существующие в голове программиста, до анализа решения: стержни очень похожи на стек, следовательно, да будет стек в модели - не полная. Для построения эффективного генератора последовательности ходов, по идее, должен понадобиться объект 'самый мелкий кружочек', который должен будет хранить информацию о предыдущем её перемещении.
(2) Такой алгоритм тоже не сможет начать строительство программы ходов для бесконечной башенки, он будет опираться на значения, записанные в стек, а в стек не влезет бесконечная башенка. Можно, конечно, и тут ООП показывает свою приятную сторону, один из стеков сделать таким, что он никогда не пуст и выдаёт (N + 1), когда выполняется pop, а он пуст.
Но этот подход по сравнению с переписыванием программы, которое (подчеркну) достаточно просто возникает при взгляде на то, какие процессы происходят при перемещении кружочков, и требует чуть больше интеллектуальных усилий, что и рекурсивные построения, будет требовать всё более и более длинные ячейки для хранения элементов стека. То есть, понадобится реализовать ещё один объект: число с переменной длинной. Ещё немного головной боли ОО программисту, imho.
P.S. пример с крестиками и ноликами очень хорош: классическая машина Тьюринга не может сыграть в крестики и нолики, а компьютер может.
Кстати : ) Вы тоже начинаете демонстрировать то, что я предписываю ОО проектированию - начали описывать всё сверху. Но тут возникают вопросы, а от куда вдруг стало известно, что nextstep и move - наилучший интерфейся для игры? От куда известно заранее, что такой интерфейс не ограничит вас в дальнейшем в выборе алгоритма решения задачи, не приведёт к лишним вспомогательным вычислениям?
Давайте разберёся с этим примером до конца. Итак, теперь у нас три стека и класс game с указанным интерфейсом, что дальше?
Давайте разберёся с этим примером до конца. Итак, теперь у нас три стека и класс game с указанным интерфейсом, что дальше?
Да, именно сверху! И приведенный класс game - имеет такую структуру, потому что подумал про возможность отобразить ходы во время вычислений.
Однако, ничто не мешает сделать еще один метод: getOptimalSolution() который возвращает массив из Step-ов?
Однако, ничто не мешает сделать еще один метод: getOptimalSolution() который возвращает массив из Step-ов?
Тык. Об этом и речь. Если мне понадобиться другое вычисление, то нужно будет поменять интерфейс, а если мы поменяем интерфейс, то не поменяется ли внутреннее представление данных? Не появиться ли необходимость всё переписать заново?
В императивном же варианте решения, у меня все данные будут торчать наружу. И я в любой момент смогу начать визуализацию, хоть в параллельном режиме, просто скопировав некоторые данные на stdout или передав их другой нити.
Это можно запроектировать и в объектной модели, но это потребует очень многих размышлений, которые вобщем-то будут не самыми очевидными. А императивное программирование нужные интерфейсы, в конце концов выявит в процессе программирования.
В императивном же варианте решения, у меня все данные будут торчать наружу. И я в любой момент смогу начать визуализацию, хоть в параллельном режиме, просто скопировав некоторые данные на stdout или передав их другой нити.
Это можно запроектировать и в объектной модели, но это потребует очень многих размышлений, которые вобщем-то будут не самыми очевидными. А императивное программирование нужные интерфейсы, в конце концов выявит в процессе программирования.
Это то, что называется, круг замкнулся :)) Конечно, у использования ассемблера есть некоторые преимущества, например быстродействие программ... ;)
Смотри, ведь ты, просто, рассмотрел концепцию рекурсии и выявил ее положительные (те возможности, которые она дает) и отрицательные стороны (ограничения, которые накладываются) [Кстати, это вообще-то должны понимать все, кто ее использует]. Разумеется, рекурсия — не универсальный подход на все случаи жизни и никто его не навязывает. Но причем здесь ООП и ФП? Ведь это парадигмы, которые выработались из того, как программисты за программистами смотрели на одни и те же типичные задачи. У каждой есть свои ограничения, но именно в этих ограничениях и заложена их полезность.
А так, разве не каждая задача требует индивидуального подхода, и может быть решена разными способами, ни один из которых не является оптимальным? Наверно, потому, что много часто взаимоисключаемых критериев оптимальности...
Смотри, ведь ты, просто, рассмотрел концепцию рекурсии и выявил ее положительные (те возможности, которые она дает) и отрицательные стороны (ограничения, которые накладываются) [Кстати, это вообще-то должны понимать все, кто ее использует]. Разумеется, рекурсия — не универсальный подход на все случаи жизни и никто его не навязывает. Но причем здесь ООП и ФП? Ведь это парадигмы, которые выработались из того, как программисты за программистами смотрели на одни и те же типичные задачи. У каждой есть свои ограничения, но именно в этих ограничениях и заложена их полезность.
А так, разве не каждая задача требует индивидуального подхода, и может быть решена разными способами, ни один из которых не является оптимальным? Наверно, потому, что много часто взаимоисключаемых критериев оптимальности...
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
OOP, IP, FP и Ханойские башни