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 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


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

 





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