3. Каждое из N предприятий города выпускает М одинаковых наименований продукции (N и М, наименования продукции и названия предприятий известны). Заданы объем выпуска и стоимость единицы продукции каждого вида для каждого из предприятий. Необходимо для каждого вида продукции определить предприятия, выпускающие наибольший объем этой продукции.

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

5. Ассортимент N магазинов состоит из М товаров (N, М и названия товаров заданы). Каждый товар характеризуется наличием или отсутствием его в магазине, а также наличием или отсутствием на него спроса покупателей. Требуется перечислить названия ходовых (есть спрос и товар имеется хотя бы в одном магазине), неходовых (спрос отсутствует, а товар имеется хотя бы в одном магазине) и дефицитных (спрос есть, а товара нет ни в одном из магазинов) товаров.

5.4 Элементы доказательного программирования

Доказательное программирование - это составление программ с доказательством их правильности. Сложность составления и доказательства правильности алгоритмов и программ состоит в следующем.

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

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

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

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

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

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

Таким образом, прагматический подход чреват созданием программ, содержащих ошибки даже после «завершения» отладки, что и наблюдается практически во всех больших программах для ЭВМ.

Рассмотрим в качестве иллюстрации принципов тестирования алгоритм и программу вычисления максимума из трех чисел: а, b, с.

алг «максимум трех чисел» 'максимум трех чисел

нач cls

ввод (а, b, с) input a, b, с

если а > b то if а > b then

тах := a max = a

инеc b > с то elseif b > с then

тах := b mах = b

инеc с > а то elseif с > a then

тах:= с mах = с

кесли end if

вывод («тах=»,тах) ? «mах=»; mах

кон end

Запуск этой программы на ЭВМ можно проверить на следующих данных:

Tecт1 Тест2 Тест3

? 1 1 2 ? 1 2 3 ? 3 2 1

max = 2 max = 3 max = 3

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

Контрпример1

? 2 1 3

max = 2

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

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

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

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

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

алг «у = х5» Результаты Утверждения

нач

v := хх v1 = хх v1 = x2

v := vv v2 = v1v1 v2 = x4

у := vx у = v2x у = х5

кон

Справа от алгоритма приведены результаты выполнения присваиваний. Результатом первого присваивания v := хх будет значение v1 = хх переменной v. Результат следующего присваивания v := vv - второе значение переменной v, равное v2 = v1v1 . Результатом третьего присваивания у := vx будет значение у = v2x .

На основе приведенных рассуждений, можно сделать три утверждения о промежуточных и конечных результатах вычислений:

Результаты Утверждения

