Интересное и Юмор - страница 3621

[Server Muradasilov]

.

[Server Muradasilov]

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

Входные данные:

1.Указанная сумма денег.

2.Массив со всеми доступными номиналами монет.

Нужно написать функцию, которая на выходе выдаст количество всех возможных способов получить указанную сумму денег при помощи различных доступных номиналов монет. Например, если вам нужно получить 4 цента из монет номиналами 1, 2 и 3 цента, то функция вернет 4 — именно столько есть возможных комбинаций из чисел 1, 2 и 3, чтобы получить в сумме 4:

1.  1, 1, 1, 1.

2.  1, 1, 2.

3.  1, 3.

4.  2, 2.

[Sergey Dzyublik]

Server Muradasilov:

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

Входные данные:

1.Указанная сумма денег.

2.Массив со всеми доступными номиналами монет.

Нужно написать функцию, которая на выходе выдаст количество всех возможных способов получить указанную сумму денег при помощи различных доступных номиналов монет. Например, если вам нужно получить 4 цента из монет номиналами 1, 2 и 3 цента, то функция вернет 4 — именно столько есть возможных комбинаций из чисел 1, 2 и 3, чтобы получить в сумме 4:

1.  1, 1, 1, 1.

2.  1, 1, 2.

3.  1, 3.

4.  2, 2.

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

[Yuriy Zaytsev]

[Server Muradasilov]

[Vitalie Postolache]

[Aleksey Levashov]

[Aleksandr Prishenko]

Alexey Volchanskiy:
Загадка на выходные: "самая сложная в мире" логическая задача

 Решение задачи есть даже в Векипедии.  Для людей в наше время инопланетяне  реальнее богов.)))   

«Самая сложная логическая головоломка»^[1](итал. L'indovinello più difficile del mondo) — название логической задачи, предложенной американским философом и логикомДжорджем Булосомв итальянской газете «la Repubblica» в1992 году:

Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Каждый вопрос задаётся только одному богу, но можно задавать одному богу более одного вопроса. Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja», причём неизвестно, какое слово обозначает «да», а какое «нет».

Булос также разъясняет некоторые моменты задачи:

• Можно задавать одному богу более чем один вопрос (поэтому другим богам может быть не задано ни одного вопроса вообще).
• Каков будет следующий вопрос и кому он будет задан, может зависеть от ответа на предыдущий вопрос.
• Бог случая отвечает случайным образом, зависящим от подбрасываний монетки, спрятанной в его голове: если выпадет аверс, то отвечает правдиво, если реверс — то врёт.
• Бог случая отвечает «da» или «ja» на любой вопрос, на который можно ответить «да» либо «нет».

Другие комментарии:

• Нельзя задавать вопросы-«парадоксы», на которые можно ответить и «da» и «ja», или никак нельзя ответить. К примеру, «Ты сейчас ответишь „da“»?
• 
  

История

Булос указывает логикаРэймонда Смаллианакак автора задачи иДжона Маккартиза увеличение сложности задачи из-за неясных трактовок «da» и «ja». Похожие задачи есть в книгах Смаллиана^[2], например, он описывает остров, где половина жителей зомби (они постоянно лгут), а другая половина — люди (они постоянно говорят правду). Ситуацию усложняет факт, что жители острова прекрасно нас понимают, но древнеетабузапрещает им использовать неродные слова. Поэтому они используют ответы «bal» или «da», которые означают «да» и «нет», причём неясно, какое из них что обозначает. Есть ещё ряд подобных головоломок в книге «The Riddle of Scheherazade». Всё это разновидности широко известныхзадач о рыцарях и лжецахСмаллиана.

Одна из таких задач была освещена в фильме «Лабиринт»: есть 2 двери и 2 стражника, один всегда говорит правду, второй всегда лжёт. Одна дверь ведёт к замку, вторая — к гибели. Смысл головоломки состоит в том, чтобы узнать, какая дверь ведёт к замку, задав один вопрос одному стражнику. В фильме Сара спрашивала: «Скажет ли он [другой стражник] мне, что эта дверь ведёт к замку?»^[3]

Решение задачи

Булос предложил решение задачи в той же статье, где он и опубликовал саму задачу. Он заявил, что первым вопросом мы должны найти бога, который не является богом случая, то есть является либо богом правды, либо богом лжи. Есть множество вопросов, которые могут быть заданы для достижения этой цели. Одна из стратегий — использование сложных логических связей в самом вопросе.

Вопрос Булоса: «Означает ли „da“ „да“, если и только если ты бог правды, а бог B — бог случая?». Другой вариант вопроса: «Является ли нечётным число истинных утверждений в следующем списке: ты — бог лжи, „ja“ означает „да“, B — бог случая?»

Решение задачи может быть упрощено, если использовать условные высказывания, противоречащие фактам (counterfactuals)^[4][5]. Идея этого решения состоит в том, что на любой вопрос Q, требующий ответа «да» либо «нет», заданный богу правды или богу лжи:

• Если я спрошу тебя Q, ты ответишь «ja»?

Ответом будет «ja», если верный ответ на вопрос Q это «да», и «da», если верный ответ «нет». Для доказательства этого можно рассмотреть восемь возможных вариантов, предложенных самим Булосом.

• Предположим, что «ja» обозначает «да», а «da» обозначает «нет»:
  • Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «ja», оно обозначает «да».
  • Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «da», оно обозначает «нет».
  • Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «da». То есть правильный ответ на вопрос «ja», который обозначает «да».
  • Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «ja». То есть правильный ответ на вопрос «da», который обозначает «нет».
• Предположим, что «ja» обозначает «нет», а «da» обозначает «да»:
  • Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «da», оно обозначает «да».
  • Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «ja», оно обозначает «нет».
  • Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «ja». Но, так как он лжёт, верный ответ на вопрос Q — «da», что означает «да».
  • Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «da». Но, так как он лжёт, верный ответ на вопрос Q — «ja», что означает «нет».

Используя этот факт, можно задавать вопросы:^[4]

• Спросим бога B: «Если я спрошу у тебя „Бог А — бог случая?“, ты ответишь „ja“?». Если бог B отвечает «ja», значит, либо он бог случая (и отвечает случайным образом), либо он не бог случая, а на самом деле бог A — бог случая. В любом варианте, бог C — это не бог случая. Если же B отвечает «da», то либо он бог случая (и отвечает случайным образом), либо B не бог случая, что означает, что бог А — тоже не бог случая. В любом варианте, бог A — это не бог случая.
• Спросим у бога, который не является богом случая (по результатам предыдущего вопроса, либо A, либо C): «Если я спрошу у тебя: „ты - бог лжи?“, ты ответишь „ja“?». Поскольку он не бог случая, ответ  «da» обозначает, что он бог правды, а ответ «ja» обозначает, что он бог лжи.
• Спросим у этого же бога «Если я у тебя спрошу: „Бог B — бог случая?“, ответишь ли ты „ja“?». Если ответ «ja» — бог B является богом случая, если ответ «da», то бог, с которым ещё не говорили, является богом случая.

Оставшийся бог определяется методом исключения.

[Vitaly Murlenko]

Aleksandr Prishenko:

 Решение задачи есть даже в Векипедии.  Для людей в наше время инопланетяне  реальнее богов.)))   

Года эдак три или более назад, когда ещё существовал отдельный форум mql4.com мы уже решали эту задачу :) И решили не просто успешно, а привели доказательства языком булевой алгебры :)

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

Годах эдак в девяностых я столкнулся с задачей Эйнштейна - там было 5 домов, 5 людей разных национальностей и т.д. Задачка была мною вычитана из ещё советского номера журнала "Наука и жизнь". Цапнула она меня тем, что со слов самого Эйнштейна, решить её могут только 7% населения земного шара. Мне стало любопытно, смогу ли я? Взяв лист бумаги и авторучку, я потратил около двух часов, но решение нашёл. Приятно стало от осознания, что смог-таки. И только спустя годы я узнал, что Эйнштейн, когда сформулировал эту задачу, сказал, что решать её нужно не на бумаге, а в уме :) Вот тут то я и приплыл :)))))))))

[Alexandr Bryzgalov]

Vitaly Murlenko:

Года эдак три или более назад, когда ещё существовал отдельный форум mql4.com мы уже решали эту задачу :) И решили не просто успешно, а привели доказательства языком булевой алгебры :)

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

Годах эдак в девяностых я столкнулся с задачей Эйнштейна - там было 5 домов, 5 людей разных национальностей и т.д. Задачка была мною вычитана из ещё советского номера журнала "Наука и жизнь". Цапнула она меня тем, что со слов самого Эйнштейна, решить её могут только 7% населения земного шара. Мне стало любопытно, смогу ли я? Взяв лист бумаги и авторучку, я потратил около двух часов, но решение нашёл. Приятно стало от осознания, что смог-таки. И только спустя годы я узнал, что Эйнштейн, когда сформулировал эту задачу, сказал, что решать её нужно не на бумаге, а в уме :) Вот тут то я и приплыл :)))))))))

Энштейн вообще говорят шутник был, откуда он знал процент людей которые могут решить задачу? )

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