7, 11, 13, 14, 19, 21, 22, 25, …., Небольшая последовательность |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
7, 11, 13, 14, 19, 21, 22, 25, …., Небольшая последовательность |
Cheburashka |
17.06.2010 18:36
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 195 Пол: Мужской Реальное имя: Сергей Репутация: 2 |
В общем дана последовательность 7, 11, 13, 14, 19, 21, 22, 25, ….
Нужно по заданному N найти N-ый член. В общем-то задача является олимпиадной, хотелось бы узнать как ее можно решить Что это за последовательность я нашел: Это числа которые содержат 3 единицы в двоичной записи числа, числа по возрастанию идут. 7 - 111 11 - 1011 13 - 1101 14 - 1110 19 - 10011 и т.д. Вот мой код program N468; Но к сожалению данный алгоритм не является быстрым( Где-то начиная с 32,000,000-го члена программа начинает долго очень работать, при том что 1 <= N <= 2,147,483,647. И это еще при том, что я не реализовал длинную арифметику. Подскажите какой-нибудь алгоритм или сами подскажите, как можно находить данные числа намного быстрее. Сообщение отредактировано: Lapp - 17.06.2010 22:11 -------------------- ♣♣♣
"Себя великим не считай, гордясь величьем предков, Величья не добудешь ты и золота ценою! Хоть светит на небе луна, но отраженным светом - Чужою славой не живи, не будь второй луною!!!" ♣♣♣ |
TarasBer |
18.06.2010 9:53
Сообщение
#2
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Надо найти N-ю записть из 3х единиц...
Значит, надо найти какую-то закономерность. Ага, вот. Ищем, на какой позиции находится 1я единица, то есть скольки-значное число под номером N. Записи до 1й включительно - 3 значные. до 4й - 4 значные до 10й - 5 значные до 20й - 6 значные. до C(2, 2) + C(2, 3) + ... + C(2, K) - (K+1) - значные где C(n, k) = fact(n)/(fact(k)*fact(n-k)) Далее, C(2, 2) + C(2, 3) + ... + C(2, K) = (2*(2-1)/2 + 3*(3-1)/2 + ... + K*(K-1)/2) = (K*K*K-K)/6 То есть надо найти минимальное такое K, что N<=(K*K*K-K)/6 Вводим N1 := ((K-1)*(K-1)*(K-1)-(K-1))/6 Ну типа кубическое уравнение решить... Я бы дихотомил, наверное. Для второй единицы смотрим, где она может быть до N1+1 - она на 2 месте до N1+3 - на 3 до N1+6 - на 4 итд до N1+(L*L-L)/2 - на L То есть находим минимальное L, что N <= N1+(L*L-L)/2 Вводим N2 := N1 + ((L-1)*(L-1)-(L-1))/2 Далее, тогда 3я единица находится на N-N2+1 позиции, это видно сразу. -------------------- |
Lapp |
18.06.2010 9:59
Сообщение
#3
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Подскажите какой-нибудь алгоритм или сами подскажите, как можно находить данные числа намного быстрее. Здесь нужен совсем другой подход, мне кажется.. Комбинаторику знаешь? Плясать нужно от количества расстановок: три единицы по N местам. Подробнее ниже.. Разряды в числе заполняются справа налево. Число способов размещения трех единиц по k разрядам равно: mk = k!/(6*(k-3)!) Эти числа образуют последовательность: 0, 0, 1, 4, 10, ... - первые два члена я положил нулями, но это неважно, поскольку они не нужны. С этой последовательностью тебе следует сравнить данное число n. Нужно найти такое k, при котором выполняется двойное неравенство: mk-1 < n <= mk Оно находится либо последовательным сравнением, либо дихотомией - второе быстрее, но я думаю, это уже неважно. Найденное k - это позиция самой левой из тех трех единиц. Если справа осуществляется равенство, то поиск прекращается, и все остальные единицы просто приписываются за первой. Если нет, то .. .. после этого задача трансформируется в задачу о такой же последовательности, только не для трех единиц, а для двух, при этом ищем ее n-mk-1 член. Так мы определим позицию второй единицы. Затем продолжим процесс с одной единицей.. Если что-то неясно - спрашивай ). Добавлено через 1 мин. Немного я опоздал )). TarasBer'у респект и +1. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 18.05.2024 3:01 |