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

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

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

 
 Ответить  Открыть новую тему 
> Последовательность Кеане
сообщение
Сообщение #1


mea culpa
*****

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

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


Привет всем smile.gif

Пробую решить олимпиадную задачку (конечно, с уже давно окончившейся олимпиады )), про последовательность (битов) Кеане - кто этот Кеане, я не знаю, и Вики с гуглом тоже. Формулировка такая:

Цитата

Последовательность Кеане
(Время: 1 сек. Память: 16 Мб Сложность: 57%)

Бесконечная последовательность битов, предложенная Кеане, равна 001001110001001110110110001… и формируется следующим алгоритмом: вначале записывается 0, потом 001, далее 001001110, то есть, для получения следующего члена, предыдущий записывается дважды, а справа приписывается его отрицание. Элементы этого ряда являются начальными подпоследовательностями Кеане.

Требуется написать программу, которая по заданному n определит N-й бит этой последовательности.
Входные данные

Входной файл INPUT.TXT содержит число N (N <= 10200).
Выходные данные

В выходной файл OUTPUT.TXT должен содержать найденный бит.


Просто генерировать последовательность у меня получается, вот так:

{$APPTYPE CONSOLE}

var n:int64;
s:string;

function invers(s:string):string;
var i:integer;
begin
for i:=1 to length(s) do if s[i]='0' then result:=result+'1' else result:=result+'0';
end;

begin
assign(input,'input.txt');
readln(n);
s:='0';
while (length(s)<=n) do s:=s+s+invers(s);
assign(output,'output.txt');
writeln(s[n]);
end.



(хотя, у меня такое ощущение, что она как-то неправильно генерирует)

Проблема в очень большом максимально возможном N. Здесь, видимо нужно использовать длинную арифметику, но я вот не понимаю, в каком месте её использовать. Ну допустим есть строка-последовательность, есть N в виде строки, и что с чем складывать? Кажется, даже строку с последовательностью такой длины получить не получится, и тем более length() от неё. Может, формулу можно вывести для нахождения бита по позиции?

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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Бывалый
***

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

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


Генерация может быть и правильная, но проблема не в этом!
ты берешь тип инт64, который сам по себе не может включать 10^200, у него всего 10^18 (может больше, может меньше. Не помню я smile.gif).
Вот и реализовывай длинную арифметику для числа N.
Думаю, что с тем, чтобы считать длинное число с файла, проблем не возникнет. Но надо подумать как найти элемент строки с этим номером!

Сообщение отредактировано: Сергей Меркурьев -


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


Гость






Unconnected, вот смотри, какой путь я бы избрал (показываю с применением обычной арифметики, с небольшими значениями). Идея - такая.
  1. определяем, в каком члене последовательности находится искомый бит. То есть, допустим, надо найти значение бита под номером 20. Вот так выглядит последовательность, сформированная по приведенному тобой правилу:
    0_001_001001110_001001110001001110110110001 (40 бит). Она состоит, как видим, из 4-х членов (я разделил их символами подчеркивания). Нужный нам бит находится в третьем члене, начиная с 0-го;
  2. находим номер нужного бита, начиная с начала того члена, в котором он находится;
  3. последовательно делим текущий член на 3 части, и определяем, в какой части находится нужный бит (в зависимости от этого принимаем решение о необходимости инвертирования);
  4. продолжаем эти действия до тех пор, пока не дойдем до 3-х битных кусочков. Тут уже можно с легкостью определить, какой бит чему равен.
Все действия прокомментирую кодом (у меня для проверки строится и сама последовательность, и результаты выводятся как вычисленные, так и взятые из строки. Потестируй, если какой-то результат не совпадет - говори, при каком N, будем думать что делать)
const
inverted: array['0' .. '1'] of char = ('1', '0');

function log3(n: integer): real;
begin
result := ln(n) / ln(3);
end;
function power(n: integer): longint;
var
i: integer;
begin
result := 1;
for i := 1 to n do result := result * 3;
end;

function generate(len: longint): string;

function invert(s: string): string;
var i: integer;
begin
result := '';
for i := 1 to length(s) do result := result + inverted[s[i]];
end;

var s: string;

begin
s := '0';
result := '';
repeat
result := result + s;
s := s + s + invert(s);
writeln(s);
until length(result) > len;
end;

var
s: string;
n: integer;

k, bit_in_seq: longint;
power_3: longint;
negate: boolean;

res: char;

begin
n := 22;
s := generate(n);

writeln(length(s), ' -> ', s);
writeln('from string: ', s[n]);

k := trunc(log3(2 * n + 1));
bit_in_seq := pred(n - ((power(k) - 1) div 2));
negate := false;
power_3 := power(k);

if power_3 > 3 then
repeat
power_3 := power_3 div 3;
if (bit_in_seq div power_3) = 2 then negate := not negate;
bit_in_seq := bit_in_seq mod power_3;
until power_3 = 3;

case bit_in_seq of
0, 1: res := '0';
2: res := '1';
end;
if negate then res := inverted[res];

writeln('calculated: ', res);
readln;
end.


Что меня мучает - это уж очень маленькое время задано для таких огромных чисел, времени может не хватить, тем более в случае использования длинной арифметики. Но это пока то, что мне придумалось, может потом наступит прозрение, как решать эту задачу... smile.gif

P.S. И все-таки, по поводу
Цитата
кто этот Кеане, я не знаю, и Вики с гуглом тоже
- это Mephisto Waltz Sequence
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


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

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

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


[indent]
Цитата(volvo @ 5.06.2010 22:09) *
Вот так выглядит последовательность, сформированная по приведенному тобой правилу:
0_001_001001110_001001110001001110110110001 (40 бит). Она состоит, как видим, из 4-х членов (я разделил их символами подчеркивания). Нужный нам бит находится в третьем члене, начиная с 0-го;
volvo, мне думается, что все не совсем так, и заодно немного проще..

Последовательность, как я ее понял, представляет собой не совокупность членов, а просто один такой член, растущий по приведенному правилу.

0
001
001001110
001001110001001110110110001


Мне кажется, что красмвее и понятнее формулировать так: последовательность получается посредством приписывания САМОЙ СЕБЯ к себе слева и своего отрицания - справа.

Легко видеть, что отсюда сразу следуют два положения:

1. значение n-нного бита сохраняется;
2. длина последовательности на каждом шагу выражается степенью тройки.

Первый пункт делает вопрос задачи осмысленным. Второй, как мне кажется, дает ключ к решению. Но самого решения у меня пока нет. Сегодня пока занят другими делами, освобожусь - порешаю.


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


Гость






Да. Не совсем так... Правда. Нужно кое-что добавить:

  // после строки:
if negate then res := inverted[res];
// вот это надо добавить:
if(power(k) - 1) div 2 = n then res := inverted[res];


Тогда для любого N > 1 (особый случай N = 1 обрабатывается отдельно, в ветке else основного if-а, который с циклом repeat/until), от 2 до 21 миллиона (больше не проверял, ждать генерации последовательности для сравнения приходится очень долго) программа выдает одинаковый результат при вычислении значения заданного бита и при его извлечении из последовательности. Это достаточный критерий правильности программы?

Если указанное изменение не вносить, то при значениях N, являющихся членами вот этой последовательности результат получается некорректным.

Update
Если имеется в виду, что я не прав в том, что я сначала подставляю нулевой, потом - первый, и так далее члены MW Sequence, а надо сначала сгенерировать i-тый член подходящей длины, и только в нем искать N-ый бит (не обращая внимание на предыдущие i-1 членов последовательности), так еще проще: экономим одно действие, bit_in_seq вычислять не надо, можно просто брать N и работать с ним... Результат еще быстрее вычислится.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


mea culpa
*****

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

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


Сейчас дорассмотрел наконец код volvo (лето, напряжёнка ) ), для небольших чисел это наверное и будет самый оптимальный вариант (погонял, кстати - string- и calceulated-результаты соответствуют), а вот если взять n=10200 - то я, например, даже не представляю, как находить для него логарифм и т.п. с помощью длинной арифметики. (благодарю за код, познавательно!)

Последовательность состоит из элементарных 001 и 110 (при n>=3). Может, обозначать их нулём и единицей, к примеру? Тогда генерировать меньше будет, и находить быстрее.

Lapp, не совсем понял насчёт этих положений. Ну и что с того, что длина выражается степенью тройки? Это как-то поможет в нахождении нужного члена?


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

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


> n=10^200 - то я, например, даже не представляю, как находить для него логарифм

ln(10)*200


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


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

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

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


Цитата(Unconnected @ 9.06.2010 17:35) *
Ну и что с того, что длина выражается степенью тройки? Это как-то поможет в нахождении нужного члена?
Так volvo же это как раз и использовал! трихотомия ))


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

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

 





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