2. Анализ алгоритмов

Анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объёма исходных данных. Используются также термины «временная сложность», «трудоёмкость» алгоритма. Фактически эта оценка сводится к подсчёту количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также ёмкостная сложность, то есть увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности даёт количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и ёмкостных затрат.

 

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

 

 

У исполнителя Делитель две команды, которым присвоены номера:

 

     1. Раздели на \(2\).

 

     2. Прибавь \(1\).

 

Первая из них уменьшает число на экране в \(2\) раза, вторая увеличивает его на \(1\). Исполнитель работает только с натуральными числами. Составь алгоритм, чтобы из числа \(23\) получить число \(4\), он должен содержать не более \(5\) команд. В ответе запиши только номера команд. (Например, \(11222\) — это алгоритм: раздели на \(2\), раздели на \(2\), прибавь \(1\), прибавь \(1\),  прибавь \(1\), который преобразует число \(36\) в \(12\).) Если таких алгоритмов более одного, то запиши любой из них.

 

 

Так как в задаче есть ограничение на количество используемых команд, то нужно чаще использовать команду «Раздели на \(2\)» для чётных чисел и прибавлять \(1\) к нечётным в противном случае. Решение от исходного числа даёт при этом однозначное решение.

 

При помощи элементарных рассуждений и вычислений получаем:

 

       \(23 + 1 = 24 / 2 = 12 / 2 = 6 / 2 = 3 + 1 = 4\).

 

Ответ: \(12221\).

 

 

Чертёжнику был дан для исполнения следующий алгоритм:

 

    Повтори \(7\) paз

 

        Сместиться на (\(−1\), \(2\))

 

        Сместиться на (\(−2\), \(2\))

 

        Сместиться на (\(4\), \(−4\))

 

    Конец

 

Каковы координаты точки, с которой Чертёжник начинал движение, если в конце он оказался в точке с координатами (\(0\), \(0\))?

 

1) (\(7\), \(0\))
2) (\(−7\), \(0\))
3) (\(0\), \(−7\))
4) (\(0\), \(7\))

 

  

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

 

По оси абсцисс: \(7 * ( -1 -2 + 4 ) = 7\).

 

По оси ординат: \(7 * (2 + 2 - 4) = 0\).

 

Для обнуления результата (\(7\), \(0\)) берём его с обратным знаком и получаем (\(−7\), \(0\)).

 

Ответ: \(2\).