{ v1 = хх v1 = х2

{ v2 = v1v1 v2 = x4

{ у = v2x у = х5

Таким образом можно высказать окончательное

Утверждение. Конечным результатом выполнения будет

у = х5 для любых значений х.

Доказательство. Исходя из описания результатов выполнения присваиваний значение у будет равно

у = v2x = (v1v,)x = ((хх).(хх))) х = x5.

Что и требовалось доказать.

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

разбор случаев;

подбор контрпримеров;

выделение лемм;

индуктивный вывод.

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

алг «у = тах(а, b,с)» Результаты

нач

если а > b то при а > b

у := а у = а

инес b > с то при b > с

у := b у = b

инес с > а то при с > а

у := с у = с

кесли при не (b > с)

кон

Справа от алгоритма приведены результаты вычислений с указанием условий, при которых они получаются. На основании этих фактов можно заключить, что конечные результаты вычисления имеют три варианта:

а, при а > b,

у = b, при b > с и b а,

с, при с > а и с b.

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

а, при а b и а с,

mах = b, при b с и b а,

с, при с а и с b.

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

Для опровержения общего утверждения достаточно указать хотя бы один контрпример. В данном случае утверждение о правильности алгоритма гласило бы: для любых значений переменных а, b, с конечным было бы значение mах (а, b, с).

Контрпримером в данном случае будут значения: а = 2, b = 1, с = 3. Для этих данных по определению mах = 3, а по результатам выполнения алгоритма у = 2. Следовательно, в алгоритме содержится ошибка.

Однако оказывается, что это не единственная ошибка. Более тонкие ошибки вскрывает второй контрпример: а = 1, b = 1, c = 1. Для этих данных в алгоритме вовсе не определен результат вычислений у = ? и конечный результат выполнения программы будет непредсказуем!?

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

Постановка задачи Метод решения

Вычисление mах (а, b, с).

Дано: а, b, с - три числа, mх = mах(mах(а,b),с)

Треб.: mх - максимум, mах(х,у) = х, при х у

Где: mх = mах (а, b, с). у, при у х

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

алг «тх = тах(а,b,с)» Результаты

нач

если а b то при а b

тх := а mx = a

иначе при b > а

mх := b mх = b

кесли { mх = mах(а,b) } при с < mх

если с mх то при с mх

mх := с mх' = с

кесли

кон

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

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

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

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

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

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

Лемма: Конечными результатами выполнения алгоритма

Алгоритм Результаты

если а > b то при а b

тх := а mx = a

иначе при b > a

тх := b mx = b

если

является значение mx = max(а, b) для любых значений а и b.

Доказательство. Результатом вычислений здесь будут значения

а при а b

mx =

b при а < b

что совпадает с определением max (а, b).

С помощью этой леммы легко доказать правильность алгоритма в целом.

{ mх = max (а, b) } Результаты

если с mx то при с mx

mx := с mx' = с

кесли mx' = mx

при с < mx

Утверждение. Конечным результатом выполнения алгоритма вычисления максимума будет значение mx' = max (а, b, с) для любых значений а, b и с.

Доказательство. В силу предположения предшествующее значение переменной mx = max(a,b). Отсюда получаем, что

с, при с mx

mx = = max(a,b,c).

mx, при с < mx

Что и требовалось доказать.

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

Одним из важнейших применений аппарата лемм является анализ результатов выполнения и доказательство правильности алгоритмов с циклами. Используемые для анализа циклов леммы называются индуктивными утверждениями. Эти леммы выражают утверждения о промежуточных результатах выполнения циклов.

В качестве примера использования индуктивных рассуждений рассмотрим алгоритм вычисления среднего арифметического последовательности чисел. В приводимом алгоритме предполагается, что последовательность чисел размещена в массиве X[1:N].

алг «среднее значение»

массив 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 = S00/1 + Х[1]/1 = Х1/1;

S2 = S1(2 - 1)/2 + Х[2]/2 = S11/2 + Х[2]/2 = Х1/2 + Х[2]/2;

S3 = S2(3 - 1)/3 + Х[3]/3 = S22/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 + ... + Xk-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), ... .

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

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

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

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

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

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

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

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

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

Min := тп Min = mnN

кон

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

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

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

х[1] при х[1] < mn0

mn1 = = min (х[1], mn0).

mn0 при х[1] mn0

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

mn1 = min (x[l], mn0)

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

mnk = min (x[k], Min(x[k-l], ..., х[1], mn0) = Min (x[k], xk-1], ..., х[1], mn0).

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

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

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

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

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

В самом деле, если значение mn0 окажется меньше любого из значений последовательности х[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, равное mn0 = х[1].

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

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

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

Что и требовалось.

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

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

Вопросы

1. Как показать наличие ошибок в алгоритме?

2. Сколь долго может продолжаться отладка программ?

3. Зачем нужны доказательства в анализе алгоритмов?

4. Из чего состоит техника доказательств правильности?

5. Когда применяется разбор случаев?

6. Что такое леммы?

7. Что такое индуктивные рассуждения?

3адачи

1. Приведите постановку, алгоритм решения и разбор правильности для следующих задач:

а) подсчет суммы целых чисел;

б) подсчет суммы нечетных чисел;

в) подсчет членов арифметической прогрессии;

г) подсчет членов геометрической прогрессии.

2. Для последовательности чисел х1, х2,..., хN, приведите постановку, алгоритм решения и разбор правильности следующих задач:

а) подсчет суммы всех чисел;

б) вычисление среднего арифметического чисел;

в) определение наибольшего из чисел;

г) определение наименьшего из чисел.

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

а) нахождение самого высокого ученика;

г) нахождение самого легкого ученика;

д) нахождение среднего роста учеников;

е) нахождение суммарного веса учеников.

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

а) подсчет сумм элементов матрицы по столбцам;

в) нахождение минимального значения в каждом столбце;

е) нахождение максимального значения в каждой строке;

ж) нахождение наибольшего из минимальных значений в столбцах;

з) нахождение наименьшего из максимальных значений в строках.

5. Для N точек на плоскости, заданных случайным образом, приведите постановку, метод решения, сценарий, алгоритм и программу решения следующих задач:

