Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [С++] Генерация перестановок


Автор: seansy 26.3.2007, 07:36
  
Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке. Требования к заданию множества - те же, что в предыдущих лабораторных работах.
Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый - минимальный - набор), затем - посредством МИНИМАЛЬНО ВОЗМОЖНЫХ ПЕРЕСТАНОВОК! - сгенерировать последовательно возрастающие (лексикографически) наборы, вплоть до последнего, в котором все элементы упорядочены по убыванию.
Дополнительно: 
1)     Предоставить пользователю возможность выбора другого варианта работы программы, в котором за исходную точку упорядочивания наборов выбирается не минимальный набор, а тот, который задан пользователем. 
2)     Оценивать количество возможных перестановок и в случае, если они не поместятся на экран, выполнять их вывод в файл с выдачей на экран соответствующей информации для пользователя или выполнять поэкранный вывод с ожиданием нажатия клавиши.
Возможный алгоритм решения (Пример: множество А={1,2,3,4,5,6}, |A| = n):
Предположим, что уже построено m наборов. Тогда для получения m+1-го набора:
1)     Выполняется проверка последнего (m-го) набора на наличие в его конце некоторого количества символов, упорядоченных по убыванию - пусть это символы ak+1…an.      
           3 5 2 6 4 1  - k=3, символы с 4-го по 6-й упорядочены по убыванию.
2)     Если такое k найдено, то поменять местами k-й элемент и наименьший элемент из ak+1…an, больший этого ak.      
          В нашем примере это 2 и 4:  3 5 4 6 2 1 . 
3)     После шага 2 упорядочить элементы с k+1-го до последнего по возрастанию. Получен очередной набор ==> выдать его на печать.      
           3 5 4 1 2 6 .
4)     Если на шаге 1 ответ отрицательный, то поменять местами 2 последних элемента и выдать на печать полученный набор. В частности, после шага 3 это неизбежное действие, т.к. все последние элементы были размещены по возрастанию ==> целесообразно после выполнения ш.3 задавать признак его выполнения, который будет анализироваться (и сбрасываться) на шаге 1.           После шага 3 было  3 5 4 1 2 6  ==> выдать  3 5 4 1 6 2 .      
          Если был набор  3 5 2 6 1 4  ==> выдать  3 5 2 6 4 1 . 
5)     Возврат на шаг 1.

Автор: GIK 26.3.2007, 23:00
Не понятно, как определяется k, он задается пользователем, или определяется исходя из найденного диапазона убывания?
Вото, кое что сделал, можно доработать:

Код


#include<conio>
#include<cstdio>
#include<string>
#include<stdlib>
#include<iostream>

using namespace std;

void main()
{  int i, j;

 int new_m[12];
 for(i=0; i<12; i++){
  cin>>new_m[i];
}

int k;
cout<<"Enter the k:";
cin>>k;
if(k>12 || k<0){
cout<<"No correct"<<endl;
getch();
return;
}
k--;
int max_r=(new_m[k+1]<0 ? new_m[k+1] * -1 : new_m[k+1]); 
int ran_nex_m; 

int for_index_beg=0; 
int for_index_end=0;

int min_k; 

for(i=k+2; i<12; i++){
  ran_nex_m=(new_m[i]<0 ? new_m[i] * -1 : new_m[i] );
  if(ran_nex_m>=max_r){
     max_r=ran_nex_m;
     for_index_beg=i; 
     for_index_end=i;

  }else{

    for_index_end=i;

  }
}

 if(for_index_beg==for_index_end){
   cout<<"Not diapazon"<<endl;
   getch();
   return;
  }

 for(i=for_index_beg; i<=for_index_end; i++){
  cout<<new_m[i]<<"  ";
  }
  cout<<endl;


min_k=new_m[k+1]; 
int bul=0;
int ii; 

 for(i=k+1; i<12; i++){ 

 if((new_m[i]<=min_k) && new_m[i]>new_m[k]){
  bul=1;
  min_k=new_m[i];
  ii=i;
 }
}
if(bul){
 int ran=new_m[k];
 new_m[k]=new_m[ii]; 
 new_m[ii]=ran;
}
else{
  cout<<"Not zamena"<<endl;
  getch();
  return;
}

for(i=0; i<12; i++){
cout<<new_m[i]<<"  ";
}

for(i=k+1; i<12-1; i++){
  for(j=i; j<12; j++)
   if(new_m[i]>new_m[j]){
    int ran=new_m[i];
    new_m[i]=new_m[j];
    new_m[j]=ran;
  }
}
cout<<endl;

for(i=k+1; i<12; i++){
 cout<<new_m[i]<<" ";
 
}


getch();

}

Автор: seansy 27.3.2007, 03:09
Спасибо GIK! Могу ли я еще с чем-нибудь подобным к тебе обратиться? А то я решаю задачи только школьного курса да и то на Паскале... в нем я тоже могу кого-нибудь выручить...

Автор: GIK 27.3.2007, 10:27
Да конечно можно smile  Обращайся, всегда поможем, чем можем smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)