IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> 7, 11, 13, 14, 19, 21, 22, 25, …., Небольшая последовательность
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


В общем дана последовательность 7, 11, 13, 14, 19, 21, 22, 25, ….
Нужно по заданному N найти N-ый член.
В общем-то задача является олимпиадной, хотелось бы узнать как ее можно решить smile.gif
Что это за последовательность я нашел:
Это числа которые содержат 3 единицы в двоичной записи числа, числа по возрастанию идут.
7 - 111
11 - 1011
13 - 1101
14 - 1110
19 - 10011 и т.д.

Вот мой код
program N468;
var n, i, k, q : longint;
Number : longint;
res : int64;
a : array [1..10000] of byte;

begin
Readln (n);
a[1] := 1;
a[2] := 1;
a[3] := 1;
number := 1;
k := 3;
While Number <> n do
begin
If ((a[1] = a[2]) and (a[2] = a[3]))
then begin
For i := 1 to k do a[i] := 0;
inc (k);
a[1] := 1;
a[k] := 1;
a[k - 1] := 1;
Inc (number);
end; {Переход в следующий разряд}
For i := k downto 3 do
If a[i] = 1 then
If a[i - 1] <> a[i]
then begin
a[i - 1] := 1;
a[i] := 0;
Inc (number);
break;
end
else begin
a[i - 1] := 0;
a[i] := 0;
a[i-2] := 1;
a[k] := 1;
inc (number);
break;
end;
end;
q := 1;
res := 0;
For i := k downto 1 do
begin
res := res + (a[i] * q);
q := q * 2;
end;
Write (res);
end.

Но к сожалению данный алгоритм не является быстрым( Где-то начиная с 32,000,000-го члена программа начинает долго очень работать, при том что 1 <= N <= 2,147,483,647. И это еще при том, что я не реализовал длинную арифметику.

Подскажите какой-нибудь алгоритм или сами подскажите, как можно находить данные числа намного быстрее.

Сообщение отредактировано: Lapp -


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 позиции, это видно сразу.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Сергей Меркурьев @ 17.06.2010 19:36) *
Подскажите какой-нибудь алгоритм или сами подскажите, как можно находить данные числа намного быстрее.
Здесь нужен совсем другой подход, мне кажется..
Комбинаторику знаешь? Плясать нужно от количества расстановок: три единицы по 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.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:57
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name