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

Рисунок 7.1 – Алгоритм, использующий вложенные циклы

Следует отметить, что в рассмотренном ранее алгоритме вычисления суммы (пример 5.4) начальное значение переменной S обнулялось, при вычислении произведения начальное значение переменной Р задается равным 1.

Наиболее распространенными ошибками при решении подобных задач являются следующие.

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

2. Вывод результата за пределами циклов перебора элементов матрицы. В этом случае будет выведено значение произведения для элементов последней строки матрицы.

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

 

Пример 7.2. Удалить в строке начальные пробелы.

Решение.

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

Таблица 7.1 – Операции по работе со строками

Слияние (S1, S2, …, Sn)	S1, S2, …, Sn – строки, которые необходимо слить.
Копирование (S, Start, Len)	S – строка, из которой, начиная с позиции Start, копируется подстрока длиной Len символов.
Длина (S)	S – строка, длину которой необходимо определить.
Позиция (Str, S)	S – строка, в которой ищется вхождение подстроки Str, и запоминается позиция первого символа этой подстроки. Если подстрока не найдена, то возвращается значение 0.
Удаление (S,Start,Len)	S – строка, из которой удаляется Len символов, начиная с позиции Start.
Вставка(Str, S, Start)	S – строка, в которую, начиная с позиции Start, вставляется подстрока Str.

Алгоритм.

 

Пример 7.3. В строке удалить все «нечетные» слова (слова, стоящие на нечетных позициях).

Решение.

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

К разделителям отнесем: пробел, знаки препинания (- . , ? ! : ; ” ), признак окончания строки.

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

1) строка не содержит ни одного символа – результатом в этом случае является сообщение о невозможности обработки;

2) строка содержит только разделители – результатом является сообщение о том, что в строке нет ни одного слова;

3) строка содержит кроме разделителей и другие символы - в этом случае каждое слово обрабатывается по следующей схеме:

- пропускаем в исходной строке все разделители, предшествующие текущему слову, и записываем их в результирующую строку;

- если слово «нечетное», то пропускаем все символы слова до ближайшего разделителя;

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

Входные данные: S:строка.

Выходные данные:

S1:строка;

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

Промежуточные данные:

i:цел. {номер текущего символа строки}

k:цел. {признак наличия слов в строке (при k=0 слов в строке нет, если k=1, то в строке есть хотя бы одно слово)}

Р:цел. {определяет «четность» или «нечетность» текущего слова (если Р=0, то текущее слово «четное», если Р=1, то текущее слово «нечетное»)}

Алгоритм.

 

8 ТРАССИРОВКА АЛГОРИТМОВ

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

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

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

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

В любой момент времени каждая переменная имеет лишь одно значение.

Пример 5.1. Проверить правильность составления алгоритма обмена значениями величин А и В.

Предположим, что был составлен следующий алгоритм:

А:=А+В

В:=А-В

А:=А-В

Проверим работу данного алгоритма. Пусть А=3, В=7. Выполним алгоритм и заполним трассировочную таблицу:

№ шага	А	В
	3	7
1	10
2		3
3	7
Результат	7	3

Видим, что после выполнения алгоритма А стало равным 7, а В стало равным 3, то есть эти величины обменялись значениями. Следовательно, для этих значений А и В алгоритм работает верно. Утверждать, что этот алгоритм будет так же правильно работать и при любых других значениях А и В, пока нельзя. Покажем это.

Возьмем произвольные значения для А и В: А=а, В=b и снова выполним трассировку алгоритма:

№ шага	А	В
	a	b
1	a+b
2		a
3	b
Результат	b	a

Таким образом, при любых значениях переменных А и В алгоритм приводит к правильному решению.

Пример 5.2. Проверить, решает ли следующий алгоритм задачу упорядочения по возрастанию значений А, В, С:

 

если A>B то

P:=A

A:=B

B:=P

если B>C то

P:=В

В:=С

С:=P

Решение.

Для тестирования разветвляющегося алгоритма необходимо иметь все комбинации значений исходных данных: A<B<C, A<C<B, B<A<C, B<C<A, C<A<B, C<B<A.

Будем выполнять алгоритм, последовательно перебирая эти варианты значений величин A, B, C.

1-й вариант: А=3, В=5, С=7.

№ шага	А	В	С	Р	Проверка условий
	3	5	7
1					3>5, Нет
2					5>7, Нет
Результат	3	5	7

Результат выполнения алгоритма верен.

2-й вариант: А=3, В=7, С=5.

№ шага	А	В	С	Р	Проверка условий
	3	7	5
1					3>7, Нет
2					7>5, Да
3				7
4		5
5			7
Результат	3	5	7

Результат выполнения алгоритма верен.

3-й вариант: А=5, В=3, С=7.

№ шага	А	В	С	Р	Проверка условий
	5	3	7
1					5>3, Да
2				5
3	3
4		5
5					5>7, Нет
Результат	3	5	7

Результат выполнения алгоритма верен.