Каталог по источникам

Задачи

Страница: << 1 2 3 4 5 6 >> [Всего задач: 30]

Задача 60899 (#05.061)

Тема:

[

Теория алгоритмов (прочее)

]

Сложность: 3+
Классы: 7,8,9,10

а) Имеются две веревки. Если любую из них поджечь с одного конца, то она сгорит за час. Веревки горят неравномерно. Например, нельзя гарантировать, что половина веревки сгорает за 30 минут. Как, имея две такие веревки, отмерить промежуток времени в 15 минут?
б) Сколько промежутков времени (считая нулевой) можно отмерить, имея три такие веревки?

Прислать комментарий

Решение

Задача 60900 (#05.062)

Темы:	[	Теория алгоритмов (прочее)	]
Темы:	[	Троичная система счисления	]

Сложность: 3
Классы: 6,7,8,9

а) У одного человека был подвал, освещавшийся тремя электрическими лампочками. Выключатели этих лампочек находились вне подвала, так что включив любой из выключателей, хозяин должен был спуститься в подвал, чтобы увидеть, какая именно лампочка зажглась. Однажды он придумал способ, как определить для каждого выключателя, какую именно лампочку он включает, сходив в подвал ровно один раз. Какой это способ?
б) Сколько лампочек и выключателей можно идентифицировать друг с другом, если разрешается 2 раза спуститься в подвал?

Прислать комментарий

Решение

Задача 60901 (#05.063)

Темы:	[	Процессы и операции	]
Темы:	[	Двоичная система счисления	]

Сложность: 3
Классы: 8,9,10

С числом разрешается производить две операции: ``увеличить в два раза'' и ``увеличить на 1''. За какое наименьшее число операций можно из числа 0 получить
а) число 100; б) число n?

Прислать комментарий

Решение

Задача 60902 (#05.064)

Темы:	[	Теория алгоритмов (прочее)	]
Темы:	[	Двоичная система счисления	]

Сложность: 3+
Классы: 8,9,10

Бинарный метод возведения в степень. Предположим, что необходимо возвести число x в степень n. Если, например, n = 16, то это можно сделать выполнив 15 умножений x¹⁶ = x^.x^....^.x, а можно обойтись лишь четырьмя:

x₁ = x^.x = x², x₂ = x₁^.x₁ = x⁴, x₃ = x₂^.x₂ = x⁸, x₄ = x₃^.x₃ = x¹⁶.

Пусть

n = 2^e₁ + 2^e₂ +...+ 2^e_r (e₁ > e₂ >...> e_r $\displaystyle \geqslant$ 0).

Придумайте алгоритм, который позволял бы вычислять xⁿ при помощи

b(n) = e₁ + $\displaystyle \nu$ (n) - 1

умножений, где $\nu$ (n) = r — число единиц в двоичном представлении числа n.

Прислать комментарий

Решение

Задача 60903 (#05.065)

Темы:	[	Теория алгоритмов (прочее)	]
Темы:	[	Примеры и контрпримеры. Конструкции	]

Сложность: 3
Классы: 8,9,10

Пусть l (n) — наименьшее число умножений, необходимое для нахождения xⁿ. На примере чисел n = 15 и n = 63 покажите, что бинарный метод возведения в степень (смотри задачу 5.64) не всегда оптимален, то есть для некоторых n выполняется неравенство l (n) < b(n).

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 6 >> [Всего задач: 30]