Алг «нахождение минимума»

массив x[1:N]

нач Результаты:

от k = 1 до N цикл

если x[k] < min то

тп:= x[k] mn_k = { x[k], при x[k] < mn_k-1,

все { mn_k-1, в ином случае

кцикл [ k = (1... N)]

Min:= тп Min = mn_N

Кон

Утверждение. Приведенный алгоритм определения минимального значения последовательности чисел неправильный.

Доказательство. Для демонстрации ошибок необходимо привести контрпример. Для построения контрпримера разберем результаты выполнения на первом шаге цикла.

Результаты выполнения первого шага цикла при k = 1:

х[1] при х[1] < mn₀

mn₁ = = min (х[1], mn₀).

mn₀ при х[1] £ mn₀

Следовательно, результатом будет

mn₁ = min (x[l], mn₀)

Однако поскольку начальное значение mn₀ неизвестно, то не­определено значение результата выполнения первого шага цикла. Аналогичное утверждение можно сделать о втором и всех последу­ющих шагах выполнения цикла:

mn_k = min (x[k], Min(x[k-l],..., х[1], mn₀) = Min (x[k], x[k-1],..., х[1], mn₀).

В силу математической индукции это утверждение справедливо при k = N:

mn_N = Min (x[N], x[N - 1],..., x[2], х[1], mn₀),

Таким образом на основании этого утверждения можно сделать заключение о конечном результате выполнения алгоритма в целом:

Min = mn_N = Min (x[N], x[N - 1],..., x[2], х[1], mn₀).

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

В самом деле, если значение mn₀ окажется меньше любого из значений последовательности х[1],.... x[N], то конечный результат вычислений будет неправильным. В частности, при реализации алгоритма на Бейсике неправильный результат будет получен, если последовательность будет состоять только из положительных чисел. Например, для последовательности чисел: 1, 2, 3,..., N.

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

алг «нахождение минимума» массив х[1:п] нач тп:= x[1] от k = 1 до N цикл если x[k] < тп то тп = x[k] все кцикл Min = тп кон

Результаты: mn0 = х[1] [k = (1... N)] Min = mnN

Утверждение. Для любой последовательности чисел x[l:N] конечным результатом вычислений будет значение Min = Min (х[1],..., x[N]).

Доказательство. Воспользуемся результатами анализа выполнения алгоритма, рассмотренного ранее. Различие между ними состоит в добавлении перед началом цикла присваивания mn:= х[1], которое задает начальное значение переменной mn, равное mn₀ = х[1].

Тогда в силу приведенных ранее рассуждений и выкладок ко­нечным результатом выполнения новой версии алгоритма будет значение

Min = mn_N = Min(x[N], x[N-l],..., х[2], х[1], mn₀) =

= Min(x[N], x[N-l],..., x[2], x[l], x[l]) = Min(x[N],.... х[1]).

Поиск по сайту: