Ссылки по теме:
Подборка статей в журнале "Квант"
Подтемы:
Подборка статей в журнале "Квант"
Подтемы:
-
Теория игр
(278 задач)
Взвешивания
(154 задачи)
Теория алгоритмов (прочее)
(268 задач)
Кооперативные алгоритмы
(29 задач)
Переправы
(1 задача)
Фильтр
Задачи
Страница: << 105 106 107 108 109 110 111 >> [Всего задач: 737]
На n карточках, выложенных по окружности, записаны числа, каждое из которых равно 1 или –1. За какое наименьшее число вопросов можно наверняка определить произведение всех n чисел, если за один вопрос разрешено узнать произведение чисел на а) любых трёх карточках; б) любых трёх карточках, лежащих подряд? (Здесь n — натуральное число, большее 3).
По заданному ненулевому x значение x8 можно найти за три арифметических действия: x2 = x · x, x4 = x2 · x2, x8 = x4 · x4,
а x15 — за пять действий: первые три — те же самые, затем x8 · x8 = x16 и x16 : x = x16. Докажите, что
В нашем распоряжении имеются 32k неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3k + 1 взвешиваний?
Двое играют в такую игру. Один задумывает натуральное число n, а другой задаёт вопросы типа «верно ли, что n не меньше x» (число x он может выбирать по своему усмотрению) и получает ответы «да» или «нет». Каждой возможной стратегии T второго игрока сопоставим функцию fT(n), равную числу вопросов (до отгадывания), если было задумано число n. Пусть, например, стратегия T состоит в том, что сначала задают вопросы: «верно ли, что n не меньше 10?», «верно ли, что n не меньше 20?», ... до тех пор, пока на какой-то вопрос «верно ли, что n не меньше 10(k + 1)» не будет дан ответ «нет», а затем задают вопросы «верно ли, что n не меньше 10k + 1», «верно ли, что n не меньше 10k + 2» и так далее. Тогда fT(n) = a + 2 + (n – a)/10, где a — последняя цифра числа n, то есть fT(n) растёт примерно как n/10.
За один ход разрешается или удваивать число, или
стирать его последнюю цифру. Можно ли за несколько ходов получить
из числа 458 число 14?
Страница: << 105 106 107 108 109 110 111 >> [Всего задач: 737]
Задача 73814 |
|
|
|
|
Решение |
Задача 73775 |
|
|
а) x16 можно найти за
б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log2n действий.
|
|
|
Решение |
Задача 111884 |
|
|
|
|
|
Решение |
Задача 73715 |
|
|
а) Предложите стратегию, для которой функция fT растёт медленнее.
б) Сравнивая две стратегии, удобно для произвольной
|
|
|
Решение |
Задача 88085 |
|
|
|
|
|
Решение |
Страница: << 105 106 107 108 109 110 111 >> [Всего задач: 737]
