|
|||||
Алг «среднее значение»Дата добавления: 2014-11-24 | Просмотров: 1537
массив X[1:N] нач Результаты: от k = 1 до N цикл S := S * (k-l)/k + X[k]/k Sk = Sk-1*(k-l)/k + X[k]/k кцикл [k = (1...N)] Xcp := S Xcp = S Кон
Этот алгоритм обычно считается ошибочным (?!). «Ошибкой» в этом алгоритме считается отсутствие присваивания S := 0 перед началом цикла. Разберем результаты выполнения алгоритма на первых трех шагах: S1 = S0×(l - 1)/1 + Х[1]/1 = S0×0/1 + Х[1]/1 = Х[1]/1; S2 = S1×(2 - 1)/2 + Х[2]/2 = S1×1/2 + Х[2]/2 = Х[1]/2 + Х[2]/2; S3 = S2×(3 - 1)/3 + Х[3]/3 = S2×2/3 + Х[3]/3 = Х[1]/3 + Х[2]/3 + Х[3]/3. Можно утверждать, что на первых трех шагах результатом является среднее арифметическое обрабатываемых чисел. На основе этих примеров можно сделатьиндуктивное утверждение - «на каждом очередном k-м шаге выполнения цикла результатом будет среднее арифметическое» Sk = Sk-1×(k-l)/k + X[k]/k = X[l]/k + X[2]/k + ... + X[k]/k. Доказательство этого утверждения проводится с помощью математической индукции. На первом шаге при k = 1 оно уже доказано. Допустим, что оно справедливо на (k -1)-м шаге Sk-1 = X[l]/(k-l) + X[2]/(k-l) + ... + X[k-l]/(k-l). Подставим его в описание результатов цикла на k-м шаге Sk= Sk-1×(k-l)/k +X[k]/k. Тогда результат выполнения цикла на k-м шаге оказывается равным Sk = X[l]/k + X[2]/k + ... + X[k-l]/k + X[k]/k, т. е. среднему арифметическому первых k чисел. Таким образом, индуктивное утверждение доказано. В силу математической индукции это утверждение верно для всех k = l, 2, ..., N. Следовательно, на последнем шаге конечным результатом выполнения цикла станет значение SN = SN-1×(N-1) + X[N]/N = X[1]/N + ... + X[N]/N. Исходя из этого утверждения конечным результатом выполнения алгоритма в целом будет среднее арифметическое значение Xcp = SN = X[1]/N + ... + X[N]/N. Следовательно, приведенный алгоритм, несмотря на содержащуюся в нем «ошибку», является правильным. В целом анализ правильности алгоритмов с циклами во многом построен на использовании индукции. Индукция - это вывод общих суждений из частных примеров. При анализе циклов она используется для подбора индуктивных утверждений о промежуточных результатах выполнения циклов. Однако для доказательства правильности индуктивных утверждений о результатах выполнения циклов используется полная математическая индукция. Математическая индукция - это принцип доказательства последовательностей утверждений Р(1), Р(2), Р(3), ..., P(N), .... когда известно, что верны первые утверждения для n = 1, 2, 3 и из истинности (n - 1)-го утверждения следует истинность n-го утверждения: Принцип математической индукции: если первое утверждение Р(1) истинно и из утверждения Р(n - 1)следует утверждение Р(n), то истинны все утверждения Р(1), Р(2), Р(3), ..., Р(n), ... . Приведем примеры индуктивного анализа циклов для алгоритма нахождения минимального значения в последовательности чисел, который в этот раз действительно будет ошибочным.
|
При использовании материала ссылка на сайт Конспекта.Нет обязательна! (0.054 сек.) |