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

[FPaul]

Да. У меня FreePascal, а PascalABC и PascalABC.NET такое не понимают.
Введите промежуточную переменную

          Temp := DFS(Combination + Digit);
          DFS := Temp;
          if Temp then

Или, лучше, обзовите её Result.

[Nurz]

Да, все работает, спасибо. Сейчас буду код изучать. Бился над ней чуть больше недели. А вы тут за пару часов решили её. Эх, мне бы ваши знания. Но буду стремится. Еще раз огромное спасибо за помощь.

[FPaul]

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

[FPaul]

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

[Smitt&Wesson]

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

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

В стандартные - нет. Но есть ведь и длинная арифметика. А если использовать стек, гигушную память, вообще можно забить за 15 секунд пушем.

[Nurz]

Я знаю что код еще нужно будет модефицировать. Да и в динамические структуры нужно запихнуть. В принципе это задумывалось изначально. Думал сначала о списке кольцевом. Но что-то мне кажется что он не зайдет здесь.

[BDA]

FPaul, насколько я понял Ваш код, там осуществляется поиск в глубину, у которого сложность явно выше линейной. А в условии требуется линейная. Предлагаю такой вариант (написан на C++, но ничего сложного в переводе на паскаль нет):

#include <iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    int count = 1 << N - 1;
    int flags[count] = {0};
    flags[0] = 1;
    int mask = count - 1;
    for (int i =  mask; i > 0; i = (i << 1) & mask) flags[i] = 1;
    for (int i = 0; i < N; ++i) cout << 0;
    for (int i = 0, j = 0; i < (1 << N) - 2 * N; ++i) {
    	cout << flags[j];
    	int tmp = j;
    	j = (j << 1) & mask | flags[j];
    	flags[tmp] = 1;
    }
    for (int i = 0; i < N; ++i) cout << 1;
    return 0;
}

Для N от 1 до 6 ответ верный, дальше не проверял.

[Nurz]

FPaul

  
    int flags[count] = {0};
  //А так разве можно задавать массив? Там же по сути должна быть константа. А таким образом задается динамический массив.
 // int *flags = new int[count]; Но если использовать этот вариант, у меня вылетает ошибка.

[BDA]

Компилятор и предыдущую запись понимал (и выделял место под count).
У меня ошибок не возникает:

#include <iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    int count = 1 << N - 1;
    int *flags = new int[count];
    for (int i = 0; i < count; ++i) flags[i] = 0;
    flags[0] = 1;
    int mask = count - 1;
    for (int i =  mask; i > 0; i = (i << 1) & mask) flags[i] = 1;
    for (int i = 0; i < N; ++i) cout << 0;
    for (int i = 0, j = 0; i < (1 << N) - 2 * N; ++i) {
    	cout << flags[j];
    	int tmp = j;
    	j = (j << 1) & mask | flags[j];
    	flags[tmp] = 1;
    }
    for (int i = 0; i < N; ++i) cout << 1;
    delete[] flags;
    return 0;
}

[Nurz]

А вот эта программа у меня спокойно компилируется, без всяких ошибок. Спасибо.