Логические задачи.

[sto2299]

Логические задачи.

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

Можно сразу давать ссылку на ответ если такая есть в интернете.

Вот например такая задача.

Условие задачи: в скачках участвуют 25 лошадей. В одной скачке может участвовать максимум 5. Условие ограничено тем, что любая выбранная лошадь X в любом забеге скачет с одинаковой скоростью. Время и скорость лошадей засекать нельзя, можно лишь сравнить кто быстрее или медленнее (Vx<Vy).

Найти: минимальное количество забегов, после которых определиться тройка призеров, т.е. 1-е, 2-е и 3-е место среди всех 25 лошадей.

Вот ответ:

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

 

[burning_LEGION]

логические задачи это, конечно, прикольно, но программистам приходиться их решать не чаще всех остальных людей

 

[avbua]

логические задачи это, конечно, прикольно, но программистам приходиться их решать не чаще всех остальных людей

кодерам - да, не часто, программистам почаще.

 

[burning_LEGION]

кодерам - да, не часто, программистам почаще.

как насчет примера такой задачи в большом коммерческом проекте?

 

[Me1]

как насчет примера такой задачи в большом коммерческом проекте?

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

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

 

[sto2299]

Давайте всё таки по сути. Кто знает интересные логические задачи, пишите.

 

[avbua]

1. Составить формулу подсчета суммы из списка подряд расположенных цифр (например 7,8,9,10), начиная от n_first и заканчивая n_last. Под формулой подразумевается исключение каких-либо реализаций циклов или функций, использующих циклы.

Ну такие задачки с часами мы решали ещё лет 25 назад.
(n_first+n_last)*(n_last-n_first+1)/2

2. Функция arcsin в glsl-шейдерах реализована с ошибкой. Логика задачи требует использования этой ф-ии. Ваши решения?

Выразить через другие тригонометрические функции.

 

[avbua]

Вот еще задачка. Немного интересней.

Вы на шоу, где есть 3 закрытых кабинки, в одной из которых приз. У вас есть 1 шанс указать на желаемую кабинку, в которой, как вы считаете, лежит приз. Ведущий знает в какой из кабинок приз. Вы указываете на кабинку, где по вашему лежит приз. Тут ведущий предлагает вам поменять ваше решение, и указывая на одну из оставшихся двух кабинок, говорит что в ней точно нет приза. А ведущий, по условию, не имеет права врать!(т.е. приза там действительно нет). Вопрос - стоит ли вам менять ваше решение с первого выбора на второй(исключив указанную ведущим кабинку из двух оставшихся), или оставаться на той кабинке, которую вы указали вначале?

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

 

[lugal]

Вот еще задачка. Немного интересней.

Вы на шоу, где есть 3 закрытых кабинки, в одной из которых приз. У вас есть 1 шанс указать на желаемую кабинку, в которой, как вы считаете, лежит приз. Ведущий знает в какой из кабинок приз. Вы указываете на кабинку, где по вашему лежит приз. Тут ведущий предлагает вам поменять ваше решение, и указывая на одну из оставшихся двух кабинок, говорит что в ней точно нет приза. А ведущий, по условию, не имеет права врать!(т.е. приза там действительно нет). Вопрос - стоит ли вам менять ваше решение с первого выбора на второй(исключив указанную ведущим кабинку из двух оставшихся), или оставаться на той кабинке, которую вы указали вначале?

Школьный сборник со звездочкой?
Считаем...
Изначально шанс получить приз 1/3.
После заявления ведущего мы получаем 2 кабинки и вероятность для обоих из них становиться 1/2.
Следовательно пофиг - менять или не менять.



Вот вам задачка из области логики...
Докажем что все кони в мире черные путем мат индукции:
1 - Пусть это утверждение верно для n коней. Докажем что оно верно для n+1 коня:
ВОзьмем первые попавшиеся n коней - все они черные согласно условию. Возьмем другие n коней, таким образом что бы n-1 конь соответствовали первой выборке а n-й конь отличался (Мы можем это сделать так как любые n конец всегда черные, согласно условию). Возьмем объеденение этих множеств. ОЧевидно что в этом объеденении будет n+1 черных коней. ЧТо и требовалось доказать.
2 - Докажем что это утверждение верно для 1го коня:
Всем известно что буцефал был черным.

Следовательно раз мы доказали истинность для 1го элемента и доказали итеративность утверждения (имея n элементов удовлетворяющий уловию мы всегда получаем n+1 элемент) - утверждение верно - все кони на зеиле черные.

Внимание вопрос - где логическая ошибка в рассуждениях?

 

[avbua]

Считаем...
Изначально шанс получить приз 1/3.
После заявления ведущего мы получаем 2 кабинки и вероятность для обоих из них становиться 1/2.
Следовательно пофиг - менять или не менять.

Ну смотри, играют двое и указывают всегда на одинаковые кабинки. Первый всегда отказывается от предложения ведущего, а второй всегда принимает предложение ведущего. В данной схеме приз всегда кому-то достаётся. У первого шансы 1/3 и он заберёт треть всех призов, соответственно, второй заберёт 2/3 всех призов.

 

