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

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

При решении задач на алгоритмы немаловажным является умение использовать язык блок-схем. Процесс решения одной и той же задачи можно реализовать посредством применения алгоритмов разных классов, поэтому результат может отличаться и по времени счета, и по объему вычислений, и по сложности. Записывая алгоритмическую последовательность с помощью составления блок-схем, вы сможете сравнить решения, выбрав самый лучший algorithm. Также появляется возможность упростить способ решения, найти и устранить ошибку.

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

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

В решении задачи на алгоритмы выделяют ряд этапов:

1. Математическое описание.
2. Определение входных/выходных данных.
3. Разработка алгоритма по решению поставленной задачи.

Алгоритмические конструкции базовых классов

В теории программирования считают, что для того, чтобы составить запись любого, даже самого сложного алгори тма, хватит  3-х базовых структур. Речь идет о следующих алгоритмах:

• линейного класса;
• ветвления (речь идет о разветвляющихся алгоритмах);
• циклического класса.

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

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

В качестве примера возьмем задание с разработкой алгоритма по вычислению гипотенузы прямоугольного треугольника, зная длины катетов a и b. Вспоминаем вышеописанные этапы разработки:

1. Математическое описание.

Математически задача решается по следующей формуле:

Здесь c является длиной гипотенузы, a, b – длинами катетов.

2. Определяем входные/выходные данные.

Входные данные — значения катетов a и b. Выходные — длина гипотенузы c.

3. Разработка алгоритма.

Алгоритмы ветвления

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

Для примера возьмем задание, постановка которого связана с разработкой алгоритма по вычислению наибольшего числа из 2-х чисел: x и y.

1. Математическое описание.

Из первых классов математики мы знаем, что когда x > y, то x больше y и наоборот, что является очевидными вещами. И если x = y, то числа равны.

2. Определяем входные/выходные данные.

Входные данные — это значения x и y. Выходными данными являются:

• самое большое число;
• любое из чисел в том случае, если они равны.

Таким образом, чтобы решить эту задачу на алгоритмы, надо знать значения переменных x и y.

3. Разработка.

В вышеуказанной схеме цифрами отмечены номера алгоритмических элементов, соответствующие номерам шагов словесного описания. Здесь есть 3 ветви решения:

• 1, 2, 3, 4, 8;
• 1, 2, 3, 5, 6, 8;
• 1, 2, 3, 5, 7, 8.

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

В алгоритмах циклического класса некоторая часть действий из задания повторяется до тех пор, пока не нарушится заранее определенное условие. Выполнение условия проверяется в начале. Совокупность операций, которые выполняются многократно, — это тело цикла.

В алгоритмических последовательностях этого класса выделяют ряд понятий:

• параметр цикла (с изменением этой величины связано многократное выполнение цикла);
• начальное и конечное значения циклических параметров;
• шаг цикла (речь идет о значении, на которое меняется параметр при каждом повторе).

Работу циклов организуют по специальным правилам. Алгоритмическая последовательность циклического класса включает в себя и подготовку, и тело, и условия продолжения работы.

В подготовку входят действия, которые связаны с заданием исходных значений:

• начальные значения;
• конечные значения;
• шаг.

В тело цикла входят:

• многократно повторяющиеся операции по вычислению искомых величин;
• подготовка последующего значения параметра;
• подготовка иных значений, нужных для повторного выполнения действий непосредственно в теле.

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

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

1. Математическое описание.

Сначала следует обозначить сумму натуральных чисел буквой S. В результате формулу вычисления суммы чисел от 1 до 100 можно записать следующим образом:

Здесь Xi является натуральным числом X c номером i. Этот номер меняется от 1 до n. А n=100 обозначает общее кол-во натуральных чисел.

2. Определяем входные/выходные данные.

Входные данные — это натуральные числа: 1, 2, 3, …, 99, 100.

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

Относительно параметра цикла — речь идет о величине, определяющей число циклических повторений. В нашем задании i представляет собой номер натурального числа.

Подготовка цикла — задание начального и конечного значений циклического параметра. Тут надо пояснить следующее:

• начальное значение циклического параметра равняется единице,
• конечное значение — n,
• шаг равен 1.

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

Тело цикла. В теле станут выполняться как накопление значения суммы, так и вычисление последующего значения циклического параметра по формулам ниже:

• S=S+i;             
• I=I+1.

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

3. Разработка.

Вводим следующие обозначения: S – это сумма последовательности, i – это значение натурального числа.

