Форум программистов, компьютерный форум CyberForum.ru

Лексикографическое порождение перестановок - C++

Восстановить пароль Регистрация
 
romanticVL
0 / 0 / 0
Регистрация: 21.06.2012
Сообщений: 50
28.01.2014, 16:30     Лексикографическое порождение перестановок #1
Первая ячейка массива получает значение из -1 ячейки массива в строке while (A[i] > A[i + 1]) i--; Как исправить? генерация работает нормально, но теряется первое значение. Помогите!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int main()
{
    setlocale (LC_ALL, "Rus");
 
    const int n = 3;
    int A[n];
    
    
    for (int k = 0; k < n; k++) 
    {
        //cout << "Введите символ" << endl;
        A[k] = n - k;
    }
    
    cout << "\tГенерация" << endl;
    
    int i = 1;
    while (i != 0)
    {
        for (int l = 0; l < n; l++) cout << A[l] << ' ';
        
        // Найти самое правое место, где A[i] < A[i + 1]
        i = n - 1;
        
        while (A[i] > A[i + 1]) i--; // тут ошибка вылазиет!
 
        // Найти A[j], наименьший элемент справа от A[i] и больший его
        int j = n;
        while (A[i] > A[j]) j--;
 
        // Поменять местами A[i] и A[j] и затем перевернуть A[i + 1], ... , A[n]
        swap (A[i], A[j]);
        int r = n;
        int s = i + 1;
 
        while (r > s)
        {
            swap (A[r], A[s]);
            r--;
            s++;
        }
        cout << endl;
    }
 
 
    _getch();
    return 0;
}
Добавлено через 24 минуты
Помогите кто-нибудь!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2014, 16:30     Лексикографическое порождение перестановок
Посмотрите здесь:

C++ кол-во перестановок
Выведение всех перестановок C++
Количество перестановок C++
C++ Порядок перестановок
C++ Задача на количество перестановок
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
28.01.2014, 16:54     Лексикографическое порождение перестановок #2
Не уверен что правильно понял алгоритм, но ошибка у тебя возникает в 43 строке из-за 38 строки:
Должно быть int r=n-1; иначе когда r=n, то r=3 , тогда A[r]=A[3] (вылетел за пределы массива 0,1,2).

Добавлено через 2 минуты
и в 33 строчке та же ошибка!
romanticVL
0 / 0 / 0
Регистрация: 21.06.2012
Сообщений: 50
28.01.2014, 16:55  [ТС]     Лексикографическое порождение перестановок #3
Подскажи чем компилировал?
DPS
 Аватар для DPS
32 / 32 / 3
Регистрация: 12.11.2011
Сообщений: 107
Завершенные тесты: 1
28.01.2014, 16:58     Лексикографическое порождение перестановок #4
Ну просто прогоните через отладчик:

Вот такой у вас массив:
C++
1
2
3
A[0] = 3;
A[1] = 2;
A[2] = 1;

Вот этот цикл
C++
1
 while (A[i] > A[i + 1]) i--; // тут ошибка вылазиет!
выполняется у вас два раза (перед циклом while значение i = 1)

первый раз:
C++
1
A[1] > A[2], т.е. 2 больше 1? - да, поэтому отнимем 1 (теперь i = 0)
второй раз:
C++
1
A[0] > A[1]? т.е. 3 больше 2? - да, поэтому снова отнимем 1 (и вот теперь-то i = -1)
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
28.01.2014, 17:00     Лексикографическое порождение перестановок #5
и в 28 то же

Добавлено через 1 минуту
VC++ 2012
romanticVL
0 / 0 / 0
Регистрация: 21.06.2012
Сообщений: 50
28.01.2014, 17:04  [ТС]     Лексикографическое порождение перестановок #6
я понял почему в -1 уходит, как исправить то?

Добавлено через 3 минуты
Цитата Сообщение от mustimur Посмотреть сообщение
и в 28 то же

Добавлено через 1 минуту
VC++ 2012
Хмм, я в VS 2012 тоже делал, только ни ошибок, ни предупреждений никаких
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
28.01.2014, 17:46     Лексикографическое порождение перестановок #7
Цитата Сообщение от romanticVL Посмотреть сообщение
Хмм, я в VS 2012 тоже делал, только ни ошибок, ни предупреждений никаких
Он и не выдаст, ошибка у Вас в алгоритме: массив ваш A[0], A[1], A[2] тогда разберем ваш код
C++
1
2
3
4
5
6
7
8
9
10
 i = n - 1; // ошибка в этом случае при n=3 то i=2 тогда A[i + 1]=A[3] - вылет за пределы массива меняем на  i = n - 2;
        
        while (A[i] > A[i + 1]) i--; //При i=0 у Вас A[0]>A[1] т.е. выполняется действие i-- и становится i=-1, допустим исправим так while ((A[i] > A[i + 1]) && i>0) то в этом случаи после цикла i=0, тогда см. ниже 
 
        // Найти A[j], наименьший элемент справа от A[i] и больший его
        int j = n;// ошибка j=3 то A[j]=A[3] - вылет за пределы массива исправим j=n-1; j=2;
        while (A[i] > A[j]) j--; //помним что i=0, тогда условие будет A[i] > A[j] соблюдаться до A[0] > A[1], т.е. до j=1 и выполнится действие j--; следовательно на выходе из этого цикла получите j=0
 
        // Поменять местами A[i] и A[j] и затем перевернуть A[i + 1], ... , A[n]
        swap (A[i], A[j]);; // помним что i=0 и j=0 и что получаем????