а) найти точку, наиболее удаленную от центра координат;

б) соединить пару наиболее удаленных точек;

в) найти три точки, образующие треугольник с наибольшим периметром;

г) найти три точки, образующие треугольник с наибольшей площадью.

5.5 Решение сложных задач

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

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

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

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

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

Первая задача: упорядочение массивов данных. Пример, для чисел 3, 7, 9, 1, 4 упорядоченная последовательность имеет вид: 1, 3, 4, 7, 9.

Существует несколько способов и методов упорядочения массивов и последовательностей. Простейший из них называется методом «пузырька».

Метод «пузырька» состоит в нахождении в массиве наименьшего числа и перестановке его на первое место. Это как бы «пузырек», поднимающийся к началу массива. Затем в остатке массива находится наименьшее число, которое перемещается на второе место, и так далее - до исчерпания всего массива.

Для рассматриваемых чисел метод «пузырька» дает следующие перестановки:

исходные числа: 3, 7, 9, 1, 4.

перестановка1: 1, 7, 9, 3, 4.

перестановка2: 1, 3, 9, 7, 4.

перестановка3: 1, 3, 4, 7, 9. упорядочено.

Приведем точную математическую постановку задачи.

Постановка задачи

Упорядочение последовательности чисел.

Дано: x1, х2, ..., хN - исходные числа.

Треб.: x1', x2', ..., хN' - упорядоченные числа.

Где: х1' х2' ... хN'.

При: N > 0.

Упорядочение чисел по методу «пузырька» в общей форме имеет вид:

Способ «упорядочение чисел»

нач

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

хтп := xk

imn := k

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

если xi < хтп то

хтп := xi

imn : = i

кесли

кцикл

xmn = Min (хk, ..., хN)

xk' = хтп

ximn ' = xk

кцикл хk = Min (хk, ..., хN)

кон x1 < х2 < ... < хk

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

Первый фрагмент (внутренний цикл) решает подзадачу нахождения минимального значения в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального значения на k-e место в массиве.

Лемма 1. Для вспомогательного алгоритма

алг «поиск минимума»

нач

хтп := xk

imn := k

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

если xi < хтп то

хтп := xi

imn := i

кесли

кцикл { xmn = Min (хk, ..., х1) }

кон

конечным результатом вычислений будет значение

xmn = Min (хk, ..., хN).

Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает

xmnk = xk.

Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:

xk+1 при xk+1 < xmnk,

xmnk+l =

xmnk при xk+1 xmnk.

На втором шаге цикла будет получен минимум первых трех чисел:

xmnk+2 = min (xk+2, min (хk+1, хk)) = Min (хk+2, хk+1, хk).

Теперь можно утверждать, что на третьем и последующих шагах цикла результатом будет минимальное значение среди чисел xk , ..., xi

хmni = Min (хk, ..., хi).

Данное утверждение доказывается с помощью математической индукции. На первых двух шагах при i = k + 1, k + 2 оно уже установлено. Покажем, что оно будет выполняться на (i + 1)-м шаге. Действительно, на следующем шаге цикла результатом будет:

xi+1 при хi+1 < xmni = min(xi+1, хmni)

хmni+1 =

хmni при хi+1 хmni = min(xi+1, xmni)

= min (xi+1, Min (хk , ..., хi)) = Min (хk, ..., хi, xi+1).

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

xmnN = Min (xk, ..., хN)

Что и требовалось доказать.

Лемма 2. Для вспомогательного алгоритма

алг «перестановки»

нач { xmn = Min (хk, ..., хN) }

ximn= xk

кон

конечным результатом будет значение хk' = Min (хk, ..., хN).

Доказательство. В силу леммы 1 xmn = Min (xk, ..., хN). А так как в этом алгоритме хk' = xmn, то в итоге получим

хk' = xmn = Min (хk, ..., хN).

Что и требовалось.

Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х1', ..., хN', удовлетворяющая условию х1' х2' ... хN'.

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

алг «упорядочение чисел»

нач

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

xmn := хk

............... { xmn = Min (хk, ..., хi) }

хk = xmnN

хmп = хk

кцикл { хk' = Min (хk, ..., хN) }

кон { х1' х2' ... хk' }

На первом шаге при k = 1 первый элемент последовательности

х1' = Min (x1, х2, ..., хN),

На втором шаге второй элемент последовательности

x2' = Min (х2, ..., хN).

В силу свойств минимума последовательности чисел будем иметь

х1' = Min(x1, x2, ..., хN) = min (x1, Min (х2, ..., хN) (Min (х2, ..., хN) = x2'.

Таким образом, при k = 2 результатом станут значения х1' и x2', такие что

х1' x2'

На третьем шаге выполнения основного цикла результатом станет

х3 = Мin(х3, ..., хN).

Опять же в силу свойств минимума последовательности имеем

х2' = Min (х2, х3, ..., хN) = min (x2, Min (x3, ..., хN)) Min (x3, ..., хN) = x2'.

Таким образом, после третьего шага при k = 3 первые три значения последовательности х1', x2', x3' будут удовлетворять условию

х1' x2' x3'

Из приведенных выкладок можно сделать индуктивное предположение, что на каждом очередном k-м шаге выполнения основного цикла первые k членов последовательности х1', x2', .... хk' будут удовлетворять условию

х1' x2' … xk'.

Данное предположение доказывается с помощью математической индукции. На начальных шагах при k == 2 и k = 3 оно уже показано. Покажем, что оно будет выполнено на (k + 1)-м шаге, если это условие выполнено на k-м. шаге.

В силу Леммы 2 на k-м и (k + 1)-м шагах выполнения основного цикла промежуточными результатами будут

хk' = Min(xk, xk+1, ..., хN),

хk+1' = Min (xk+1, ..., хN).

В силу свойств минимума последовательности чисел имеем

хk' = Min(xk, xk+1, ..., хN) = min (хk, Min (хk+1, ...,хN)) Min (xk+1, ..., хN) = хk+1'.

Таким образом, хk xk+1 и в силу индуктивного предположения получаем, что

x1' х2' ... хk' xk+'1.

Что и требовалось доказать.

Осталось уточнить результаты выполнения последнего шага цикла при k = N - 1. В силу Леммы 2 результатом будет значение

xN-'1 = Min (xN-1, xN) хN'.

Таким образом, после N - 1 шагов выполнения основного цикла для последовательности в целом будут выполнены соотношения упорядоченности

x1' x2' ... хN' .

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

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

Данные о товарах представлены двумя таблицами:

товар стоим кол-во

яблоки	500	200
огурцы	400	250
арбузы	200	600

Товар цена остаток

яблоки	2500	100
огурцы	2000	150
арбузы	1200	200

Для представления исходных данных в программе примем операторы data:

tovs: 'товары: osts: 'остатки:

data «яблоки», 500, 200 data «яблоки», 2500, 100

data «огурцы», 400, 250 data «огурцы», 2000, 150

data «арбузы», 200, 600 data «арбузы», 1200, 200

data «персик», 800, 100 data «персик», 2000, 0

data «», 0, 0 data «», 0, 0

Приведем теперь алгоритм и программу решения поставленной задачи в соответствии с выбранным сценарием и рассмотренным выше способом упорядочения массивов методом «пузырька».

При составлении алгоритмов и программы решения этой задачи будем использовать принцип нисходящей разработки «сверху-вниз»: от основного алгоритма и основной части программы к алгоритмам и подпрограммам решения вспомогательных подзадач.

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

Для размещения исходных данных о товарах в поставленной задаче примем пять массивов: tv(l:N), s(l:N), m(l:N), с (1:N), p(l:N). Общий размер этих массивов ограничим числом N = 200, которое явно выделено в описании массивов с тем, чтобы в дальнейшем его можно было увеличить для большего количества данных без других изменений программы.

алг «выручка и остатки товаров» 'выручка и остатки товаров

N = 100 N = 100

массив tv[1:N],s[1:N],m1l:N] dim tv$(N),s(N),m(N)

массив L[1:N],c[1:N],p[1:N] dim L(N),c(N),p(N)

нач сls

вывод («товары:») ? «товары:»

данные-товаров gosub tovar 'товары

вывод («остатки:») ? «остатки:»

данные-остатков gosub ostatok 'остатки

вывод («-----») ? «-----»

подсчет-выручки gosub vyruch 'выручка

вывод («выручка», S) ? «выручка=»;S

вывод («сортировка:») ? «сортировка:»

сортировка-товаров gosub sortdan 'сортировка

кон end

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

алг «данные товаров» tovar: 'данные товаров

нач '

загрузка-товаров restore tovs

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

чmeнue(tv(k),s(k),m(k)) read tv$(k),s(k),m(k)

при tv(k) = «» то if tv$(k) = «» then exit for

вывод (tv(k),s(k),m(k)) ? tv$(k);s(k);m(k)

кцикл next k

если k< Nmo N := k-1 if k < N then N = k-1

кон return

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

алг «данные остатков» ostatok: 'данные остатков

нач '

загрузка-остатков restore osts

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

чmeнue(tv(k),c(k),p(k)) read tv$(k),c(k),p(k)

при tv(k) = «» выход if tv$(k) = «» then exit for

вывод (tv(k),c(k),p(k)) ? tv$(k);c(k);p(k)

кцикл next k

если k < N mo N := k-1 if k < N then N = k-1

кон return

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

алг «подсчет выручки» vyruch: 'подсчет выручки

нач '

S := 0 S = 0

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

S := S+(c(k)-s(k)) *(m(k)-p(k)) S = S+(c(k)-s(k))*(m(k)-p(k))

кцикл next k

кон return

Лемма 3. Конечным результатом выполнения данного вспомогательного алгоритма будет сумма

SN = (с(1) - s(l))(m(l) - р(1)) + ... + (c(N) - s(N))(m(N) - p(N)).

Доказательство проводится с помощью индуктивных рассуждений. Первое присваивание S := 0 обеспечивает начальное значение суммы S0 = 0.

О результатах k-го шага выполнения цикла можно сделать индуктивное утверждение

Sk = Sk-1 + (c(k)- s(k))-(m(k) - p(k)) = (с(1) - s(l))(m(l) - p(l)) + ... + (c(k) - s(k))(m(k) - p(k)).

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

SN = (с(1) - s(l))(m(l) - р(1)) + ... + (c(N) - s(N))(m(N) - p(N)).

Что и требовалось доказать.

Для сортировки данных воспользуемся алгоритмом упорядочения чисел по методу «пузырька», предполагая, что исходная и упорядоченная последовательность чисел r1, r2, ..., rN будут записаны в массиве x[l:N].

Для формирования результирующих упорядоченных данных используется массив индексов L(1:N), в котором будут записаны номера элементов исходной последовательности так, что x(k) = p(L(k)) для всех k = 1, ..., N.

алг «сортировка данных» sortdan: 'сортировка данных

массив x[1:N] dim x(N)

нач '

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

L(k) = k L(k) = k

x(k)=p(L(k)) x(k)=p(L(k))

кцикл next k

сортировка-массива gosub sortmas 'сортировка

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

i := L(k) i = L(k)

вывод (tv(i),c(i),p(i)) ? tv$(i);c(i);p(i)

кцикл next k

кон return

Модификация алгоритма упорядочения чисел, размещаемых в массиве x[l:N], с учетом перестановок значений в массиве индексов L[1:N] получает следующий вид:

алг «сортировка массива» sortmas: 'сортировка массива

нач '

от k = 1 до N-1 цикл for k = 1 to N-1

xmn := x(k) xmn = x(k)

imn := k imn = k

от i = k + 1 до N цикл for i = k + 1 to N

если x(i) < xmn то if x(i) < xmn then

xmn := x(i) xmn = x(i)

imn := i imn = i

кесли end if

кцикл next i

Imn := L(imn) Imn = L(imn)

xmn := x(imn) xmn = x(imn)

L(imn) := L(k) L(imn) = L(k)

x(imn) := x(k) x(imn) = x(k)

L(k) :=Imn L(k) = Imn

x(k) := xmn x(k) = xmn

кцикл next k

кон return

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

х(1)' х(2)' ... x(N)'

и последовательность индексов в массиве L[1:N], удовлетворяющих условиям

x(k)' = p(L(k)) для всех k = 1, .... N.

Доказательство. Первое утверждение об упорядоченности значений х(1)' х(2)' ... x(N)' массива x[l:N] по завершении алгоритма следует из доказательства правильности алгоритма упорядочения последовательности чисел. Для доказательства второго утверждения рассмотрим результаты перестановок значений элементов:

Imn := L(imn) Imn = L(imn)

xmn := x(imn) xmn = x(imn)

L(imn) := L(k) L(imn)' = L(k)

x(imn) := x(k) x(imn)' = x(k)

L(k) := Imn L(k)' = Imn = L(imn)

x(k) := xmn x(k)' = xmn = x(imn)

Перед началом выполнения алгоритма упорядочения массива в алгоритме сортировки данных массив индексов L[1:N] и упорядочиваемый массив x[l:N] получают значения, удовлетворяющие следующим соотношениям:

х(i)' = P(L(i) для всех i = 1, ..., N.

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

Imn = L(imn)

xmn = x(imn) == p(L(imn))

L(imn)' = L(k)

x(imn)' = x(k) = p(L(k)) = p(L(imn)')

L(k)' = Imn = L(imn)

x(k)' = xmn = x(imn) = p(L(imn)) = p(L(k)')

Следовательно, после каждого шага цикла для переставленных элементов массивов сохраняются соотношения

x(i)' = p(L(i)) для всех i = 1, ..., N.

Что и требовалось доказать.

Утверждение. Конечным результатом выполнения алгоритма и подпрограммы сортировки данных будет список данных, в котором последовательность значений р1', р2', ..., рN' будет упорядочена:

p1' р2' … pN'

Доказательство. В соответствии с доказанной выше леммой 4 значения в массиве x[l:N] после выполнения алгоритма упорядочения чисел будут удовлетворять условиям

х(1)' х(2)' ... x(N)'.

В силу этой же леммы 4 значения индексов в массиве L[1:N] будут удовлетворять соотношениям x[k]' = p(L(k)) для всех k = 1, ..., N.

Конечным результатом алгоритма сортировки данных является вывод значений из массива p[l:N] в соответствии с массивом индексов L[1:N]. Таким образом, очередные значения последовательности p1', p2',... будут равны:

р1' = p(L(l)) = х(1)',

p2'= р(L (2)) = х(2)'и т. д.

В силу упорядоченности значений х(1)', х(2)', ..., x(N)' получаем, что значения выходной последовательности будут также упорядочены:

