Найти НОД с наибольшей суммой цифр - Turbo Pascal
Формулировка задачи:
Думаю условие понятное, можно только пояснить на примере.
НОД чисел 220 и 440 это 220, а с наибольшей суммой цифр 55.
и еще (1<=a,b<=10^9)
Достаточно будет алгоритма, думаю с кодом проблем особых не будет.
Решение задачи: «Найти НОД с наибольшей суммой цифр»
textual
Листинг программы
function gcd(const a, b: LongInt): LongInt; begin if b = 0 then gcd := a else gcd := gcd(b, a mod b); end; function sum_dig(num: LongInt): LongInt; var sum: LongInt; begin sum := 0; while num > 0 do begin sum := sum + num mod 10; num := num div 10; end; sum_dig := sum; end; var a, b, g, i, ans, max_sum, sum: LongInt; begin Readln(a, b); max_sum := 0; g := gcd(a, b); for i := 1 to Round(sqrt(g)) do if g mod i = 0 then begin sum := sum_dig(i); if sum > max_sum then begin max_sum := sum; ans := i; end; sum := sum_dig(g div i); if sum > max_sum then begin max_sum := sum; ans := g div i; end; end; Writeln(ans); end.
Объяснение кода листинга программы
- Создается функция
gcd
, которая принимает два аргумента типаLongInt
и возвращает наибольший общий делитель этих двух чисел. Алгоритм Евклида используется для нахождения НОДа. - Создается функция
sum_dig
, которая принимает один аргумент типаLongInt
и возвращает сумму цифр этого числа. Функция использует циклwhile
для сложения цифр числа последовательно. - Создается переменная
a
иb
для хранения введенных пользователем чисел. - Вызывается функция
gcd
с аргументамиa
иb
и сохраняется результат в переменнойg
. - Инициализируется переменная
max_sum
значением 0. - Запускается цикл
for
, который выполняется от 1 до округленного значения квадратного корня изg
. - В каждой итерации цикла проверяется, делится ли
g
на текущее значениеi
без остатка. Если да, то вызывается функцияsum_dig
с аргументомi
, и если сумма цифр большеmax_sum
, то обновляется значениеmax_sum
иans
устанавливается равнымi
. - После завершения цикла, значение
max_sum
будет содержать наибольший общий делитель, а значениеans
будет содержать соответствующий делитель. - Выводится значение
ans
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д