Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

19.01.2016, 10:11. Просмотров 578. Ответов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2016, 10:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти степень перестановки (C++):

Перестановки: чтобы любые две соседние перестановки отличались только порядком двух соседних элементов - C++
Вводится число n &lt;= 8. Вывести все перестановки чисел 1,2..,n, так, чтобы две любые две соседние перестановки отличались только порядком...

Найти перестановки цифр в числе - C++
Здравствуйте. Пишу программу на C++, по условию мне необходимо в цикле отправить в функцию массив из 6 элементов, элементы массива могут...

Не могу найти ошибку в коде, генерирующего всевозможные перестановки - C++
Всем привет! Условие задачи: задано множество, состоящие из натуральных чисел от 1 до n с шагом 1. Например: {1, 2, 3, 4, 5}. Получить...

Вычислить 10-ю степень двойки сложением, умножением и просто возведением в степень. - C++
Написать код на С++ или С# или на Java Вычислить 10-ю степень двойки 1 - сложением, умножением и просто возведением в степень.

Найти решение СЛАУ методом Гаусса (без перестановки строк) - C++
Итак, требуется найти решение СЛАУ методом Гаусса (без перестановки строк). Проще говоря, есть матрица А, умножаемая на матрицу Х,...

Найти степень двойки - C++
Дано целое число N&gt;0, являющееся некоторой степенью числа 2:N=2 ^k. Найти целое число К - показатель этой степени. Если можно на С

3
avgoor
931 / 566 / 124
Регистрация: 05.12.2015
Сообщений: 1,585
19.01.2016, 12:44 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от loko95 Посмотреть сообщение
Прошу лишь объяснить алгоритм.
Запихиваешь перестановку в массив или vector;
Как я понял, у тебя нумерация элементов с 1. Тогда обходишь массив в порядке перестановки, приравнивая пройденные элементы 0 и инкрементируя счетчик пройденных элементов, пока не придешь к исходному элементу.
Сейчас мы прошли один цикл. У нас есть его длина. Запоминаем ее в порядок и обнуляем счетчик. Продолжаем со следующего не нулевого. Когда пришли в него новый порядок будет НОК(порядок, счетчик). И т.д. пока не закончатся ненулевые элементы.
1
loko95
0 / 0 / 0
Регистрация: 27.07.2015
Сообщений: 2
19.01.2016, 13:15  [ТС] #3
спасибо огромное!
0
Mr.X
Эксперт С++
3051 / 1696 / 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;
}
0
20.01.2016, 09:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2016, 09:22
Привет! Вот еще темы с ответами:

Найти степень многочлена - C++
Ребята, помогите пожалуйста, нужно составить программу для вычисления степень многочлена!!

программ найти x степень n (рекурсией) - C++
help me please! thanks

Написать программу с функцией, вычисляющей целую степень дробного числа. Учесть,что степень может быть положительной, отрицательной, нулевой - C++
Написать программу с функцией, вычисляющей целую степень дробного числа. Учесть,что степень может быть положительной, отрицательной,...

Найти степень числа и сумму цифр - C++
есть 2 задачи на циклы которые надо решить 1) Дано действительное число а , и натуральное число n . Не используя математические функции...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.