p1' р2' … pN'

Что и требовалось доказать.

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

Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим образом, при указанных исходных данных дает следующие результаты:

товары:

яблоки, 500, 200

огурцы, 400, 250

арбузы, 200, 600

персики, 800, 100

остатки:

яблоки, 2500, 100

огурцы, 2000, 150

арбузы, 1200, 200

персики, 2000, 0

выручка = 880000

сортировка:

персики, 2000, 0

яблоки, 2500, 100

огурцы, 2000, 150

арбузы, 1200, 200

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

Вопросы

1. Что такое сложные алгоритмы и программы?

2. Что такое упорядоченная последовательность?

3. Что такое упорядочение методом «пузырька»?

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

5. Что такое разработка программ «сверху-вниз»?

Задачи

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

а) подсчет планируемых доходов от продажи товаров;

б) подсчет начальной суммы вложений реализации товаров;

в) подсчет планируемой прибыли от продажи товаров;

г) подсчет текущей задолженности.

2. Составьте алгоритм и программу сортировки данных о товарах и постройте обоснование их правильности для следующих задач:

а) сортировка данных по начальному количеству;

б) сортировка данных по остаточному количеству;

в) сортировка данных по начальной стоимости;

г) сортировка данных по продажной цене.

3. Составьте алгоритм и программу сортировки данных о товарах по следующим признакам и приведите обоснование их правильности:

а) по доле планируемых доходов от реализации товаров;

б) по доле прибыли от реализации товаров;

в) по доле убыточности реализации товаров.

Глава 6. ЭКЗАМЕНЫ ПО ИНФОРМАТИКЕ

6.1 Экзамены и зачеты по информатике

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

Зачеты и экзамены по информатике могут и должны проводиться с помощью и использованием персональных ЭВМ. При дистанционном образовании персональные компьютеры являются основным средством обучения и поэтому экзамены по информатике должны проводиться только с помощью ЭВМ.

На зачетах должны проверяться уровень изучения курса информатики и выполнение компьютерных заданий. Проверка знаний и анализ выполнения заданий по информатике могут и должны проверяться на ЭВМ. В качестве средств контроля могут и должны использоваться бумажные копии результатов тестирования и выполнения заданий на ЭВМ.

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

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

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

На зачетах в соответствии с требованиями государственных стандартов должны быть проверены минимальные умения работы на персональных ЭВМ, отвечающих минимальному уровню компьютерной грамотности и выражающихся в выполнениии следующих учебных заданий:

1) оформление на ЭВМ стихотворения или юмористического рассказа, подготовленных с помощью редактора текстов;

