28.11.2012, 23:54 | #1 (permalink) |
Новичок
Регистрация: 28.11.2012
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Составить алгоритм
Последовательность 011212201220200112… строится так: сначала 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е. 0->01->0112->01121220->… Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательности нулей ( за исключением представления числа 0).Используя эту функцию, получить двоичное 1|16-ричное 2 представления данных пяти чисел. |
28.11.2012, 23:54 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Очень полезно почитать темы созданные людьми ранее Составить алгоритм и написать код программы Составить алгоритм циклической структуры в Visual Studio C++ Алгоритм rle Описать алгоритм |
29.11.2012, 00:00 | #2 (permalink) |
Новичок
Регистрация: 28.11.2012
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
у меня есть даже объяснения я и эго не понимаю (((
Пусть a(k) - k-ый член последовательности. Рассмотрим последовательность, формируемую по следующему правилу: a(0)=0; ряд a(0)...a(2k-1) получаем приписыванием к этой последовательности справа этой же последовательности, но при этом каждый член приписываемой части увеличивается на единицу. Получаем 0->01->0112->01121220->... Докажем, что a(k) есть сумма единиц в двоичном представлении числа k. Доказательство проведем по индукции. Для a(0)=0 это справедливо. Пусть предположение справедливо для всех a(i), 0<=i<=2(k-1)-1 (т.е. для всех чисел i, состоящих из не более чем k-1-го двоичных разрядов). Тогда в двоичном разложении числа l, 2(k-1)<=l<2k, в k-ом разряде появляется добавочная единица, и поэтому a(l)=1+a(l-2(k-1))), ч.т.д. Возьмем a(i) mod 3, и получим число, стоящее на i-ом месте в последовательности, описанной в условии задачи. |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|