Guest User

Anal'nie shariki

a guest
Dec 14th, 2019
160
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. void Perestanovka(int *a, int i, int j) { // данная функция меняет значения двух элементов
  6. int buff = a[i];
  7. a[i] = a[j];
  8. a[j] = buff;
  9. }
  10.  
  11. bool Step(int *a, int n) { // данная функция генерирует комбинации и возвращает булево значение (false - если комбинаций не осталось, true - наоборот)
  12. int j = n - 2;
  13. while ((j != -1) && (a[j] > a[j + 1])) {
  14. j--;
  15. }
  16. if (j == -1) {
  17. return false;
  18. }
  19. int k = n - 1;
  20. while (a[j] >= a[k]) {
  21. k--;
  22. }
  23. Perestanovka(a, j, k); // устанавливают два элемента в порядке убывания (строки 12-23)
  24. int l = j + 1, r = n - 1;
  25. while (l < r) {
  26. Perestanovka(a, l++, r--);
  27. } // устанавливают все элементы, находящиеся справа от изменненных выше в порядке возрастания (строки 24-28)
  28. return true;
  29. }
  30.  
  31. void VivodKomb(int *a, int n) { // данная функция выводит соответствующую условию перестановку
  32. static int st = 1; // порядковый номер комбинации, которая соответствует условию задачи
  33. int i = 0;
  34. while ( i <= n) {
  35. if (i+1 == a[i]) { // если найден элемент номер которого соответствует его значению, то комбинация выводится на экран и функция завершает свою работу
  36. cout << st++ << ": ";
  37. for (int i = 0; i < n; i++) {
  38. cout << a[i] << " ";
  39. }
  40. cout << endl;
  41. break;
  42. }
  43. else {
  44. i++;
  45. }
  46. }
  47. }
  48. int main()
  49. {
  50. setlocale(LC_ALL, "");
  51. int n, i;
  52. cout << "Введите количество шариков:\n";
  53. cin >> n;
  54. int *a = new int[n]; // создаем динамический массив;
  55.  
  56. for (i = 0; i < n; i++) {
  57. a[i] = i+1;
  58. }
  59. cout << "Комбинации соответствующие условию задачи:\n";
  60. VivodKomb(a, n); // Выводим самую первую комбинацию, так как она в любом случае соответствует условию
  61. while (Step(a, n)) {
  62. VivodKomb(a, n);
  63. }
  64. return 0;
  65. }
RAW Paste Data