На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (6) [1] 2 3 ...  5 6 все  ( Перейти к последнему сообщению )  
> головоломки на написание алгоритма
    некоторые головоломки таковы, что не имеют ни конкретного ответа(напр "x=42") ни даже диапазона решений( напр "a=2b и |b|<100"), а подразумевают написание алгоритма или программы.

    например, первое задание: можно попробовать написать такую прогу: входной файл содержит некий текст на русском, а эта прога выдаёт выходной файл, в котором содержится весь текст входного файла + такая вот доп.инфа о выходном файле, верная, с учётом всего текста выходного файла(включая доп.инфу):

    Цитата
    В этом предложении есть сорок четыре буквы "а", тридцать четыре буквы "б",
    сорок четыре буквы "в", одна буква "г", тридцать четыре буквы "д",
    двадцать семь букв "е", одна буква "ё", две буквы "ж", одна буква "з",
    тридцать букв "и", одна буква "й", тридцать шесть букв "к", две буквы "л",
    шесть букв "м", девятнадцать букв "н", двадцать букв "о", три буквы "п",
    восемнадцать букв "р", одиннадцать букв "с", тридцать шесть букв "т",
    тридцать четыре буквы "у", одна буква "ф", одна буква "х",
    пятнадцать букв "ц", семь букв "ч", четыре буквы "ш", одна буква "щ",
    одна буква "ъ", восемнадцать букв "ы", двадцать одна буква "ь",
    две буквы "э", одна буква "ю", и три буквы "я".


    для определённости допустим, что входной файл должен содержать не более 1000 русских букв(а другие символы наша прога не подсчитывает).

    и лучше, если доп.инфа будет написана так: "В этом файле есть ..." (не в предложении, а в файле).
    Сообщение отредактировано: ya2500 -
    Зачем кой-кому блокчейн? (полит.тема)
      я понимаю, что скорее всего, этим никто(кроме, быть может, меня) заморачиваться не станет.

      но мне интересно порой заморачиваться подобными вещами и я хотел бы отписываться об этом на форуме. кстати, на эту задачку я наткнулся не сам. на неё навёл Славян.

      Добавлено
      Цитата ya2500 @
      мне интересно порой заморачиваться подобными вещами


      я люблю находить или выдумывать безумные задачки ИЛИ какие-нибудь игры ИЛИ искать стратегии для каких-нибудь игр.
      Зачем кой-кому блокчейн? (полит.тема)
        путь к решению покажется не таким уж сложным, если

        Скрытый текст
        если разбить решение на части:
        для начала можно написать прогу, подсчитывающую лишь буквы "я"(коих может быть от 0 до 1000 в тексте входного файла + ещё не менее одной в тексте доп.инфы):
        Цитата
        Я написал первую версию этой программы, а решением будет тридцать третья её версия!
        =>
        Цитата
        Я написал первую версию этой программы, а решением будет тридцать третья её версия!
        В этом файле есть четыре буквы "я".
        Сообщение отредактировано: ya2500 -
        Зачем кой-кому блокчейн? (полит.тема)
          далее- ясно, что среди букв особую сложность составляют
          Скрытый текст
          такие буквы, которые могут встречаться в числительных. например, таковы буквы "я" и "ь".

          так что первую версию проги лучше писать не для "я", а для какой-нить другой буквы. например, для "ю". чтобы просто отработать числительные.

          и уже не сложно будет сделать вторую версию проги про все буквы, которые нам никогда не встретятся в числительных. их не так уж и много.

          а вот третья версия проги, если в ней добавится ещё и буква "я", то она не для любого текста сможет сформировать выходной файл: допустим, входной текст + остальные слова(не числительные) доп.инфы содержат ровно четыре буквы "я", а вместе с буквой "я" в кавычках- пять. при попытке описать эту ситуацию числом "пять", получим уже шесть букв "я". облом! следующее числительное с буквой "я"- девять, но, ясен пень, что оно(и никакое другое!) не добавит столько букв "я", чтобы получился верный текст.

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

          допустим, в числительных могут встретиться всего 20-ть разных букв(их на самом деле столько или больше). и, допустим, каждая буква в словах, обозначающих одно число строго меньшее 2000, встретится не более 4-х раз, то есть- всего не более 20*4=80 раз в числительных количества всех букв, которые могут встретиться в числительных. допустим, это максимум(это не так, но допустим). тогда числительные, используемые для описания количества букв, которые могут встретиться в числительных, могут добавить гарантированно не более 80 каждых таких букв. получается 80^20 вариантов, среди которых есть смысл искать ответ. многовато, чтобы надеяться решить задачу полным перебором..

          некоторый более тщательный анализ возможной неопределённости мало что дал- можно на несколько порядков снизить количество вариантов, но их всё равно получается слишком дохренища.

          можно попробовать приближаться к решению рандомно, а точный ответ находить перебором.

          то есть- генерим текст, в котором подсчитаны все буквы, но БЕЗ учёта букв в тех числительных, которые описывают количество тех 20-ти букв, которые могут встречаться в числительных.

          если прикидка 80 выше верна(надо будет точнее исследовать этот потолок), то ответом будет набор из 20-ти чисел от 0 до 80, обозначающих количество каждой из 20-ти букв в числительных, встречающихся в описании этих букв.

          генерим сотню совершенно рандомных "ответов".

          оцениваем их, например, по сумме погрешностей подсчёта букв в получившемся тексте.

          для каждого из десяти лучших рандомных "ответов" генерим по девять таких рандомных "ответов", которые от своего родителя уходят не совсем далеко(задана некая дельта).

          из всех этих 10+90 ответов опять выбираем десять лучших и немного уменьшаем дельту.

          вот, похоже, что ответ придётся искать какими-то такими методами. метод имитации отжига надо покурить- он обходит локальные минимумы, с некоторой вероятностью выбирая решения даже хуже родительского, при большой дельте.

          как бы ещё учесть, что суммарно эти 20-ть чисел дают не более 80-ти?


          короч- возникла побочная задача: как можно быстро и равновероятно выбрать один из возможных наборов 20-ти чисел от 0 до 80, дающих в сумме не более 80-ти?
          Сообщение отредактировано: ya2500 -
          Зачем кой-кому блокчейн? (полит.тема)
            Цитата ya2500 @
            можно попробовать приближаться к решению рандомно, а точный ответ находить перебором.
            Думаю, что задача не из серии непрерывных, а потому крохотное отклонение будет вести к принципиально другому случаю. Это будет не спуск к решению, а бег по полю в поиске нужного атома/молекулы в цветочке. Грубо и бесполезно. :oops:
              Цитата Славян @
              Думаю, что задача не из серии непрерывных, а потому крохотное отклонение будет вести к принципиально другому случаю. Это будет не спуск к решению, а бег по полю в поиске нужного атома/молекулы в цветочке. Грубо и бесполезно. :oops:


              да. некрасивая вырисовывается задачка.

              но и такое можно решить.

              в любом случае на следующей неделе дам другую задачку.
              Зачем кой-кому блокчейн? (полит.тема)
                ..

                сложность в том, что удовлетворительным является лишь точное решение. и, хотя, нам достаточно найти одно любое из точных решений, но..

                представьте 21-мерный куб со стороной 80, через который проходит какой-то 20-мерный рельеф(возможно, местами, вылезающий за пределы куба), по которому мы, поисках решения, можем ползать, как муравьи.

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

                так вот: проблема в том, что мы шагаем дискретно и даже минимальное движение на один шаг в одном измерении может дать до +-12 единиц подьёма или спада рельефа. и довольно часто даёт до +-4 единиц.

                то есть- поверхность похожа на график лёгкого шума, на котором нужно найти точку точной высоты.

                пожалуй, мои слова:
                Цитата ya2500 @
                но и такое можно решить

                были не обоснованны.

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

                короч, на этом, я, пожалуй, забью на первое задание.
                Сообщение отредактировано: ya2500 -
                Зачем кой-кому блокчейн? (полит.тема)
                  Цитата ya2500 @
                  и лучше, если доп.инфа будет написана так: "В этом файле есть ..." (не в предложении, а в файле).

                  Адекватного решения к этой задаче может и не быть. Для интереса - решение с входными данными "" как должно выглядеть? Посчитай-ка. :D
                  Долог путь в бессмертие... я еще вернусь.
                  Профильный скилл "Телепатия" 8%
                  ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                  Прошу потестить игру.
                    Цитата Vesper @
                    Адекватного решения к этой задаче может и не быть.
                    Согласен; только слово "Адекватного" излишне.
                      Цитата ya2500 @
                      некоторые головоломки таковы, что не имеют ни конкретного ответа(напр "x=42") ни даже диапазона решений( напр "a=2b и |b|<100"), а подразумевают написание алгоритма или программы.


                      собственно, для решения таких головоломок достаточно представить алгоритм на каком-нибудь понятном языке. поэтому переименовал тему с "головоломки на написание программ" на "головоломки на написание алгоритма". хотя, порой, бывает интересно написать и программу.
                      Зачем кой-кому блокчейн? (полит.тема)
                        Вот такая сверхрацуха пришла в голову: т.к. во фразах 'здесь одна буква "н"' и 'здесь две буквы "н"' явные противоречия, то хорошим способом будет действительно ваш, ya2500, способ подбора близкого решения с перебором (a'la 'здесь две "н"'), а потом добавка к фразе какого-то текста из нужных оставшихся букв!!! Это сильно упрощает задачку, хоть и делает её немножко не честной. ;)

                        Добавлено
                        Типа так:
                        Цитата
                        Здесь две буквы "а", две буквы "н" и не пять, а шесть букв "в".

                        Но всё-равно, детсад какой-то... :'(
                          и переименование темы было с умыслом:

                          Цитата ya2500 @
                          я люблю находить или выдумывать безумные задачки ИЛИ какие-нибудь игры ИЛИ искать стратегии для каких-нибудь игр


                          вот! стратегия игры- это тоже некий алгоритм. и можно в этой теме рассмотреть и их.

                          для разминки дам простую задачку, которую я сам только что придумал и решил.

                          она основана на модификации всем известной и обсосанной игры:

                          на столе лежит N спичек, два игрока поочерёдно берут от 1 до M спичек. проигрывает тот, кто не сможет сделать ход(из-за того, что спички закончились). и это означает выигрыш его соперника.

                          стратегия этой игры широко известна(а если кому не известна то может быть интересно её найти). вот она:
                          Скрытый текст


                          1. если M >= N, то первый игрок сразу может забрать все спички.

                          2. если M < N и (N делится на (M+1) нацело), то:

                          второй игрок может каждым своим ходом брать b = (1+M-a) спичек, где a- количество спичек, взятых первым игроком.

                          тогда, после их первых ходов останется N - (a+b) = N - (M+1) спичек; после вторых ходов останется N - 2*(M+1) спичек; и так далее..

                          в итоге, поскольку N делится на (M+1) нацело, то неизбежно возникнет ситуация, когда после хода второго игрока спичек не останется.

                          3. если M < N и (N не делится на (M+1) нацело), то:

                          остаток от деления N на M+1 является числом от 1 до M. тогда первый игрок, взяв число спичек, равное этому остатку, будет иметь выигрышную стратегию, описанную в п.2.


                          а модификация в следующем:

                          пусть два игрока поочерёдно берут от K до M спичек, где K < M < N. какой будет выигрышная стратегия в этом случае?

                          такая вот несложная разминка. решения я давать не буду- справитесь сами. только, пожалуйста, помещайте решения под спойлер.

                          Добавлено
                          Цитата Славян @
                          т.к. во фразах 'здесь одна буква "н"' и 'здесь две буквы "н"' явные противоречия

                          Скрытый текст

                          вот, куска (одна буква "н") в результирующем файле точно быть не может.

                          можно найти и более сложные утверждения о том, чего не может быть в результирующем файле.

                          и можно анализировать закономерности рельефа нашей 20-ти мерной поверхности. например, при шаге от (одна буква "..") к (две буквы ".."), для любой буквы(в любом из 20-ти измерений), рельеф поднимется или понизится в 21-м измерении одинаково. (21-е измерение отражает суммарную погрешность подсчёта букв).

                          и, кстати- я ранее не учитывал, что для вычисления суммарной погрешности нужно суммировать модули погрешностей. поэтому в предыдущем сообщении на эту тему немного налажал.


                          Добавлено
                          ..

                          в продолжение разминки- менее известная игра "Конфета": задано натуральное число N — "конфета". Игроки по очереди "откусывают" (вычитают от конфеты) натуральное число(больше нуля!), не больше половины от имеющегося кусочка. Проигрывает тот, кто не сможет сделать ход- не сможет ничего откусить по правилам игры.

                          Давайте разберёмся, как в неё играть. "Конфета" величиной в один квант — {1} — проигрышная позиция для того, кто ходит первым. "Конфета" {2} — выигрышная: мы ходим в {1} и выигрываем. Далее: {3} — проигрышная, потому что из неё можно сходить только в конфету {2}. Из {4} можно сходить в {3}, а значит поставить соперника в плохую ситуацию. То есть {4} — выигрышная позиция.

                          сможете найти выигрышную стратегию для общего случая? (надеюсь, я понятно выразился, хотя понятие общего случая- не такая простая вещь).
                          Сообщение отредактировано: ya2500 -
                          Зачем кой-кому блокчейн? (полит.тема)
                            Может придумаете что-то для непрерывного случая? Начало как-то так:
                            "Петя и Маша играют в игру: Петя умеет откусывать у фигуры остроугольный треугольник, а Маша умеет выпекать и прикладывать к стороне фигуры квадрат. Начав с треугольника, ..."
                            Оптимальная стратегия может выдать какой-нибудь красивый фрактальчик. ;)
                              Цитата Славян @
                              Может придумаете что-то для непрерывного случая?


                              ну, в спички можно играть и с действительными числами- из начального числа N спичек брать поочерёдно от K до M спичек, где 0<K<M<N.

                              Добавлено
                              Цитата Славян @
                              "Петя и Маша играют в игру: Петя умеет откусывать у фигуры остроугольный треугольник, а Маша умеет выпекать и прикладывать к стороне фигуры квадрат. Начав с треугольника, ..."
                              Оптимальная стратегия может выдать какой-нибудь красивый фрактальчик.


                              эмм.. а какая может быть цель у такой игры? но да, можно что-то такое придумать.

                              НО я бы двинулся слегка в другом направлении:

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

                              как бы, в сложном есть свой интерес, НО рассмотрение принципиально иного- ещё интереснее. и начать рассмотрение лучше с простого.

                              а в данный момент я думаю над доказательством того, что в шахматах есть беспроигрышная стратегия(по крайней мере у одного из игроков). это не простая задача, но вполне посильная. наверное.
                              Сообщение отредактировано: ya2500 -
                              Зачем кой-кому блокчейн? (полит.тема)
                                Цитата ya2500 @
                                рассмотрение принципиально иного


                                можно ещё рассмотреть игру, в которой прописаны правила изменений правил этой игры (начинается игра всегда с неких стандартных правил, но по ходу игры правила изменяются).

                                лёгкие намёки на такое я видел в паре настольных игр, где можно было голосовать за принятие каких-то "законов".
                                Зачем кой-кому блокчейн? (полит.тема)
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (6) [1] 2 3 ...  5 6 все


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1426 ]   [ 14 queries used ]   [ Generated: 23.09.17, 21:52 GMT ]