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

Педагогика и психология. Актуальные исследования 17 int sum_cifr(long int x) { int s = 0; while (x > 0) { s += x % 10; x /= 10; } return s; } В результате мы имеем дело с двумя вложенными циклами, каждый из ко- торых перебирает 1000 чисел. В соответствии со вложенностью циклов и логи- кой сравнения результатов получаем 1000000 итераций, по которым можно пе- ребрать все возможные номера билетов. Попробуем оптимизировать решение. Рассмотрим первую половину заданного шестизначного числа (если цифр в левой половине числа будет меньше трех, добавим левые нули). Сумма цифр любого трехзначного числа может принимать значения из от- резка [0, 27]. Количество чисел от 0 до 999 с определенной суммой цифр запишем в соответствующий элемент массива m, состоящего из 28 элементов (индекс эле- мента массива = сумме цифр числа). Вторая половина заданного числа также бу- дет трехзначным числом. Следовательно, мы можем использовать для второй по- ловины тот же массив данных. Количество «счастливых» билетов определяется следующим образом (и здесь в дело вступает Жадный алгоритм): luck=0; for (i=0; i<28; i++) luck+= m[i] * m[i]; где luck – количество счастливых билетов, m – массив значений суммы цифр. Количество операций в алгоритме уменьшено в 1000 раз! Далее студентам дается задание написать программу вычисления количе- ства счастливых билетов на основе алгоритма перебора всех возможных значе- ний суммы цифр первой и второй половины их номеров, провести тестирование и составить таблицу аргументов, результатов и времени выполнения про- граммы. Дальнейшее усиление эффективности алгоритма проходит при по- мощи жадного алгоритма, описанного выше. Студенты составляют модель дан- ных и программу, тестируют ее и определяют корректность работы на рассмот- ренных примерах. Дальнейшее продвижение в сторону усиления эффективности связано с ис- пользованием того факта, что суммы цифр чисел в пределах одного десятка из- меняются четко на единицу. Например: Число Сумма цифр числа 120 3 121 4 122 5 123 6