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

    Первое, что пришло на ум: закодировать ключ 8-ю вагонами-битами, отсутствие света 0, присутствие 1. 2 ^ 32 вариантов, шанс случайного совпадения крайне низок
    char *out = "|*0>78-,+<|"; size_t cc = char_traits<char>::length(out);
    for (size_t i=0;i<cc;i++){cout<<static_cast<char>((out[i]^89));}cout<<endl;


    user posted image Чат Исходников в СкайпеНе тормози, форум теперь здесь!Чат Исходников в Дискорде
      Цитата B.V. @
      шанс случайного совпадения крайне низок

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

      а вот ЗАДАЧКА именно для программистов: нужно написать прогу(а лучше- алгоритм).


      ДАНО: дан входной файл, состоящий из конечного кол-ва строк вида:

      <номер строки>. LET <имя переменной>= <логическое выражение>;
      <номер строки>. IF <логическое выражение> GO TO <номер строки>;
      <номер строки>. END.

      где
      <номер строки> - это просто какие-то уникальные номера, которые служат метками строк.
      <имя переменной> - допустимы всего два имени переменных: A и B. все переменные имеют булевский тип.
      <логическое выражение>- может быть..
      .. либо числом 0 или 1(понимаются как булевские FALSE и TRUE),
      .. либо переменной (A или B),
      .. либо конструкцией вида not(<логическое выражение>)

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

      НАДО: написать по-возможности простую прогу, для определения того, может ли зациклиться прога, представленная во входном файле, или же она достигнет END за конечное время при любых начальных значениях переменных A и B

      простота оценивается по следующим параметрам: краткость кода, использование минимального набора операторов, НЕ использование средств, специфичных для какого-то конкретного языка программирования.

      вот, как-то так, если склероз мне не изменяет память.
      Сообщение отредактировано: ya2500 -
      "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
      "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
        Скрытый текст
        1) смотрим метку END. и смотрим, откуда она вызывается.
        2)Далее смотрим те строки, откуда она вызывается.
        3)Далле смотрим, откуда вызываются строки, вызвающие END. и т.д.
        4)Если дошли до 1й строки (несколькими способами даже), то смотрим, при каких значениях А и В вызывается строка, вудущая к END. Если при всех, то проверяем, какие параметры вызвают вызов тртьей ступени и т.д.
        5)Ели выходит, что END. вызывается при любых А и В, то све нормально, если мы к END можем прийти не всегда, то не все нормально :whistle:
        Сообщение отредактировано: Alexander N -
          Alexander N, и первую задачку ты тоже первый правильно решил: крут! тока спрячь решение под спойлер. хоть оно и простое, но мож кому будет интересно подумать.

          Добавлено
          сам я правильного решения не знаю, НО более простой алгоритм вряд ли возможно придумать.
          "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
          "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
            Отлично, вот вам задачка, взрывающая мозг:

            Есть массив из нечётного количества элементов, в массив записаны некоторые значения по два раза, но существует такой элемент массива, который встречается только один раз. Требуется найти этот элемент - сила алгоритма O от N

            Добавлено
            З.Ы. Оказывается эти занятия называются - спортивное программирование :lol:
              Цитата Serafim @
              спортивное программирование

              буду теперь знать, что гуглить))
              "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
              "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                --

                интересно, а если текст входного файла склеен из:
                1. проги, проверяющей завершимость всей программы, представленной входным файлом
                2. остальной части, которая запускается, если принято решение о завершимости
                :crazy:

                Скрытый текст
                и, сразу подумалось, что если 2-я часть будет просто тупо зацикливаться, то первая часть должна принять решение о том, что входной файл не завершим, и значит не надо запускать 2-ю часть на исполнение. таким образом, вся программа, представленная входным файлом вполне себе завершима.. такс-c, захотелось расписать эту прогу по нумерованным строкам)) но я слишком ленив для этого. НО интересно- что же из этого получится?


                Добавлено
                --

                Цитата Serafim @
                чно, вот вам задачка, взрывающая мозг:

                Есть массив из нечётного количества элементов, в массив записаны некоторые значения по два раза, но существует такой элемент массива, который встречается только один раз. Требуется найти этот элемент - сила алгоритма O от N

                простое решение:
                Скрытый текст
                складывать все значения в одну переменную побитным исключающим или(XOR)
                Сообщение отредактировано: ya2500 -
                "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                  Цитата ya2500 @
                  простое решение:

                  Правильно :lol: Мне уже и задавать-то нечего. :(
                    ну, есть у меня задачка от меня лично, НО она не честная в том плане, что это не задачка, а то, что я хотел бы сделать. а именно:
                    Скрытый текст
                    интересно бы составить такую прогу, которая получала бы входное число N, и строила бы в квадрате NxN популяцию, развитие которой по правилам Конвея(игра "жизнь") представляло бы из себя цикл с числом _различных_ состояний == N. ну, и ещё эта популяция на каждом шаге развития должна оставаться строго в пределах заданного квадрата, и за пределы никогда не вылезать.

                    первое, что приходит на ум- генетические алгоритмы. НО как составить оценку популяций, чтобы для данной задачи ген-алгоритм быстро сходился?

                    второе, что приходит на ум- составить для ячеек первого шага развития формулы зависимости от состояния ячеек нулевого(начального) шага. учесть ограничения. упростить. составить для ячеек второго шага формулы. подставить в них формулы ячеек первого шага, чтобы выразить состояние ячеек второго шага ч/з зависимость от начального состояния. наложить ограничения, упростить. и т д- до последнего шага. при N=30 уже получается чё-та до хрена. а мне хотелось бы видеть, например, N= 1021.

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

                    третье, о чём думал: забить куб NxNxN рандомно элементами 0, 1 и X. предположим, что этот куб представляет из себя решение, в котором последовательно показаны все N шагов развития популяции. X- элементы, про которые не ясно, чему они должны быть равны. работаем так:
                    1. рандомно выбираем в кубе любой Х или ошибочный элемент(0 или 1, которые не могут быть получены в этом месте из предыдущего состояния
                    популяции)
                    2. перебираем 512(или меньше если у края) вариантов конкретного заполнения(0 или 1) области 3х3 с выбранным элементом в центре. для каждого из 512 случаев прогоняем популяцию (N-1) шагов и подсчитываем кол-во ошибок в кубе. оставляем один из тех вариантов, при котором кол-во ошибок в кубе станет наименьшим.

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


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

                    Добавлено
                    --

                    кстати, доработанный вариант решения задачи про вагоны:
                    Скрытый текст
                    Значит, делаем следующим образом:
                    :Start
                    Тот вагон, в котором мы находимся, назовем "первичный вагон". Включаем в нем свет.
                    : Loop
                    Идем в одном направлении, отсчитывая вагоны от первичного до тех пор, пока не дойдем до вагона с включенным светом. Выключаем в нем свет и возвращаемся в обратном направлении к первичному вагону (благо мы отсчитывали).
                    IF Если в первичном вагоне свет выключился THEN следовательно, мы сделали один оборот & goto HappyEnd ELSE Если свет в первичном вагоне остался включенным, значит, тот вагон, в котором мы выключили, свет был не первичным. & Goto Loop
                    :HappyEnd
                    Число вагонов, которое мы отсчитали до вагона, в котором в последний раз выключили свет = общее число вагонов в кольце.
                    беготни меньше.
                    "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                    "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                      Цитата ya2500 @
                      беготни меньше.

                      но мозг зато взрывает больше :lol:
                        поскольку в теме не осталось не решённых задачек, то попробуйте следующую:

                        ДАНО: игра с семачками для двух игроков. на столе лежит куча семачек(начальное кол-во точно известно- пересчитывать разрешается))
                        1.первым ходом можно взять 1..2 семечки.
                        2. каждым следующим- 1..2*n, где n- кол-во семачек, которые взяты предыдущим ходом[соперником].
                        3. если возможно взять все оставшиеся семачки, то их брать- обязательно. и это- выйгрыш.


                        НАДО: составить прогу, которая получив на входе кол-во семечек K определяет, для какого из игроков(первого или второго) в данном случае существует выйгрышная стратегия. собственно, это не программистская, а математическая задачка. насколько я помню, описать решение можно было очень кратко.


                        пример партии:
                        игроки a и b, в кучке 70 семачек:
                        кто: -взял = осталось
                        a: -2 = 68
                        b: -4 = 64
                        a: -8 = 56
                        b: -12 = 44
                        a: -24 = 20
                        b: -20 = 0 - выйграл второй игрок(b)
                        а вот, для кого из них существовала выйгрышная стратегия? :scratch:
                        "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                        "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                          Alexander N, кста, твоё решение про зацикливание проги не очень-то хорошее. щазз доделаю своё, и буду готов разобрать недостатки твоего.

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

                          Добавлено
                          в-общем, получается так:

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

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

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

                          ну, и ещё, конечно, если нашли одно зацикливание, то на этом можно бы и остановиться.


                          ну, вот так. проще не получается.
                          Сообщение отредактировано: ya2500 -
                          "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                          "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                            Цитата ya2500 @
                            запоминаем, какие строки мы посещали, и какими были тогда значения переменных. и если мы попали на строку, на которой уже были, и при этом среди значений запомненных для неё переменных уже есть такие, с которыми мы на неё попали сейчас, то делаем вывод, что прога зацикливается. иначе- мы в конце концов доберёмся до какого-нибудь энда.
                            Только надо не забыть запоминать все комбинации А и В, при которых мы бывали на строке, благо таких комбинаций всего 4. Мы можем прийти на одну строку с 1 и 1, потом прийти с 1 и 0, поотом опять с 1 и 1.
                              мне кажется, что оба наши решения можно объединить в нечто получше

                              Добавлено
                              --

                              и, кстати: Конкурс по программированию на C/С++ (сообщение #2724225)

                              Добавлено
                              --

                              на этом всем пока, я пошёл спать))
                              "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                              "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                                Цитата ya2500 @
                                и, кстати: Конкурс по программированию на C/С++ (сообщение #2724225)
                                Дико извиняюсь, но я Дельфист :blush:
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (45) 1 [2] 3 4 ...  44 45


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1509 ]   [ 17 queries used ]   [ Generated: 16.07.19, 08:18 GMT ]