C# Computing Tools for Solving the Problem of Enumerating Partitions of a Rectangle
Абдулкарим Магомедович Магомедов, Serge Lawrencenko · HERALD of Dagestan State University · 2020
Рассматривается проблема перечисления всех разбиений прямоугольника заданных целочисленных размеров h×w на прямоугольники размеров 1×2, возникшая в 60-е годы XX в. при исследовании учеными-физиками вопросов термодинамики потоков жидкости.Выявление равносильности задаче перечисления всех совершенных паросочетаний в некотором планарном графе привлекло внимание к проблеме со стороны специалистов по дискретной математике.Несмотря на то, что исследованию задачи посвящены десятки работ, интерес к ней не ослабевает.Приведен краткий обзор известных подходов к решению задачи с анализом их недостатков, в частности «классическая» формула двойного произведения включает действия над числами с плавающей запятой (значения тригонометрических функций и др.), что существенно сужает диапазон значений h и w, для которых возможно точное вычисление искомого значения количества всех возможных разбиений.Указан способ вычисления коэффициентов рекуррентной формулы, использующей для нахождения a h (количества разбиений при фиксированном значении параметра w) лишь операции сложения и умножения целых чисел.Предложен двухшаговый подход к решению.На первом шаге с использованием классов BigInteger и BigFloat языка программирования C# выполняется трудоемкая работа по точному вычислению необходимого количества начальных членов последовательности a 1 , a 2 …, которые в свою очередь предоставляют возможность для вычисления целочисленных коэффициентов для формирования рекуррентной формулы.На втором шаге рекуррентная формула обеспечивает эффективное и точное вычисление последующих членов данной последовательности, используя лишь операции сложения и умножения целых чисел.В конце статьи сформулированы актуальные подзадачи рассматриваемой проблемы.Ключевые слова: