Простой метод сортировки массива

Необходимо отсортировать в порядке возрастания числовой массив, например, такой: 13, 3, 5, 21, 7, 1, 11.

Поставим частную цель: найти в массиве максимальный элемент и поменять его местами с последним элементом.

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

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

Вопрос №101. Разработка алгоритмов методом «отрабатывания назад» (на примере задачи о взвешивании монет).

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

Задача о взвешивании монет

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

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

1) Очевидно, что на последнем шаге процедуры взвешивания мы должны иметь дело максимум с 3 монетами, чтобы в при любом исходе взвешивания получить результат.

2) Задача предпоследнего шага – отобрать группу из 3-х монет. Это можно сделать, если в нашем распоряжении будет не более 9 монет (3 группы по 3 монеты).

3) Наконец, если у нас будет от 10 до 27 монет, мы сможем отобрать из них не более 9

монет, среди которых обязательно будет и дефектная монета.

Ответ: Определить дефектную монету из 25 можно не более чем за 3 шага:

1. 9 + 9 + 7;

2. 3 + 3 + 3 или 3 + 3 + 1 (может быть конец процедуры);

3. 1 + 1 + 1 (конец).

Вопрос №102. Использование рекурсии при разработке алгоритмов (на примере задачи о Ханойской башне).

В программировании рекурсия — вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

Рисунок ниже иллюстрирует древнюю игру, известную под названием Ханойской башни. Игра начинается, когда n дисков разного диаметра расположены по возрастанию диаметров на одном из трех стержней. Цель игры — по одному перенести диски, чтобы они в конечном счете были расположены в том же порядке на другом стержне. Не разрешается класть диск большего диаметра на диск меньшего диаметра. Разработать алгоритм, который проделывает эту процедуру за 2ⁿ-1 операций, где под операцией подразумевается перемещение диска с одного стержня на другой.

Р екурсивная функция mov, решающая задачу.

#include <stdio.h>

#include <stdlib.h>

int k;