Начальное циклическое значение i=1, конечное — i =100, шаг равен 1.

По материалам: https://www.turbopro.ru/index.php/osnovy-programmirovaniya/6836-algoritmy-razrabotka-algoritma-resheniya-zadachi.

Решение задач с использованием алгоритма бинарного поиска

Алгоритм бинарного (или двоичного) поиска — это один из базовых алгоритмов, который часто применяется при решении алгоритмических задач. На LeetCode на момент написания этой статьи порядка 190 задач в решении которых он используется (можно посмотреть здесь: https://leetcode.com/tag/binary-search/). Бинарный поиск разбирается во множестве статей, его идея достаточно несложная и интуитивно понятная. Однако алгоритм имеет некоторое количество «подводных камней». В этой заметке я хотел бы показать решение одной из задач с его помощью.

Для начала несколько слов о самом алгоритме. Задача, которую он решает, может быть сформулирована следующим образом: «найти в отсортированном массиве индекс элемента, значение которого соответствует заданному». Обычно массив отсортирован по возрастанию и в данной заметке мы будем предполагать, что это так и есть.

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

Сложность алгоритма бинарного поиска по времени выполнения O(logN) (так как мы уменьшаем срез массива на 2 на каждой итерации и проверяем только 1 элемент), и O(1) по памяти. Что касается реализации алгоритма, то обычно она выглядит следующим образом:

left, right = 0, len(array)-1
while left <= right do
	middle = (left + right) / 2
  if array[middle] > target then
  	right = middle - 1 // дальше будем проверять левую часть массива
  else if array[middle] < target then
  	left = middle + 1 // дальше будем проверять правую часть массива
  else
  	return middle // нашли элемент
  end if
end while
return -1 // элемента нет в массиве

Код на Golang можете посмотреть здесь. Есть тесты, которые включают часть corner cases. На эти случаи стоит обратить внимание и, возможно, почитать про них, например на stackoverflow (найти их описание сейчас не составляет проблем, есть много материалов как на английском, так и на русском языках).

Давайте перейдем к решению задачки с LeetCode. Возьмем для примера задачу Find Target Indices After Sorting Array. Она довольно простая, уровня easy, что позволит нам сосредоточится на одном алгоритме, а точнее его небольшой модификации. Если кратко, то суть задачи состоит в том, что нам необходимо в отсортированном массиве найти индексы всех элементов, значения которых соответствуют заданному. Есть еще одно дополнительное условие: необходимо вернуть их в порядке возрастания значений элементов массива (то есть надо сначала массив отсортировать). Таким образом, очень похоже, что нам подойдет алгоритм бинарного поиска, однако он позволяет найти индекс только одного из элементов.

Важное замечание: приведенное здесь решение задачи не является оптимальным. Оно взято просто как удобный пример. Оптимальное решение за O(N) вы можете посмотреть в этом комментарии или здесь. Далее мы говорим о сложности после сортировки, которая сама по себе O(NlogN).

Наиболее простым способом для нас будет нахождение элемента (любого) с заданным значением, затем распространение вправо и влево от него, пока значение не станет отличным с обеих сторон или мы не достигнем конца и начала массива. Однако, такой подход может привести к O(N) сложности по времени, тогда как бинарный поиск имеет сложность O(logN). Здесь может быть полезным модификация бинарного поиска, которая вернет наиболее левый элемент массива с искомым значением. Реализация алгоритма выглядит так (код на Golang можете посмотреть здесь, тесты здесь):

left, right = 0, len(array)
while left < right do
	middle = (left + right) / 2
  if array[middle] < target then
  	left = middle + 1 // дальше будем проверять правую часть массива
  else
  	right = middle // дальше будем проверять левую часть массива
  end if
end while
return left

Отлично, теперь мы сможем найти первый индекс в массиве и просто добавить все элементы начиная от него и пока не встретится элемент с отличным значением. Алгоритм будет выглядеть следующим образом (код на Golang здесь, тесты здесь):

sort(array) // сортируем массив по возрастанию ( обычно за O(NlogN) )

// бинарный поиск наиболее левого элемента
left, right = 0, len(array)
while left < right do
	middle = (left + right) / 2
  if array[middle] < target then
  	left = middle + 1 // дальше будем проверять правую часть массива
  else
  	right = middle // дальше будем проверять левую часть массива
  end if
end while

// собираем индексы элементов в результирующий массив
result = []
while left < length(array) and array[left] == target do
	append(result, left)
  left = left + 1
end while

Казалось бы, что все неплохо, но мы все еще можем получить сложность по времени O(N) в том случае, если все элементы массива содержат искомое значение. И, что может быть менее очевидным, мы можем потерять скорость на многократном выделении памяти и копировании при append.

Дальнейшим развитием решения может быть поиск индекса наиболее правого элемента массива с искомым значением. Это еще одна небольшая модификация бинарного поиска. Вот так выглядит сам алгоритм (код на Golang здесь, тесты здесь):

left, right = 0, len(array)
while left < right do
	middle = (left + right) / 2
  if array[middle] > target then
  	right = middle // дальше будем проверять левую часть массива
  else
  	left = middle + 1 // дальше будем проверять правую часть массива
  end if
end while
return right

Теперь мы можем найти оба (самый левый и самый правый) элемента за время O(logN) каждый. Код на golang можете посмотреть здесь и тесты.

Проверка кода на LeetCode дает результаты, представленные в таблице. Она включает в себя еще и результаты решения сортировкой и линейным поиском, которое не было рассмотрено в силу его простоты (код можно посмотреть здесь)

Бенчмарки на Golang с массивом из 30 одинаковых элементов, каждый из которых равен искомому дают следующие результаты.

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

Примеры составления блок-схемы алгоритма

Пример 1.
Составить схему алгоритма вычисления
значения :

Для
начала для построения блок –схемы
алгоритма опишем последовательность
действий, необходимых для решения данной
задачи:

• начало

• ввод
  чисел a,b

• вычисление
  х

• вычисление
  z

• вывод
  результата

• конец

Исходя из этого
составляем блок-схему алгоритма согласно
ГОСТ, используя соответствующие блоки.

Пример
2. Составить
схему алгоритма вычисления значения:
x=a+b
при a>b,
x=a*b,
при a<=b.

Пример 3. Составить схему алгоритма вычисления значения:

Для начала для
построения блок –схемы алгоритма опишем
последовательность действий, необходимых
для решения данной задачи:

Исходя из этого
составляем блок-схему алгоритма согласно
ГОСТ, используя соответствующие блоки.

Порядок выполнения работы

1. Изучить
   теоретические сведения по теме
   ”Построение блок-схем алгоритмов”.

2. Получить
   у преподавателя индивидуальное задание
   и нарисовать блок-схему алгоритма
   согласно заданному варианту.

3. Ответить
   на контрольные вопросы.

4. Сформулировать
   выводы.

Контрольные вопросы

1. Основные
   этапы решения задач на компьютере.

2. Свойства алгоритма.
   Типы вычислительных процессов.

3. Блок схемы. Понятие
   и правила построения.

4. Примеры построения
   блок-схем алгоритмов.

Задание
№1: Разработайте
алгоритм и представьте его в графическом
виде (блок-схемы) для следующих задач:

Задание 1.1
Вычислить значение выражения при
заданных исходных данных.

Указание.
Для упрощения выражений введите
промежуточные переменные.

Сравнить полученное
значение с указанным правильным
результатом.

1.

При
x = 14.26;
y = – 1.22;
z = 3.5ответs
= 0.749155.

2.

При
x = –4.5; y = 0.75;
z = –0.845ответs
= –3.23765.

3.

При
x = 3.74;
y=–0.825; z = 0.16ответs
= 1.05534.

4.

При
x = 0.4;
y = –0.875; z = –0.475ответ
s = 1.98727.

5.

При
x = –15.246; y = 4.642;
z = 21 ответ
s = –182.038.

6.

При
x = 16.55;
y = –2.75; z = 0.15
ответ s
= –40.6307.

7.

При
x = 0.1722; y = 6.33; z = 3.25ответ
s = –205.306.

8.

При
x = –2.235;
y = 2.23; z = 15.221
ответ s
= 39.3741.

9.

При
x = 1.825;
y = 18.225; z = –3.298ответ
s = 1.21308.

10.

При
x = 3.981;
y = –1.625;
z = 0.512
ответ s
= 1.26185.

11.

При
x = 6.251; y = 0.827; z = 25.001
ответ
s = 0.712122.

12.

При
x
= 3.251; y
= 0.325; z
= 0.466
ответ s
= 4.23655.

13.

.

При
x
= 17.421; y
= 10.365;
z
= 0.828
ответ s
= 0.330564.

14.
.

При
x
= 12.3;
y
= 15.4; z
= 0.252
ответ s
= 82.8256.

15.

.

При
x
= 2.444; y
= 0.869;
z
= –0.13
ответ s
= –0.498707.

Задание
1.2 Вычислить
значение выражения при заданных исходных
данных. Предусмотреть вывод информации
о выбранной ветви вычислений.

Задание
1.3 Вывести
на экран таблицу значений функции Y(x)
и ее разложения в ряд S(x)
для x,
изменяющегося от a
до b
с шагом h
= (b –
a)/10,
табл. 1.

Таблица 1.

Задание
№2:
Решите представленные ниже задачи,
указав номер задачи и полученный ответ. 

Задача
2.1
Определите
результаты работы блок-схемы алгоритма
при

Задача
2.2
Какие
значения примут t и k в
результате работы фрагмента блок-схемы
алгоритма?

Задача
2.3.
Определите
значения
элементов
массива А₂,
А₄,
А₆,
А₈
при N=8
в результате работы фрагмента алгоритма

Практическая
раборта № 1

Построение
блок-схем алгоритмов(теория)

Предпочтительнее
до записи на алгоритмическом языке представить алгоритм в виде блок-схемы. Для
построения алгоритма в виде блок-схемы необходимо знать назначении каждого из
блоков. В таблице 1. приводятся типы блоков и их назначение.

Таблица 1

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

Алгоритмизация выступает как набор
определенных практических приёмов, особых специфических навыков рационального
мышления в рамках заданных языковых средств. Алгоритмизация вычислений
предполагает решение задачи в виде последовательности действий, т.е. решение,
представленное в виде блок-схемы. Можно выделить типичные алгоритмы. К ним
относятся: линейные алгоритмы, разветвляющиеся алгоритмы, циклические
алгоритмы.

Линейные алгоритмы

Линейный алгоритм является наиболее
простым. В нём предполагается последовательное выполнение операций. В этом
алгоритме не предусмотрены проверки условий или повторений.

Пример: Вычислить функцию z=
(х-у)/x +y².

Составить блок-схему вычисления функции по
линейному алгоритму. Значения переменных х, у могут быть
любые, кроме нуля, вводить их с клавиатуры.

Решение: Линейный алгоритм вычисления
функции задан в виде блок-схемы на рис.1. При выполнении линейного алгоритма
значения переменных вводятся с клавиатуры, подставляются в заданную функцию,
вычисляется результат, а затем выводится результат.

Рис.1. Линейный алгоритм

Назначение блоков в схеме на
рис.1:

·       
Блок 1 в схеме служит в качестве
логического начала.

·       
Блок 2 соответствует вводу данных.

·       
Блок 3 представляет арифметическое
действие.

·       
Блок 4 выводит результат.

·       
Блок 5 в схеме служит в качестве
логического завершения схемы.

Алгоритмы ветвлений

Разветвляющийся алгоритм предполагает
проверку условий для выбора решения. Соответственно в алгоритме появятся две
ветви для каждого условия.

В
примере рассматривается разветвляющийся алгоритм, где в зависимости от условия
выбирается один из возможных вариантов решений. Алгоритм представляется в виде
блок-схемы.

Пример:
При выполнении условия x>0
вычисляется функция: z=
x+
y,
иначе, а именно, когда х=0 или x<0,
вычисляется функция: z=x²+y².

Составить
блок-схему вычисления функции по алгоритму ветвления. Значения переменных х,
у могут быть любые, вводить их с клавиатуры.

Решение:
На рис.2 представлен разветвляющийся алгоритм, где в зависимости от условия
выполнится одна из веток. В блок-схеме появился новый блок 3, который проверяет
условие задачи. Остальные блоки знакомы из линейного алгоритма.

Рис.2. Алгоритм ветвления

Пример: Найти максимальное значение
из трёх различных целых чисел, введенных с клавиатуры. Составить блок-схему
решения задачи.

Решение: Данный алгоритм
предполагает проверку условия. Для этого выбирается любая из трёх переменных и
сравнивается с другими двумя. Если она больше, то поиск максимального числа
окончен. Если условие не выполняется, то сравниваются две оставшиеся
переменные. Одна из них будет максимальной. Блок-схема к этой задаче
представлена на рис 3.

Рис. 3. Блок-схема поиска максимума

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

Циклический алгоритм предусматривает
повторение одной операции или нескольких операций в зависимости от условия
задачи.

Из
циклических алгоритмов выделяют два типа:

1)                
с заданным количеством циклов или со
счётчиком циклов;

