В. Рубанцев - Как решать комбинаторные задачи на компьютере (1127108), страница 7
Текст из файла (страница 7)
. .for (int i = 1; i <= nPart; ++i){int j = a[i];s += j.ToString();if (i != nPart) s += "+";}. . .}73Рис. 9.8. Красиво поделились!В книге Красиковых [КК07], на страницах 197-200 вы найдёте итерационную версию алгоритма, который генерирует все разбиения заданногочисла в антилексикографическом порядке, то есть как и у нас.
Он реализован на языке C++, так что можете сравнить его с нашим вариантом.Далее, на страницах 200-202 рассматривается алгоритм разбиения числана заданное количество частей.В книге [KS98], на страницах 67-68 представлен тот же самый рекурсивный алгоритм для генерации всех разбиений числа, что и в нашей программе. А дальше рассматриваются диаграммы Феррерса и алгоритмразбиения числа на заданное количество частей.Большие числа склонны давать огромное количество разбиений, а ведьиногда нам нужно просто узнать, сколько имеется тех или иных разбие-74ний, не генерируя их одно за другим.
В той же книге [KS98] на этот случайуже готов Алгоритм 3.5, который мы любезно позаимствуем для собственных нужд.В метод новой кнопки btnEnumPart Посчитать P(n,k)! мы записываем перевод алгоритма на Си-шарп:private void btnEnumPart_Click(object sender, EventArgs e){int n = (int)udNum.Value;adds = new int[n + 1];int k = (int)udK.Value;int[,] p = new int[n + 1, k + 1];enumPart(p, n, k);for (int i = 1; i <= n; ++i){string s = "";int pn=0;for (int j = 1; j <= k; ++j){pn += p[i, j];s += ("P("+i + "," + j + ")=" + p[i, j].ToString()+" ");}if (n==k)lstVar.Items.Add("P(" + i +") = " + pn);lstVar.Items.Add(s);}lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}void enumPart(int[,] p, int n, int k){p[0, 0] = 1;for (int i = 1; i <= n; ++i)p[i, 0] = 0;for (int i = 1; ifor (int j = 1;{if (i < 2 *p[i, j]elsep[i, j]}<= n; ++i)j <= Math.Min(i,k); ++j)j)= p[i - 1, j - 1];= p[i - 1, j - 1] + p[i-j, j];}Теперь нам не составит никакого труда удовлетворить своё любопытствобез лишних подробностей (Рис.
9.9).75Рис. 9.9. Статистика знает всё!Давайте ещё более сконцентрируем наш алгоритм, чтобы он выдавалтолько общее количество разбиений для заданного числа n, то есть P(n).Добавляем кнопку btnEnumPart2 Посчитать P(n)! и переводим Алгоритм3.6:private void btnEnumPart2_Click(object sender, EventArgs e){int n = (int)udNum.Value;int[] p = new int[n + 1];enumPart2(p, n);for (int i = 1; i <= n; ++i){lstVar.Items.Add("P(" + i + ") = " + p[i]);}lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;76}void enumPart2(int[] p, int n){int sign = 0;int sum = 0;int w = 0;int w2 = 0;int j = 0;p[0] = 1;p[1] = 1;for (int i = 2; i <= n; ++i){sign = 1;sum = 0;w = 1;j = 1;w2 = w + j;while (w <= i){if (sign==1)sum += p[i-w];elsesum -= p[i-w];if (w2 <= i){if (sign == 1)sum += p[i - w2];elsesum -= p[i - w2];}w += (3*j+1);++j;w2 = w + j;sign = 0-sign;} //whilep[i] = sum;} //for}Тут нужно отметить, что авторы книги [KS98] запутались в алгоритме инапечатали странную таблицу 3.1, в которой посчитаны не все значенияP(m,n), поэтому P(m), начиная с m=11, неверные.В главе Даёшь сотню! нам понадобятся композиции числа 9.
Если в разбиениях порядок слагаемых значения не имеет (обычно они записываются встандартной форме, но это непринципиально), то в композициях важен ипорядок слагаемых в записи. Это значит, что для каждого разбиения мы77должны составить и все перестановки слагаемых. Если k=1, то число разбиений равно числу композиций и равно единице, то есть и разбиение, икомпозиция равны самому числу n.Если k=2, то возможны варианты разбиений.
Если n, к примеру, равняетсяпяти, то мы имеем два разбиения:4132А композиций вдвое больше, поскольку числа в разбиениях можно переставить:41и1432и23Для k=3 число композиций утраивается по сравнению с разбиениями:311221311и131и113221и212и122Дальше можно не продолжать…Таким образом, мы можем дополнить алгоритм для генерирования разбиений кодом для перестановки слагаемых, но лучше использовать болеепростой алгоритм, который оба действия выполняет одновременно.В книге Handbook of Applied Algorithms, на странице 12 приведён красивыйкороткий алгоритм на этот счёт. Одна беда – он не работает.Обратимся к книге Algorithms for Programmers: Ideas and Source Code, где вглаве 7 мы найдём «классное» решение нашей проблемы. Код несколькотяжеловат, но зато универсален: позволяет генерировать композиции невсе разом, а по числу групп, причём в прямом (лексикографическом) и обратном (антилексикографическом) порядке.Переводим код с языка C++ на C# и добавляем новый класс в нашу библиотеку:public class Compositions{int N;int K;int[] p;78int nk1; //= N-K+1//КОНСТРУКТОРpublic Compositions(int n, int k){N = n;K = k;nk1 = N - K + 1;//nk1 >= 1 !!!p = new int[K+1];first();}public void first(){p[0] = nk1;p[K] = 0;for (int i = 1; i < K; ++i)p[i] = 1;}public void last(){for (int i = 0; i < K; ++i)p[i] = 1;p[K-1] = nk1;}public int next(){int i = 0;//ищем первое слагаемое, большее 1:while (p[i] == 1) ++i;//текущая композиция - последняя:if (i == K) return K;int v = p[i];p[i] = 1;p[0] = v-1;++i;++p[i];return i;}public int prev(){int v = p[0];//текущая композиция - первая:if (v == nk1) return K;p[0] = 1;int i = 1;//ищем первое слагаемое, большее 1:while (p[i] == 1) ++i;--p[i];79p[i-1] = v+1;return i;}public int[] data(){return p;}}Устанавливаем кнопку btnComposition Композиции! и запускаем генераторна полную мощность:private void btnComposition_Click(object sender, EventArgs e){int n = (int)udNum.Value;int k = (int)udK.Value;if (n < k) MessageBox.Show("Число меньше слагаемых!", "Разбиения");//выводим в антилексикографическом порядке:bool rq = false;//выводим в лексикографическом порядке://bool rq = true;Compositions P = new Compositions(n, k);if (rq) P.last();else P.first();nVar = 0;//только считаем://if (rq)//do//{//++nVar;//} while (P.prev() != k);//else//do//{//++nVar;//} while (P.next() != k);//генерируем композиции:int[] p = P.data();int q = k - 1;do{++nVar;//печатаем композицию:string s = "";for (int i = 0; i < k; ++i){s += (p[i] + " ");}lstVar.Items.Add(s);80if (rq) q = P.prev();else q = P.next();} while (q != k);lstVar.Items.Add("Всего композиций " + nVar);lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}Если вы раскомментируете строки после //только считаем:, то можете закомментировать генерирование композиций и получить только числокомпозиций.
Порядком вывода слагаемых управляет логическая переменная rq.Ну и для уравновешивания кнопок на форме поставим ещё одну btnComp100 Композиции 100!. В её метод клика впишем облегчённую версию алгоритма, который используется в последней главе:private void btnComp100_Click(object sender, EventArgs e){int n = (int)udNum.Value;int k = (int)udK.Value;if (n < k) MessageBox.Show("Число меньше слагаемых!", "Разбиения");nVar = 0;//массив с числами композиции:int[] c= new int[n + 1];//формируем начальную композицию:c[1] = n - k + 1;for (int j = 2; j <= k; ++j)c[j] = 1;//генерируем остальные композиции:writeC(c, k);compC(c, 1, k);lstVar.Items.Add("Всего композиций " + nVar);lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}void compC(int[] a, int n, int nGr){//для первой композиции:if (nGr == 1) return;int[] L = (int[])a.Clone();while (L[n] > 1){--L[n];++L[n + 1];writeC(L, nGr);if (n + 1 < nGr){compC(L, n + 1, nGr);81}}}//ПЕЧАТАЕМ ОЧЕРЕДНУЮ КОМПОЗИЦИЮvoid writeC(int[] a, int n){++nVar;string s = "";for (int i = 1; i <= n; ++i)s += (a[i] + " ");lstVar.Items.Add(s);}Сравнительные испытания обоих алгоритмов показывают их полное согласие с комбинаторной теорией (Рис.
9.10).Рис. 9.10. Числовой композитор в действии!82Примерный вид интерфейса приложенияИсходный код программы находится в папке Разбиения.831. Как мы знаем, наборы монет (или других объектов) могут бытьразными, однако пользователи нашей программы лишены возможности задавать наборы, отличные от тех, что уже «зашиты» вкоде программы. Добавьте компонент TextBox, чтобы пользователимогли передавать в приложение собственные наборы монет.2.
В книге А.М. и И.М. Ягломов Неэлементарные задачи в элементарном изложении есть ряд задач по размену денег и разбиениючисел.Решите их помощью нашей программы и сравните затраты труда слогическими решениями авторов книги!19. Сколькими способами можно разменять 20 копеек на монетыдостоинством 5 копеек, 2 копейки и 1 копейка.20. Сколькими способами можно составить n копеек из монет достоинством 2 копейки и 1 копейка.21**.
Сколькими способами можно составить n копеек из монет:а) достоинством 1 копейка, 2 копейки и 3 копейки?б) достоинством 1 копейка, 2 копейки и 5 копеек?21**. Сколькими способами можно составить рубль из монет достоинством в 1, 2, 5, 10, 20 и 50 копеек?22. Сколькими способами можно представить число n в виде суммы двух целых положительных слагаемых, если представления,отличающиеся лишь порядком слагаемых, считать одинаковыми?Конечно, решение задач с неопределенной суммой в n копеек потребует и размышлений, а не только нажимания кнопки.3. Двойные кружкиРешите такую задачу (Рис.
9.15). Впишите в кружки, расположенныена окружности, 9 чисел, сумма которых равна 100. В те кружки, чтонаходятся снаружи, следует записывать те же числа, что и в соприкасающихся с ними кружках (то есть каждое число используется вожерелье дважды).84Теперь составьте из любых пар чисел натуральный ряд последовательных чисел максимальной длины, начинающийся с единицы.Например, при таком заполнении бусин числами мы получим ряд,очень близкий к рекордному (Рис.
9.16).Рис. 9.15. Двойное ожерельеРис. 9.16. Почти рекордный результатОн состоит из 37 чисел: 1, 2 (1+1), 3, 4, 5 (4+1), 6 (3 + 3), 7 (4 +3), 8 (4+4), 9, 10 (9 +1), …, 35 (18 + 17), 36 (18+18), 37 (22+15).85А самая длинная последовательность включает 40 чисел, причёмзадача имеет единственное решение (Рис. 9.17).Рис. 9.17. А вот и рекорд!Исходный код программы находится в папке Двойные кружки.86ОтветыСловесные магические квадраты87Литература[РВ13]Рубанцев ВалерийТотальный тренинг по Сишарпу. Большой практикум попрограммированию на языке C#RVGames, 2013.
– 615 с.[KS98]Kreher D.L., Stinson D.R.Combinatorial Algorithms: Generation, Enumeration, and SearchCRC, 1998.- 344 c.ISBN: 084933988X88[WM99]Weiss M.A.Data Structures and Problem Solving Using C++Pearson Education, 1999. – 976 с.ISBN 0321205006[ГМ72]Гарднер МартинМатематические досугиМ.:Мир, 1972. – 495 с.[ГМ90]Гарднер МартинПутешествие во времениМ.:Мир, 1990. – 341 с.ISBN: 5-03-001166-889[ГМ10]Гарднер Мартин1000 развивающих головоломок, математических загадок иребусов для детей и взрослыхACT, Астрель, 2010.
– 287 с.ISBN 978-5-17-059779-6ISBN 978-5-271-24093-5[КД43]Дональд Эрвин КнутИскусство программирования,том 4, выпуск 3. Генерация всехсочетаний и разбиений.Вильямc, 2007. – 208 с.ISBN: 978-5-8459-1132-2[КД44]Дональд Эрвин КнутИскусство программирования,том 4, выпуск 4.
Генерация всехдеревьев. История комбинаторной генерацииВильямc, 2007. – 160 с.ISBN: 978-5-8459-1158-290[КК07]Красиков И. В., Красикова И. Е.АлгоритмыЭксмо, 2007.- 256 с.ISBN: 978-5-699-21047-3Серия: Просто как дважды два[ЛВ88]Липский В.Комбинаторика для программистовМосква: Мир, 1988. – 200 с.91[МФ06]Меньшиков ФёдорОлимпиадные задачи по программированиюПитер, СПб, 2006.
– 315 с.ISBN: 5-469-00765-09293.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
