107
правок
Изменения
→Специализация алгоритма для генерации предыдущего разбиения на слагаемые
<tex> 1) </tex> Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на 1, так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.
<tex> 2) </tex> Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое точно больше предыдущего на 1. Обозначим его номер за <tex>j</tex>. Тогда <tex> a[j] = a[j] - 1 </tex>, а <tex> a[j + 1] = 1 + \sum_{i = j + 1}^n a[i] </tex>. Причем <tex> a[j + 1] </tex> последнее слагаемое в разбиении.
Первое слагаемое находится под индексом 1.
'''list<int>''' prevPartition('''list<int>''' ba):
a[0] = 0
'''if''' a[a.size] / 2 >= a[a.size - 1]
sum +=a[i]
a.pop_back();
Пример:
Случай 1.
[[Файл:Prevpart1.png|600px|left|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]
Случай 2.
[[Файл:Prevpart2.png|600px|left|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]
== Специализация алгоритма для генерации предыдущего разбиения на множества ==