2)                
количество циклов неизвестно.

Пример:
В цикле вычислить значение функции z=x*y при условии, что одна из
переменных x
меняется в каждом цикле на единицу, а другая переменная у не
меняется и может быть любым целым числом. В результате выполнения цикла при
начальном значении переменной х=1 можно получить таблицу умножения.
Количество циклов может быть любым. Составить блок-схему решения задачи.

Решение:
В примере количество циклов задаётся. Соответственно выбирается алгоритм
циклов первого типа. Алгоритм этой задачи приводится на рис. 4.

Во
втором блоке вводятся количество циклов n и любые целые числа х,
y.

В
блок-схеме появился новый блок 3, в котором переменная i считает
количество циклов, после каждого цикла увеличиваясь на единицу, пока счётчик не
будет равен i=n. При i=n будет выполнен последний
цикл.

В
третьем блоке указывается диапазон изменения счётчика цикла (от i =1 до i=n).

В
четвёртом блоке изменяются значения переменных: z, x.

В
пятом блоке выводится результат. Четвёртый и пятый блоки повторяются в каждом
цикле.

Рис.4 . Циклический алгоритм со счётчиком
циклов

Этот
тип циклических алгоритмов предпочтителен, если дано количеством циклов.

Если количество циклов неизвестно, то
блок-схемы циклических алгоритмов могут быть представлены в виде рисунков 5, 6.

