Лекции по информатики 2 (стр. 22 из 43)

Четвертая задача: Определить суммы элементов столбцов в матрице A_nxm:

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

Постановка задачиСценарий

Дано: Матрица <N>´<M>

(a₁₁ … a_1N) < a₁₁> ... < a_1N >

(... ... ... ) - матрица Anxm... ... ...

(a_Ml … a_MN) < a_Ml> … < a_MN >

Треб.: Суммы элементов:

(S₁ ..., S_N) - суммы столбцов <S₁> ... <S_N>

Где:

S_i = а_i1 + ...+ а_iM

[i = (1… N)]

При: N > 0, М > 0.

Метод вычисленийПредставление данных

sk0 = 0 matr:' матрица Anm:

s_k1⁼ a_k1⁺ s_k1-1 data3, 4

[1 = (1 ... M)] data I, 2, 3, 4

S_k = S_kN data 0, 1, 2, 3

[k = (1 ... N)] data 0, 0, 1, 2

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

АлгоритмПрограмма

алг «сумма строк матрицы»' сумма строк матрицы

нач cls

чтение (п, т) . read n, m

если п > 0 и т > 0 то if N > 0 and М > 0 then

массив А[1:п,1:т] dim A (N,M)

массив S[1:n] dim S(n)

ввод-вывод_матрицы gosub vvod 'ввод-матрицы

суммирование_строкgosub sum 'суммирование

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

выв (s[k])? s[k]

кцикл next k

все end if

кон end

алг «суммирование строк» sum: 'суммирование строк

нач' нач

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

s[k] := 0 s[k] = 0

от l = 1 до М цикл for I = 1 to m

s[k] := s[k] +A[k,l] s[k] = s[k] + a[k,l]

кцикл next I

кцикл next k

кон return

алг «ввод-вывод_матрицы» vvod: 'ввод-вывод_матрицы

нач' нач

вывод («Матрица», N, «х», М)? «Матрица»; m; «х»; m

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

от I = 1 до М цикл for l = 1 to m

чтение (A [k,l]) read A (k,l)

вывод (A [k,l])? A (k,l)

кцикл next 1

нов_строка?

кцикл next k

кон return

В о п р о с ы

1. Что такое постановка задачи?

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

3. Что такое способ решения?

4. Что такое метод решения?

5. Каков порядок решения новых задач?

6. Что такое систематическая разработка алгоритмов и программ?

З а д а ч и

1. Приведите постановку задачи, сценарий, алгоритм и программу подсчета сумм:

а) нечетных чисел;

б) квадратов целых чисел;

в) кубов целых чисел.

2. Приведите постановку задачи, сценарий, алгоритм и программу подсчета сумм:

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

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

3. Для последовательности чисел х₁, х₂ ..., х_N приведите постановку задачи, составьте сценарий, алгоритм решения и программу:

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

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

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

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

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

а) самого высокого ученика; г) самого легкого ученика;

б) самого низкого ученика; д) средний рост учеников;

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

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

а) определения ровесников;

б) определения людей, родившихся в один день;

в) самого молодого из своих друзей и родных;

г) самого старшего из своих родных и друзей.

5.2. Анализ правильности алгоритмов

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

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

Проявления ошибок:

Программа

¯

данные ® ЭВМ ® { отказ | сбой | ошибка }

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

Сбой - это потеря части данных либо получение непредусмотренных данных. Такого рода ошибки говорят о их частичной неработоспособности программ либо об их недостаточной надежности.

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

Оценка программ:

Задача

исходное требуемое

данные ® программа ® результаты

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

В качестве примера рассмотрим решение квадратного уравнения:

х² + 3×х + 2 = 0.

Исходные данные - коэффициенты – а = 1, b = 3, с = 2. Требуемые результаты - пара чисел х₁ и x₂, являющихся корнями уравнения. Посмотрим, будут ли корнями уравнения пары чисел:

а) х₁ = 2, x₂ = 3;б) x₁ = -2, x₂ = -3.

Решением уравнений являются числа, подстановка которых превращает уравнение в тождество. В первом случае подстановка чисел х₁ = 2, х₂ = 3 в уравнение дает:

2² + 3×2 + 2 = 12 ¹ 0 - неправильно,

3² +3×3+2 = 20 ¹ 0 - неправильно.

Следовательно, числа х₁ = 2, х₂ = 3 не являются правильными результатами.

Подстановка в уравнение чисел х₁ = -2, х₂= -3:

(-2)² + 3×(-2) +2 = 0- правильно;

(-3)² + 3×(-3) +2 = 0- правильно.

Следовательно, числа х₁ = -2, х₂= -3 являются правильными результатами.

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

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

Решение квадратного уравнения

а×х² + b×x + с = 0.

Дано: a, b, с - коэффициенты.

Треб.: х₁, х₂ - корни.

Где: а×х₁² + b×х₁ + с = 0.

а×х₂² + b×х₂ + с =0.

При: а ¹ 0.

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

Способ правильный, если он дает правильные результаты. Способ неправильный, если он дает неправильные результаты или не дает результатов вообще.

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

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

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

Метод решения

x₁ = (-b + )/(2×а),

x₂= (-b -

)/(2×a),

где

{ D = b² - 4×а×с.

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

Для первого корня х₁= (-b +

)/(2×a) подстановка и тождественные преобразования формул дадут:

а×х₁² + b×х₁ + с = а×[(-b +

)/(2×а)]² + b× (-b + )/(2×a) + с =