⇢ Ма
Мария
Помогите с программированием...
Задана перестановка А чисел 1,…,100.Для каждого i, 1<=i<=100, указать такое (зависящее от i) минимальное значение К, при котором А^к (i)=i. Я не могу понять чего от меня хотят...
ВЗ
Валерий Закарлюка
Есть подозрение, что мы имеем дело со следующим: Над множеством перестановок определяем некоммутативную группуE(i) = i -- единичный элемент, тривиальная перестановка (A*B)(i) = A(B(i)) -- правоассоциативная операция "умножения" перестановок. A*E = E*A = A.A^k = A*A*...*A (k раз) ; A^0 = E, A^1 = A -- степенная функция. А теперь быстренько забываем всё, что я сказал, и ищем то, что требуется. 1) Для каждого по отдельности числа i требуется найти k : (A^k)(i) = i. Помимо очевидного решения k=0
int A(int i) { ...}
int findk(int i)
{
int k = 0, a = i;
do
{
a = A(a);
++k;
}
while(a != i);
return k;
}
Будем считать, что A — это честная перестановка, а это значит, что k < N, где N — мощность множества чисел i, т. е. 1002) Найти k>0 : A^k = E.Очевидно, k = НОК ( { findk(i) | i=1..N } )
Похожие вопросы