2) оформление на ЭВМ рекламы или забавного рисунка, созданных с помощью графического редактора;

3) проведение поиска информации в сети Интернет по своим личным и профессиональным вопросам и проблемам.

Базовый уровень знаний основ информатики и владения средствами ЭВМ проверяется на зачетах или экзаменах по результатам самостоятельного выполнения на ЭВМ следующих учебных заданий:

1) организация на ЭВМ базы данных о товарах, услугах или фирмах со своими сведениями в некоторой системе управления базами данных;

2) организация на ЭВМ базы знаний о своих знакомых, друзьях или круге предметов с самостоятельно подобранными правилами вывода.

3) организация на ЭВМ калькуляций и расчетов закупок товаров или сметы затрат с помощью электронных таблиц.

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

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

1) организация на ЭВМ диалоговой процедуры или программы с использованием диалоговой системы программирования;

2) организация на ЭВМ обработки данных на основе самостоятельно составленных алгоритмов и программ;

3) самостоятельное составление алгоритмов и программ решения задач вплоть до отладки и получения результатов на ЭВМ.

Высшим уровнем изучения основ информатики является овладение технологией решения профессиональных задач с помощью ЭВМ. Это уровень изучения курса информатики проверяется по результатам выполнения следующих учебных заданий:

1) самостоятельная постановка задач и разработка соответствующих алгоритмов и программ их решения на ЭВМ:

2) подбор методов решения некоторого класса профессиональных задач и его реализации в виде диалоговых программ на ЭВМ;

3) обоснование правильности результатов решения задач, полученных на ЭВМ с помощью самостоятельно созданных алгоритмов и программ.

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

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

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

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

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

При компьютерном тестировании предварительная оценка ответов проводится сразу после ввода их в ЭВМ, а преподаватели выставляют окончательную оценку по протоколам тестирования. Данная форма наиболее удобна для учащихся и существенно упрощает работу преподавателям.

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

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

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

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

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

Для записи программ, могут применяться любые языки программирования - Бейсик, Паскаль, Си, Фортран и т.д. Однако необходимо помнить, что в вузах для обучения и принятия экзаменов используются обычно персональные компьютеры IBM PC с операционной системой MS DOS или Windows.

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

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

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

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

Во многих вузах экзамены по информатике проводятся и для поступающих. В 1999 г. приказом № 640 министра образования Российской Федерации всем вузам разрешено вводить вступительные экзамены по информатике в качестве альтернативных вступительных испытаний на профильные специальности и факультеты.

Для вступительных экзаменов по информатике по заказу Госкомвуза России в 1994 г. была создана типовая программа [З]. Она основана на учебных программах, утвержденных Министерством образования, и школьных учебниках информатики, имеющихся в средних учебных заведениях.

В 1999 г. более 40 вузов Российской Федерации принимали вступительные экзамены по информатике: вузы - Москвы, Петербурга, Владивостока, Владимира, Воронежа, Комсомольска-на-Амуре, Перми, Самары, Саратова, Томска, Тулы, Череповца. Полный список вузов, принимающих вступительные экзамены по информатике, можно найти в сети Интернет с помощью запроса «экзамен информатика» в поисковой системе Апорт.

В средних школах выпускные экзамены по информатике, как правило, проводятся по выбору учащихся в зависимости от их дальнейших планов. Программы курса информатики с выпускными экзаменами были созданы и рекомендованы Министерством образования для средних школ в 1988, 1992 и 1998 гг. [4, 5].

6.2 Решение экзаменационных задач

Решение задач по информатике представляют интерес не только для всех студентов, но и для абитуриентов и учащихся средних школ, собирающихся поступать на профильные специальности и факультеты. Здесь рассматриваются задачи, предлагавшиеся на вузовских экзаменах по информатике, а также задачи выпускных и вступительных экзаменов в 1994-1997 годах.

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

Основной сложностью организации экзаменов по информатике является необходимость отладки программ и получения результатов на ЭВМ при разнообразии языков программирования - Бейсик, Паскаль, Си, Фортран, изучаемых в вузах и школах. В силу этих причин приводимые здесь формулировки задач носят содержательный характер, независимый от языков программирования и используемых ЭВМ.

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

Существуют три основных общих способа организации ввода исходных данных в персональных ЭВМ, имеющихся в таких языках программирования как Бейсик, Паскаль, Си и Фортран. Рассмотрим их особенности и недостатки.

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

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

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

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

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

...