TUZ_2-13 Достижение стабильного состояния в болгарском пасьянсе
2.13 Достижение стабильного состояния в болгарском пасьянсе
В этой задаче дается список из n карт, представленных положительными целыми числами.
Цель состоит в том, чтобы продолжать генерировать новые списки чисел, отличающиеся от исходного,
пока не будет достигнуто стабильное состояние. Под стабильным состоянием понимается ситуация,
когда новый список содержит те же элементы, что и предыдущий список, но сами элементы могут быть упорядочены иначе.
При генерировании новых списков применяются два правила:
1) сумма чисел в списке должна быть равна треугольному числу (треугольные числа определяются согласно формуле 2.6);
\(\frac{k\times(k+1)}{2};\ \ \ \ \ \ \ \ \ \ \ \ (2.6)\)
2) при создании нового списка на каждом этапе из всех чисел вычитается одна единица, а последним элементом списка становится длина предыдущего списка. Если результат вычитания равен нулю, он удаляется.
Этот процесс повторяется до тех пор, пока не будет достигнуто стабильное состояние.
Таким образом задача требует найти список, удовлетворяющий обоим условиям.
Этот процесс называется болгарским пасьянсом.
Например, подсчитаем количество шагов для достижения стабильного состояния для [3] – заданного списка чисел и k = 2.
- Сначала необходимо проверить, равно ли треугольное число сумме элементов данного списка: k × (k + 1)/2 → 2 × (2 + 1)/2 = 3, т. е. 3 = 3.
- Следующие шаги показывают, как достигается стабильное состояние: [3] → [2, 1] → [1, 2, 0] → [1, 2].
- Поскольку элементы [2, 1] и [1, 2] равны, можно считать, что стабильное состояние достигнуто,
даже притом что элементы в списках [2,1] и [1, 2] упорядочены по-разному.
Поэтому стабильное состояние достигается уже после одного шага.
Ваша задача: написать функцию, которая принимает список из n положительных целых чисел и треугольное число
и возвращает количество шагов, необходимых для достижения стабильного состояния.
В табл. 2.13 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.13. Некоторые ожидаемые результаты для задачи подсчета шагов, необходимых для достижения стабильного состояния |
| Points, k |
Ожидаемый результат |
3
2 |
1 |
3, 7, 8, 14
4 |
0 |
10, 10, 10, 10, 10, 5
10 |
74 |
3000, 2050
100 |
7325 |