Пример:
Вычислить у=у-x
пока y>x,
если y=30,
x=4.
Подсчитать количество выполненных циклов, конечное значение переменной у.
В цикле вывести значение переменной у, количество выполненных
циклов. Составить блок-схему решения задачи.

Решение:
В примере количество циклов неизвестно. Соответственно выбирается алгоритм
циклов второго типа. Алгоритм этой задачи приводится на рис. 5.

Условие
проверяется на входе в цикл. В теле цикла выполняется два блока:

1)
у=у-х; i=i+1;

2)
вывод значений переменных i,
y.

Цикл
выполняется до тех пор, пока выполняется условие y>x. При условии
равенства этих переменных у=х или y<x цикл заканчивается.

Алгоритм,
представленный на рис.5, называется циклический алгоритм с предусловием,
так как условие проверяется в начале цикла или на входе в цикл.

Рис.5. Блок-схема
циклического алгоритма с предусловием

Во втором блоке вводятся y=30,
x=4.

В
третьем блоке проверяется условие y>x
на входе в цикл. Если условие выполняется, то переход к блоку 4, иначе на блок
6.

В
четвёртом блоке вычисляется значение переменной у, подсчитывается
количество выполненных циклов i=i+1.

В
пятом блоке выводится результат:

·       
значение переменной у,

