Регистрация
ВладДвоичник2002
20.04.2022 00:42
Информатика
Есть ответ 👍

Женя учится на 8 и 9.он принципиально не получает другие оценки.любая последовательность его оценок состоит из этих двух цифр.интересно,сколько существует n-значных чисел, в десятичной записи которых присутствуют только цифры 8 и 9.

283
341
Посмотреть ответы 2

Ответы на вопрос:

SHiiimochka
SHiiimochka
4,5(42 оценок)
Тебе нужно ввести число 2 в степени n. но по условию (просто эта находится у нас в dots) это число может быть равно 25. а число 2 в 25 степени довольно большое. поэтому единственное что осталось написать - это алгоритм возведения n в квадрат (но длинной арифметикой).
Аля19251
Аля19251
4,7(33 оценок)

для нахождения НОДа не мало, не буду углубляться во всякие сложные алгоритмы, так как вряд ли Вы их проходите.

Сравним перебор и алгоритм Евклида, сразу можем сказать, что алгоритм Евклида в разы быстрее, так как при переборе мы тупо перебираем значения, то есть, данный алгоритм зависит от величины числа очень сильно. Конечно, алгоритм Евклида также зависит от введенного числа, однако, в нём будет намного меньше повторений, нежели в с перебором.

Можем глянуть немного статистики:

Генерируется 500 пар чисел

Перебор - 0.5022 с

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

Теперь мы точно можем сделать вывод, что алгоритм Евклида в разы быстрее простого перебора.

Популярно: Информатика