понедельник, 12 января 2015 г.

Перестановка букв

Задача: 
Дано N - количество букв и сами буквы (можно через пробел). Вывести все слова длиной N (1<=N<=10), содержащие все буквы без повторений.

Решение:
Данная задача имеет N! слов.

1. Эти слова можно получить рекурсивно:
процедура Gen(k - количество букв в слове)
{
 если длина слова меньше N, то
  цикл с первой буквы и до последней 
     если буква еще не выбрана - добавляем к слову
     вызов процедуры Gen(k+1)
     удаляем букву из слова
  конец цикла
иначе 
 вывод слова.
}
Этот вариант алгоритма выведет слова в алфавитном порядке.

Например:
АВС
АСВ

ВАС
ВСА

САВ
СВА

Пример программы на Паскале:
Var
       S,F:string;
       N:integer;
Procedure Gen ( K:integer );

Var I: integer;
Begin
  If (Length(S)=N) Then
      Writeln(S)
  else
  For I:=1 to N do
     if pos(F[i], S)=0 then begin
       S:=S+F[i];
       Gen(K+1); 
       delete(S,K,1);
   End;
End;

Begin
  Readln (N);
  Readln (F);
  S:='';
  Gen(1); 
End.

2. А можно и по технологии динамического программирования без рекурсии:
берем первую букву и образуем одно слово
в цикле по k от 1 до n
  скопируем все слова еще k раз
  для каждого слова
  в цикле по i от 1 до k+1
   вставляем следующую букву на i-ое место
  конец цикла по i
конец цикла по k
вывод всех слов.

Слова хранятся в массиве. Размер массива заранее не известен, но его можно вычислить по формуле n! В С++ для этих целей можно использовать класс vector.
Этот вариант алгоритма выведет слова не алфавитном порядке. Поэтому получившийся массив слов перед выводом нужно отсортировать.

Например:
k=1
скопировали 1 раз
А
А
вставили В на 1-е и на 2-е место
ВА
АВ

k=2
скопировали 2 раза
ВА
АВ
ВА
АВ
ВА
АВ
вставили С на 1-е, 2-е и 3-е место
СВА
САВ
ВСА
АСВ
ВАС
АВС
и т.д.

Пример программы на С++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  int n,k,m; 
  string c;
  vector <string> A;

  cin>>n;
  cin>>c;
  A.push_back(c);
  k=1;
  for (int i=1;i<n;i++)
   {
       cin>>c;
       m=A.size();
       for (int j=1;j<=k;j++)
         for (int l=0; l<m;l++)
            A.push_back(A[l]);
  
       int p=0;
       for (int j=0;j<=k;j++)
        for (int l=0; l<m;l++)
        {
             A[p].insert(j,c);
             p++;
        }
       k=k+1;
   }

   m=A.size();
   sort(A.begin(), A.end());

   for (int i=0;i<A.size();i++)
   {
     cout<<A[i]<<endl;
   }
    return 0;
}


Комментариев нет:

Отправить комментарий