Форум «Всё о Паскале» _ Задачи _ Последовательность Кеане
Автор: Unconnected 5.06.2010 21:20
Привет всем
Пробую решить олимпиадную задачку (конечно, с уже давно окончившейся олимпиады )), про последовательность (битов) Кеане - кто этот Кеане, я не знаю, и Вики с гуглом тоже. Формулировка такая:
Цитата
Последовательность Кеане (Время: 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() от неё. Может, формулу можно вывести для нахождения бита по позиции?
Автор: Сергей Меркурьев 5.06.2010 21:52
Генерация может быть и правильная, но проблема не в этом! ты берешь тип инт64, который сам по себе не может включать 10^200, у него всего 10^18 (может больше, может меньше. Не помню я ). Вот и реализовывай длинную арифметику для числа N. Думаю, что с тем, чтобы считать длинное число с файла, проблем не возникнет. Но надо подумать как найти элемент строки с этим номером!
Автор: volvo 6.06.2010 1:09
Unconnected, вот смотри, какой путь я бы избрал (показываю с применением обычной арифметики, с небольшими значениями). Идея - такая.
определяем, в каком члене последовательности находится искомый бит. То есть, допустим, надо найти значение бита под номером 20. Вот так выглядит последовательность, сформированная по приведенному тобой правилу: 0_001_001001110_001001110001001110110110001 (40 бит). Она состоит, как видим, из 4-х членов (я разделил их символами подчеркивания). Нужный нам бит находится в третьем члене, начиная с 0-го;
находим номер нужного бита, начиная с начала того члена, в котором он находится;
последовательно делим текущий член на 3 части, и определяем, в какой части находится нужный бит (в зависимости от этого принимаем решение о необходимости инвертирования);
продолжаем эти действия до тех пор, пока не дойдем до 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;
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.
Что меня мучает - это уж очень маленькое время задано для таких огромных чисел, времени может не хватить, тем более в случае использования длинной арифметики. Но это пока то, что мне придумалось, может потом наступит прозрение, как решать эту задачу...
P.S. И все-таки, по поводу
Цитата
кто этот Кеане, я не знаю, и Вики с гуглом тоже
- это http://mathworld.wolfram.com/MephistoWaltzSequence.html
Автор: Lapp 6.06.2010 7:19
[indent]
Цитата(volvo @ 5.06.2010 22:09)
Вот так выглядит последовательность, сформированная по приведенному тобой правилу: 0_001_001001110_001001110001001110110110001 (40 бит). Она состоит, как видим, из 4-х членов (я разделил их символами подчеркивания). Нужный нам бит находится в третьем члене, начиная с 0-го;
volvo, мне думается, что все не совсем так, и заодно немного проще..
Последовательность, как я ее понял, представляет собой не совокупность членов, а просто один такой член, растущий по приведенному правилу.
0 001 001001110 001001110001001110110110001
Мне кажется, что красмвее и понятнее формулировать так: последовательность получается посредством приписывания САМОЙ СЕБЯ к себе слева и своего отрицания - справа.
Легко видеть, что отсюда сразу следуют два положения:
1. значение n-нного бита сохраняется; 2. длина последовательности на каждом шагу выражается степенью тройки.
Первый пункт делает вопрос задачи осмысленным. Второй, как мне кажется, дает ключ к решению. Но самого решения у меня пока нет. Сегодня пока занят другими делами, освобожусь - порешаю.
Автор: volvo 6.06.2010 8:10
Да. Не совсем так... Правда. Нужно кое-что добавить:
// после строки: 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, являющихся членами http://research.att.com/~njas/sequences/A003462 результат получается некорректным.
Update Если имеется в виду, что я не прав в том, что я сначала подставляю нулевой, потом - первый, и так далее члены MW Sequence, а надо сначала сгенерировать i-тый член подходящей длины, и только в нем искать N-ый бит (не обращая внимание на предыдущие i-1 членов последовательности), так еще проще: экономим одно действие, bit_in_seq вычислять не надо, можно просто брать N и работать с ним... Результат еще быстрее вычислится.
Автор: Unconnected 9.06.2010 20:35
Сейчас дорассмотрел наконец код volvo (лето, напряжёнка ) ), для небольших чисел это наверное и будет самый оптимальный вариант (погонял, кстати - string- и calceulated-результаты соответствуют), а вот если взять n=10200 - то я, например, даже не представляю, как находить для него логарифм и т.п. с помощью длинной арифметики. (благодарю за код, познавательно!)
Последовательность состоит из элементарных 001 и 110 (при n>=3). Может, обозначать их нулём и единицей, к примеру? Тогда генерировать меньше будет, и находить быстрее.
Lapp, не совсем понял насчёт этих положений. Ну и что с того, что длина выражается степенью тройки? Это как-то поможет в нахождении нужного члена?
Автор: TarasBer 9.06.2010 20:46
> n=10^200 - то я, например, даже не представляю, как находить для него логарифм
ln(10)*200
Автор: Lapp 10.06.2010 7:48
Цитата(Unconnected @ 9.06.2010 17:35)
Ну и что с того, что длина выражается степенью тройки? Это как-то поможет в нахождении нужного члена?
Так volvo же это как раз и использовал! трихотомия ))