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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
loko95
0 / 0 / 0
Регистрация: 27.07.2015
Сообщений: 2
#1

Найти степень перестановки - C++

19.01.2016, 10:11. Просмотров 418. Ответов 3
Метки нет (Все метки)

Весь код не нужен. Прошу лишь объяснить алгоритм.

Требуется вычислить степень заданной перестановки.

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно PN = N!

Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.

Обратной перестановкой к перестановке π называется такая перестановка π-1, что ππ-1 = π-1π = ε, где ε – тождественная перестановка.

Степенью перестановки называется минимальное натуральное число k такое, что πk = ε

Входные данные

В первой строке входного файла INPUT.TXT записано число 0 < N <= 100 - порядок перестановки. Во второй строке записана сама перестановка.

Выходные данные

В выходной файл OUTPUT.TXT выведите степень данной перестановки.

Пример


INPUT.TXT
3
2 3 1


OUTPUT.TXT
3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2016, 10:11     Найти степень перестановки
Посмотрите здесь:

Возведение числа в степень. Не могу найти ошибку C++
программ найти x степень n (рекурсией) C++
C++ Найти степень двойки
C++ Написать программу с функцией, вычисляющей целую степень дробного числа. Учесть,что степень может быть положительной, отрицательной, нулевой
Найти степень многочлена C++
Найти с помощью рекурсии сумму и возвести в степень C++
C++ Найти степень числа и сумму цифр
C++ Найти решение СЛАУ методом Гаусса (без перестановки строк)
Не могу найти ошибку в коде, генерирующего всевозможные перестановки C++
C++ Перестановки: чтобы любые две соседние перестановки отличались только порядком двух соседних элементов
Найти ошибку в программе возведения числа в степень C++
Найти перестановки цифр в числе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
avgoor
 Аватар для avgoor
789 / 431 / 93
Регистрация: 05.12.2015
Сообщений: 1,272
19.01.2016, 12:44     Найти степень перестановки #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от loko95 Посмотреть сообщение
Прошу лишь объяснить алгоритм.
Запихиваешь перестановку в массив или vector;
Как я понял, у тебя нумерация элементов с 1. Тогда обходишь массив в порядке перестановки, приравнивая пройденные элементы 0 и инкрементируя счетчик пройденных элементов, пока не придешь к исходному элементу.
Сейчас мы прошли один цикл. У нас есть его длина. Запоминаем ее в порядок и обнуляем счетчик. Продолжаем со следующего не нулевого. Когда пришли в него новый порядок будет НОК(порядок, счетчик). И т.д. пока не закончатся ненулевые элементы.
loko95
0 / 0 / 0
Регистрация: 27.07.2015
Сообщений: 2
19.01.2016, 13:15  [ТС]     Найти степень перестановки #3
спасибо огромное!
Mr.X
Эксперт С++
 Аватар для Mr.X
3021 / 1677 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
20.01.2016, 09:22     Найти степень перестановки #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
//Степень перестановки
//(Время: 1 сек. Память: 16 Мб Сложность: 46%)
 
//Требуется вычислить степень заданной перестановки.
 
//Перестановкой из N элементов называется упорядоченный набор из N различных чисел
//от 1 до N. Количество различных перестановок порядка N равно PN = N!
 
//Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает
//преобразование этого множества. А именно, она говорит, что
//на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.
 
//Обратной перестановкой к перестановке ПЂ называется такая перестанов   ка ПЂ^-1,
//что ПЂПЂ^-1 = ПЂ^-1ПЂ = Оµ, где Оµ – тождественная перестановка.
 
//Степенью перестановки называется минимальное натуральное число k такое, что ПЂ^k = Оµ
 
//Входные данные
 
//В первой строке входного файла INPUT.TXT записано число 0 < N <= 100 -
//порядок перестановки. Во второй строке записана сама перестановка.
//Выходные данные
 
//В выходной файл OUTPUT.TXT выведите степень данной перестановки.
//Гарантируется, что ответ не превышает 109.
 
//Пример
//INPUT.TXT
//3
//2 3 1
//OUTPUT.TXT
//3
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >   T_permutation;
typedef unsigned long long          T_degree;
///////////////////////////////////////////////////////////////////////////////
const   int     FIRST_POSITION_IND  =   1;
///////////////////////////////////////////////////////////////////////////////
struct  T_is_not_zero
{
    //-------------------------------------------------------------------------
    bool    operator()  ( int  val )
    {
        return  val     !=  0;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
T_permutation::iterator     it_from_elem
    (
        T_permutation   &   permutation,
        int                 element
    )
{
    return      permutation.begin()
            +   element
            -   FIRST_POSITION_IND;
}
///////////////////////////////////////////////////////////////////////////////
int     elem_from_it
    (
        T_permutation                       &   permutation,
        T_permutation::iterator     const   &   it
    )
{
    return      it
            -   permutation.begin()
            +   FIRST_POSITION_IND;
}
///////////////////////////////////////////////////////////////////////////////
void    set_last_cycle_element_and_set_it_to_zero_in_permutation
    (
        T_permutation   &   permutation,
        int             &   last_cycle_element
    )
{
    T_permutation::iterator     it  =   it_from_elem
                                            (
                                                permutation,
                                                last_cycle_element
                                            );
 
    last_cycle_element              =   *it;
    *it                             =   0;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_set_cycle_size
    (
        T_permutation   &   permutation,
        int             &   cycle_size
    )
{
    T_permutation::iterator    it  =   std::find_if
                                            (
                                                permutation.begin   (),
                                                permutation.end     (),
                                                T_is_not_zero       ()
                                            );
 
    bool    bool_res    =   it  !=  permutation.end();
 
    if( bool_res )
    {
        cycle_size                      =   1;
 
        int     first_cycle_element     =   elem_from_it
                                                (
                                                    permutation,
                                                    it
                                                );
 
        int     last_cycle_element      =   first_cycle_element;
 
        for(;;)
        {
            set_last_cycle_element_and_set_it_to_zero_in_permutation
                (
                    permutation,
                    last_cycle_element
                );
 
            if( last_cycle_element  ==  first_cycle_element )
            {
                break;
            }
 
            ++cycle_size;
        }//for
    }//if
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
T_degree    GCD
    (
        T_degree    L,
        T_degree    R
    )
{
    if( L > R )
    {
        std::swap(L, R);
    }
 
    return  L   ==  0
                ?   R
                :   GCD( L, R % L );
}
///////////////////////////////////////////////////////////////////////////////
T_degree    LCM
    (
        T_degree    L,
        T_degree    R
    )
{
    return  L * R / GCD( L, R );
}
///////////////////////////////////////////////////////////////////////////////
T_degree    degree( T_permutation   permutation )
{
    T_degree    res         =   1;
    int         cycle_size  =   0;
 
    while   (
                successfully_set_cycle_size
                    (
                        permutation,
                        cycle_size
                    )
            )
    {
        res     =   LCM     (
                                res,
                                cycle_size
                            );
    }//while
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    int     n   =   0;
    std::cin    >>  n;
 
    T_permutation   permutation;
 
    for( int  i = 0; i < n; ++i )
    {
        int     cur_val     =   0;
        std::cin    >>  cur_val;
        permutation.push_back( cur_val );
    }//for
 
    std::cout   <<  degree( permutation )
                <<  std::endl;
}
Yandex
Объявления
20.01.2016, 09:22     Найти степень перестановки
Ответ Создать тему
Опции темы

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