VPF::Перебрать все цепочки языка в заданном диапазоне

Alexey91

Дата 16.10.2011, 08:56 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

Здравствуйте!

Есть язык, который задается множеством {0,1}
Как можно перебрать все возможные элементы множества в заданном диапазоне

Например, диапазон от 2 до 3 включительно
00,01,10,11
000,001,010,011,100,101,110,111

Проблема в том, что язык может состоять из произвольных цепочек, т.е. {a,b,0}, {d,e,1}

math64

Дата 16.10.2011, 09:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

Перебирай N = количество букв в слове
Для I = 1..N
Перебирай все возможные буквы на I-м месте
Проверь полученное слово на допустимость в языке

Alexey91

Дата 16.10.2011, 09:34 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

math64, мне не понятно как перебирать

Хорошо для {0,1}
Минимальная длина слова N=2. Начинаем цикл.
Первая позиция (I=1). Выбираем 0 или 1. Выбрали 0. На второй тоже 0. Получили 00
Но в данном случае я выбираю сам ))), а не программа
Как сделать так, чтобы программа сама догадывалась, что следующее будет, например, 01

Alexey91

Дата 16.10.2011, 10:20 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

Я придумал с помощью рекурсии
Например N=3 (длина цепочек 3)

Код


char **M; // Множество цепочек
si label=0, L=7, S=2;  // L - длина цепочки, S - размер алфавита
char alphabet[2]={'0','1'}

// shift сдвиг по позиции текущей цепочки
// label номер элемента во множестве цепочек

void rek(char* A, si N, si shift)
{
 si i,j,k;

 if(N==1)
 {
  for(k=0; k < S; k++, label++)
  {
   A[shift]=alphabet[k];
   for(j=0; j < L; j++) M[label][j]=A[j];
  }
  shift=0;
 }

 else
 {
  for(i=0; i < S; i++)
  {
   A[shift]=alphabet[i];
   rek(A,N-1,shift+1);
  }

 }


}

Это сообщение отредактировал(а) Alexey91 - 16.10.2011, 12:03

math64

Дата 16.10.2011, 13:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

Код


const char letters[] = "01";
const int letterCount = sizeof(letters)/ sizeof(letters[0]) - 1;
const char firstLetter = letters[0];
const char lastLetter = letters[letterCount-1];
char nextLetter(char letter) {
   const char*p = strchr(letters, letter);
   return p[1];
}
bool nextWord (char* word, int wordLen = 0) {
  if (wordLen == 0)
    wordLen = strlen(word);
  for (int i = wordLen - 1; i >=0; i--) {
    char letter = word[i];
    if (letter == lastLetter) {
       word[i] = firstLetter;
       continue;
    }
    word[i] = nextLetter(letter);
    return true;
  }
  return false;
}

void enumWords(int len) {
  char* word = new char[len+1];
  for(int i =0; i < len; i++)
    word[i] = firstLetter;
  word[len] = '\0';
  do {
    addWord(word);
  } while(nextWord(word, len) );
  delete[] word;
}

Это сообщение отредактировал(а) math64 - 16.10.2011, 13:23

Alexey91

Дата 16.10.2011, 16:13 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

math64, зачем вы пишете const перед переменными?

math64

Дата 16.10.2011, 19:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

Цитата(Alexey91 @ 16.10.2011, 16:13

)

math64, зачем вы пишете const перед переменными?

Потому что они константы - чтобы защитить от случайного изменения и чтобы компилятор мог выполнить оптимизацию.
Если нужна возможность задавать алфавит программно - нужно соответственно модифицировать алгоритм, например, поместить всё в класс (защитой будет помещение их в секцию private):

Код


class Language {
public:
  typedef void (*AddWord)(const char*); // callback функция

  Language(const char* p_letters);
  ~Langage();
  char nextLetter(char letter);
  bool nextWord(char* word, int length = 0);
  void enumWords(int length, AddWord addWord);
private:
  char* letters;
  int letterCount;
  char firstLetter;
  char lastLetter;
};

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »