Исправлены упражнения на алгоритмические структуры

Следующие исправленные упражнения относятся к алгоритмическим структурам, структурам управления и структурам данных. Цель состоит в том, чтобы предложить структуры, наиболее подходящие для утверждения.

алгоритмические структуры

Упражнение 1

Этот метод умножения, используемый в Древнем Египте, не требует знания всех таблиц умножения до 10, а требует только сложения и умножения на 2.

Вот, например, умножение 13 на 78. Сначала нужно написать таблицу степеней 2, меньших или равных 13. Затем написать таблицу удвоений числа 78.

Египетский алгоритм умножения

Затем вы должны отметить наибольшую степень двойки, разбивая число 13 (то есть двоичный бит равен 1). Другими словами, отметьте степени двойки, введя двоичное преобразование числа 13 = 1101.

Египетский алгоритм умножения

Сумма 78+312+624=1014.

a – Рассчитайте произведение по вашему выбору, используя алгоритм египетского деления. 

б – Легче ли вычислить произведение 78 на 13? Почему ?

c – Напишите египетский алгоритм умножения (согласно вашему ответу b!). Постарайтесь оптимизировать его как можно лучше!

Проще всего выбрать наименьшее число для степени двойки и, следовательно, наибольшее число, которое нужно удвоить. Действительно, количество итераций равно тому, сколько раз надо умножить 2 само на себя, чтобы получить больше, чем число минус одна итерация (мы оставляем только то, что строго меньше. Таким образом, у нас будет число d итераций n таких что 2нет > а (описанное число). Мы делаем вывод, что n>log2(а) отсюда процент, что а является наименьшим.

Сначала вспомним двоичное преобразование десятичного числа.

Египетский алгоритм умножения

Вот идея алгоритма: вы можете написать его менее формально, потому что алгоритм также включает десятичное преобразование в двоичное, здесь алгоритм очень хорошо продуман и оптимизирован 🙂

структура алгоритма египетского умножения

Упражнение 2

а - напишите алгоритм чьи параметры являются тремя действительными переменными и который циклически переставляет их значения. 

б – Напишите алгоритм, параметрами которого являются три действительные переменные, и который возвращает максимальное значение среди этих трех значений. 

c – Напишите алгоритм, допускающий значения двух переменных без использования дополнительной переменной.

d — Напишите алгоритм, который возвращает true, если два целых числа a и b имеют одинаковый знак, иначе false.

имеет - Переменные a, b и c являются переменными, определенными вне алгоритма. Эти значения изменяются, даже если ничего не возвращается. Обратите внимание на порядок ваших действий!

алгоритм перестановки

Вы также можете сделать это, не используя дополнительную переменную. В этом случае мы будем иметь в начале (a,b,c). Например, a и b меняются местами с помощью следующих операций:

а ← а + б

б ← а–б

а ← а–б

Таким образом, у нас есть тройка значений (b, a, c). Осталось поменять местами a и c, чтобы получить утроенные (b,c,a).

Или вы также можете поменять местами три значения, используя серию вычислений.

а ← а + б + в;

в ← а–б–в;

б ← а–б–в;

а ← а–б–в;

б- Здесь алгоритм должен возвращать значение, поэтому есть входы и выходы. Есть много способов сделать что-то, вам решать, как найти варианты (например, с несколькими условиями в ветке).

максимальный алгоритм

Идея заключалась бы в том, чтобы вернуть максимум без использования дополнительных переменных.

алгоритм максимум с тремя переменными

Там тоже не очень красиво, поэтому попробуем вернуть максимум только один раз, не используя новые переменные. Мы переставим значения, чтобы сохранить максимум в x (будьте осторожны, в зависимости от языков вы можете оказать реальное влияние на значения в xy и z, поэтому используйте с осторожностью!)

максимально оптимизированный алгоритм

против- Мы просто делали это несколько раз… для тех, кто не следил.

алгоритм перестановки

д- Мы собираемся подумать о хорошо оптимизированном алгоритме, чтобы избежать большого количества ветвлений. Произведение двух целых чисел с одинаковым знаком будет положительным!

идентичный знаковый алгоритм

Упражнение 3

Копировальный центр берет 2 евро за первые десять фотокопий, 1,50 евро за следующие двадцать и 1 евро за последующие. Напишите алгоритм, который запрашивает у пользователя количество сделанных фотокопий, а затем отображает соответствующее количество.

алгоритм счета

Можно расположить ветви последовательно, но это менее эффективно с точки зрения времени расчета.

Упражнение 4

Напишите алгоритм для отображения времени года, введя номер месяца.

Упражнение 5

Напишите алгоритм для решения каждой из следующих задач: (попробуйте с разными управляющими структурами FOR, WHILE, DO… WHILE и т. д.).

1- Расчет суммы первых N целых чисел. 

2- Нахождение минимума и максимума в наборе N чисел. 

3- Вычисление частного и остатка от деления двух целых чисел А и В без использования операции деления. 

4- Расчет произведения двух целых чисел с использованием только операции сложения «+». 

5- Определение, делится ли A на B. С положительными целыми числами A и B. 

6- Определите все делители данного целого числа X. 

7- Определите, является ли целое число X простым или нет. 

8- Вычислите сумму цифр, составляющих натуральное число N.

Делиться
ru_RURU
%d такие блоггеры, как: