АиСД-2 Экзамен — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Pankovamg (обсуждение | вклад) м |
Pankovamg (обсуждение | вклад) (Добавлены вопросы) |
||
| Строка 1: | Строка 1: | ||
| − | '''<big>Вопросы к | + | '''<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>''' | ||
=== Тема "Алгоритмы: классификация, сложность" === | === Тема "Алгоритмы: классификация, сложность" === | ||
Текущая версия на 19:38, 9 декабря 2025
Вопросы к письменной части экзамена по АиСД, 2 модуль
Содержание
- 1 Тема B "Теория чисел"
- 2 Тема "Алгоритмы: классификация, сложность"
- 3 Тема "Теория чисел"
- 4 Тема "Линейный поиск в массиве данных"
- 5 Тема "Структуры данных: множества, словари, стеки, деки, очереди"
- 6 Тема "Жадные алгоритмы"
- 7 Тема "Обработка событий"
- 8 Тема "Бинарный поиск"
- 9 Тема "Квадратичные сортировки"
- 10 Тема "Комбинаторные рекурсивные алгоритмы"
- 11 Тема "Рекурсивные сортировки: быстрая сортировка, сортировка слиянием"
- 12 Тема "Структура данных - куча. Пирамидальная сортировка"
- 13 Тема "Динамическое программирование"
Тема 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 модуль
