3.6. Примеры проектирования программ
Сортировка выбором
Для начала рассмотрим пример, в котором само задание уже содержит в себе описание образной модели. Сортировка заключается в выборе на очередном шаге минимального элемента из входной последовательности, исключения его оттуда и перенесения в конец выходной последовательности (или выбор максимального и включение в начало).
Образная модель. Сбор фактов. При разработке образной модели сразу же надо обратить внимание на взаимное расположение упорядоченной и неупорядоченной частей. Пусть они будут находиться в одном массиве, при этом упорядоченная будет справа. Важный момент: образная модель должная изображать программу «в процессе» выполнения, а не в начале работы, т.е. в упорядоченной части должны уже быть данные (в начале работы программы мы ничего «не увидим»).
По образной модели можно описать процесс сортировки так: из левой части выбирается максимальный элемент и удаляется, элементы от него до конца неупорядоченной части сдвигаются влево. Удаленный элемент помещается на освободившееся место в конец левой части (или в начало упорядоченной).
В образной модели сразу же бросаются в глаза действия, реализуемые стандартными программными контекстами. Кроме того, что они являются заготовками нашей будущей программы, они дают нам связанные с ними переменные и определяют их «смысл». Другое дело, к ним нельзя относиться как к истинам в последней инстанции, некоторые их характеристики нам пока будут неизвестны, они окончательно прояснятся только в процессе выстраивания фрагментов.
- Сортировка выбором базируется на выборе максимального из оставшихся. В нашей модели неупорядоченные элементы находятся в левой части массива (размерность этой части пока неизвестна). Кроме того, нам нужно знать местонахождение элемента, то есть его индекс.
// k - индекс минимального элемента
for (i=k=0; i< граница неотсорт.части; i++)
if (A[i] < A[k]) k=i;Выбранный элемент необходимо сохранить в промежуточной переменной.
Для сдвига элементов на один влево также имеется стандартный программный контекст:
for (int i=a; i<b; i++) A[i]=A[i+1];Выбранный элемент помещается в конец неупорядоченной части.
Процесс сортировки является повторяющимся. Каждый его шаг подразумевает выполнение перечисленных действий, причем справа в массиве располагается отсортированная часть, а слева – оставшаяся исходная. На каждом шаге граница частей смещается влево.
Начало проектирования. В соответствии с принципами модульного проектирования программа представляет собой функцию, получающую все входные данные через формальные параметры. Массив передается по ссылке, то есть сортировка производится в нем самом.
//---- Сортировка выбором. Шаг 0.
void sort(int A[], int n){
Ш1: сортировать A[] выбором
}Пошаговое нисходящее проектирование. Данный пример является простым потому, что внешняя конструкция прямо бросается в глаза. Сущность сортировки заключается в повторении выполнения одного и того же действия - шага сортировки, о чем в списке фактов говорит п.5..
//---- Сортировка выбором. Шаг 1.
void sort(int A[], int n){
Ш1: повторять шаг сортировки (п.5 из списка фактов).
}Однако для записи цикла нам необходимо определить его параметр и его содержательную интерпретацию, «смысл» переменной. Пусто это будет длина отсортированной части – i. Тогда длина неотсортированной части будет вычисляться как n-i (понадобится в дальнейшем).
//---- Сортировка выбором. Шаг 1.
void sort(int A[], int n){
Ш1: for(int i=0; i<n; i++){
Ш2: Шаг сортировки. i – длина отсортированной части
}
}Шаг сортировки включает в себя последовательность действий, перечисленных в пп.1-4 списка фактов. Поставленные «для надежности» фигурные скобки в теле цикла оказались кстати: синтаксически последовательность действий образует блок. Для связи шагов последовательности необходимо определить две переменные: индекс минимального элемента – k и извлеченное значение, хранимое в переменной v.
//---- Сортировка выбором. Шаг 2.
void sort(int A[], int n){
Ш1: for(int i=0; i<n; i++){
Ш2: последовательность действий пп.1-4
}
}
//---- Сортировка выбором. Шаг 2.
void sort(int A[], int n){
for(int i=0; i<n; i++){ // i – длина отсортированной части
int k; // k – индекс минимального элемента
int v; // v – сохраненное выбранное значение
Ш3: найти max в неотсортированной части // kß
Ш4: сохранить минимум в v // kà vß
Ш5: сдвинуть «хвост» влево // k,n,ià
Ш6: записать сохраненный последним // v,n,ià
}
}Дальнейшая формализация фрагментов идет по линии наименьшего сопротивления. Сначала просто переведем «слова» в операции и операнды, используя «смысл» уже определенных переменных: сохранение и запись – присваивание, сохраненный – v, последний из неупорядоченных – A[n-i-1], минимальный – A[k].
Ш4: v=A[k];
Ш6: A[n-i-1]=v;Для оставшихся фрагментов используются стандартные программные контексты, в которых в заголовках циклов поставлены необходимые границы. В каждом цикле используется своя рабочая переменная j – индекс текущего элемента.
jnt j;
Ш3: for(k=j=0; j<n-i; j++) // До границы неотсортированной части
if (A[j]<A[k]) k=j;
Ш5: for(j=k; j<n-i-1; j++) // От максимального до конца неупорядоченной части
A[j]=A[j+1];Окончательный вариант.
//------------------------------------------------------36-01.cpp
//---- Сортировка выбором. Окончательный вариант.
void sort(int A[], int n){
for(int i=0; i<n; i++){ // i длина отсортированной части
int k; // k индекс минимального элемента
int v; // v сохраненное выбранное значение
int j;
for(k=j=0; j<n-i; j++) // Ш3
if (A[j]>A[k]) k=j;
v=A[k]; // Ш4
for(j=k; j<n-i-1; j++) // Ш5
A[j]=A[j+1];
A[n-i-1]=v; // Ш6
}}Замечание: вместо сдвига можно использовать простой обмен максимального элемента в последним из оставшихся, программа от этого только выиграет:
int c=A[k]; A[k]=A[n-i-1]; A[n-i-1]=c; // Вместо Ш4,Ш5,Ш6Задача на вычеркивание
Из n-значного числа нужно вычеркнуть m цифр таким образом, чтобы оставшееся число было максимальным из возможных.
Образная модель. На примере этой задачи можно видеть, что образной модели может предшествовать обсуждение идей, положенных в основу решения. И не всегда, казалось бы, здравая идея дает правильное (универсальное) решение.
Например, естественно предположить, что для того, чтобы оставить максимальное число, необходимо вычеркивать минимальные цифры. Однако, такой простой пример, как 120 (n=3,m=1), показывает, что эта идея работает не всегда (правильный результат 120) . Аналогично, для 53784564 (n=8 m=4) получаем 53784564 вместо 53784564. Видимо, необходимо учитывать не только значение цифры, но и ее положение.
Попробуем рассуждать по-другому, с точки зрения всех возможных вариантов решения для заданного числа. Для того, чтобы оставшееся число было максимальным, в старшей позиции должна быть максимальная из возможных цифр. Поскольку вычеркивать можно не больше, чем m цифр, то следует найти максимальную из m+1 цифр и вычеркнуть все предыдущие (54378564 при n=8 m=4). Эта идея и является основой процесса решения задачи.
Вопрос, что делать дальше. Ответ простой: для оставшейся части числа решается та же задача (4564 при n=4 m=1) – 4564. Процесс повторяется, пока нечего будет вычеркивать (при 64 n=2 m=0).
В образной модели обсуждается также и способ представления данных. Нам удобно хранить и обрабатывать цифры числа по отдельности, а при вычеркивании цифры просто заменять ее на некоторое недопустимое значение, например на -1. Тогда цифры при вычеркивании цифр не потребуется их перемещения в массиве.
Сбор фактов осуществляется по принципу «исторического» программирования. Мы рассмотрим первый шаг алгоритма, а потом попытаемся внести коррективы.
Исходное число представлено в массиве, содержащем его цифры A[], а также входными параметрами – исходное количество цифр – n и вычеркиваемое – m.
Выбирается максимальная цифра (элемент массива) от начала в диапазоне m-1;
Затем «удаляются» (заменяются на -1) значения цифр от начала до найденной максимальной. При этом корректируется значение m – количество оставшихся цифр.
Для оставшейся части процесс необходимо повторить. В технологии «исторического» программирования этому соответствует «переход к п.2», структурное программирование требует введения цикла повторения: повторять пп.2,3, пока m не станет равным 0 (нечего вычеркивать).
Этим набор действий, выполняемых в программе, исчерпывается. Можно сразу же набросать структурированную схему программы, выполнив 3 шага проектирования.
Ш1: void F(int A[], int n, int m){
Ш2: п4 while(m!=0){
Ш3: последовательность п2,п3
}Все-таки мы здесь немного забежали вперед, поскольку не определили характеристик цикла из Ш2. На первом шаге он выполняется от начала массива, но на всех других, от цифры, следующей за найденной – максимальной. Это типичный пример итерационного цикла (см. 4.3). После того, как мы введем две переменные, все встанет на свои места: i – индекс очередной максимальной цифры, k – начало интервала просмотра цифр на очередном шаге.
Ш1: void F(int A[], int n, int m){
int s,k=0; // s – индекс максимальной цифры
Ш2: п4 while(m!=0){ // k – начало интервала просмотра
Ш3: последовательность п2,п3
k=s+1; // интервал начинается за макс. цифрой
}Дальше нужно сформулировать подробнее п2,п3, а затем формально их расписать:
Ш1: void F(int A[], int n, int m){
int s,k=0; // s – индекс максимальной цифры
Ш2: п4 while(m!=0){ // k – начало интервала просмотра
Ш3: последовательность п2,п3
Ш4:
п2 найти максимум в A[] в диапазоне, начиная с k длиной m+1
результат – индекс максимального значения s
п3 A[j]=-1 в диапазоне от k до s-1, корректируя s
k=s+1; // интервал начинается за макс. цифрой
}
Ш5: п2 найти максимум в A[] в диапазоне, начиная с k длиной m+1
for (s=j=k; j<k+m+1;j++)
if(A[j]>A[s]) s=j;
Ш6: п3 A[j]=-1 в диапазоне от k до s-1, корректируя s
for (j=k;j!=s;j++,m--) A[j]=-1;В результате получим программу, которая будет работать на приведенных выше примерах.
//---------------------------------------------------------------------------
// Вычеркивание цифр: вычеркнуть из n-значного числа
// m цифр, чтобы осталось максимальное
void F(int A[], int n, int m){
int s,j,k=0; // k - начало интервала просмотра
while(m!=0){ // пока есть что вычеркивать
for (s=j=k; j<k+m+1;j++) // Найти максимальную цифру в
if(A[j]>A[s]) s=j; // интервале k..k+m (включительно)
for (j=k;j!=s;j++,m--) // Вычеркнуть цифры перед максимальной
A[j]=-1;
k=s+1; // Пропустить максимальную
}}Однако, стоит на значении 98765432, при n=8 и m=4 программы «вывалится». Если попытаться проанализировать поведение программы, либо просто проследить за ней при помощи отладчика, то мы увидим следующее: максимальная цифра находится в начале диапазона, поэтому на каждом шаге вычеркивания не будет¸ а начало будет смещаться на 1. В результате программа зациклится, выйдет за пределы массива и, скорее всего, «вывалится» по защите памяти (особенности Си, точнее, его адресной арифметики).
Ошибка вида «крайняя ситуация»
Обнаруженная ошибка является типичной ошибкой, которая возникает из-за неучтенной крайней ситуации. Дело в том, что образная модель просматривается нами на конкретном примере, не учитывающем многообразие вариантов выходных данных, т.е. для некоторого усредненного случая. Поэтому, общей рекомендацией является перечисление всех «крайних ситуаций», которые могут возникнуть в программе от различных сочетаний входных данных. Это можно сделать уже по написанному коду. Для каждой из них возможны два варианта:
написанный код адекватно реагирует на сочетание данных, соответствующих «крайней ситуации», в программе ничего менять не надо;
программа работает неправильно. В этом случае достаточно бывает наложить «заплатку», вылавливающую «крайнюю ситуацию» и содержащую правильной программный код.
В нашем примере в образной модели мы пропустили ситуацию, когда количество вычеркиваемых цифр станет равным количеству оставшихся (именно она возникла на последнем сочетании данных). Исправить ее достаточно просто. В основной цикл нужно добавить условие выхода по n==m, а после выхода добавит цикл вычеркивания, если m!=0. Причем вычеркивать нужно от начала текущего диапазона (т.е. k).
//------------------------------------------------36-02
// Вычеркивание цифр: вычеркнуть из n-значного числа
// m цифр, чтобы осталось максимальное
void F(int A[], int n, int m){
int s,j,k=0; // k - начало интервала просмотра
while(!(m==0 || m==n)){ // есть что вычеркивать или вычеркивать все
for (s=j=k; j<k+m+1;j++) // Найти максимальную цифру в
if(A[j]>A[s]) s=j; // интервале k..k+m (включительно)
for (j=k;j!=s;j++,m--) // Вычеркнуть цифры перед максимальной
A[j]=-1;
k=s+1; // Пропустить максимальную
}
while(m--!=0) A[k++]=-1; // вычеркивать все
}Отладка: две программы – в компьютере и в голове
Большинство начинающих искренне считают, что их программа должна работать уже потому, что она написана. На самом деле отладка программы является еще более трудным делом, чем ее написание. Это только так кажется, что программист в состоянии контролировать разработанную им программу. На самом деле число возможных вариантов ее поведения, обусловленных как логикой программы, так ошибками, разбросанными там и сям по ее тексту, чрезвычайно велико. Отсюда следует, что к собственной программе следует относиться скорее как к противнику в шахматной игре: фигуры расставлены, правила известны, число возможных ходов не поддается логическому анализу.
Основной принцип отладки: работающая программа на самом деле находится в голове программиста. Реальная программа в компьютере – лишь грубое к ней приближение. Программист должен отследить, когда между ними возникает расхождение – в этом месте и находится очередная ошибка. Для этой цели служат средства отладки. Они позволяют наблюдать поведение программы: значения выбранных переменных при пошаговом ее выполнении, при выполнении ее до заданного места (точки останова), либо до момента выполнения заданных условий.
В отладке программы, как и в ее написании существует своя технология, сходная со структурным программированием:
нельзя отлаживать все сразу. На каждом этапе проверяется отдельный фрагмент, для чего программа должна проходить только по уже протестированным частям, «внушающим доверие».
отладку программы нужно начинать на простых тестовых данных, обеспечивающих прохождение программы по уже отлаженным фрагментам. Входные данные для отладки лучше не вводить самому, а задавать в виде статических последовательностей в массивах или в файлах;
если поведение программы не поддается анализу и определить местонахождение ошибки невозможно, необходимо произвести «следственный эксперимент»: проследить выполнение программы на различных комбинациях входных данных, набрать статистику уже на ее основе строить догадки и выдвигать гипотезы, которые в свою очередь нужно проверять на новых данных;
модульному программированию соответствует модульное тестирование. Отдельные модули (функции, процедуры) следует сначала вызывать из головной программы (main) и отлаживать на тестовых данных, а уже затем использовать по назначению. Вместо ненаписанных модулей можно использовать «заглушки», дающие фиксированный результат;
нисходящему программированию соответствует нисходящее тестирование. Внутренние части программы аналогично могут быть заменены «заглушками», позволяющими частично отладить уже написанные внешние части программы.
Ошибки лучше всего различать не по сложности их обнаружения и не по вызываемым ими последствиям, а по затратам на их исправление:
мелкие ошибки типа «опечаток», которые обусловлены просто недостаточным вниманием программиста. К таковым относятся неправильные ограничения цикла (плюс-минус один шаг), использование не тех индексов или указателей, использование одной переменной одновременно в двух «смыслах» и т.п.;
локальные ошибки логики программы, состоящие в пропуске одного из возможных вариантов ее работы или сочетания входных данных, ошибка вида «крайняя ситуация»;
грубые просчеты, связанные с неправильным образным представлением того, что и как должна делать программа. Это «идейные» ошибки, когда предложенная идея либо просто не работает, либо дает правильный результат не во всех случаях.
«Любая программа в любой момент содержит как минимум одну ошибку». Программистский фольклор.
