Университет XXI века: научное измерение

«Университет XXI века: научное измерение» – 2024 18 Число Сумма цифр числа 124 7 125 8 126 9 127 10 128 11 129 12 Использование данного факта даст возможность в каждом десятке чисел вы- числять сумму цифр только для первого числа, а дальше только наращивать сумму (Усиление 1), что существенным образом уменьшит количество операций на всем пространстве чисел. Еще одно направление усиления эффективности (Усиление 2) связано с тем, что просмотр значений массива с количеством чисел, имеющих оди- наковую сумму цифр, позволил увидеть, что в массиве совпадают значения элемен- тов, равноудаленных от его концов. Студентам дается задание установить значи- мость влияния данного факта на алгоритм и программу на основе тестирования на тех же наборах данных. Анализ результатов работы программ, написанных по каж- дому из этих алгоритмов, позволил убедиться в усилении их эффективности. k Результат Время выполнения программы Алгоритм полного перебора Жадный алгоритм Усиление 1 Усиление 2 2 9 0.003 0.001 0.001 0.001 4 669 0.007 0.001 0.001 0.001 6 55251 0.014 0.001 0.001 0.001 8 4816029 1.257 0.002 0.001 0.002 10 432457639 157.233994 0.004 0.001 0.002 12 39581170419 (результат без полного перебора) > 30 мин 0.029 0.018 0.007 14 3671331273479 (результат без полного перебора) > 1.5 часа 0.316 0.048 0.043 16 343900019857309 (результат без полного перебора) > 8 часов 4.114 0.73 0.577 Как видим, на малых значениях аргумента расхождение во времени работы алгоритмов незначительно, однако, с ростом значения k время работы алгорит- мов существенно меняется. Данная задача, на первый взгляд, кажется очень простой, но она довольно убедительно направляет мысли студентов в сторону необходимости построения таких математических моделей в предлагаемых задачах, которые позволят напи- сать максимально эффективную программу и с точки зрения модели данных, и с точки зрения количества операций, и, как следствие, времени работы.