|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.10.2012, 17:54 | #1 |
Пользователь
Регистрация: 13.09.2012
Сообщений: 12
|
Алгоритм генерации перестановок в лексикографическом порядке
У меня проблема. Нужно перебрать все лексикографически следующие перестановки. Вот мой код. Одна перестановка делается, а дальше я не знаю, как мне повторить все мои действия для этой перестановки и так дали до конечной.
Если нужно, то вот Алгоритм генерации перестановок в лексикографическом порядке: 1. Просматриваем а1, ..., аn с конца до тех пор, пока не попадется ai<ai+1. Если таковых нет, то генерация закончена. 2. Рассматриваем ai+1, ai+2, ..., an. Найдем первый с конца am больший ai и поменяем их местами. 3. ai+1, ai+2, ..., an переставим в порядке возрастания (для этого достаточно её переписать с конца). 4. Печатаем найденную перестановку. 5. Возвращаемся к пункту 1. Спасибо!!! #include <iostream> #include <iomanip> #include <sstream> #include <conio.h> #include <cmath> using namespace std; int main() { cout.width(62); cout<<"Pobudova leksykografichno nastupnoi perestanovky"<<endl<<endl; int n; cout<<"Vvedit naturalne chyslo: "; cin>>n; cout<<endl; int *mas=new int[n]; for (int i=1;i<=n;++i) { cout<<"Vvedit "<<i<<"-te chyslo perestanovky: "; cin>>mas[i]; } for (int i=1;i<=n;++i) { cout<<mas[i]; } cout<<endl; int b1=0,b2=0,k,k1,i; for (i=n;(i>=1)&&(b1<=b2);--i) { b1=mas[i]%10; b2=mas[i-1]%10; k=mas[i-1]; k1=i-1; } cout<<k<<endl<<k1<<endl; int temp,min2; for (int i=n;i>=n;--i) { if (mas[i]>k) { temp=k; mas[k1]=mas[i]; mas[i]=temp; } } for (int i=1;i<=n;++i) cout<<mas[i]; cout<<endl; for (int i=k1+1,f=0;(i<=(n+k1+1)/2)&&(f<n);++i,++f) { swap(mas[i],mas[n-f]); } for (int i=1;i<=n;++i) cout<<mas[i]; //while (1) goto start; getche(); return 0; } |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Написать рекурсивную процедуру генерации всех перестановок чисел от 1 до n | Proskurina | Паскаль, Turbo Pascal, PascalABC.NET | 5 | 04.06.2012 10:34 |
Алгоритм перестановок | Pirotexnik | Visual C++ | 0 | 05.12.2011 13:08 |
генерация следующей перестановки в лексикографическом порядке. | Dimanw92 | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 26.09.2011 23:19 |
Прерывание генерации перестановок | Goombold | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 26.05.2011 10:21 |
Прогамма должна выполнять сортировку имен в лексикографическом порядке методом Хоора и Шелла. | ser_b | Помощь студентам | 2 | 27.05.2010 21:26 |