[lugal]

Ну смотри, играют двое и указывают всегда на одинаковые кабинки. Первый всегда отказывается от предложения ведущего, а второй всегда принимает предложение ведущего. В данной схеме приз всегда кому-то достаётся. У первого шансы 1/3 и он заберёт треть всех призов, соответственно, второй заберёт 2/3 всех призов.

ПО условию задачи играет один
После того как ведущий спалил левую кабинку шансы выиграть всегда составляют 1/2.
Абсолютно пофиг - полуполон стакан сверху или снизу.

 

[avbua]

ПО условию задачи играет один

Хорошо, играет один и всегда отказывается от предложения ведущего и забирает 1/3 призов, а Сергей Юрьевич Беляков, который любит разговаривать с телевизором, всегда принимает предложение ведущего и виртуально выигрывает в два раза больше призов.

Подойдём к вопросу с другой стороны, зная что ведущий мне сделает предложение, я выбираю две кабинки где может лежать приз и указываю на третью, затем принимаю предложение ведущего. И если приз в выбраных мною первых двух кабинках, то он мой. Соответственно шансов, что приз в первых двух кабинках 2/3 и значит мои шансы угадать 2/3

 

[lugal]

Хорошо, играет один и всегда отказывается от предложения ведущего и забирает 1/3 призов, а Сергей Юрьевич Беляков, который любит разговаривать с телевизором, всегда принимает предложение ведущего и виртуально выигрывает в два раза больше призов.

Подойдём к вопросу с другой стороны, зная что ведущий мне сделает предложение, я выбираю две кабинки где может лежать приз и указываю на третью, затем принимаю предложение ведущего. И если приз в выбраных мною первых двух кабинках, то он мой. Соответственно шансов, что приз в первых двух кабинках 2/3 и значит мои шансы угадать 2/3

Предложение ведущего нифига не меняет
ПОложим изначально ты выбрал кабинку с призом. Ведущий указывает на любую кабинку без приза и говорит что приза там нет. Далее если ты выбераешь оставшуюся кабинку, то приза там гарантировано нет.
Положим ты выбрал кабинку без приза. Ведущий указывает на оставшуюся кабинку без приза. ТЫ принимешь его предложение и гарантировано получаешь приз...
Казалось бы вероятность выбрать кабинку с призом 1/3, кабинку без приза 2/3. Следовательно вероятность получить приз в итоге 2/3.
Но это не так...
Потому что ведуший по факту исключает одну пустую кабинку. И задача сводиться к выбору из 2х. Либо принять предложение ведущего либо нет. В обоих слуяах вероятность успешного исхода 1/2 как и в случае выбора из двух кабинок.

 

[avbua]

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

Откуда взялась вторая попытка? Согласно задаче даётся 1 попытка/шанс(открытие кабинки).

 

[swisst]

Подойдём к вопросу с другой стороны, зная что ведущий мне сделает предложение, я выбираю две кабинки где может лежать приз и указываю на третью, затем принимаю предложение ведущего. И если приз в выбраных мною первых двух кабинках, то он мой. Соответственно шансов, что приз в первых двух кабинках 2/3 и значит мои шансы угадать 2/3

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

 

[avbua]

но ведь можно рассмотреть ситуацию, начав ее анализ с того момента, как ведущий исключил одну кабинку. Так? Тогда у вас кол-во вариантов уменьшается, с 3 до 2. Т.е. вероятность увеличивается с 1/3 до 1/2.

Но шансов попасть призу в мою кабинку 1/3, а шансов попасть призу в кабинку, предложеную ведущим 2/3.

 

[lugal]

Но шансов попасть призу в мою кабинку 1/3, а шансов попасть призу в кабинку, предложеную ведущим 2/3.

Чо? Ведуший не предлагает кабинку. Он гарантировано исключает 1 кабинку без приза, причем в не зависимости от того выбрали вы кабинку с призом или без и независимо от того, измените ли вы свой выбо или нет.

 

[avbua]

Чо? Ведуший не предлагает кабинку. Он гарантировано исключает 1 кабинку без приза, причем в не зависимости от того выбрали вы кабинку с призом или без и независимо от того, измените ли вы свой выбо или нет.

Есть кабинка указанная мною, шанс что там приз 1/3. Есть две оставшиеся кабинки с шансом нахождения приза 2/3 и после того как ведущий указал на кабинку без приза, шанс их никак не поменялся.

 

[lugal]

Есть кабинка указанная мною, шанс что там приз 1/3. Есть две оставшиеся кабинки с шансом нахождения приза 2/3 и после того как ведущий указал на кабинку без приза, шанс их никак не поменялся.

Не подменяйте пространства вероятностей

 

[Vlad777]

а том то и дело, что ту одно поле вероятностей.
просто ведущим оно было сужено)

А почему сужено?

lugal сразу так и сказал : вероятность угадать, что приз в одной из двух кабинок 2/3, если из этих двух потом еще угадывать - 1/2, т.е (2/3)*(1/2) = 1/3, что и равно вероятности угадать одну из трех