Ссылки по теме:
Подборка статей в журнале "Квант"
Подтемы:
Подборка статей в журнале "Квант"
Подтемы:
-
Теория игр
(278 задач)
Взвешивания
(154 задачи)
Теория алгоритмов (прочее)
(268 задач)
Кооперативные алгоритмы
(29 задач)
Переправы
(1 задача)
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
За один ход разрешается или удваивать число, или стирать его последнюю цифру. Можно ли за несколько ходов получить из числа 458 число 14?
Решение
Убрать все задачи
За один ход разрешается или удваивать число, или стирать его последнюю цифру. Можно ли за несколько ходов получить из числа 458 число 14?
Решение
Задачи
Страница: << 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]