а этот цикл тоже закончен сразу while (i != 0) т.к. i=0
romanticVL
0 / 0 / 0
Регистрация: 21.06.2012
Сообщений: 50
28.01.2014, 18:18  [ТС]     Лексикографическое порождение перестановок #8
Охх.. переписывал из учебника, неужели там столько опечаток, как же исправить сейчас =(
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
28.01.2014, 18:29     Лексикографическое порождение перестановок #9
Цитата Сообщение от romanticVL Посмотреть сообщение
Охх.. переписывал из учебника, неужели там столько опечаток, как же исправить сейчас =(
Могу ошибаться но лексикографическим упорядочением тут и не пахнет пока же то, так уж получилось, что я помогал с лексикографическим упорядочением чисел посмотри здесь лексикографически упорядочены числа
romanticVL
0 / 0 / 0
Регистрация: 21.06.2012
Сообщений: 50
28.01.2014, 18:56  [ТС]     Лексикографическое порождение перестановок #10
я нашел код на паскале, помогите пожалуйста перевести, плохо знаю синтаксис
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Program perms;
var
  i, j, h, n, k: integer;
  a:array[0 .. 100] of integer;
 
procedure output;
var i: integer;
begin
  writeln;
  for i:=1 to n do write(a[i],' ');
end;
 
begin
  write('Êîëè÷åñòâî ýëåìåГ*òîâ ïåðåñòГ*Г*îâêè: '); readln(n);
  fillmem(a, sizeof(array[0..100] of integer), 0);
 
 
  for i:=1 to n do a[i]:=i;
 
  repeat
    output;
    i:=n;
    while a[i-1]>a[i] do dec(i);
    j:=i-1;
    h:=a[j];
    while a[i+1]>h do inc(i);
    a[j]:=a[i];  a[i]:=h;
    i:=j+1; k:=n;
    while i<k do begin
       h:=a[i]; a[i]:=a[k]; a[k]:=h;
       inc(i); dec(k)
    end
  until j=0;
end.
Это то что нужно, и похоже очень на мой код!
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
28.01.2014, 19:19     Лексикографическое порождение перестановок #11
А мой код не понравился значит? ну ладно помогу с переводом
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
int i, j, h, n, k;
int a[100];
 
void output()
{
      
  for (int i=1;i<=n;i++)std::cout<<a[i]<<' ';
}
 
int main()
{
  std::cout<<"Kol-vo elementov "; std::cin>>n;
 
 for (int i=0;i<=100;i++) a[i]=0;
 
for (int i=0;i<=n;i++) a[i]=i;
 
  do
  {
    output();
    i=n;
    while (a[i-1]>a[i]) i--;
    j=i-1;
    h=a[j];
    while (a[i+1]>h) i++;
    a[j]=a[i];  a[i]=h;
    i=j+1; k=n;
    while (i<k)
    {
       h=a[i]; a[i]=a[k]; a[k]=h;
       i++; k--;
    }
  } while (j!=0);
  std::system ("pause");
  return 0;
 
}
Сразу говорю это дословный перевод (почти), так что за алгоритм и результат ответсвености не несу
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
28.01.2014, 22:27     Лексикографическое порождение перестановок #12
romanticVL, Элементы массива int A[n] это A[0], A[1], ... A[n-2], A[n-1]
Последний элемент массива : n-1
Цитата Сообщение от romanticVL Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
    int A[n];
 
        // Найти самое правое место, где A[i] < A[i + 1]
        /* А если нет такого i , что делать ? */
 
        i = n - 2; /* Последний элемент массива : n-1 . А в след. команде A[i+1] */
        // i = n - 1;  // error 
 
        while (A[i] > A[i + 1]) i--; 
        /* А если получим i < 0 ? */
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2014, 05:57     Лексикографическое порождение перестановок
Еще ссылки по теме:

C++ Число перестановок QuickSort
C++ Наследование,порождение объектов
C++ Лексикографическое сравнение. Сортировка строк по алфавиту

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
romanticVL
0 / 0 / 0
Регистрация: 21.06.2012
Сообщений: 50
29.01.2014, 05:57  [ТС]     Лексикографическое порождение перестановок #13
Цитата Сообщение от mustimur Посмотреть сообщение
А мой код не понравился значит? ну ладно помогу с переводом
спасибо
Yandex
Объявления
29.01.2014, 05:57     Лексикографическое порождение перестановок
Ответ Создать тему
Опции темы

Текущее время: 08:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru