|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.11.2012, 21:55 | #1 |
Регистрация: 28.11.2012
Сообщений: 6
|
Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательност
Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательности нулей ( за исключением представления числа 0).Используя эту функцию, получить двоичное 1|16-ричное 2 представления данных пяти чисел.
Последовательность 011212201220200112… строится так: сначала 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е. 0->01->0112->01121220->011212202001->0112122020010112. |
28.11.2012, 22:10 | #2 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Если исследовать, какой знак стоит на n-ном месте последовательности из второго абзаца, то там простая формула, вычислимая за O(lnN) (совет: возьмите знак на n-ном месте и посмотрите, из какого знака он получен - найдёте рекуррентное соотношение). Если требуется найти n-ную последовательность цифр между нулями в последовательности из второго абзаца, задача становится менее красивой, но не сильно более интересной: опираясь на формулу для N-ного члена, легко сформулировать формулу для позиции n-ного нуля (придётся, впрочем, предварительно вычислить число нулей среди первых 256 членов последовательности). |
|
28.11.2012, 22:26 | #3 |
Регистрация: 28.11.2012
Сообщений: 6
|
Понятно ) у меня вот есть, объяснение но блин в голову не лезит как написать код ((( уже целый день мучаюсь
Пусть 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-ом месте в последовательности, описанной в условии задачи. |
28.11.2012, 22:52 | #4 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
А в чём проблема тогда? Посчитать число единиц в двоичной записи числа?
Например, так: 2n имеет столько же единиц, сколько и n; 2n+1 имеет на одну единицу больше, чем n. 0 имеет 0 единиц. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательност | FIREMAX | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 28.11.2012 20:54 |
целое число больше 5 000 000 000 в С++ | Артём Волжанкин | Помощь студентам | 5 | 06.11.2012 18:38 |