Задача. Получить все перестановки элементов 1, …, 6.
Решение
Все перестановки считаются и выводятся с помощью рекурсивной функции perestanovka().
Когда в ней складывается новый набор элементов, проверяем что бы в нем не было повторяющихся значений (считаем факториал и сумму, они должны совпадать со стандартом (6! = 720, 1+2+3+4+5+6 = 21) и тогда выводим.
Что бы убедиться, что выведено правильное количество перестановок, выводим в конце значение счетчика cnt (находится внутри функции perestanovka()) и требуемое значение перестановок ( 6! = 720). Эти значения совпадают.
|
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 |
#include <iostream> #include <stdio.h> using namespace std; const int n = 6; int cnt = 0; int a[n]; int ft, sum; unsigned int fact(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n * fact(n - 1); } unsigned int summa(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n + summa(n - 1); } void perestanovka(int k) { int pr, sm; for ( a[k] = 1; a[k] <= n; a[k]++) { if ( k == n-1) { pr = 1; sm = 0; for ( int i = 0; i < n; i++) { pr = pr*a[i]; sm += a[i]; } if ( (ft == pr) && (sum == sm) ){ for ( int i = 0; i < n; i++) cout << a[i]; cout << endl ; cnt++; } } else perestanovka(k+1); } return; } int main() { ft = fact(n); sum = summa(n); perestanovka(0); cout << endl << cnt << "/" << fact(n) << endl; } |
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class a1031 { static int n; static int cnt ; // Количество возможных перестановок static int a[]; // Массив чисел с которыми делаются перестановки static void transposition(int k) { boolean flag ; boolean b[] = new boolean[n]; // Массив индикаторов повторов // Для элемента k перебираются все числа for ( a[k] = 1; a[k] <= n; a[k]++) { if ( k == n-1) { //Если элемент последний flag = false; for ( int i = 0; i < n; i++) b[i] = false; // Массиву индикаторов повторов присваивается False for ( int i = 0; i < n; i++) { if ( b[a[i]-1] == true ) { // Проверка на повторы flag= true ; // Если повтор то флаг = true break; } else b[a[i]-1] = true; } if ( flag == false ) { // если повторов не было то печать for ( int i = 0; i < n; i++) System.out.print(a[i]); System.out.println(); cnt++; } } else transposition(k+1); // если не последний элемент то перебирается для следующего k } return; } public static void main(String[] args) { n = 6; cnt = 0; a = new int[n]; transposition(0); System.out.println(cnt); } } |
Зачтено, конечно.
Я побаивался, что Вы просто используете стандартную функцию генерации перестановок, которую мы учили в прошлом семестре.
— «perestanovka» категорически против использования транслитерации русских слов в именах. Представьте, что Вам достался код написанный индийцев. Каково Вам будет разбираться с его транслитерациями?
— Мы уже не на первом курсе и понимаем, нужно поменять подход. Что это за рекурсивное вычисление суммы арифметической прогрессии? Найдите способ не вычисляя факториала.
Нет ссылки на Online IDE, 5 баллов.