Доказать, что для всякого n существует последовательность нулей и единиц длины 2^n (Pascal)

[Nurz]

Ребята, помогите пожалуйста с алгоритмом, программу в принципе и сам могу написать, но вот над алгоритмом бьюсь уже неделю и не могу найти верное решение. Перестановка будет содержать огромное кол-во последовательностей потому эту идею сразу бросил. Пытался найти смысл в этом кольце, построил уже для n = 5 но все равно не вижу никаких закономерностей. Крутил по всякому но ничего. Наверняка тут все просто но я что-то упускаю. Поэтому пришел к вам просить помощи.

Доказать, что для всякого n существует последовательность нулей и единиц длины 2^n с последующим свойством: если "обратить ее в кольцо" и рассмотреть все фрагменты длины n (их количество равно 2^n), то получим все возможные последовательности нулей и единиц длиной n. Построить алгоритм поиска такой последовательности, который требует не более чем Сn действий для некоторой константы С.

[FPaul]

Одновременно напоминает
- код Грея
- поиск Гамильтонова пути.
В практических целях для n=4 искал перебором как Гамильтонов путь. Но у меня была вечность времени.
Из каждого числа x было два пути ((x<<1) & ~(1<<n)) + 1 и + 0. Перебор с возвратом.

Но, и код Грея стоит рассмотреть.

[Nurz]

Спасибо за информацию. Учусь на первом курсе, но нам и близко такого не давали. Сейчас буду пробовать что-то с этим сделать.

[FPaul]

Лучше - Гамильтонов цикл. Причём без построения матрицы смежности, т.к. смежные вершины легко вычисляются.

Кстати, в условии речь о закольцованности - чтобы уменьшить длину последовательности.
Например, для n=4, начиная c 0000 получаем последовательность (апострофы лишь для разделения сплошного блока)
0000'1111'0110'0101'000
0,1,3,7,15,14,14,13,11,6,12,9,2,5,1 0,4,8
Видно, что если отбросить 3 (n-1) первых 0, то при закольцовывании эти нули восстановятся из последнего числа (или наоборот - отбросить последние нули - восстановятся из первых).

[Smitt&Wesson]

Сообщение от Nurz

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

А вот эту фразу, вообще не понял.
Последовательность из нулей и единиц, подчиняется закону нормального распределения. Обычная статистика. При чём здесь цикл Гамильтона? Да, у него есть интересная закономерность. Я ещё в 70-х прогу писал по нему. Но к этому вопросу, он никак к не вяжется.

[Аватар]

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

И мульон нулей с единичкой в конце?

[FPaul]

По правде, я такую задачу решал на работе, для перебора всех комбинаций чисел с 4-мя разрядами, получаемых из предыдущих путём сдвига влево и записи в младший разряд 0 или 1.
Ещё не знал о теории графов. Решил перебором.
Потом стало любопытно, сколько возможных решений. Оказалось, что много. Т.е. было почти всё равно, куда двигаться из числа по 0 или по 1.

[Smitt&Wesson]

Сообщение от Аватар

И мульон нулей с единичкой в конце?

Я не об этом. Я о кодировках. Unicode, ASCII и пр. А искусственно, можно и нулей и единиц навалять, сколько захочется.

[FPaul]

Так для n=3 (не буду обманывать, было на форуме подобное задание для десятеричных чисел, после изменения 2-х констант стало для n=3 двоичных)

program SRegister;

const
  MaxCombination = 2 * 2 * 2;
  K = 2;
type
  TVectorBool = array[0..MaxCombination - 1] of boolean;
  TVectorByte = array[0..MaxCombination - 1] of byte;

  procedure GetSequence(var Sequence: TVectorByte);
  var
    UsedComb: TVectorBool;
    CountUsedCombination: integer;
    Depth: integer;

    function DFS(Combination: word): boolean;
    var
      Digit: byte;
    begin
      if CountUsedCombination = MaxCombination then
      begin
        DFS := True;
        exit;
      end;
      Inc(Depth);
      DFS := False;
      Combination := (Combination * K) mod MaxCombination;
      for Digit := 0 to K - 1 do
      begin
        if not UsedComb[Combination + Digit] then
        begin
          UsedComb[Combination + Digit] := True;
          Inc(CountUsedCombination);
          DFS := DFS(Combination + Digit);
          if DFS then
          begin
            Sequence[Depth - 1] := Digit;
            break;
          end;
          Dec(CountUsedCombination);
          UsedComb[Combination + Digit] := False;
        end;
      end;
      Dec(Depth);
    end;

  var
    i: integer;
  begin
    for i := low(UsedComb) to high(UsedComb) do
      UsedComb[i] := False;
    CountUsedCombination := 1;
    Depth := 1;
    UsedComb[0] := True;
    DFS(0);
  end;

var
  i: integer;
  Sequence: TVectorByte;
begin
  GetSequence(Sequence);
  //Write('00');
  for i := low(Sequence) to high(Sequence) do
    Write(Sequence[i]);
  writeln;
end.

[Nurz]

Огромное спасибо. Как-то это все сложно, нужно переварить.

 if not UsedComb[Combination + Digit] then
        begin
          UsedComb[Combination + Digit] := True;
          Inc(CountUsedCombination);
          DFS := DFS(Combination + Digit);
          if DFS then // << Вот здесь пишет что неверное число параметров функции
          begin
            SSequence[Depth - 1] := Digit;
            break;
          end;
          Dec(CountUsedCombination);
          UsedComb[Combination + Digit] := False;
        end;