АиСД-2 Экзамен

Вопросы к письменной части экзамена по АиСД, 2 модуль

Тема B "Теория чисел"

Алгоритм Евклида

1. Какое минимальное количество шагов (делений с остатком) требуется алгоритму Евклида для вычисления НОД(34, 21)?
2. Напишите пропущенную строку в итеративной реализации алгоритма Евклида на Python:

   def gcd(a, b):
       while b != 0:
           pass
       return a

1. Напишите формулу нахождения НОК натуральных чисел a, b используя функцию нахождения НОД двух чисел - gcd(a, b).
2. Напишите оценку по времени в O нотации для алгоритма нахождения НОД для чисел a и b
3. Для решения задачи "Полоска бумаги имеет размеры A × B. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?" Использовали реализацию алгоритма Евклида с вычитанием. Напишите условие, которое позволит сократить решение задачи для тестов, где одно из входных чисел очень велико, а другое равно 1.

   n, m = map(int, input().split())
   k = 1

   else:
       while n != m:
           k += 1
           if n > m:
              n-= m
           else:
               m-= n
       print(k)

Вопросы к устной части экзамена по АиСД, 2 модуль