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

Задачи

Страница: << 90 91 92 93 94 95 96 >> [Всего задач: 604]

Задача 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.

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

Решение

Задача 73582

Темы:	[	Сочетания и размещения	]
	[	Десятичная система счисления	]
	[	Подсчет двумя способами	]

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

Из цифр 1 и 2 составили пять n-значных чисел так, что у каждых двух чисел совпали цифры ровно в m разрядах, но ни в одном разряде не совпали все пять чисел. Докажите, что отношение ^m/_n не меньше ⅖ и не больше ⅗.

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

Решение

Задача 78508

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

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

Доказать, что из одиннадцати произвольных бесконечных десятичных дробей можно выбрать две дроби, разность которых имеет в десятичной записи либо бесконечное число нулей, либо бесконечное число девяток.

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

Задача 78662

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

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

Можно ли выбрать 100 000 номеров телефонов из 6 цифр каждый так, чтобы при одновременном вычеркивании из всех этих номеров k-той цифры (k = 1, 2,...6) получились все пятизначные номера от 00000 до 99999?

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

Задача 78708

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

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

С числом 123456789101112...9989991000 производится следующая операция: зачёркиваются две соседние цифры a и b (a стоит перед b) и на их место вставляется число a + 2b (можно в качестве a взять нуль, ``стоящий'' перед числом, а в качестве b — первую цифру числа). С полученным числом производится такая же операция и т.д. (Например, из числа 118 307 можно на первом шаге получить числа 218 307, 38 307, 117 307, 111 407, 11 837, 118 314.) Доказать, что таким способом можно получить число 1.

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

Страница: << 90 91 92 93 94 95 96 >> [Всего задач: 604]