Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 87
Просто список задачек как таковой мало интересен. А вот описание различных вариантов решения было бы интересно почитать.
p.s.
≥ больше либо равно
≤ меньше либо равно
≠ не равно
p.s.
≥ больше либо равно
≤ меньше либо равно
≠ не равно
Это перевод, как есть. Я знаю не все решения. Я полагаю, что не все решены. Могу выложить известные мне решения отдельным материалом.
Выложи отдельный пост и предложи решение задачки с невестой. На мой взгляд, невесте стоит составить ограниченный список вопросов по приоритетам, затем собрать воедино женихов и одновременно задавать вопросы по порядку сразу всем, если ответ не устраивает — прогонять.
Сразу всем нельзя — ограничения задачи, только по очереди.
Решение Березовского
Провести вменяемое количество опытов, скажем 1000. Далее если кандидат превосходит весь пройденный материал хотя бы по одному параметру, например самый лысый, то считать годным. Потом подругам хвастаться, мой по крайней мере самый лысый
Решение Березовского
Провести вменяемое количество опытов, скажем 1000. Далее если кандидат превосходит весь пройденный материал хотя бы по одному параметру, например самый лысый, то считать годным. Потом подругам хвастаться, мой по крайней мере самый лысый
Я в МГУ в 90х годах слышал про эту задачу в такой постановке - мы приходим на продуктовый рынок, там цены на одни и те же товары сравнимого качества сильно разнятся, пусть это будут помидоры, задача - купить самые дешевые помидоры, не возвращаясь обратно.
Решение
Нужно обойти примерно размер рынка деленное на "e" и купить первые помидоры, которые дешевле тех, что уже обошли. Это будут с большой вероятностью самые дешевые помидоры.
Задача про собеседование, аналогичная задаче невесте, приводится с решением в книге «с ослом» (Кормен, Лейзерсон, Ривест. Алгоритмы. Построение и анализ).
Если заранее известно число кандидатов (N), то нужно пропустить первых k = N/e независимо от их качеств (пусть качества каждого кандидата оцениваются одним числом), после чего либо следует выбрать первого кандидата, оказавшегося лучше первых k, либо последнего.
Если заранее известно число кандидатов (N), то нужно пропустить первых k = N/e независимо от их качеств (пусть качества каждого кандидата оцениваются одним числом), после чего либо следует выбрать первого кандидата, оказавшегося лучше первых k, либо последнего.
Как написано у Гарднера, «Если первый же, кто делает ей предложение, очень близок к ее идеалу, то, как написал нам один из читателей, «она будет просто дурой, если не примет предложения». ». Решение с N/e предполагает, что нам вообще неизвестна функция распределения женихов по «качеству», а есть только функция сравнения (как в типичной задаче сортировки).
По человечески, я Бауманку заканчивал, приятно было ощутить соосность. Что в курилках MIT о том же трепятся
Задача 1 — встречал такую, только не с 12 шарами, а с 13
Да там суть решения не изменится, все равно первое взвешивание по 4 шара на каждую сторону, и дальше от этого плясать.
там всегда надо по 4 взвешивать. Просто правильный порядок взвешивания выбрать.
как-то так
пусть a — первая чашка легче, b — равно, c — вторая легче. Имеем 27 вариантов от aaa до ссс. откидываем bbb. Остается 26. А затем учитываем, что мы не знаем, легче шар или тяжелее, aba == cbc, например. отбираем разные варианты и подбираем номера шаров, которые дадут 12 (13) разных исходов
а в 3 попытки уложитесь?
Вполне
Мы получаем 13 пар ((aaa,ccc),(aab,ccb),(aac,cсa)...). «ааа» = все три раза левая чаша легче, «ссс» = все три раза правая чаша легче. так как мы не знаем, легче или тяжелее неизвестный шар, для нас исходы ааа и ссс — равнозначны.
Из полученных 13 пар выбираем 12 вариантов таким образом, чтоб буквы а, b и c находились на первой, второй и третьей позиции по 4 раза. Я подобрал, например, так:
Combination Number Combination
ccb 1 aab
aac 2 cca
aba 3 cbc
cbb 4 abb
cba 5 abc
aca 6 cac
cab 7 acb
acc 8 caa
bcc 9 baa
bab 10 bcb
bac 11 bca
bba 12 bbc
Слева и справа у нас «эквивалентные» комбинации.
Присвавиваем полученным комбинациям номера от 1 до 12.
далее логика такая: Число 1, комбинация ccb. Значит, шар №1 в первом взвешивании лежит на правой чаше, во втором — тоже на правой, а в третьем взвешивании не участвует. и т.д.
Для такого выбора получаем взвешивания:
1. №№ 2,3,6,8 и 1,4,5,7
2. №№ 2,7,10,11 и 1,6,8,9
3. №№ 3,5,6,12 и 2,8,9,11
Проверка: пусть у нас более тяжелый шар №8. Видим, что исход будет такой: caa. По табличке — это соответствует номеру 8.
Из полученных 13 пар выбираем 12 вариантов таким образом, чтоб буквы а, b и c находились на первой, второй и третьей позиции по 4 раза. Я подобрал, например, так:
Combination Number Combination
ccb 1 aab
aac 2 cca
aba 3 cbc
cbb 4 abb
cba 5 abc
aca 6 cac
cab 7 acb
acc 8 caa
bcc 9 baa
bab 10 bcb
bac 11 bca
bba 12 bbc
Слева и справа у нас «эквивалентные» комбинации.
Присвавиваем полученным комбинациям номера от 1 до 12.
далее логика такая: Число 1, комбинация ccb. Значит, шар №1 в первом взвешивании лежит на правой чаше, во втором — тоже на правой, а в третьем взвешивании не участвует. и т.д.
Для такого выбора получаем взвешивания:
1. №№ 2,3,6,8 и 1,4,5,7
2. №№ 2,7,10,11 и 1,6,8,9
3. №№ 3,5,6,12 и 2,8,9,11
Проверка: пусть у нас более тяжелый шар №8. Видим, что исход будет такой: caa. По табличке — это соответствует номеру 8.
А, ну и 13 шар определяется исходом bbb — то есть как шар, который ни разу не взвешивали, а все три взвешивания показали равенство.
Здесь задача с подвохом — вам не известно легче или тяжелее шар. «Ваша задача заключается в том, чтобы определить какой именно и легче он или тяжелее»
Если при первом взвешивании положить на каждую чашу по три шара мы будем знать в любом результате по меньшей мере шестерку не бракованных шаров.
О, а 3я задача красивая.
Плод моего воображения
Закодируем номер каждой бутылки в двоичной системе счисления, пронумеруем мышек от 1 до 10, и каждую бутылку дадим попробовать тем мышкам, у которых номера совпадают с единицами в двоичной записи номера бутылки. Например, из бутылки с номером 1100110001 отведают вина мышки с номерами 1, 2, 5, 6, 10. Таким образом из каждой бутылки выпьет хотя бы одна мышка. Номер каждой бутылки — число от 1 до 1000, а десятью двоичными цифрами можно закодировать любое число от 1 до 1024 (вообще-то от 0 до 1023, но здесь не важно). По истечении суток смотрим, какие мышки сдохли, декодируем число и однозначно восстанавливаем номер бутылки. PROFIT, ибо на вечеринку отправятся 999 бутылок.
Недостаток решения: каждой мышке придётся выпить примерно из 500 бутылок. Реалистичный прогноз: все они загнутся раньше 24 часов от передозировки алкоголя или гипергидратации.
Недостаток решения: каждой мышке придётся выпить примерно из 500 бутылок. Реалистичный прогноз: все они загнутся раньше 24 часов от передозировки алкоголя или гипергидратации.
Можно проще — распределить бутылки на 10 мышей, итого получим 100 рядов по 10 бутылок. Каждая мышь выпивает в ряду из своей и соседней. например, первая выпивает из бутылки 1 и 2 и переходит к бутылке 11 и 12, затем 21 и 22 и т.д. Вторая мышь выпивает из 2 и 3, 12 и 13 и т.д. Десятая мышь пьет 10 и 1, 20 и 11 и т.д. Далее смотрим какие мыши траванулись — если 2 и 3, то яд в 3й бутылке (т.е. на персечении множеств), если отравились 1 и 2, то яд во второй бутылке. Суть решения такое же, просто подход обозначение несколько иное.
Не понял.
Пусть отравились 1 и 2 мыши. Первая пила из бутылок с номерами 1, 2, 11, 12, ..., 991, 992. Вторая — из 2, 3, 12, 13, ..., 992, 993. Пересечение — 2, 12, ..., 992.
Пусть отравились 1 и 2 мыши. Первая пила из бутылок с номерами 1, 2, 11, 12, ..., 991, 992. Вторая — из 2, 3, 12, 13, ..., 992, 993. Пересечение — 2, 12, ..., 992.
В вашем варианты если отравились мыши 2 и 3, то нужно выкинуть бутылки (3,13,23,33...)
Предложенный выше вариант предполагает, что 999 бутылок попадут на вечеринку.
Предложенный выше вариант предполагает, что 999 бутылок попадут на вечеринку.
Элегантно. Апплодисменты.
Третья задача часто встречается в варианте «240 бочек, 48 часов до момента Х, 5 тестеров, смерть наступает не позднее, чем через 24 часа (т.е. может и раньше) ». И главные действущие лица: патриций и рабы, никакой жестокости в обращении с животными
Задача 9.
Мы конечно не знаем закон, по которому распределены случайные числа в конвертах, но предположим, что это равномерное распределение на (0; +inf).
Тогда F(x)=0 для любого x, где F(x) — вероятность того, что случайное число X < x.
Открываем один из конвертов, случайное число в нём принимает конкретное значение x.
Вероятность того, что число в другом конверте меьше, равна нулю, соответстенно нужно открыть второй конверт и мы со 100% вероятностью получим большее число.
P.S. Вас не должно смущать что конкретное меньшее число в конверте появиться может, но вероятность этого равна нулю. Такова уж теория вероятностей.
Мы конечно не знаем закон, по которому распределены случайные числа в конвертах, но предположим, что это равномерное распределение на (0; +inf).
Тогда F(x)=0 для любого x, где F(x) — вероятность того, что случайное число X < x.
Открываем один из конвертов, случайное число в нём принимает конкретное значение x.
Вероятность того, что число в другом конверте меьше, равна нулю, соответстенно нужно открыть второй конверт и мы со 100% вероятностью получим большее число.
P.S. Вас не должно смущать что конкретное меньшее число в конверте появиться может, но вероятность этого равна нулю. Такова уж теория вероятностей.
Тут я недостаточно подкован, теряю нить.
Как уже указывалось, мне задачка встречалась в формулировке, где содержимое конвертов можно полагать рознящимся вдвое. Обнаруживаем в конверте 100 и ожидаем в другом 50 или 200 с равными вероятностями, то есть (1/2)*50 + (1/2)*200 = 125. Уверенно выбираем оставшийся нераспечатанным.
Как уже указывалось, мне задачка встречалась в формулировке, где содержимое конвертов можно полагать рознящимся вдвое. Обнаруживаем в конверте 100 и ожидаем в другом 50 или 200 с равными вероятностями, то есть (1/2)*50 + (1/2)*200 = 125. Уверенно выбираем оставшийся нераспечатанным.
Если представить себе, что на втором конверте сидит второй игрок, он тем же образом получит выигрушность обмена конвертами и для себя тоже, а оба игрока выигрывать не могут.
Ошибка в подсчете вероятности, там вовсе не 50/50 )
Самая простая стратегия — вибираем любое число X, и если в открытом конверте значение меньше X — производим обмен. Этот прием увеличивает вероятность выбора с исходных 50% на чуть большую величину (на сколько именно — зависит от того, какова плотность значений в районе X).
Для ещё большего гарантированного увеличения уже потребуется дополнительная информация о распределении значений, например, для игры, где значения отличаются в два раза — разбиваем все на непересекающиеся промежутки [a/2, 2a), [b/2, 2b),… и в зависимости от того в какой промежуток попали — сравниваем с a или с b и т.д.
Самая простая стратегия — вибираем любое число X, и если в открытом конверте значение меньше X — производим обмен. Этот прием увеличивает вероятность выбора с исходных 50% на чуть большую величину (на сколько именно — зависит от того, какова плотность значений в районе X).
Для ещё большего гарантированного увеличения уже потребуется дополнительная информация о распределении значений, например, для игры, где значения отличаются в два раза — разбиваем все на непересекающиеся промежутки [a/2, 2a), [b/2, 2b),… и в зависимости от того в какой промежуток попали — сравниваем с a или с b и т.д.
А если представить себе, что на другом конверте сидит другой игрок? Воспользовавшись тем же алгоритмом, он придет к такому же выводу и согласится поменяться, но обмен, очевидно, не может быть выигрышным для обоих игроков, и ни один игрок не может выигрывать чаще — они же в одинаковых условиях. Получаем равновероятность. По идее, ваша логика должна работать, если число появляется в момент вскрытия конверта, но не в случае, когда число на момент начала игры уже зафиксировано.
Если бы было сказано «положительные целые числа», то можно было бы легко выкрутится правилом «если увидели в первом конверте число 1 — выбираем второй». И того на множестве пар любых положительных целых чисел мы в среднем будем выбирать большее число в > 50% случаев. Но сказано просто «положительные», так что тут фиг его знает.
Если натуральные — то все, похоже, зависит от способа рандомизации. По идее, если сначала сгенерировать два случайных, а потом случайно одно из них дать в конверте игроку — то будет, очевидно, 50% (если у игрока не 1; собственно, в задаче с конкретной, поставленной здесь целью это будет верно не только для натуральных, а для любых чисел). Если сначала сгенерировать одно, дать игроку выбрать, а при вскрытии конверта сгенерировать второе (неважно, получит его игрок или нет) — то с вероятностью 100% второе будет больше, так как меньших чисел всего-навсего конечно. Вообще эта задача сильно отличается от классической проблемы двух конвертов — там нас просят максимизировать выигрыш, а тут надо всего-навсего с максимальной вероятностью получить большее число, неважно, насколько именно оно будет больше.
Мы конечно не знаем закон, по которому распределены случайные числа в конвертах, но предположим, что это равномерное распределение на (0; +inf).Собственно закон распределения тут играет решающую роль при выборе стратегии. Что такое «равномерное распределение на (0:+inf)» науке не известно, посему и все остальные рассуждения смысле не имеют.
Закон распределения не имеет никакого значения. Даже если каждый раз в конвертах будет одна и та же пара чисел, стратегия будет работать. Надо только выбирать не только случайную степень двойки (опять, с любой функцией распределения — лишь бы вероятность каждой степени было ненулевой), но и брать строго случайный конверт из двух предложенных.
Вы о какой стратегии говорите? Я отвечал на пост Andrew1000000. Там ни о каких степенях двойки речи не было.
,
,
Не заметил. Я говорил об этой стратегии: habrahabr.ru/post/202682/#comment_7001972
Согласен, что условие задачи некорректное.
Нужно либо указать закон распределения, либо сделать уточнение, как в топике, что числа отличаются в два раза.
А всё-таки интересно, можно ли определить равномерное распределение на бесконечности, например так:
F(x)=0 для любого x.
Тогда f(x)=F'(x)=0 тоже для любого x.
Вот здесь тоже задавались этим вопросом.
Нужно либо указать закон распределения, либо сделать уточнение, как в топике, что числа отличаются в два раза.
А всё-таки интересно, можно ли определить равномерное распределение на бесконечности, например так:
F(x)=0 для любого x.
Тогда f(x)=F'(x)=0 тоже для любого x.
Вот здесь тоже задавались этим вопросом.
Почему же некорректное? Распределение неизвестно, отношение сумм неизвестно, выигрывает игрок, если выберет конверт с большей суммой… решение существует. Только если отношение сумм в конвертах неизвестно, придётся выбирать случайное число с распределением, плотным на всей прямой. Например, с плотностью 1/(pi*(1+x^2)). Всё равно шанс, что оно окажется между суммами в конвертах, ненулевой (как бы ни играло казино) — и в этом случае мы выиграем. А в остальных случаях шанс на выигрыш будет ровно 50%.
Равномерного распределения на всей прямой, к сожалению, не существует.
Равномерного распределения на всей прямой, к сожалению, не существует.
Про равномерное распределение на всей прямой:
Существенным условием является интеграл от плотности — он должен быть равен 1. Для константных функций из R в R такое невозможно.
Если расширить действительные числа бесконечно малыми величинами, то построить константную функцию можно, но при таком расширении нарушаются многие другие аксиоматические требования и нужно заново выстраивать всю теорию вероятностей. Может быть кто-то и пытался этим заниматься, но если результат и был, то большого распространения он не получил.
Существенным условием является интеграл от плотности — он должен быть равен 1. Для константных функций из R в R такое невозможно.
Если расширить действительные числа бесконечно малыми величинами, то построить константную функцию можно, но при таком расширении нарушаются многие другие аксиоматические требования и нужно заново выстраивать всю теорию вероятностей. Может быть кто-то и пытался этим заниматься, но если результат и был, то большого распространения он не получил.
Задача 6 представляется в совсем ином свете, если доступны арифметические операции ADD и SUB )
В частности, классический вариант — быстро посчитать кол-во единичных бит в 32-х битном слове на стандартной x86 архитектуре )
В частности, классический вариант — быстро посчитать кол-во единичных бит в 32-х битном слове на стандартной x86 архитектуре )
В задаче 6 не сказано, есть ли загрузка константы. Думаю, что сдвиг всегда на 1 бит. Если загрузки константы нет (то есть, мы даже младший бит выделить не можем быстрее, чем за n-2 операции (хотя нет, можем за 3)), то дело становится интересным. Похоже, что ответ порядка n*log(n), но надо считать точнее.
Я как-то программировал игру «жизнь» с использованием битовых масок для представления поля — так там была похожая задачка: по 8 маскам построить две — в одной будут те разряды, в которых единички есть ровно в 2 масках из 8, в другой — в которых единички ровно в 3 масках.
Делал через сложение с помощью and,or,xor.
Я как-то программировал игру «жизнь» с использованием битовых масок для представления поля — так там была похожая задачка: по 8 маскам построить две — в одной будут те разряды, в которых единички есть ровно в 2 масках из 8, в другой — в которых единички ровно в 3 масках.
Делал через сложение с помощью and,or,xor.
В задачке 7 первая реакция — посчитаем интеграл, получим 100/3 * sqrt(50), то есть примерно 236. А дальше зависит от того, сколько есть времени — можно посчитать сумму нескольких первых, а остальное добить интегралом. Или посчитать все корни до 3 знаков… 2 листочков должно хватить.
Задачки 8,10,11,13 пока не встречались (про 10 что-то слышал). Надо их подумать.
Задачки 8,10,11,13 пока не встречались (про 10 что-то слышал). Надо их подумать.
Задачи 2, 3, 4 мне давали на различных собеседованиях
задача 10 с тремя звездами
куб не разбиваем, в отличие от квадрата.
доказательство тут ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B0#.D0.9A.D1.83.D0.B1.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BA.D1.83.D0.B1.D0.B0
это скорее на знания и общую эрудицию задачи.
куб не разбиваем, в отличие от квадрата.
доказательство тут ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B0#.D0.9A.D1.83.D0.B1.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BA.D1.83.D0.B1.D0.B0
это скорее на знания и общую эрудицию задачи.
такое мнение что задачи со звездой, часто встречаются на собеседованиях и мелькают в инете регулярно,
задача 13 например, сильно напоминает задачу о мудрецах habrahabr.ru/post/72824/
задачи с двумя звездами достаточно сложны, в разных вариациях встречаются и разрешимы.
а три звезды — это заведомые нерешайки…
задача 13 например, сильно напоминает задачу о мудрецах habrahabr.ru/post/72824/
задачи с двумя звездами достаточно сложны, в разных вариациях встречаются и разрешимы.
а три звезды — это заведомые нерешайки…
задача 9 по смыслу похожа на задачу профессора из фильма «21», только чуть чуть надо прописать стратегию…
ну и напоследок: 7я задача без звездочек. — это школьная программма — сумма геометрической прогрессии
1^(`1/2) + 2^(1/2) +…
Если вкратце, то это — не прогрессия.
Геометрическая прогрессия — это показательный ряд (не уверен в точности термина; скажем, ряд, соответствующий показательной функции) an
В данном случае — степенной ряд na.
Это все-таки очень разные вещи.
Геометрическая прогрессия — это показательный ряд (не уверен в точности термина; скажем, ряд, соответствующий показательной функции) an
В данном случае — степенной ряд na.
Это все-таки очень разные вещи.
согласна.
это сумма ряда. не прогрессия. и уж тем более не геометрическая.
ошиблась.
и сумма степенного ряда тоже считается. но, действительно уже не в школьной программе.
виноватая.
это сумма ряда. не прогрессия. и уж тем более не геометрическая.
ошиблась.
и сумма степенного ряда тоже считается. но, действительно уже не в школьной программе.
виноватая.
Можно написать
sqrt(n-1)=sqrt(n)*(1-1/2n-1/8n^2-1/16n^3-...)
(это бином Ньютона),
задать функцию S(n)=sqrt(n)*(2/3*n+a+b/n+c/n^2+...)
и потребовать условие S(n)-S(n-1)=sqrt(n).
Методом неопределённых коэффициентов находим a=1/2, b=1/24, c не находится — ну и не надо.
Теперь сумму sqrt(a+1)+sqrt(a+2)+...+sqrt(b) можно оценить как S(b)-S(a).
Находим S(50)=sqrt(50)*(100/3+1/2+1/1200)=239.2
S(5)-sqrt(5)=sqrt(5)*(7/3+1/2+1/120)=6.35
sqrt(1)+...+sqrt(50)=S(50)-(S(5)-sqrt(5))+1+sqrt(2)+sqrt(3)+2=239.0. Пишем это в качестве ответа. Всё решение — поллисточка.
Если бы мы посчитали S(50) с большим числом знаков, получили бы
S(50)-(S(5)-sqrt(5))+1+sqrt(2)+sqrt(3)+2=239.0357914
Правильный ответ — 239.0358004, то есть ошибка была бы 10^(-5) (а у нас получилась 0.035 — меньше надо было с sqrt(50) лениться, ведь ясно, что это примерно 7.071068 — строится из 8 знаков sqrt(2)).
sqrt(n-1)=sqrt(n)*(1-1/2n-1/8n^2-1/16n^3-...)
(это бином Ньютона),
задать функцию S(n)=sqrt(n)*(2/3*n+a+b/n+c/n^2+...)
и потребовать условие S(n)-S(n-1)=sqrt(n).
Методом неопределённых коэффициентов находим a=1/2, b=1/24, c не находится — ну и не надо.
Теперь сумму sqrt(a+1)+sqrt(a+2)+...+sqrt(b) можно оценить как S(b)-S(a).
Находим S(50)=sqrt(50)*(100/3+1/2+1/1200)=239.2
S(5)-sqrt(5)=sqrt(5)*(7/3+1/2+1/120)=6.35
sqrt(1)+...+sqrt(50)=S(50)-(S(5)-sqrt(5))+1+sqrt(2)+sqrt(3)+2=239.0. Пишем это в качестве ответа. Всё решение — поллисточка.
Если бы мы посчитали S(50) с большим числом знаков, получили бы
S(50)-(S(5)-sqrt(5))+1+sqrt(2)+sqrt(3)+2=239.0357914
Правильный ответ — 239.0358004, то есть ошибка была бы 10^(-5) (а у нас получилась 0.035 — меньше надо было с sqrt(50) лениться, ведь ясно, что это примерно 7.071068 — строится из 8 знаков sqrt(2)).
да верю я,
написала же, что ошиблась, сказав, что это геометрическая прогрессия…
меня интересовала больше сложность задач, и то что,
часть из задач заведомо не решаемы,
а часть имеют решения но сложные,
а часть стандартные…
ну почему вы не читаете коменты с нчала?
вот кстате ответ экселя на туже сумму. можете сопоставить неточность. 239,0358006
написала же, что ошиблась, сказав, что это геометрическая прогрессия…
меня интересовала больше сложность задач, и то что,
часть из задач заведомо не решаемы,
а часть имеют решения но сложные,
а часть стандартные…
ну почему вы не читаете коменты с нчала?
вот кстате ответ экселя на туже сумму. можете сопоставить неточность. 239,0358006
Сумма квадратных корней равна S(n)+C1
C1=-1/(Pi)*(1+1/2V2+1/3V3+1/4V4+...), примерно 0,21
C1=-1/(Pi)*(1+1/2V2+1/3V3+1/4V4+...), примерно 0,21
Задача 7.
1+√2+√3+2+√5+√2*√3+√7+2*√2+3+√2*√5+√11+2*√3+√13+√2*√7+√3*√5+4+√17+3*√2+√19+2*√5+√3*√7+√2*√11+√23+2*√2*√3+5=15+√2(1+√3+2+√5+√7+3+√11+2*√3)+√3*(1+2+√5+√7)+√5(1+2)+√7+√11+√13+√17+√19+√23=15+√2*(6+3*√3+√5+√7+√11)+√3*(3+√5+√7)+3*√5=15+27,4+13,7+6,7=62,8
Это для первых 25 чисел, дальше лень считать.
Нет, в лоб тут не посчитаешь, нужно найти какую-то закономерность, но пока ничего в голову не приходит.
1+√2+√3+2+√5+√2*√3+√7+2*√2+3+√2*√5+√11+2*√3+√13+√2*√7+√3*√5+4+√17+3*√2+√19+2*√5+√3*√7+√2*√11+√23+2*√2*√3+5=15+√2(1+√3+2+√5+√7+3+√11+2*√3)+√3*(1+2+√5+√7)+√5(1+2)+√7+√11+√13+√17+√19+√23=15+√2*(6+3*√3+√5+√7+√11)+√3*(3+√5+√7)+3*√5=15+27,4+13,7+6,7=62,8
Это для первых 25 чисел, дальше лень считать.
Нет, в лоб тут не посчитаешь, нужно найти какую-то закономерность, но пока ничего в голову не приходит.
Задача 5 — нет решения: каждое домино покрывает одну чёрную и одну белую клетку. Но на доске из условия клеток одного цвета на 2 больше клеток другого цвета.
Задачка 11.
Предположим, что числа удалось раскрасить в 3 цвета так, что для чисел, разность которых — полный квадрат, цвета разные.
Пусть COL(1)=A, COL(26)=C.
Тогда COL(10)=COL(17)=B (поскольку 10-1=26-17=3^2, 17-1=26-10=4^2).
Получается, что клетки, расстояние между которыми равно 7, должны быть одинакового цвета (если их номера лежат между 10 и 1997), а значит, клетка 59 имеет тот же цвет, что и клетка 10. Но 59-10=7^2 — противоречие.
На самом деле, получается, что 10, 51 и 52 одного цвета, но 52-51=1^2, и для этого хватает графа из 61 вершины. Какова минимальная длина отрезка, который можно раскрасить в 3 цвета, пока не знаю.
Пусть COL(1)=A, COL(26)=C.
Тогда COL(10)=COL(17)=B (поскольку 10-1=26-17=3^2, 17-1=26-10=4^2).
Получается, что клетки, расстояние между которыми равно 7, должны быть одинакового цвета (если их номера лежат между 10 и 1997), а значит, клетка 59 имеет тот же цвет, что и клетка 10. Но 59-10=7^2 — противоречие.
На самом деле, получается, что 10, 51 и 52 одного цвета, но 52-51=1^2, и для этого хватает графа из 61 вершины. Какова минимальная длина отрезка, который можно раскрасить в 3 цвета, пока не знаю.
Боюсь запутать вас переводом. Хорошо, если под теорией узлов и хроматическим числом графа мы подразумеваем одно и то же. Еще вернее вам будет глянуть в оригинал статьи,
Заглянул. Там написано «пусть COL — раскраска множества 1..2006 в три цвета». Впрочем, так я и думал. Графы там подразумеваются, но явно не упоминаются.
Собственно термин 3-coloring, вольно переведенный мной как трехцветный широко употребляется в англоязычных статьях, как хроматическое число графа или узла,
Если верить Вики, то graph coloring — это правильная раскраска графа, а chromatic number — минимальное количество цветов в правильной раскраске. Если coloring где-то действительно употребляется в смысле «число», то это как-то странно. Впрочем, восток — дело тонкое…
Может вы правы и здесь никаких графов в помине нет, а просто множество. Но вроде множества не красят.
Исправлено. Это был overengineering с моей стороны. Спасибо.
Программа сказала, что самый длинный отрезок, который можно покрасить в 3 цвета — 28 чисел.
Задачка 8.
Проведём через заключенного прямые, параллельные диагоналям квадрата, и научим собак находиться в точках пересечения этих прямых с периметром. Очевидно, что как бы заключенный не двигался, собакам не придётся бежать быстрее, чем в sqrt(2) раза больше его скорости — значит, выполнить задание они смогут. Когда заключённый подойдёт к стороне, его всегда встретят две собаки. А если он догадается подойти к углу — то сразу три.
Задача 6
Если константы есть, то для регистра длиной 2^N можно справиться за 2^N+N*(N-1)*3/2+1 операций (пример для N=5):
Если сдвиги на любое число разрядов считаются за 1 такт, то остаётся (3*N^2-N)/2+2 операции.
Без констант сложнее — придётся затратить 3*2^N операций, только чтобы получить отдельные биты.
b=a&0x55555555;
a=(a>>1)&0x55555555;
a=((a&b)<<1) | (a^b);
b=a&0x33333333;
a=(a>>2)&0x33333333;
c=(a&b)<<1;
a^=b^c;
b=a&0x0f0f0f0f;
a=(a>>4)&0x0f0f0f0f;
c=(a&b)<<1;
a^=b;
b=(a&c)<<1;
a^=b^c;
b=a&0x00ff00ff;
a=(a>>8)&0x00ff00ff;
c=(a&b)<<1;
a^=b;
b=(a&c)<<1;
a^=c;
c=(a&b)<<1;
a^=b^c;
b=a&0x0000ffff;
a>>=16;
c=(a&b)<<1;
a^=b;
b=(a&c)<<1;
a^=c;
c=(a&b)<<1;
a^=b;
b=(a&c)<<1;
a^=b^c;
Если сдвиги на любое число разрядов считаются за 1 такт, то остаётся (3*N^2-N)/2+2 операции.
Без констант сложнее — придётся затратить 3*2^N операций, только чтобы получить отдельные биты.
Ай, ну зачем решение 13й задачи прямо в тексте топика давать? Предупреждать же надо.
Видел в точности этот список задач на своём любимом форуме с головоломками, года два назад. Задачки, безусловно, хороши, но с бородой.
А что насчет 4й задачи?
По-моему там два варианта:
1. мы можем использовать условия в программе (например, остановиться когда все кружки в одинаковой позиции) и тогда задача не имеет смысла, т.к. можно просто переворачивать одну кружку пока не получим нужный результат.
2. мы должны составить последовательность команд из которой мы не можем выйти до полного завершения, и в процессе мы не можем ставить условия или получать состояние кружек. И тогда эту задачу невозможно решить.
Или я не прав и во втором случае есть решение?
По-моему там два варианта:
1. мы можем использовать условия в программе (например, остановиться когда все кружки в одинаковой позиции) и тогда задача не имеет смысла, т.к. можно просто переворачивать одну кружку пока не получим нужный результат.
2. мы должны составить последовательность команд из которой мы не можем выйти до полного завершения, и в процессе мы не можем ставить условия или получать состояние кружек. И тогда эту задачу невозможно решить.
Или я не прав и во втором случае есть решение?
Там, скорее, первый вариант. Но «переворачивать одну кружку» — не работает, поскольку вредный робот может всегда переворачивать неправильную кружку. Непредсказуемо оно для нас, но не для робота.
Похожая, но более интересная задача была в книжке «Математический цветник». Там можно было выбрать две кружки, на ощупь определить их ориентацию, и в зависимости от результата перевернуть сколько-то из них (0, 1 или 2).
Похожая, но более интересная задача была в книжке «Математический цветник». Там можно было выбрать две кружки, на ощупь определить их ориентацию, и в зависимости от результата перевернуть сколько-то из них (0, 1 или 2).
«вредный робот может всегда переворачивать неправильную кружку», все равно, это практически не усложняет задачу.
И сколько ходов достаточно для гарантированного выигрыша?
Т.к. нам не важно как именно поставить кружки, все вверх или все вниз дном, и не важно на каком угле, грани или диагонали стоит «неправильная кружка» — считаем что такие состояния эквивалентны:
Тогда имеем 4 возможных начальных состояния:
С вот такой таблицей переходов:
(а) «перевернуть угловую кружку»
(б) «перевернуть две диагональных кружки»
(с) «перевернуть две соседние кружки».
Собственно получаем:
Кол-во шагов для выхода из состояния:
0 = 0
1 = 1-3
2 = 1-2
3 = 1
++ -+ -- +- ++ -+ и т.д.
Тогда имеем 4 возможных начальных состояния:
0 1 2 3 ++ +- -- +- ++ ++ ++ -+
С вот такой таблицей переходов:
(а) «перевернуть угловую кружку»
(б) «перевернуть две диагональных кружки»
(с) «перевернуть две соседние кружки».
| а | б | с |
-------------------------------
0 | ++ | 1 | 3 | 2 |
| ++ | | | |
-------------------------------
1 | -+ | 0,2,3 | 1 | 1 |
| ++ | | | |
-------------------------------
2 | -- | 1 | 2 | 0,3 |
| ++ | | | |
-------------------------------
3 | +- | 1 | 0 | 2 |
| -+ | | | |
Собственно получаем:
while(state != 0) {
switch(state) {
case 1:
а();
break;
case 2:
с();
break;
case 3:
б();
break;
}
state = getState();
}
Кол-во шагов для выхода из состояния:
0 = 0
1 = 1-3
2 = 1-2
3 = 1
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пара старых задачек по-массачусетски