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


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

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


                                  у меня получилось :yes:

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

                                    Может :) "В этом файле ... двадцать одна буква "н" ..." (при этом в остальном тексте их 19). Но все же, мне кажется, можно подобрать файл, к которому решение просто не сойдется в данной формулировке.
                                    Долог путь в бессмертие... я еще вернусь.
                                    Профильный скилл "Телепатия" 8%
                                    ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                    Прошу потестить игру.
                                      Цитата Vesper @
                                      Но все же, мне кажется, можно подобрать файл, к которому решение просто не сойдется в данной формулировке.


                                      трудно сказать. ведь мы формируем доп.инфу, в тексте которой сотни букв. возможно, что обычно для входного файла задача имеет тысячи решений. и если окажется так, то я бы усомнился в том, что можно подобрать файл, к которому решения найти невозможно.
                                        да, вот ещё:
                                        Цитата ya2500 @
                                        менее известная игра "Конфета"

                                        Скрытый текст
                                        Выигрыш - откусить так, чтобы осталось 2^N-1, где N>=0. Если у самого 2^N-1, ты проиграл.
                                        Долог путь в бессмертие... я еще вернусь.
                                        Профильный скилл "Телепатия" 8%
                                        ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                        Прошу потестить игру.
                                          Vesper, есть пара вопросов:

                                          Скрытый текст
                                          действительно ли из любой выигрышной позиции возможно создать сопернику ситуацию 2^n-1?

                                          действительно ли нет такой ситуации 2^n-1, (при n>0), из которой возможно создать проигрышную позицию сопернику?


                                          Добавлено
                                          впрочем, ответом на эти вопросы будет любое доказательство твоей стратегии.
                                            ya2500
                                            Скрытый текст
                                            Что из 2^N-1 нельзя перейти в 2^(N-1)-1 - понятно, потому что разница между ними 2^(N-1) что больше желаемого остатка. То есть из множества 2^N-1 переход возможен только в точки, не принадлежащие множеству. Это ответ на второй вопрос.
                                            Ответ на первый вопрос - если число не равно 2^N-1, значит, из него можно перейти в 2^(N-1)-1, где 2^(N-1)<=X < 2^N-1, так как X-(2^(N-1)-1) меньше либо равна 2^(N)-2 - (2^(N-1)-1) = 2*(2^(N-1))-2-(2^(N-1)-1) = 2^(N-1)-1, то есть меньше или равна целевому числу, а значит, меньше или равна половине X. То есть, из любого числа, не имеющего вид 2^N-1, всегда есть ход в число из множества 2^N-1, т.е. из выигрышного всегда есть ход в проигрышное. Это ответ на первый вопрос.
                                            Хватит для доказательства?
                                            Долог путь в бессмертие... я еще вернусь.
                                            Профильный скилл "Телепатия" 8%
                                            ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                            Прошу потестить игру.
                                              Цитата Vesper @
                                              Хватит для доказательства?


                                              да.

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

                                              ...

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

                                              даны три числа: n, m, k. n и m- стороны исходного прямоугольника. найти минимальное количество квадратов, на которое его можно разрезать так, чтобы хотя бы один из квадратов имел сторону равную k.
                                              Сообщение отредактировано: ya2500 -
                                                Цитата
                                                В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup 2014. В нем участвовало 802 программиста, показавшие лучшие результаты в четырех квалификациях. В этом этапе участникам предстояло за 3 часа решить шесть задач, что на один час и на одну задачу больше, чем в квалификационных раундах. Да и задачи были существенно сложнее, чем предыдущие. За время соревнования из 802-х только 444 участника смогли решить хотя бы одну задачу. Всего было отправлено 3271 решения, из них правильных 1402.

                                                Больше всего решений на GNU C++ — 1516.
                                                Решений на Java 7 — 333.
                                                Решений на Java 8 — 106.


                                                вот статья с Хабра с разбором задач: http://habrahabr.ru/company/mailru/blog/225743/

                                                полная формулировка первой задачи (без решения) здесь: https://www.russiancodecup.ru/championship/...nd/9/problem/A/

                                                там же можно перейти и на другие задачи.

                                                Добавлено
                                                в том числе и на задачи 4-х квалификационных раундов.
                                                  вот, например, простая задача из первого раунда: https://www.russiancodecup.ru/championship/...nd/7/problem/A/

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

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

                                                  Добавлено
                                                  да, этот конкурс меня заинтересовал :yes:
                                                    Цитата ya2500 @
                                                    да, этот конкурс меня заинтересовал

                                                    Поздно ты спохватился :)
                                                    Подпись была включена в связи с окончанием срока наказания
                                                      другой сайт с задачами на программирование:

                                                      http://codeforces.ru/contest/538/problem/B

                                                      про именно ту задачку, что по ссылке, открыта отдельная тема: Простая задача
                                                        пожалуй, помещу это сюда:

                                                        Цитата
                                                        Из аналогов codeforces выделяется разве что Topcoder - тот же codeforces (т.е. регулярные соревнования с рейтингом и общение), но исключительно на английском языке и с несколько более разнообразным форматом соревнований.
                                                        Если просто архивы задач, то их море:
                                                        http://acm.timus.ru/, http://acm.sgu.ru/, http://www.spoj.com/, http://acm.mipt.ru/judge - просто архивы задач сложности от "сумма двух чисел" до "а оно вообще решается?" :)
                                                        http://acmp.ru/ - архив простых задач, ориентированный на начинающих.
                                                        Куча сайтов соревнований, проводимых ежегодно различными компаниями (Яндекс, гугл, мейлру, фейсбук, КРОК, Вконтакте - только те, что вспомнил навскидку).


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

                                                          А это не очевидно?
                                                          На всякий случай спрячу
                                                          Допустим, у белых есть стратегия, позволяющая выигрывать, тогда данная стратегия является искомой. Если же её нет, то это означает, что на любой ход белых чёрные смогут ответить так, чтобы не проиграть. И тогда стратегия чёрных - искомая.
                                                          Подпись была включена в связи с окончанием срока наказания
                                                            Цитата ya2500 @
                                                            у меня получилось

                                                            Добавлено 29 мая 2014, 22:09
                                                            надо только продумать, как кратко это доказательство записать.

                                                            Цитата OpenGL @
                                                            А это не очевидно?
                                                            На всякий случай спрячу


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

                                                            но, да- у меня такой замут вышел потому, что я не догадался до такого простого доказательства.
                                                              Цитата OpenGL @
                                                              На всякий случай спрячу
                                                              Да нечего там прятать.
                                                              Цитата OpenGL @
                                                              Допустим, у белых есть стратегия, позволяющая выигрывать, тогда данная стратегия является искомой. Если же её нет, то это означает, что на любой ход белых чёрные смогут ответить так, чтобы не проиграть. И тогда стратегия чёрных - искомая.
                                                              Увы, но тут изъян. Итак, рассматриваем второй вариант, когда выигрышной стратегии у белых нет. Да, чёрные могут будут ходить, не проигрывая, но белые могут начать так ходить, что ситуация будет повторяться и тогда зачтут ничью, или, допустим, поражение чёрным. А ведь может оказаться, что у чёрных есть шанс! Как быть? Это показывает, что наличие беспроигрышной стратегии всё же непонятно. Ну мне то точно. Допускаю, что OpenGL сможет поподробнее расписать. :blush:
                                                                Цитата Славян @
                                                                Увы, но тут изъян. Итак, рассматриваем второй вариант, когда выигрышной стратегии у белых нет. Да, чёрные могут будут ходить, не проигрывая, но белые могут начать так ходить, что ситуация будет повторяться и тогда зачтут ничью,


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

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


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

                                                                Цитата Славян @
                                                                Да, чёрные могут будут ходить, не проигрывая,


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

                                                                ---

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

                                                                тогда можно обратиться к определению того, что такое стратегия. из него (для таких игр как шахматы) следует истинность этой связки.
                                                                Сообщение отредактировано: ya2500 -
                                                                  Да, формально, думаю, у вас с OpenGL всё правильно. Беспокойство вызывает такая схема:
                                                                  1.Пусть нет выигрышной у белых.
                                                                  2.Действуя как надо, чёрные получают беспроигрышную. ч.т.д.
                                                                  3.Комиссия решает, что бывают частые повторения и засчитывает проигрыш тому, кто повторяет.
                                                                  4.Появляется выигрышная у белых - вводить чёрных в повторялово.
                                                                  5.Комиссия решает, что белые так не выигрывают, а вводят=принуждают чёрных к такому бардаку. Решает, что такое принуждение ведёт к проигрышу принуждающей стороны.
                                                                  6.Стратегия 'выигрышная' у белых пропадает, снова появляется беспроигрышная у чёрных.
                                                                  7.Как-то так дальше.
                                                                  Мораль: игра не переделывается, а лишь сложные окончания достраиваются, правила дорабатываются, но стратегия 'беспроигрышная' кочует то к одним, то к другим. Бардак и непонятки. :oops:
                                                                    Цитата Славян @
                                                                    Комиссия решает, что бывают частые повторения и засчитывает проигрыш тому, кто повторяет
                                                                    Цитата Славян @
                                                                    стратегия 'беспроигрышная' кочует то к одним, то к другим. Бардак и непонятки.


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

                                                                    если чёткие однозначно определённые правила есть, то таких непоняток не возникнет.

                                                                    Добавлено
                                                                    ---

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

                                                                      И что ты так всё комиссии любишь :D


                                                                      Добавлено
                                                                      Цитата Славян @
                                                                      3.Комиссия решает, что бывают частые повторения и засчитывает проигрыш тому, кто повторяет.

                                                                      В условии сказано, что игра "шахматы". Правило "проигрывать при повторе" к ним отношения не имеет.
                                                                      Подпись была включена в связи с окончанием срока наказания
                                                                        Цитата OpenGL @
                                                                        И что ты так всё комиссии любишь
                                                                        Это просто однословное название "группы людей из разных стран, отвечающих за текущие правила игры". :blush:
                                                                        Цитата ya2500 @
                                                                        бардак и непонятки получаются из того, что в твоём примере, получается, что нет чётких заранее прописанных правил игры и приходится привлекать какую-то комиссию.

                                                                        если чёткие однозначно определённые правила есть, то таких непоняток не возникнет.
                                                                        Да, снова согласен с вами. Но если переделка идёт не фундаментальных правил, а вот таких вот редких да мутных концовок, то получится же пляска, о коей я пытаюсь донести идею. Вот это и вызывает тревогу.
                                                                        Цитата OpenGL @
                                                                        В условии сказано, что игра "шахматы". Правило "проигрывать при повторе" к ним отношения не имеет.
                                                                        Да, поэтому я и написал, что
                                                                        Цитата Славян @
                                                                        формально, думаю, у вас с OpenGL всё правильно.
                                                                        Но всё же всякие правила рубки на проходе, рокировки чрез битое поле и т.д. намекают, что базовые правила достраивались. Мне сейчас неизвестны правила, кои гласят, что "если белые с чёрными играют сверхдолго, то что делать". А сделать игру можно ну очень долгой и безо всякой периодичности. Подскажите это правило, если вы в курсе.
                                                                          Цитата ya2500 @
                                                                          т.е. регулярные соревнования с рейтингом и общение), но исключительно на английском языке и с несколько более разнообразным форматом соревнований.
                                                                          Если просто архивы задач, то их море:


                                                                          ещё ссыль примерно в тему(по SQL): http://sql-ex.ru
                                                                            Цитата Славян @
                                                                            Мне сейчас неизвестны правила, кои гласят, что "если белые с чёрными играют сверхдолго, то что делать"

                                                                            Ничья, если не было в течение последних 50 ходов хода пешкой или взятия, или произошло троекратное повторение позиции.
                                                                            Подпись была включена в связи с окончанием срока наказания
                                                                              Цитата OpenGL @
                                                                              Ничья, если не было в течение последних 50 ходов хода пешкой или взятия, или произошло троекратное повторение позиции.
                                                                              Вот! А теперь хорошо бы увидеть, что ничейность ситуации - навязана правилами, она не отражает некоей истинности положения, т.к. результат не известен, а предсказать его нельзя. Т.е. вполне реально ходить каждой стороне внутри своей области, без продвижения пешек и без взятия, но так, чтобы произошло такое положение, кое будет выгодно одной стороне.
                                                                              Опущусь до сверхнаглядности:
                                                                              1.Белые задали число 7.
                                                                              2.Чёрные - 10.
                                                                              3.У белых меньше - они добавили 7, 14 получили.
                                                                              4.Потом чёрные и т.д.
                                                                              Так вот, они столкнутся в 7*10 = 70. Но ходов будет много сделано. Так и в шахматах: возможно, что внутренней перестройки позиции нужно очень много ходов, дабы понять у кого лучше, а комиссия берёт и говорит - ничья. Жутчайшая искусственность. :scratch:
                                                                                Так твоё предположение выше о проигрыше при повторении позиции ровно настолько же искусственно. Кроме того, если заменить это правило правилом "ничья при однократном повторении позиции", которое выглядит вполне логично с математической точки зрения, то доказательство по прежнему останется верным.
                                                                                Подпись была включена в связи с окончанием срока наказания
                                                                                  Цитата OpenGL @
                                                                                  Так твоё предположение выше о проигрыше при повторении позиции ровно настолько же искусственно.
                                                                                  Да, согласен. Речь про то, что правила концовок/повторов какие-то есть оттого, что нет понимания каково будущее позиции.
                                                                                  Цитата OpenGL @
                                                                                  Кроме того, если заменить это правило правилом "ничья при однократном повторении позиции", которое выглядит вполне логично с математической точки зрения, то доказательство по прежнему останется верным.
                                                                                  Я не спорю с тем, что ваша схема верна. Просто верность её пока базируется на правилах конца, кои не идеальны. А создавать ситуации, когда никакого повтора нет, но заметно "гуляние всё вокруг да около чего-то одинакового" - можно. Вот 'комиссия' и решила задать барьер в виде движения пешек или поедания фигур. Но барьер этот всё же искусственный, - что говорит о том, что некая 'истинная беспроигрышность' - непонятна.
                                                                                    Цитата Славян @
                                                                                    А создавать ситуации, когда никакого повтора нет, но заметно "гуляние всё вокруг да около чего-то одинакового" - можно. Вот 'комиссия' и решила задать барьер в виде движения пешек или поедания фигур. Но барьер этот всё же искусственный, - что говорит о том, что некая 'истинная беспроигрышность' - непонятна.

                                                                                    Почему непонятный? Если все эти "барьеры" убрать, то просто появятся длинные партии, которые, очевидно, не закончатся поражением игроков и, как следствие, их наличие никак не будет противоречить наличию беспроигрышных стратегий.
                                                                                    Подпись была включена в связи с окончанием срока наказания
                                                                                      Цитата OpenGL @
                                                                                      Если все эти "барьеры" убрать, то просто появятся длинные партии, которые, очевидно, не закончатся поражением игроков и, как следствие, их наличие никак не будет противоречить наличию беспроигрышных стратегий.
                                                                                      Для меня это сильно не очевидно, а для вас - "я думаю, что вы не сможете доказать это". <_<
                                                                                        Цитата Славян @
                                                                                        Для меня это сильно не очевидно

                                                                                        Что именно не очевидно? Что имелись ввиду "бесконечно длинные"? Или что поражение означает конец партии, поэтому стратегия, приводящая к бесконечной партии, не даст проиграть?
                                                                                        Подпись была включена в связи с окончанием срока наказания
                                                                                          Славян, в своих рассуждениях ты неявно предполагаешь, что правила могут непредсказуемо меняться прямо во время раунда игры. Хотя при описании ситуации, комиссия у тебя корректирует правила между раундами. То есть каждый новый раунд играется по вполне конкретным фиксированным правилам, которые могут отличаться от правил предыдущего раунда, но до конца раунда не изменятся. Так вот в таком случае либо у одного игрока есть выигрышная стратегия, либо

                                                                                          В принципе число позиций в шахматах ограничено. Тем более при фиксированном наборе фигур. И из них ещё меньше осмысленных позиций, которые могут встретиться в игре. Так что рано или поздно позиции начнут повторяться. Повтор позиций означает, что ни тот ни другой игрок не знают способа заставить противника сделать проигрышный ход (или ход ведущий у форсированной ничьей). Для страховки позицию позволяют повторить два раза, вдруг в первый раз игрок просто не воспользовался возможностью выиграть.
                                                                                          Правило 50 ходов введено, по-видимому, чтобы не ждать трёх повторов. Шахматы - игра довольно динамичная, и если в течение 50 ходов ничего существенного на доске не происходит, то скорее всего и не произойдёт. Кстати, когда-то это ограничение было более жёстким, но потом обнаружился эндшпиль (заканчивающийся матом), который в старое ограничение не укладывался.

                                                                                          Кроме того, ничья признаётся, если на оставшиеся на доске фигуры не позволяют закончить партию выигрышем одной из сторон. Но это обычно уже игроки между собой решают.
                                                                                          Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                                            так получилось, что от сути задачи Славян перешёл к рассмотрению другого вопроса, а именно: о том, почему правила о повторениях и о 50 ходах именно таковы и какими они могли бы быть ещё.

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

                                                                                            Добавлено
                                                                                            Цитата amk @
                                                                                            уже игроки между собой решают.


                                                                                            и, да- правила предусматривают возможность предложить (и согласиться на) ничью.
                                                                                              Цитата OpenGL @
                                                                                              Что именно не очевидно?
                                                                                              Выделил жирным:
                                                                                              Цитата OpenGL @
                                                                                              появятся длинные партии, которые не закончатся поражением игроков

                                                                                              Цитата amk @
                                                                                              Так вот в таком случае либо у одного игрока есть выигрышная стратегия, либо
                                                                                              Ваше предложение оборвалось.
                                                                                              Цитата amk @
                                                                                              правила могут непредсказуемо меняться прямо во время раунда игры.
                                                                                              Это слишком сильная фраза. Я указывал, что не просто правила меняются, а изменяется взгляд на хвост игры, на засчитывание ничьей или победы в весьма непонятном продолжении партии. Когда правила чётко зафиксированы, то я уже давно согласился, что рассуждения OpenGL были правильными.
                                                                                              Цитата amk @
                                                                                              если в течение 50 ходов ничего существенного на доске не происходит, то скорее всего и не произойдёт.
                                                                                              Я именно про случай написанный вами 'скорее всего', ставший для OpenGL 'очевидным'.
                                                                                              Цитата ya2500 @
                                                                                              не хватало ещё, чтобы результат партии определялся голосованием. все правила, по которым проходит партия, должны быть известны обоим игрокам до начала партии.
                                                                                              Ваше негодование вполне натыкается на фразу:
                                                                                              Цитата amk @
                                                                                              Но это обычно уже игроки между собой решают.
                                                                                              ;)

                                                                                              Добавлено
                                                                                              Цитата amk @
                                                                                              В принципе число позиций в шахматах ограничено. ... Так что рано или поздно позиции начнут повторяться.
                                                                                              Беда в том, что людям неизвестно, ведёт ли такая-то позиция к победе или проигрышу, скажем, белых. А потому комиссия решает, что будет указывать на ничью/поражение, а что - нет. Т.е. она не рассматривает истинный результат сражения, а принимает решение до него. Это и выглядит туманным.
                                                                                              По поводу ограниченности: число атомов во вселенной тоже ограничено (по одной из модели), состояний оной - тоже, но, однако, существует и доказана "теорема Гёделя о неполноте"... :whistle:
                                                                                                Цитата Славян @
                                                                                                Ваше предложение оборвалось.
                                                                                                , либо оба имеет стратегии, обеспечивающие ничью.
                                                                                                Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                                                  Чуть шаг в сторону, но всё же:
                                                                                                  1.Пусть играют очень сильный игрок и очень слабый. Немногие знают это.
                                                                                                  2.Комиссия не знает кто какой.
                                                                                                  3.На средину партии сильный уже много порубил, слабый еле 'дышит'.
                                                                                                  4.Тут вдруг сильный 'ушёл в себя', возится на своей территории, на слабого не нападает.
                                                                                                  5.Слабый ходит вокруг да около, думает, что готовится отразить то одну, то другую стратегию сильного; не нарывается.
                                                                                                  6.Оба - 'сферические в вакууме', а потому играют сверхдолго и позиции начинают повторяться.
                                                                                                  7.Комиссия (судьи) говорят: т.к. ситуация повторяется, а кажущаяся победа одной стороны нам непонятна (мы - лишь судьи), то присуждаем ничью.
                                                                                                  Мораль: правду, о том какая сторона в выигрыше (а какая - нет) мы не узнаём, а принимаем по решению комиссии! Т.е. в логическую игру внесли нехилый кусок искусства/гуманитарных приблуд. :yes-sad:
                                                                                                    Цитата Славян @
                                                                                                    Выделил жирным:

                                                                                                    И что там неочевидно? Если партия бесконечна - она не заканчивается по определению. "Не заканчивается" означает, что конца у партии не будет никакого, включая поражение игрока.
                                                                                                    Подпись была включена в связи с окончанием срока наказания
                                                                                                      Цитата OpenGL @
                                                                                                      И что там неочевидно? Если партия бесконечна - она не заканчивается по определению.
                                                                                                      Не про бесконечность речь. <_< Вот полный фрагмент (убрал очевидность и простоту):
                                                                                                      Цитата OpenGL @
                                                                                                      Цитата Славян @
                                                                                                      А создавать ситуации, когда никакого повтора нет, но заметно "гуляние всё вокруг да около чего-то одинакового" - можно. Вот 'комиссия' и решила задать барьер в виде движения пешек или поедания фигур. Но барьер этот всё же искусственный, - что говорит о том, что некая 'истинная беспроигрышность' - непонятна.
                                                                                                      Почему непонятный? Если все эти "барьеры" убрать, то появятся длинные партии, которые не закончатся поражением игроков
                                                                                                      Т.е. речь про то, что возможно появятся партии, кои всё же будут заканчиваться поражением игрока, а вы написали, что будут появляться лишь длинные, ведущие к ничье.
                                                                                                        Цитата Славян @
                                                                                                        4.Тут вдруг сильный 'ушёл в себя', возится на своей территории, на слабого не нападает.


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

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

                                                                                                        к обсуждению чего ты перешёл на этот раз? психологии игроков? высшей справедливости? на мой взгляд, очень похоже на сферический бред в вакууме.
                                                                                                          Правило троекратного повторения позиции предотвращает бесконечные итерации. Коли трижды игроки пришли к той же позиции, значит они, играя с их точки зрения оптимальным образом, либо и дальше будут играть так же оптимально, а значит бесконечно, либо кто-то вынужден будет сыграть себе во вред, а значит проиграет несправедливо.
                                                                                                          Правило 50-ти ходов когда-то существовало, чтобы предотвратить затягивание игр на турнирах. Игроки, которые не хотели повторять позиции и надеялись на ошибки оппонента, могли часами и сутками выматывать противника. В конце концов такой выигрыш тоже не вполне справедлив, т.к. не показывает более сильную игру победителя. Однако с появлением технических средств в лице компьютеров в некоторых эндшпилях были обнаружены выигрышные варианты, которые требуют для реализации более 50 ходов. В правила стали вносить поправки в лице исключений, когда правило 50 ходов заменяется на правило 100 ходов. Список эндшпилей рос, их варианты усложнялись, и в конце концов это правило было убрано вообще. Однако за организаторами турниров оставлено право вводить дополнительные ограничения на длину партий при определённых условиях на их усмотрение с обязательной публикацией в правилах проводимого турнира.
                                                                                                          Информация примерно 10-летней давности, как обстоят дела сейчас, я не в курсе.
                                                                                                          Сообщение отредактировано: Qraizer -
                                                                                                          Одни с годами умнеют, другие становятся старше.
                                                                                                            Цитата Славян @
                                                                                                            Цитата OpenGL @
                                                                                                            И что там неочевидно? Если партия бесконечна - она не заканчивается по определению.
                                                                                                            Не про бесконечность речь. <_< Вот полный фрагмент (убрал очевидность и простоту):
                                                                                                            Цитата OpenGL @
                                                                                                            Цитата Славян @
                                                                                                            А создавать ситуации, когда никакого повтора нет, но заметно "гуляние всё вокруг да около чего-то одинакового" - можно. Вот 'комиссия' и решила задать барьер в виде движения пешек или поедания фигур. Но барьер этот всё же искусственный, - что говорит о том, что некая 'истинная беспроигрышность' - непонятна.
                                                                                                            Почему непонятный? Если все эти "барьеры" убрать, то появятся длинные партии, которые не закончатся поражением игроков
                                                                                                            Т.е. речь про то, что возможно появятся партии, кои всё же будут заканчиваться поражением игрока, а вы написали, что будут появляться лишь длинные, ведущие к ничье.

                                                                                                            Так я чуть выше написал, что имелись ввиду бесконечно длинные. Это если и было неочевидно, то после всех комментариев должно было проясниться.
                                                                                                            Подпись была включена в связи с окончанием срока наказания
                                                                                                              Цитата ya2500 @
                                                                                                              Славян, ты лепишь какой-то бред.
                                                                                                              к обсуждению чего ты перешёл на этот раз? психологии игроков? высшей справедливости? на мой взгляд, очень похоже на сферический бред в вакууме.
                                                                                                              :facepalm: Ну вот, началось!.. Ладно, заканчиваю=бросаю тему, коли так понимание пошло. :whistle:
                                                                                                                сложно
                                                                                                                  На второй странице вскользь упомянуты некоторые из ресурсов, на которых можно найти годные задачи на программирование:

                                                                                                                  Цитата ya2500 @
                                                                                                                  там же можно перейти и на другие задачи.

                                                                                                                  Цитата ya2500 @
                                                                                                                  другой сайт с задачами на программирование:

                                                                                                                  Цитата ya2500 @
                                                                                                                  просто архивы задач сложности от "сумма двух чисел" до "а оно вообще решается?"


                                                                                                                  и надо будет к ним присмотреться И кое-что я нарыл уже и помимо этого, хотя самому найти хороших сложных задач было непросто. Хорошо, хоть про ЭТУ тему вспомнил :)

                                                                                                                  Добавлено
                                                                                                                  ===

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

                                                                                                                  Текущая задача:

                                                                                                                  Цитата
                                                                                                                  Даны два целых положительных числа, длиной не более 100 цифр каждое. Вычислить произведение этих чисел. И входные и выходные данные должны храниться с абсолютной точностью.


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

                                                                                                                  Добавлено
                                                                                                                  - ну вот такая простая задачка, для начала.
                                                                                                                    Скрытый текст
                                                                                                                    легкотня вроде как. чиселки разложены в массивы, первый элемент - младший разряд.
                                                                                                                    ExpandedWrap disabled
                                                                                                                      for (auto first : range (first_size))
                                                                                                                        for (auto second : range (second_size))
                                                                                                                          res_number[first + second] += first_number[first] * second_number[second];
                                                                                                                       
                                                                                                                      for (auto length : range (first_size + second_size + 1))
                                                                                                                      {
                                                                                                                        res_number[length + 1] += res_number[length] / 10;
                                                                                                                        res_number[length] %= 10;
                                                                                                                      }

                                                                                                                    Сообщение отредактировано: _lcf_ -
                                                                                                                      Цитата ya2500 @
                                                                                                                      Даны два целых положительных числа
                                                                                                                      За что мне понравился Питон, так это в частности за то, что не накладывает ограничений на величину целых.
                                                                                                                      Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                                                                        Эмм.. не ожидал, что кто-то ещё заинтересуется моей простой задачкой- это я себе выбрал на вечер. Правда, слегка подзастрял уже и пойду, наверное, передохну.

                                                                                                                        Задачку эту я выделил из более сложной:

                                                                                                                        Цитата
                                                                                                                        Дано арифметическое выражение, длиной не более 30 символов, состоящее из цифр и знаков
                                                                                                                        Цитата
                                                                                                                        +-*/().

                                                                                                                        где знак "." означает плавающую точку, которая может находиться ТОЛЬКО между двумя цифрами.

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

                                                                                                                        Размер вводимых чисел не ограничен ничем, кроме размера всей строки(30 символов).

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


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

                                                                                                                        Добавлено
                                                                                                                        ===

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

                                                                                                                        Пока что буду писать только на C++ (MS VS C++).

                                                                                                                        Добавлено
                                                                                                                        ===

                                                                                                                        Наиболее интересны в этом всём, мне были бы отзывы на мои решения. Но и чужие решения тоже интересны.. пока что интересны только на C++.
                                                                                                                        Сообщение отредактировано: ya2500 -
                                                                                                                          Большого смысла в 30 символах не вижу: всё равно потянет написать простенький парсер...
                                                                                                                            ya2500, если возьмёшь на вооружение библиотеки, в частности STL и/или BOOST, разбор выражения будет делать гораздо проще. Но не факт, что решение получишь меньшими усилиями, библиотеки тоже требуют усилий для освоения.
                                                                                                                            Одни с годами умнеют, другие становятся старше.
                                                                                                                              Цитата Qraizer @
                                                                                                                              ya2500, если возьмёшь на вооружение библиотеки, в частности STL и/или BOOST, разбор выражения будет делать гораздо проще. Но не факт, что решение получишь меньшими усилиями, библиотеки тоже требуют усилий для освоения.


                                                                                                                              с STL я знаком.
                                                                                                                                Цитата Славян @
                                                                                                                                всё равно потянет написать простенький парсер...


                                                                                                                                Ты будоражишь мою фантазию. Я уже захотел написать компилятор для вымышленного простенького языка ))

                                                                                                                                ===

                                                                                                                                Ну и ладно, вот ещё задачка:

                                                                                                                                Цитата
                                                                                                                                Написать программу, подбирающую "секретный пароль" из 15 цифр, получая после каждой попытки информацию о кол-ве быков и коров.


                                                                                                                                - имеется ввиду игра "быки и коровы";

                                                                                                                                Цитата
                                                                                                                                ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество коров) и сколько угадано вплоть до позиции в тайном числе (то есть количество быков). Например:

                                                                                                                                Задумано тайное число «3219».

                                                                                                                                Попытка: «2310».

                                                                                                                                Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции).


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

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

                                                                                                                                Добавлено
                                                                                                                                ===

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

                                                                                                                                Добавлено
                                                                                                                                Может быть, даже более интересных- на вкус и цвет, сами понимаете ))
                                                                                                                                Сообщение отредактировано: ya2500 -
                                                                                                                                  Цитата ya2500 @
                                                                                                                                  имеется ввиду игра "быки и коровы";

                                                                                                                                  Сколько "коров" должен получить на вход алгоритм, если в пароле есть 0 (хотя бы один), его длина 15, а тест состоит из 15 нулей?

                                                                                                                                  Добавлено
                                                                                                                                  ЗЫ исходная игра не допускала повторений в секрете, а здесь без них никак.
                                                                                                                                  Долог путь в бессмертие... я еще вернусь.
                                                                                                                                  Профильный скилл "Телепатия" 8%
                                                                                                                                  ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                                                                                                                                  Прошу потестить игру.
                                                                                                                                    Цитата ya2500 @
                                                                                                                                    Написать программу, подбирающую "секретный пароль" из 15 цифр, получая после каждой попытки информацию о кол-ве быков и коров.

                                                                                                                                    Хм. С 15 ещё можно сравнительно быстрый перебор написать, выбирающий те варианты, которые подходят под ответ. А вот что делать, если символов больше - непонятно :unsure:

                                                                                                                                    Добавлено
                                                                                                                                    Цитата Vesper @
                                                                                                                                    Сколько "коров" должен получить на вход алгоритм, если в пароле есть 0 (хотя бы один), его длина 15, а тест состоит из 15 нулей?

                                                                                                                                    Один
                                                                                                                                    Подпись была включена в связи с окончанием срока наказания
                                                                                                                                      Oдин коров-самец.
                                                                                                                                      Мои религиозные убеждения не позволяют мне комментировать код.
                                                                                                                                      Моё мировоззренье таково: в программе комментария ни одного!
                                                                                                                                        :crazy:
                                                                                                                                        Да, один бык, (количество нулей минус 1) коров - так правильно
                                                                                                                                        Подпись была включена в связи с окончанием срока наказания
                                                                                                                                          Вот не самый эффективный алгоритм, но самый лучший из приведенных здесь
                                                                                                                                          Скрытый текст
                                                                                                                                          1. тестируем нолями: 00000...
                                                                                                                                          2. Меняем первую цифру, пока количество быков не изменится: 10000..., 20000... Первая позиция определена. Если количество быков уменьшается при замене 0 на 1, то па первой позиции - ноль. Если количество быков увеличивается при замене К на К+1, то там - К+1.

                                                                                                                                          3. Повторяем эту операцию для каждой позиции
                                                                                                                                          Мои религиозные убеждения не позволяют мне комментировать код.
                                                                                                                                          Моё мировоззренье таково: в программе комментария ни одного!
                                                                                                                                            Цитата Vesper @
                                                                                                                                            Сколько "коров" должен получить на вход алгоритм, если в пароле есть 0 (хотя бы один), его длина 15, а тест состоит из 15 нулей?


                                                                                                                                            будет столько "быков", сколько ноликов в пароле. И ни одной "коровы".

                                                                                                                                            то есть, за каждую цифру пароля(так же как и за каждую цифру теста) может быть выдано не более одного животного:

                                                                                                                                            1) если есть полное совпадение- выдаётся бык и эти две совпавшие цифры(одна из пароля и одна из теста) выпадают из рассмотрения.

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

                                                                                                                                            ===

                                                                                                                                            хотя, наверное, проще было бы объяснить исходя из, например, рассмотрения только цифр пароля и их соответствия тесту:

                                                                                                                                            1) смотрим каждую цифру пароля.
                                                                                                                                            2) если напротив этой цифры(0) стоит такая же цифра(0)- выдаём быка и вычёркиваем обе эти цифры(0и0).
                                                                                                                                            3) если напротив этой цифры(0) стоит другая(1..9), НО в другом месте есть такая же цифра(0), стоящая напротив не такой же(1..9)- выдаём корову и вычёркиваем обе эти цифры(0и0)
                                                                                                                                            4) иначе никакого животного за этот нолик пароля не даём. можно его вычеркнуть, но- не зачем ))

                                                                                                                                            ===

                                                                                                                                            Vesper, надеюсь, на этот раз понятно объяснил.
                                                                                                                                            Сообщение отредактировано: ya2500 -
                                                                                                                                              Цитата ya2500 @
                                                                                                                                              хотя, наверное, проще было бы объяснить исходя из, например, рассмотрения только цифр пароля и их соответствия тесту:

                                                                                                                                              Ещё проще вот так:
                                                                                                                                              1) Считаем количество быков.
                                                                                                                                              2) Считаем количество каждой цифры в обоих паролях.
                                                                                                                                              3) Суммируем минимумы по каждой цифре - это даст количество "потенциальных" коров. Например, если в одном пароле три нуля, а в другом пять, то это даст три потенциальные коровы.
                                                                                                                                              4) Из потенциальных коров у нас некоторые являются быками, так что вычитаем из них количество быков, полученных в п.1. и получаем уже количество настоящих коров.
                                                                                                                                              Подпись была включена в связи с окончанием срока наказания
                                                                                                                                                Цитата Vesper @
                                                                                                                                                ЗЫ исходная игра не допускала повторений в секрете, а здесь без них никак.
                                                                                                                                                Вообще-то, вариант игры с повторами обычно тоже рассматривается. Хотя это надо оговаривать особо.
                                                                                                                                                Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                                                                                                                                  Как вариант, можно написать прогу просто для игры в "быки и коровы". Это может быть даже интереснее.
                                                                                                                                                    Цитата ya2500 @
                                                                                                                                                    Как вариант, можно написать прогу просто для игры в "быки и коровы". Это может быть даже интереснее.

                                                                                                                                                    А для проверки её можно сдать сюда.
                                                                                                                                                    Подпись была включена в связи с окончанием срока наказания
                                                                                                                                                      Цитата ya2500 @
                                                                                                                                                      это я себе выбрал на вечер. Правда, слегка подзастрял уже


                                                                                                                                                      И вот, я снова добрался до программирования И минут за 20-30 неторопясь написал и вылизал прогу, суммирующую большие числа(до 100 значных).

                                                                                                                                                      Цитата input.txt
                                                                                                                                                      Первое число:

                                                                                                                                                      19497

                                                                                                                                                      Второе число:

                                                                                                                                                      987654321

                                                                                                                                                      Конец.

                                                                                                                                                      Цитата output.txt
                                                                                                                                                      19497
                                                                                                                                                      +
                                                                                                                                                      987654321
                                                                                                                                                      =
                                                                                                                                                      987673818
                                                                                                                                                      код на с++
                                                                                                                                                      ExpandedWrap disabled
                                                                                                                                                        #include <stdio.h> // для работы с файлами и для sprintf
                                                                                                                                                        #include <stdlib.h> // для div()
                                                                                                                                                         
                                                                                                                                                        // *** получаем инфу из файла: начало
                                                                                                                                                        int get_input_data(char *input_name, unsigned char FirstNum[101], unsigned char SecondNum[101])
                                                                                                                                                        {
                                                                                                                                                            FILE *file;
                                                                                                                                                            unsigned char Tmp[100];
                                                                                                                                                            unsigned char c;
                                                                                                                                                         
                                                                                                                                                            // открываем файл для чтения
                                                                                                                                                            file = fopen(input_name, "r");
                                                                                                                                                            // w- write, r- read, a- append
                                                                                                                                                            
                                                                                                                                                            // если открыть файл не удалось
                                                                                                                                                            if (file == NULL) return -1;
                                                                                                                                                         
                                                                                                                                                            // пропускаем любое кол-во не-цифр
                                                                                                                                                            bool flag= false;
                                                                                                                                                            do
                                                                                                                                                            {
                                                                                                                                                                c = fgetc(file);
                                                                                                                                                                if(feof(file)){fclose(file);return -1;}
                                                                                                                                                         
                                                                                                                                                                if (c < 58 &&  c >= 48 )
                                                                                                                                                                {
                                                                                                                                                                    // заносим инфу в массив
                                                                                                                                                                    Tmp[0] = c-48;
                                                                                                                                                                    flag = true;
                                                                                                                                                                }
                                                                                                                                                            }
                                                                                                                                                            while (!flag);
                                                                                                                                                         
                                                                                                                                                            //считываем все подряд идущие цифры до не-цифры
                                                                                                                                                            int i = 0;
                                                                                                                                                            do
                                                                                                                                                            {
                                                                                                                                                                c = fgetc(file);
                                                                                                                                                                if(feof(file)){fclose(file);return -1;}
                                                                                                                                                         
                                                                                                                                                                if (c < 58 &&  c >= 48 && i < 100)
                                                                                                                                                                {
                                                                                                                                                                    // заносим инфу в массив
                                                                                                                                                                    i++;
                                                                                                                                                                    Tmp[i] = c-48;
                                                                                                                                                                }
                                                                                                                                                                else
                                                                                                                                                                {
                                                                                                                                                                    flag = false;
                                                                                                                                                                }
                                                                                                                                                            }
                                                                                                                                                            while (flag);
                                                                                                                                                            // лишние цифры(сверх 100) просто проигнорируются
                                                                                                                                                         
                                                                                                                                                            // заносим Tmp в FirstNum:
                                                                                                                                                            for(int k=0; k<=i; k++) FirstNum[k]= Tmp[i-k];
                                                                                                                                                            FirstNum[100] = i+1;
                                                                                                                                                         
                                                                                                                                                            // пропускаем любое кол-во не-цифр
                                                                                                                                                            do
                                                                                                                                                            {
                                                                                                                                                                c = fgetc(file);
                                                                                                                                                                if(feof(file)){fclose(file);return -1;}
                                                                                                                                                         
                                                                                                                                                                if (c < 58 &&  c >= 48 )
                                                                                                                                                                {
                                                                                                                                                                    // заносим инфу в массив
                                                                                                                                                                    Tmp[0] = c-48;
                                                                                                                                                                    flag = true;
                                                                                                                                                                }
                                                                                                                                                            }
                                                                                                                                                            while (!flag);
                                                                                                                                                         
                                                                                                                                                            //считываем все подряд идущие цифры до не-цифры
                                                                                                                                                            i = 0;
                                                                                                                                                            do
                                                                                                                                                            {
                                                                                                                                                                c = fgetc(file);
                                                                                                                                                                if(feof(file)){fclose(file);return -1;}
                                                                                                                                                         
                                                                                                                                                                if (c < 58 &&  c >= 48 && i < 100)
                                                                                                                                                                {
                                                                                                                                                                    // заносим инфу в массив
                                                                                                                                                                    i++;
                                                                                                                                                                    Tmp[i] = c-48;
                                                                                                                                                                }
                                                                                                                                                                else
                                                                                                                                                                {
                                                                                                                                                                    flag = false;
                                                                                                                                                                }
                                                                                                                                                            }
                                                                                                                                                            while (flag);
                                                                                                                                                            // лишние цифры(сверх 100) просто проигнорируются
                                                                                                                                                         
                                                                                                                                                            // заносим Tmp в SecondNum:
                                                                                                                                                            for(int k=0; k<=i; k++) SecondNum[k]= Tmp[i-k];
                                                                                                                                                            SecondNum[100] = i+1;  
                                                                                                                                                         
                                                                                                                                                            // закрываем файл
                                                                                                                                                            fclose(file);
                                                                                                                                                         
                                                                                                                                                            // 0- код успешного завершения
                                                                                                                                                            return 0;
                                                                                                                                                        }
                                                                                                                                                        // *** получаем инфу из файла: конец
                                                                                                                                                         
                                                                                                                                                        // *** выводим инфу в файл: начало
                                                                                                                                                        int put_input_data(char *output_name, unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
                                                                                                                                                        {
                                                                                                                                                            FILE *file;
                                                                                                                                                         
                                                                                                                                                            file = fopen(output_name, "w"); // открываем файл для записи
                                                                                                                                                         
                                                                                                                                                            // если открыть файл не удалось
                                                                                                                                                            if (file == NULL) return -1;
                                                                                                                                                         
                                                                                                                                                            for (int i= FirstNum[100]-1; i>=0; i--) fputc(FirstNum[i]+48,file);
                                                                                                                                                            fputc('\n',file);
                                                                                                                                                         
                                                                                                                                                            fputc('+',file);
                                                                                                                                                            fputc('\n',file);
                                                                                                                                                         
                                                                                                                                                            for (int i= SecondNum[100]-1; i>=0; i--) fputc(SecondNum[i]+48,file);
                                                                                                                                                            fputc('\n',file);
                                                                                                                                                         
                                                                                                                                                            fputc('=',file);
                                                                                                                                                            fputc('\n',file);
                                                                                                                                                         
                                                                                                                                                            for (int i= Result[200]-1; i>=0; i--) fputc(Result[i]+48,file);
                                                                                                                                                            fputc('\n',file);
                                                                                                                                                         
                                                                                                                                                            fputc('\n',file);
                                                                                                                                                            fclose(file);
                                                                                                                                                         
                                                                                                                                                            return 0;
                                                                                                                                                        }
                                                                                                                                                        // *** выводим инфу в файл: конец
                                                                                                                                                         
                                                                                                                                                        // *** собственно, сложение: начало
                                                                                                                                                        int summ(unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
                                                                                                                                                        {
                                                                                                                                                            unsigned char tmp, max;
                                                                                                                                                         
                                                                                                                                                            if (FirstNum[100] >= SecondNum[100]) max = FirstNum[100];
                                                                                                                                                            else max = SecondNum[100];
                                                                                                                                                         
                                                                                                                                                            // массивы идут от младших разрядов к старшим
                                                                                                                                                            // складываем пары цифр и кладём сумму в Result, а "в уме"- в tmp
                                                                                                                                                         
                                                                                                                                                            tmp = 0;
                                                                                                                                                            for(int i=0; i <= max; i++)
                                                                                                                                                            {
                                                                                                                                                                tmp = FirstNum[i] + SecondNum[i] + tmp;
                                                                                                                                                         
                                                                                                                                                                Result[i] = div(tmp,10).rem;
                                                                                                                                                                tmp = div(tmp,10).quot;
                                                                                                                                                            }
                                                                                                                                                            Result[max+1] = tmp;
                                                                                                                                                            if(tmp>0) Result[200] = max+1;
                                                                                                                                                            else Result[200] = max;
                                                                                                                                                         
                                                                                                                                                            return 0;
                                                                                                                                                        }
                                                                                                                                                        // *** собственно, сложение: конец
                                                                                                                                                         
                                                                                                                                                        int main()
                                                                                                                                                        {
                                                                                                                                                            unsigned char FirstNum[101]={}, SecondNum[101]={}; // в ячейке 100 хранится кол-во цифр числа
                                                                                                                                                            unsigned char Result[201]={}; // в ячейке 200 хранится кол-во цифр числа
                                                                                                                                                         
                                                                                                                                                            // получаем инфу из файла
                                                                                                                                                            get_input_data("input.txt", FirstNum, SecondNum);
                                                                                                                                                         
                                                                                                                                                            // собственно, сложение
                                                                                                                                                            summ(FirstNum, SecondNum, Result);
                                                                                                                                                         
                                                                                                                                                            // выводим инфу в файл
                                                                                                                                                            put_input_data("output.txt", FirstNum, SecondNum, Result);
                                                                                                                                                         
                                                                                                                                                        }




                                                                                                                                                      Добавлено
                                                                                                                                                      Замеченные недостатки:

                                                                                                                                                      1) Если на входе пустой файл, то прога вылетает с ошибкой.

                                                                                                                                                      2) Если входные числа начинаются с нолей, то прога считает их не убирает, а считает такими же цифрами, как и остальные. В итоге, в выходном файле и входные числа будут начинаться с нолей и выходное число.

                                                                                                                                                      Само суммирование работает, вроде бы, нормально, НО как, блин, его оттестировать до полной уверенности? (впрочем, приблизительно помню как, но лень)

                                                                                                                                                      Добавлено
                                                                                                                                                      Ну и попробую осилить таки умножение.

                                                                                                                                                      Вообще, в дальнейшем буду разбивать задачи на такие, которые, предположительно, успею сделать 2-3 штуки за имеющееся свободное время в течении одного выходного.
                                                                                                                                                        Цитата ya2500 @
                                                                                                                                                        Само суммирование работает, вроде бы, нормально, НО как, блин, его оттестировать до полной уверенности? (

                                                                                                                                                        Цитата ya2500 @
                                                                                                                                                        Ну и попробую осилить таки умножение.


                                                                                                                                                        Отдохнул, поделал дела И минут за 50 сделал умножение... почти сделал. Тестовый пример 9*12345 решается с ошибкой: нет старшей единицы. Остальные тестовые примеры, какие я только мог придумать, решаются нормально. Причём, прога умножает верно, но неверно считает кол-во цифр в числах. Сходу влез поправлять- стало выводиться правильно, но перед результатом идёт лишний 0.

                                                                                                                                                        И засада в том, что не вполне ясно, где именно проблема: может быть и в функции сложения, которую я счёл нормально работающей.
                                                                                                                                                          Наконец-то разобрался. Времени ушло больше, чем на написание.

                                                                                                                                                          Проблема действительно была в проге сложения: она неверно считала 90000 + 21105. Пришлось поправить подсчёт кол-ва цифр в результирующем числе.

                                                                                                                                                          Итого, функция сложения в проге сложения выглядит так:

                                                                                                                                                          Скрытый текст
                                                                                                                                                          ExpandedWrap disabled
                                                                                                                                                            // *** собственно, сложение: начало
                                                                                                                                                            int summ(unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
                                                                                                                                                            {
                                                                                                                                                                unsigned char tmp, max;
                                                                                                                                                             
                                                                                                                                                                if (FirstNum[100] >= SecondNum[100]) max = FirstNum[100];
                                                                                                                                                                else max = SecondNum[100];
                                                                                                                                                             
                                                                                                                                                                // массивы идут от младших разрядов к старшим
                                                                                                                                                                // складываем пары цифр и кладём сумму в Result, а "в уме"- в tmp
                                                                                                                                                             
                                                                                                                                                                tmp = 0;
                                                                                                                                                                for(int i=0; i <= max; i++)
                                                                                                                                                                {
                                                                                                                                                                    tmp = FirstNum[i] + SecondNum[i] + tmp;
                                                                                                                                                             
                                                                                                                                                                    Result[i] = div(tmp,10).rem;
                                                                                                                                                                    tmp = div(tmp,10).quot;
                                                                                                                                                                }
                                                                                                                                                                Result[max+1] = tmp;
                                                                                                                                                                if(tmp>0) Result[200] = max+2;
                                                                                                                                                                else
                                                                                                                                                                {
                                                                                                                                                                    if(Result[max]>0) Result[200] = max+1;
                                                                                                                                                                    else
                                                                                                                                                                    {
                                                                                                                                                                        Result[200] = max;
                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                             
                                                                                                                                                                return 0;
                                                                                                                                                            }
                                                                                                                                                            // *** собственно, сложение: конец



                                                                                                                                                          А прога умножения(полностью) выглядит так

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

                                                                                                                                                          ExpandedWrap disabled
                                                                                                                                                            #include <stdio.h> // для работы с файлами и для sprintf
                                                                                                                                                            #include <stdlib.h> // для div()
                                                                                                                                                             
                                                                                                                                                            // *** получаем инфу из файла: начало
                                                                                                                                                            int get_input_data(char *input_name, unsigned char FirstNum[101], unsigned char SecondNum[101])
                                                                                                                                                            {
                                                                                                                                                                FILE *file;
                                                                                                                                                                unsigned char Tmp[100];
                                                                                                                                                                unsigned char c;
                                                                                                                                                             
                                                                                                                                                                // открываем файл для чтения
                                                                                                                                                                file = fopen(input_name, "r");
                                                                                                                                                                // w- write, r- read, a- append
                                                                                                                                                                
                                                                                                                                                                // если открыть файл не удалось
                                                                                                                                                                if (file == NULL) return -1;
                                                                                                                                                             
                                                                                                                                                                // пропускаем любое кол-во не-цифр
                                                                                                                                                                bool flag= false;
                                                                                                                                                                do
                                                                                                                                                                {
                                                                                                                                                                    c = fgetc(file);
                                                                                                                                                                    if(feof(file)){fclose(file);return -1;}
                                                                                                                                                             
                                                                                                                                                                    if (c < 58 &&  c >= 48 )
                                                                                                                                                                    {
                                                                                                                                                                        // заносим инфу в массив
                                                                                                                                                                        Tmp[0] = c-48;
                                                                                                                                                                        flag = true;
                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                                while (!flag);
                                                                                                                                                             
                                                                                                                                                                //считываем все подряд идущие цифры до не-цифры
                                                                                                                                                                int i = 0;
                                                                                                                                                                do
                                                                                                                                                                {
                                                                                                                                                                    c = fgetc(file);
                                                                                                                                                                    if(feof(file)){fclose(file);return -1;}
                                                                                                                                                             
                                                                                                                                                                    if (c < 58 &&  c >= 48 && i < 100)
                                                                                                                                                                    {
                                                                                                                                                                        // заносим инфу в массив
                                                                                                                                                                        i++;
                                                                                                                                                                        Tmp[i] = c-48;
                                                                                                                                                                    }
                                                                                                                                                                    else
                                                                                                                                                                    {
                                                                                                                                                                        flag = false;
                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                                while (flag);
                                                                                                                                                                // лишние цифры(сверх 100) просто проигнорируются
                                                                                                                                                             
                                                                                                                                                                // заносим Tmp в FirstNum:
                                                                                                                                                                for(int k=0; k<=i; k++) FirstNum[k]= Tmp[i-k];
                                                                                                                                                                FirstNum[100] = i+1;
                                                                                                                                                             
                                                                                                                                                                // пропускаем любое кол-во не-цифр
                                                                                                                                                                do
                                                                                                                                                                {
                                                                                                                                                                    c = fgetc(file);
                                                                                                                                                                    if(feof(file)){fclose(file);return -1;}
                                                                                                                                                             
                                                                                                                                                                    if (c < 58 &&  c >= 48 )
                                                                                                                                                                    {
                                                                                                                                                                        // заносим инфу в массив
                                                                                                                                                                        Tmp[0] = c-48;
                                                                                                                                                                        flag = true;
                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                                while (!flag);
                                                                                                                                                             
                                                                                                                                                                //считываем все подряд идущие цифры до не-цифры
                                                                                                                                                                i = 0;
                                                                                                                                                                do
                                                                                                                                                                {
                                                                                                                                                                    c = fgetc(file);
                                                                                                                                                                    if(feof(file)){fclose(file);return -1;}
                                                                                                                                                             
                                                                                                                                                                    if (c < 58 &&  c >= 48 && i < 100)
                                                                                                                                                                    {
                                                                                                                                                                        // заносим инфу в массив
                                                                                                                                                                        i++;
                                                                                                                                                                        Tmp[i] = c-48;
                                                                                                                                                                    }
                                                                                                                                                                    else
                                                                                                                                                                    {
                                                                                                                                                                        flag = false;
                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                                while (flag);
                                                                                                                                                                // лишние цифры(сверх 100) просто проигнорируются
                                                                                                                                                             
                                                                                                                                                                // заносим Tmp в SecondNum:
                                                                                                                                                                for(int k=0; k<=i; k++) SecondNum[k]= Tmp[i-k];
                                                                                                                                                                SecondNum[100] = i+1;  
                                                                                                                                                             
                                                                                                                                                                // закрываем файл
                                                                                                                                                                fclose(file);
                                                                                                                                                             
                                                                                                                                                                // 0- код успешного завершения
                                                                                                                                                                return 0;
                                                                                                                                                            }
                                                                                                                                                            // *** получаем инфу из файла: конец
                                                                                                                                                             
                                                                                                                                                            // *** выводим инфу в файл: начало
                                                                                                                                                            int put_input_data(char *output_name, unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
                                                                                                                                                            {
                                                                                                                                                                FILE *file;
                                                                                                                                                             
                                                                                                                                                                file = fopen(output_name, "w"); // открываем файл для записи
                                                                                                                                                             
                                                                                                                                                                // если открыть файл не удалось
                                                                                                                                                                if (file == NULL) return -1;
                                                                                                                                                             
                                                                                                                                                                for (int i= FirstNum[100]-1; i>=0; i--) fputc(FirstNum[i]+48,file);
                                                                                                                                                                fputc('\n',file);
                                                                                                                                                             
                                                                                                                                                                fputc('*',file);
                                                                                                                                                                fputc('\n',file);
                                                                                                                                                             
                                                                                                                                                                for (int i= SecondNum[100]-1; i>=0; i--) fputc(SecondNum[i]+48,file);
                                                                                                                                                                fputc('\n',file);
                                                                                                                                                             
                                                                                                                                                                fputc('=',file);
                                                                                                                                                                fputc('\n',file);
                                                                                                                                                             
                                                                                                                                                                for (int i= Result[200]-1; i>=0; i--) fputc(Result[i]+48,file);
                                                                                                                                                                fputc('\n',file);
                                                                                                                                                             
                                                                                                                                                                fputc('\n',file);
                                                                                                                                                                fclose(file);
                                                                                                                                                             
                                                                                                                                                                return 0;
                                                                                                                                                            }
                                                                                                                                                            // *** выводим инфу в файл: конец
                                                                                                                                                             
                                                                                                                                                            // *** наращивание второго числа на первое: начало
                                                                                                                                                            int summ(unsigned char FirstNum[201], unsigned char SecondNum[201])
                                                                                                                                                            {
                                                                                                                                                                unsigned char tmp, max, Result[201]={}; // в ячейке 200 хранится кол-во цифр числа
                                                                                                                                                             
                                                                                                                                                                if (FirstNum[200] >= SecondNum[200]) max = FirstNum[200];
                                                                                                                                                                else max = SecondNum[200];
                                                                                                                                                             
                                                                                                                                                                // конкретно в данной проге эта функция используется так, что результат не вылезет за границы
                                                                                                                                                             
                                                                                                                                                                tmp = 0;
                                                                                                                                                                for(int i=0; i <= max; i++)
                                                                                                                                                                {
                                                                                                                                                                    tmp = FirstNum[i] + SecondNum[i] + tmp;
                                                                                                                                                             
                                                                                                                                                                    Result[i] = div(tmp,10).rem;
                                                                                                                                                                    tmp = div(tmp,10).quot;
                                                                                                                                                                }
                                                                                                                                                                Result[max+1] = tmp;
                                                                                                                                                                if(tmp>0) Result[200] = max+2;
                                                                                                                                                                else
                                                                                                                                                                {
                                                                                                                                                                    if(Result[max]>0) Result[200] = max+1;
                                                                                                                                                                    else
                                                                                                                                                                    {
                                                                                                                                                                        Result[200] = max;
                                                                                                                                                                    }
                                                                                                                                                                }
                                                                                                                                                             
                                                                                                                                                                for(int i=0; i <= 200; i++) SecondNum[i] = Result[i];
                                                                                                                                                             
                                                                                                                                                                return 0;
                                                                                                                                                            }
                                                                                                                                                            // *** наращивание второго числа на первое: конец
                                                                                                                                                             
                                                                                                                                                            // *** собственно, умножение: начало
                                                                                                                                                            int multiplication(unsigned char FirstNum[101], unsigned char SecondNum[101], unsigned char Result[201])
                                                                                                                                                            {
                                                                                                                                                                unsigned char tmp, Temp[201];  // в ячейке 200 хранится кол-во цифр числа
                                                                                                                                                             
                                                                                                                                                                // массивы идут от младших разрядов к старшим
                                                                                                                                                                // каждую цифру второго числа умножаем на первое число
                                                                                                                                                                // получившийся в Temp результат суммируем в Result
                                                                                                                                                             
                                                                                                                                                                for(int i=0; i < SecondNum[100]; i++)
                                                                                                                                                                {
                                                                                                                                                                    tmp = 0;
                                                                                                                                                                    for(int m=0; m <= 200; m++) Temp[m] = 0;
                                                                                                                                                             
                                                                                                                                                                    // каждую цифру второго числа умножаем на первое число
                                                                                                                                                                    for(int k=0; k < FirstNum[100]; k++)
                                                                                                                                                                    {
                                                                                                                                                                        tmp = (FirstNum[k]*SecondNum[i]+tmp);
                                                                                                                                                                        Temp[k +i] = div(tmp,10).rem; // +i даёт нужный сдвиг
                                                                                                                                                                        tmp = div(tmp,10).quot;    
                                                                                                                                                                    }
                                                                                                                                                                    Temp[FirstNum[100] +i] = tmp;
                                                                                                                                                                    if(tmp>0) Temp[200] = FirstNum[100]+1 +i;
                                                                                                                                                                    else Temp[200] = FirstNum[100] +i;
                                                                                                                                                             
                                                                                                                                                             
                                                                                                                                                             
                                                                                                                                                                    // получившийся в Temp результат суммируем в Result
                                                                                                                                                                    summ(Temp, Result);
                                                                                                                                                                }
                                                                                                                                                             
                                                                                                                                                                return 0;
                                                                                                                                                            }
                                                                                                                                                            // *** собственно, умножение: конец
                                                                                                                                                             
                                                                                                                                                            int main()
                                                                                                                                                            {
                                                                                                                                                                unsigned char FirstNum[101]={}, SecondNum[101]={}; // в ячейке 100 хранится кол-во цифр числа
                                                                                                                                                                unsigned char Result[201]={}; // в ячейке 200 хранится кол-во цифр числа
                                                                                                                                                             
                                                                                                                                                                // получаем инфу из файла
                                                                                                                                                                get_input_data("input.txt", FirstNum, SecondNum);
                                                                                                                                                             
                                                                                                                                                                // собственно, умножение
                                                                                                                                                                multiplication(FirstNum, SecondNum, Result);
                                                                                                                                                             
                                                                                                                                                                // выводим инфу в файл
                                                                                                                                                                put_input_data("output.txt", FirstNum, SecondNum, Result);
                                                                                                                                                             
                                                                                                                                                            }



                                                                                                                                                          И теперь я подсмотрю исходник того, кто выполнил это задание первым :)

                                                                                                                                                          Добавлено
                                                                                                                                                          Цитата _lcf_ @
                                                                                                                                                          Скрытый текст


                                                                                                                                                          Нифига непонятно. Это на чём вообще написано? :-?

                                                                                                                                                          Интересует два момента: разобраться, как оно вычисляет результат И разобраться, как оно считает кол-во разрядов результирующего числа.

                                                                                                                                                          Добавлено
                                                                                                                                                          _lcf_, буду признателен за разъяснения.
                                                                                                                                                          Сообщение отредактировано: ya2500 -
                                                                                                                                                            План на следующие выходные:

                                                                                                                                                            1) Сделать деление 100-значных целых чисел. Результат может получиться с плавающей точкой, точность результата- до 100 знаков после запятой, остальное- отбрасывается.

                                                                                                                                                            2) Сделать сложение, умножение, вычитание 100-значных чисел с плавающей точкой(то есть, число представляет из себя строку, длиной до 100 символов, один из которых может быть плавающей точкой).

                                                                                                                                                            И, если успею:
                                                                                                                                                            3) Сделать деление 100-значных чисел с плавающей точкой.

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

                                                                                                                                                            Цитата ya2500 @
                                                                                                                                                            Дано арифметическое выражение, длиной не более 30 символов, состоящее из цифр и знаков


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

                                                                                                                                                            Добавлено
                                                                                                                                                            Но, пока, слишком далеко забегать не буду И после выражения, возьмусь, пожалуй, за "быков и коров"

                                                                                                                                                            Цитата ya2500 @
                                                                                                                                                            Написать программу, подбирающую "секретный пароль" из 15 цифр, получая после каждой попытки информацию о кол-ве быков и коров.


                                                                                                                                                            Цитата ya2500 @
                                                                                                                                                            Как вариант, можно написать прогу просто для игры в "быки и коровы".
                                                                                                                                                              Цитата ya2500 @
                                                                                                                                                              Интересует два момента: разобраться, как оно вычисляет результат И разобраться, как оно считает кол-во разрядов результирующего числа.

                                                                                                                                                              А зачем там что-то особо считать? Полагай, что результат сложения на 1 длиннее самого длинного слагаемого. Если первая цифра результата получится 0 - убираешь её, и всё.
                                                                                                                                                              С умножением похоже - полагаешь длину равной сумме длин множителей, и если первая цифра ноль - убираешь его.
                                                                                                                                                              Подпись была включена в связи с окончанием срока наказания
                                                                                                                                                                Цитата OpenGL @
                                                                                                                                                                А зачем там что-то особо считать? Полагай, что результат сложения на 1 длиннее самого длинного слагаемого. Если первая цифра результата получится 0 - убираешь её, и всё.
                                                                                                                                                                С умножением похоже - полагаешь длину равной сумме длин множителей, и если первая цифра ноль - убираешь его.


                                                                                                                                                                Я тоже так думал. Но, чтобы работало нормально, пришлось в сложении две последние цифры отслеживать. Хотя.. дело, видимо, в том, что я неверно посчитал (номер последняя цифра +1), из-за того, что в c++ массивы начинаются с нулевого индекса.

                                                                                                                                                                Цитата ya2500 @
                                                                                                                                                                План на следующие выходные:


                                                                                                                                                                То есть, на понедельник, 17-го.
                                                                                                                                                                  Цитата ya2500 @
                                                                                                                                                                  Хотя.. дело, видимо, в том, что я неверно посчитал (номер последняя цифра +1), из-за того, что в c++ массивы начинаются с нулевого индекса.


                                                                                                                                                                  Нет, дело не могло быть в этом.. ведь 99*99 считало нормально и 12345*9 считало нормально и кучу других примеров считало нормально и только на 9*12345 почему-то проглатывало старшую цифру.

                                                                                                                                                                  Цитата ya2500 @
                                                                                                                                                                  чтобы работало нормально, пришлось в сложении две последние цифры отслеживать.

                                                                                                                                                                  :scratch:

                                                                                                                                                                  Но некогда в этом ковыряться. Буду двигаться дальше И помнить о том, как важно хорошо тестить проги И сожалеть о том, что нет на это времени.
                                                                                                                                                                    Цитата ya2500 @
                                                                                                                                                                    План на следующие выходные:
                                                                                                                                                                    ...
                                                                                                                                                                    3) Сделать деление 100-значных чисел с плавающей точкой.


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

                                                                                                                                                                        Цитата ya2500 @
                                                                                                                                                                        вскользь упомянуты некоторые из ресурсов, на которых можно найти годные задачи на программирование

                                                                                                                                                                        Цитата ya2500 @
                                                                                                                                                                        Цитата
                                                                                                                                                                        Даны два целых положительных числа, длиной не более 100 цифр каждое. Вычислить произведение этих чисел. И входные и выходные данные должны храниться с абсолютной точностью.

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

                                                                                                                                                                        - ну вот такая простая задачка, для начала.


                                                                                                                                                                        Цитата ya2500 @
                                                                                                                                                                        Задачку эту я выделил из более сложной:


                                                                                                                                                                        Цитата Славян @
                                                                                                                                                                        Большого смысла в 30 символах не вижу: всё равно потянет написать простенький парсер...


                                                                                                                                                                        Надо бы эти числа(100, 30) хранить в константах.

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

                                                                                                                                                                        ===

                                                                                                                                                                        А конкретно, опять начну сначала: буду пилить сложение 2х больших чисел. И, на этот раз, уделю особое внимание тщательному тестированию сделанного.


                                                                                                                                                                        ===

                                                                                                                                                                        Случайно раскопал древнюю книжку "Программирование игр и головоломок", автор Жан Арсак, задания рассчитаны на комп, не имеющий графического монитора. Вот, думаю, лучше пороюсь-ка я для начала в ней.

                                                                                                                                                                        Чтобы начать с чего-нить простого и относительно увлекательного.
                                                                                                                                                                        Сообщение отредактировано: ya2500 -
                                                                                                                                                                          Блин, ерунда какая-то. Надо остановиться и хорошо подумать.
                                                                                                                                                                            Цитата ya2500 @
                                                                                                                                                                            _lcf_, буду признателен за разъяснения.

                                                                                                                                                                            умножение столбиком! :lool: :lool:
                                                                                                                                                                              Открылась регистрация на международный чемпионат по спортивному программированию — Яндекс.Алгоритм 2018:
                                                                                                                                                                              https://academy.yandex.ru/events/algorithm/2018/#desc

                                                                                                                                                                              подробный разбор задач финала Яндекс.Алгоритм 2017:
                                                                                                                                                                              https://habrahabr.ru/company/yandex/blog/334250/
                                                                                                                                                                              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                                                                                                                                                              0 пользователей:


                                                                                                                                                                              Рейтинг@Mail.ru
                                                                                                                                                                              [ Script Execution time: 0,8903 ]   [ 17 queries used ]   [ Generated: 19.09.19, 10:40 GMT ]