·       
количество выполненных циклов i.

Пример:
Составить блок-схему примера (рисунок 5), проверяя условие выхода из цикла.
В этом примере условие задачи не меняется, и результат выведется тот же, но
блок-схема будет другой.

Решение:
В этом случае проверяется условие на выход из цикла: y<=x. При
этом условии цикл не выполняется. Условие в блок-схеме следует перенести в
конец цикла, после вывода на печать. Цикл выполняется до тех пор, пока
выполняется условие y>x.

Алгоритм,
если условие перенести в конец цикла, называется алгоритмом цикла с
постусловием. Алгоритм этой задачи приводится на рис. 6.

Во
втором блоке вводятся y=30,
x=4.

В
третьем блоке вычисляется значение переменной у, подсчитывается
количество выполненных циклов i=i+1.

В
четвёртом блоке выводится результат:

·       
значение переменной у,

·       
количество выполненных циклов i.

В
пятом блоке проверяется условие y<=x
на выход из цикла. Если условие выполняется, то переход к блоку 6, иначе на
блок 3 и цикл повторяется.

Рис.6 . Алгоритм цикла с
постусловием

Индивидуальные задания к работе:

1.
Найти
результат работы алгоритма:

Входные данные по вариантам

2.     При
заданном Х условие выполнется? Написать результат вычисления и ответ попадаем в
условие или нет.

Входные данные по вариантам

3.     Написать
результат выполнения алгоритма с указанными входными данными

Входные данные по вариантам

4.     Написать
результат выполнения алгоритма с указанными входными данными

Входные данные по вариантам

5.     Построить
блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно
найти.

6.     Построить
блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно
найти.

7.     Построить
блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно
найти.

8.     Построить
блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно
найти.

9.     Построить
блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно
найти.

10. Построить
блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно
найти.