Просмотр исходного текста страницы АиСД-2 Экзамен

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

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

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

# Какое минимальное количество шагов (делений с остатком) требуется алгоритму Евклида для вычисления НОД(34, 21)?
# Напишите пропущенную строку в итеративной реализации алгоритма Евклида на Python:
    def gcd(a, b):
        while b != 0:
            pass
        return a
# Напишите формулу нахождения НОК натуральных чисел a, b используя функцию нахождения НОД двух чисел - gcd(a, b).
# Напишите оценку по времени в O нотации для алгоритма нахождения НОД для чисел a и b
# Для решения задачи "Полоска бумаги имеет размеры 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)


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

=== Тема "Алгоритмы: классификация, сложность" ===

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

=== Тема "Линейный поиск в массиве данных" ===

=== Тема "Структуры данных: множества, словари, стеки, деки, очереди" ===

=== Тема "Жадные алгоритмы" ===

=== Тема "Обработка событий" ===

=== Тема "Бинарный поиск" ===

=== Тема "Квадратичные сортировки" ===

=== Тема "Комбинаторные рекурсивные алгоритмы" ===

=== Тема "Рекурсивные сортировки: быстрая сортировка, сортировка слиянием" ===

=== Тема "Структура данных - куча. Пирамидальная сортировка" ===

=== Тема "Динамическое программирование" ===