АиСД-2 Экзамен: различия между версиями
Перейти к навигации
Перейти к поиску
Pankovamg (обсуждение | вклад) мНет описания правки |
Pankovamg (обсуждение | вклад) Добавлены вопросы |
||
| Строка 1: | Строка 1: | ||
'''<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>''' | '''<big>Вопросы к устной части экзамена по АиСД, 2 модуль</big>''' | ||
=== Тема "Алгоритмы: классификация, сложность" === | === Тема "Алгоритмы: классификация, сложность" === | ||
Версия от 16:38, 9 декабря 2025
Вопросы к письменной части экзамена по АиСД, 2 модуль
Тема 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)
Вопросы к устной части экзамена по АиСД, 2 модуль