Книга: Технологии программирования
5.10. ПРИМЕР ВЫПОЛНЕНИЯ УЧЕБНОЙ РАБОТЫ "РАЗРАБОТКА АЛГОРИТМА УМНОЖЕНИЯ"
5.10. ПРИМЕР ВЫПОЛНЕНИЯ УЧЕБНОЙ РАБОТЫ "РАЗРАБОТКА АЛГОРИТМА УМНОЖЕНИЯ"
В качестве примера приводится учебная работа, выполненная одним из обучаемых. Работа была оформлена на отдельных листах формата A4. Курсивом выделены пояснения авторов учебника, которые были дополнительно ими внесены в текст работы.
Страница 1 (без нумерации) представляет собой титульный лист с наименованием: "ЗАДАНИЕ НА СОСТАВЛЕНИЕ СТРУКТУРИРОВАННОГО АЛГОРИТМА".
Страница 2 содержит постановку задачи и набор тестов, составленных до разработки алгоритма процесса.
Шаг 1. ПОСТАНОВКА ЗАДАЧИ
Составить алгоритм умножения двух положительных чисел с произвольным (до ста) количеством цифр. Цифры сомножителей и результата должны находиться в одномерных массивах. Разрядность результата не должна превышать 100 цифр.
Шаг 2. НАБОР ТЕСТОВ, СОСТАВЛЕННЫХ ДО РАЗРАБОТКИ АЛГОРИТМА ПРОЦЕССА
Пусть предельная разрядность сомножителей равна трем цифрам, а результата — четырем. Аналогично приведенному образцу умножения чисел 391*56 = 21896 (переполнение) были составлены тесты: 23*132 = 3036; 111*11 = 1221; 999*99 = 98901 (переполнение); 00*000 = 0; 1*0 = 0.
Алгоритм умножения обычно изучался в младших классах школы по маршрутному описанию процесса счета. Из-за теоретической огромности числа маршрутов большинство со школьной скамьи не знает процесса умножения при нулевых сомножителях!
Страница 3 содержит результаты анализа выходной и входной информации вычислительного процесса со структурами данных. Рациональность избранной структуры данных в значительной мере определяет рациональность алгоритма.
Шаг 3. АНАЛИЗ ВЫХОДНОЙ И ВХОДНОЙ ИНФОРМАЦИИ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
Анализ выходной и входной информации начинается с рассмотрения модели "черного" ящика, показанной на рис. 5.3.
Program MultNumbers;
{Расчет произведения двух чисел}
uses
Crt;
const
Digits = 100; {Число цифр в числах}
type
TNumber = record
D: array[1..Digits] of Byte;
{B D[1] находится младший разряд числа}
N: word; {Число разрядов в числе от 1 до Digits}
end;
var
C1: TNumber; {Первый сомножитель}
C2: TNumber; {Второй сомножитель}
R: TNumber; {Результат умножения}
Error: boolean; {True — ошибка переполнения}
Макет экрана со строками диалога программы приведен на рис. 5.17. Вместо трех последних строк возможен вывод: "Ошибка переполнения".
Страница 4 содержит наглядное изображение процесса преобразования входных данных обобщающего теста или тестов в выходные данные со всеми внутренними данными и/или трассу выполнения обобщающего теста или тестов. Обобщающий тест или тесты составляются на основе тестов страницы 2 и при минимальном количестве тестов охватывает все маршруты процесса вычислений. Наглядность изображения изменений всех данных способствует упрощению процесса разработки алгоритма. Рациональность избранной структуры данных в значительной мере определяет рациональность алгоритма.
Рис. 5.17. Макет экрана со строками диалога программы
Шаг 4. НАГЛЯДНОЕ ИЗОБРАЖЕНИЕ ПРОЦЕССА ПРЕОБРАЗОВАНИЯ ВХОДНЫХ ДАННЫХ ОБОБЩАЮЩЕГО ТЕСТА В ВЫХОДНЫЕ
Вводим описание новых внутренних переменных:
var {Рабочие переменные}
i, j: word;
На первый взгляд, кажется, что необходимо ввести переменное количество промежуточных массивов (в зависимости от количества цифр второго сомножителя) для запоминания продукта умножения первого сомножителя на очередную цифру второго сомножителя. Однако внимательный анализ структур данных позволяет найти иной способ выполнения расчетов. При этом способе сначала обнуляется результат. Далее результат последовательно увеличивается на сдвинутый на разряд влево продукт умножения первого сомножителя на очередную цифру второго сомножителя. Переоформляем наглядное изображение процесса преобразования входных данных обобщающего теста.
На странице 4 или следующей иногда полезно поместить описание алгоритма в обыденном неструктурированном понимании.
Каждая последующая страница содержит результаты процесса детализации очередной выделенной от общего к частному структуры.
Шаг 5. ПОСЛЕДОВАТЕЛЬНОСТЬ ДЕТАЛИЗАЦИИ АЛГОРИТМА
Шаг 5.1. Результаты детализации СЛЕДОВАНИЯ "Вся программа"
Следование "Вся программа" детализируется ЦЕПОЧКОЙ СЛЕДОВАНИЙ:
begin
ClrScr; {Очистка экрана}
{Ввод корректного значения числа цифр первого сомножителя}
C1.N
Write('Вводите цифры первого сомножителя ');
{Ввод цифр первого сомножителя в порядке от C1.D[C1.N] до C1.D[1]}
C1.D
WriteLn;
{Ввод корректного значения числа цифр второго сомножителя}
С2.N
Write('Вводите цифры второго сомножителя ');
{Ввод цифр второго сомножителя в порядке от C2.D[C2.N] до C2.D[1]}
WriteLn;
{Расчет произведения сомножителей}
R.D R.N Error
{Устранение лидирующих нулей}
WriteLn;
{Вывод результата произведения}
WriteLn;
end.
Без отступов показана входная и выходная информация структур, которая использовалась при проверке информационной согласованности СЛЕДОВАНИЙ в ЦЕПОЧКЕ СЛЕДОВАНИЙ.
СЛЕДОВАНИЕ "Устранение лидирующих нулей" необходимо при использовании сомножителя, состоящего из нескольких нулей.
Шаг 5.2. Детализация СЛЕДОВАНИЯ "Ввод корректного значения числа цифр первого сомножителя"
СЛЕДОВАНИЕ "Ввод корректного значения числа цифр первого сомножителя" декомпозируется циклом:
{Ввод корректного значения числа цифр первого сомножителя}
repeat
Write('Введите число цифр первого сомножителя');
Write(' от 1 до ', Digits, ' ');
ReadLn(C1.N);
until ((C1.N >= 1) and (C1.N <= Digits));
Цикл оттестирован тремя тестами: C1.N=1; C1.N=3; C1.N=Digits.
Аналогично декомпозируется процесс "Ввод корректного значения числа цифр второго сомножителя".
Шаг 5.3. Детализация СЛЕДОВАНИЯ "Ввод цифр первого сомножителя в порядке от C1.D[C1.N] до C1.D[1]
СЛЕДОВАНИЕ "Ввод цифр первого сомножителя в порядке от C1.D[C1.N] до C1.D[1] декомпозируется циклом:
{Ввод цифр первого сомножителя в порядке от C1.D[C1.N] до C1.D[1]}
for i:= C1.N downto 1 do begin
{До ввода корректного символа цифры}
repeat
ch:= ReadKey; {Чтение символа клавиатуры}
Val(ch, C1.D[i], InCode); {Преобразование в значение}
until(InCode = 0);
Write(ch);
end;
Описания новых переменных:
var {Рабочие переменные}
InCode: word;
ch: Char;
Несмотря на то что здесь в нарушение правил детализировано сразу два цикла, в тестировании нет необходимости.
Аналогично декомпозируется процесс "Ввод цифр второго сомножителя в порядке от C2.D[C2.N] до C2.D[1].
Шаг 5.4. Детализация СЛЕДОВАНИЯ "Вывод результата произведения"
СЛЕДОВАНИЕ "Вывод результата произведения" декомпозируется АЛЬТЕРНАТИВОЙ — РАЗВИЛКА С ДВУМЯ ДЕЙСТВИЯМИ:
{Вывод результата произведения}
if ERROR
then
WriteLn(Ошибка переполнения)
else
begin
{Вывод продукта умножения}
end;
Тесты: ERROR = True; ERROR = False.
Шаг 5.5. Детализация СЛЕДОВАНИЯ "Вывод продукта умножения"
СЛЕДОВАНИЕ "Вывод продукта умножения" декомпозируется циклом:
{Вывод продукта умножения}
for i:= R.N downto 1 do
Write(R.D[i]);
В тестировании нет необходимости.
Шаг 5.6. Детализация СЛЕДОВАНИЯ "Устранение лидирующих нулей"
СЛЕДОВАНИЕ "Устранение лидирующих нулей" декомпозируется циклом:
{Устранение лидирующих нулей}
while ((R.N > 1) and (R.D[i] = 0)) do
Dec(R.N); {R.N:= R.N — 1}
В тестировании нет необходимости.
Шаг 5.7. Детализация СЛЕДОВАНИЯ "Расчет произведения сомножителей"
СЛЕДОВАНИЕ "Расчет произведения сомножителей" декомпозируется циклом:
Вход: C1, C2.
{Расчет произведения сомножителей}
{Цикл задает номер j очередной цифры второго сомножителя}
ERROR:= False;
j:= 1;
R.D[1]:= 0;
while ((j <= C2.N) and
(not(ERROR))) do
begin
{Увеличение результата на сдвинутый продукт умножения первого сомножителя на j-ю цифру второго сомножителя}
Inc(j); {j:= j + 1}
end;
Выход: R.D, R.N, ERROR
Структура тестировалась на тестах: 390*56; 390*56, но при Digits = 5; 0*0 при C1.N = 0; 1*0 при C1.N = 1 и других тестах.
Шаг 5.8. Детализация СЛЕДОВАНИЯ "Увеличение результата на сдвинутый продукт умножения первого сомножителя на j-ю цифру второго сомножителя
СЛЕДОВАНИЕ детализируется циклом:
Вход: C1, C2.
{Увеличение результата на сдвинутый продукт умножения первого сомножителя на j-ю цифру второго сомножителя}
p:= 0;
i:= 0; {Номер цифры первого сомножителя}
while(((i < C1.N) or (p <> 0)) and (not(ERROR))) do
begin
Inc(i);
{Расчет очередной цифры результата и цифры переноса}
end;
Выход: R.D, R.N, ERROR
Шаг 5.9. Детализация СЛЕДОВАНИЯ "Расчет очередной цифры результата и цифры переноса"
СЛЕДОВАНИЕ детализируется альтернативой:
Вход: i, j, C1.D[i], C2.D[j], p, R.D, Digits.
{Расчет очередной цифры результата и цифры переноса}
{Контролируемый расчет ir — номера очередной цифры результата}
ir:= i + j — 1;
if (ir > Digits) then
ERROR:= True else
begin
{Изменение длины результата R.N}
if (R.N < ir)
then
begin
R.N:= ir;
R.D[ir]:= 0; {Обнуление новой цифры результата}
end;
{Получение очередной цифры C1D первого сомножителя}
if (i <= C1.N) then C1D:= C1.D[i] else C1D:= 0;
{Изменение очередной цифры результата и p}
RD:= р + R.D[ir] + C1D * С2.D[j];
R.D[ir]:= RD mod 10;
p:= RD div 10;
end;
Выход: R.D, R.N, ERROR, p.
Описания новых переменных:
var
ir, C1D, RD: word; {Рабочие переменные}
Шаг 6. РЕЗУЛЬТАТЫ СБОРКИ ПРОГРАММЫ
Program MultNumbers;
{Расчет произведения двух чисел}
uses
Crt;
const
Digits = 100; {Число цифр в числах}
type
TNumber = record
D: array[1..Digits] of Byte;
{BD[1] находится младший разряд числа}
N: word; {Число разрядов в числе от 1 до Digits}
end;
var
C1: TNumber; {Первый сомножитель}
C2: TNumber; {Второй сомножитель}
R: TNumber; {Результат умножения}
Error: boolean; {True — ошибка переполнения}
var
p: word; {Значение числа переноса при умножении C1.D на очередную цифру C2.D}
var {Рабочие переменные}
i, j, ir, C1D, RD, InCode: word;
ch: char; begin
ClrScr; {Очистка экрана}
{Ввод корректного значения числа цифр первого сомножителя}
repeat
Write('Введите число цифр первого сомножителя)
Write(' 1 до ', Digits, ' ');
ReadLn(C1.N);
until ((C1.N >= 1) and (C1.N <= Digits));
Write('Вводите цифры первого сомножителя ');
{Ввод цифр первого сомножителя в порядке от C1.D[C1.N] до C1.D[1]}
for i:= C1.N downto 1 do
begin
{До ввода корректного символа цифры}
repeat
ch:= ReadKey; {Чтение символа клавиатуры}
Val(ch, C1.D[i], InCode); {Преобразование в значение}
until(InCode = 0);
Write(ch);
end;
WriteLn;
{Ввод корректного значения числа цифр второго сомножителя}
repeat
Write('Введите число цифр второго сомножителя');
Write(' от 1 до ', Digits,' ');
ReadLn(C2.N);
until ((C2.N >= 1) and (C2.N <= Digits));
Write('Вводите цифры второго сомножителя ');
{Ввод цифр второго сомножителя в порядке от C2.D[C2.N] до C2.D[1]}
for i:= C2.N downto 1 do
begin
{До ввода корректного символа цифры}
repeat
ch:= ReadKey; {Чтение символа клавиатуры}
Val(ch, C2.D[i], InCode); {Преобразование в значение}
until(InCode = 0);
Write(ch);
end;
WriteLn;
{Расчет произведения сомножителей}
{Цикл задает номер j очередной цифры второго сомножителя}
ERROR:= False;
j:= 1;
R.D[1]:= 0;
while ((j <= C2.N) and (not(ERROR))) do
begin
{Увеличение результата на сдвинутый продукт умножения первого сомножителя на j-ю цифру второго сомножителя}
Р:= 0;
i:= 0; {Номер цифры первого сомножителя}
while(((i < C1.N) or (p <> 0)) and (not(ERROR))) do
begin
Inc(i);
{Расчет очередной цифры результата и цифры переноса}
{Контролируемый расчет ir — номера очередной цифры результата}
ir: = i + j — 1;
if (ir > Digits) then
ERROR:= True
else
begin
{Изменение длины результата R.N}
if (R.N < ir)
then
begin
R.N:= ir;
R.D[ir]:= 0; {Обнуление новой цифры результата}
end;
{Получение очередной цифры C1D первого сомножителя}
if (i <= C1.N)
then
C1D:= C1.D[i]
else
C1D:= 0;
{Изменение очередной цифры результата и p}
RD:= p + R.D[ir] + C1D * C2.D[j];
R.D[ir]:= RD mod 10;
p:= RD div 10;
end;
end;
Inc(j); {j:= j + 1}
end;
{Устранение лидирующих нулей}
while ((R.N > 1) and (R.D[i] =0)) do
Dec(R.N); {R.N:= R.N — 1}
WriteLn;
{Вывод результата произведения}
if ERROR
then
WriteLn('Ошибка переполнения')
else
begin
{Вывод продукта умножения}
for i:= R.N downto 1 do
Write(R.D[i]);
end;
WriteLn;
end.
По окончании сборки программы имеет смысл еще раз отредактировать комментарии с изъятием "лишних" комментариев.
Оглавление книги
- 5.1. ОБЩИЕ СВЕДЕНИЯ О ПРОЕКТНОЙ ПРОЦЕДУРЕ
- 5.2. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ПРОЕКТНОЙ ПРОЦЕДУРЫ
- 5.3. ОБЩЕЕ ОПИСАНИЕ ПРОЕКТНОЙ ПРОЦЕДУРЫ
- 5.4. РЕКОМЕНДАЦИИ НАЧИНАЮЩИМ ПО СОСТАВЛЕНИЮ ОПИСАНИЙ АЛГОРИТМОВ И ЭВРОРИТМОВ
- 5.5. ПРИМЕР РАЗРАБОТКИ ОПИСАНИЯ ПРОЦЕССА "КИПЯЧЕНИЕ ВОДЫ В ЧАЙНИКЕ"
- 5.6. ПРИМЕР ОПИСАНИЯ ПРОГРАММЫ "РЕДАКТОР ТЕКСТОВ"
- 5.7. РЕФАКТОРИНГ АЛГОРИТМОВ И ЭВРОРИТМОВ
- 5.8. КОДИРОВАНИЕ ТИПОВЫХ СТРУКТУР НА ЯЗЫКАХ ПРОГРАММИРОВАНИЯ
- 5.9. МЕТОДИКА РАЗРАБОТКИ АЛГОРИТМОВ ПРОГРАММ
- 5.10. ПРИМЕР ВЫПОЛНЕНИЯ УЧЕБНОЙ РАБОТЫ "РАЗРАБОТКА АЛГОРИТМА УМНОЖЕНИЯ"
- 5.11. ПРИМЕР ПРИМЕНЕНИЯ ПРОЕКТНОЙ ПРОЦЕДУРЫ ДЛЯ КОДИРОВАНИЯ ПРОГРАММЫ ПЕЧАТИ КАЛЕНДАРЯ НА ПРИНТЕРЕ
- Восстановление "безнадежных" баз данных. InterBase Surgeon
- Основные "рычаги" управления производительностью
- Разработка через тестирование и разработка с тестами
- 2.5. Разработка технического задания на проведение детального анализа рынка при работе над инновационным проектом. Основ...
- Разработка приложений баз данных InterBase на Borland Delphi
- Вам очень пригодится «Разработка ценностных предложений», если…
- Using Double Quotes to Resolve Variables in Strings with Embedded Spaces
- Глава 5. Разработка и анализ бизнес-планов в системе Project Expert
- 2.2. Практическая разработка фирменного стиля компании 51
- Разработка формы
- Разработка медиаплана
- 4.11.4. Правила "все кроме"