На головну

намиста

Завдання "намиста" - це одна з класичних комбінаторних завдань. Потрібно порахувати кількість різних намист з  намистин, кожна з яких може бути пофарбована в один з  кольорів. При порівнянні двох намист їх можна повертати, але не перевертати (тобто дозволяється зробити циклічний зсув).

Рішення

Вирішити це завдання можна, використовуючи лему Бернсайда і теорему Пойа. [Нижче йде копія тексту з цієї статті]

У цьому завданні ми можемо відразу знайти групу інваріантних перестановок. Очевидно, вона буде складатися з  перестановок:





Знайдемо явну формулу для обчислення  . По-перше, зауважимо, що перестановки мають такий вигляд, що в  -ої перестановці на  -ої позиції стоїть  (Узяте по модулю  , Якщо воно більше  ). Якщо ми будемо розглядати циклічну структуру  -ої перестановки, то побачимо, що одиниця переходить в ,  переходить в ,  - в  , І т.д., поки не прийдемо до числа  ; для інших елементів виконуються схожі затвердження. Звідси можна зрозуміти, що все цикли мають однакову довжину, рівну  , Тобто  ( "Gcd" - найбільший спільний дільник, "lcm" - найменше спільне кратне). Тоді кількість циклів в  -ої перестановці дорівнюватиме просто .

Підставляючи знайдені значення в теорему Пойа, отримуємо рішення:

Можна залишити формулу в такому вигляді, а можна її згорнути ще більше. Перейдемо від суми за всіма  до суми тільки по делителям  . Дійсно, в нашій сумі буде багато однакових доданків: якщо  не є дільником  , То такий дільник знайдеться після обчислення  . Отже, для кожного дільника  його доданок  врахує кілька разів, тобто суму можна уявити в такому вигляді:

де  - Це кількість таких чисел  , що  . Знайдемо явний вираз для цієї кількості. Будь-яке таке число  має вигляд:  , де  (Інакше було б  ). Згадуючи функцію Ейлера, ми знаходимо, що кількість таких  - Це величина функції Ейлера  . Таким чином,  , І остаточно отримуємо формулу:

Завдання про ферзів

int SIZE = 0;

int board [13] [13];

int results_count = 0;

void showBoard ()

{

for (int a = 0; a

{

for (int b = 0; b

{

std :: cout << ((board [a] [b])? "Q": ".");

}

std :: cout << '\ n';

}

}

bool tryQueen (int a, int b)

{

for (int i = 0; i

{

if (board [i] [b])

{

return false;

}

}

for (int i = 1; i <= a && b-i> = 0; ++ i)

{

if (board [a-i] [b-i])

{

return false;

}

}

for (int i = 1; i <= a && b + i

{

if (board [a-i] [b + i])

{

return false;

}

}

return true;

}

void setQueen (int a) {

if (a == SIZE)

{

results_count ++;

return;

}

for (int i = 0; i

{If (tryQueen (a, i))

{

board [a] [i] = 1;

setQueen (a + 1);

board [a] [i] = 0;

}

}

return;

}

int main ()

{

std :: cin >> SIZE;

setQueen (0);

std :: cout << results_count << std :: endl;

return 0;

}

36) Ханойські вежі

void hanoi_towers (int quantity, int from, int to, int buf_peg) {

 if (quantity! = 0)
{
 hanoi_towers (quantity-1, from, buf_peg, to);

cout << from << '' << to << endl;

hanoi_towers (quantity-1, buf_peg, to, from);
}
}

int main ()
{
 setlocale (LC_ALL, "rus");
 int start_peg = 1, destination_peg = 2, buffer_peg = 3, plate_quantity;
 cin >> plate_quantity;

hanoi_towers (plate_quantity, start_peg, destination_peg, buffer_peg);
 return 0;
}

 



числа Каталана | Принцип включень-виключень

Алгоритм пошуку компонент зв'язності в графі | Пошук точок зчленування | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Розширений Евклід | дискретного логарифмування | Теорема Піка. | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти |

© um.co.ua - учбові матеріали та реферати