Версия для печати
Убрать все задачи

---

Можно ли нарисовать правильный треугольник с вершинами в узлах квадратной сетки?

   Решение

---

Двое игроков играют в карточную игру. У них есть колода из n попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если A бьёт B, а B бьёт C, то может оказаться, что C бьёт A). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.

   Решение

---

На сторонах AB, BC, CA треугольника ABC взяты такие точки A₁ и B₂, B₁ и C₂, C₁ и A₂, что отрезки A₁A₂, B₁B₂ и C₁C₂ параллельны сторонам треугольника и пересекаются в точке P. Докажите, что PA₁ ^. PA₂ + PB₁ ^. PB₂ + PC₁ ^. PC₂ = R² - OP², где O — центр описанной окружности.

   Решение

---

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

   Решение

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

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 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ⁿ при помощи

умножений, где (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]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями