Каталог по темам

Задачи

Страница: << 13 14 15 16 17 18 19 >> [Всего задач: 277]

Задача 60902

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

Сложность: 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.

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

Решение

Задача 35529

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

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

На столе - куча из 1001 камня. Ход состоит в том, что из какой-либо кучи, содержащей более одного камня, выкидывают камень, а затем одну из куч делят на две. Можно ли через несколько ходов оставить на столе только кучки, состоящие из трех камней?

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

Задача 60899

Тема:

[

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

]

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

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

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

Решение

Задача 61405

Тема:

[

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

]

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

Спортпрогноз. Предположим, что ожидается баскетбольный матч между двумя командами A и B, в котором возможно только два исхода: одна из команд выигрывает. Две букмекерские конторы принимают ставки с разными коэффициентами k_A⁽¹⁾, k_B⁽¹⁾, k_A⁽²⁾, k_B⁽²⁾. Например, если игрок сделал ставку N в первой конторе на команду A, и эта команда выиграла, то игрок получает сумму k_A^{(1) .}N. Пусть

k_A⁽¹⁾ = 2, k_B⁽¹⁾ = $\displaystyle {\textstyle\frac{3}{2}}$ , k_A⁽²⁾ = $\displaystyle {\textstyle\frac{4}{3}}$ , k_B⁽²⁾ = 3.

Как, имея капитал N, распорядиться им оптимальным образом, то есть как сделать ставки в двух конторах, чтобы получить максимальный гарантированный выигрыш?
Проанализируйте случай произвольных коэффициентов k_A⁽¹⁾, k_B⁽¹⁾, k_A⁽²⁾, k_B⁽²⁾ и найдите связь между максимальным гарантированным выигрышем и средним гармоническим наибольших коэффициентов.

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

Решение

Задача 66900

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

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

Автор: Дидин М.

В комнате находится несколько детей и куча из 1000 конфет. Дети по очереди подходят к куче. Каждый подошедший делит количество конфет в куче на количество детей в комнате, округляет (если получилось нецелое), забирает полученное число конфет и выходит из комнаты. При этом мальчики округляют вверх, а девочки – вниз. Докажите, что суммарное количество конфет у мальчиков, когда все выйдут из комнаты, не зависит от порядка детей в очереди.

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

Страница: << 13 14 15 16 17 18 19 >> [Всего задач: 277]