Алгоритм решения задачи с математической формулировкой

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения

Факультет Радиотехники, Электроники и Связи

КАФЕДРА № 24

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ

по дисциплине: ИНФОРМАТИКА И ПРОГРАММИРОВАНИЕ

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. 2245

В.А. Фабричнов

Санкт-Петербург - 2013



Введение

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

Постановка задачи (задача, которую предстоит решать на ЭВМ, формулируется пользователем или получается им в виде задания).

Математическая формулировка задачи.

Разработка алгоритма решения задачи.

Написание программы на языке программирования.

Подготовка исходных данных.

Ввод программы и исходных данных в ЭВМ.

Отладка программы.

Тестирование программы.

Решение задачи на ЭВМ и обработка результатов.

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

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

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

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

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

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

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

Задание при обработке на ЭВМ проходит ряд шагов: компиляцию, редактирование (компоновку) и выполнение.

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



Теоретическая часть

Составим алгоритм для решения задач. На изображение схем алгоритмов существует ГОСТ 19.701-90, согласно которому каждой группе действий ставится в соответствие блок особой формы.

Некоторые используемые обозначения приведены в табл. 1.

Основные элементы схем алгоритма

Таблица 1

Наименование	Обозначение	Функция
Блок начало-конец (пуск-остановка)		Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение ? начало и конец программы). Внутри фигуры записывается соответствующее действие.
Блок вычислений (вычислительный блок)		Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания a = 10*b + c.
Логический блок (блок условия)		Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае ? сравнение (три выхода: >, <, =); в программировании ? условные операторы if (два выхода: true, false) и case (множество выходов).
Предопределенный процесс		Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании ? вызов процедуры или функции.
Данные (ввод-вывод)		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Граница цикла		Символ состоит из двух частей ? соответственно, начало и конец цикла ? операции, выполняемые внутри цикла, размещаются между ними. Условия цикла и приращения записываются внутри символа начала или конца цикла ? в зависимости от типа организации цикла. Часто для изображения на блок-схеме цикла вместо данного символа используют символ решения, указывая в нем условие, а одну из линий выхода замыкают выше в блок-схеме (перед операциями цикла).
Соединитель		Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения ее в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при том уникальное) обозначение.
Комментарий		Используется для более подробного описания шага, процесса или группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.



Задача №1. Умножить L столбец квадратной матрицы порядка N на заданное число A

Матрица -- математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля (например, целых, действительных или комплексных чисел), которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы. Количество строк и столбцов матрицы задают размер матрицы. Хотя исторически рассматривались, например, треугольные матрицы, в настоящее время говорят исключительно о матрицах прямоугольной формы, так как они являются наиболее удобными и общими.

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

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

· сложение матриц, имеющих один и тот же размер;

· умножение матриц подходящего размера (матрицу, имеющую столбцов, можно умножить справа на матрицу, имеющую строк);

· в том числе умножение на матрицу вектора (по обычному правилу матричного умножения; вектор является в этом смысле частным случаем матрицы);

· умножение матрицы на элемент основного кольца или поля (то есть скаляр).

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

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

То же можно сказать о представлении матрицами билинейный (квадратичных) форм.

В математике рассматривается множество различных типов и видов матриц. Таковы, например, единичная, симметричная, кососимметричная, верхнетреугольная (нижнетреугольная) и т. п. матрицы.

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

Умножение матрицы на число (обозначение: ) заключается в построении матрицы , элементы которой получены путём умножения каждого элемента матрицы на это число, то есть каждый элемент матрицы равен

Свойства умножения матриц на число:



1. 1A = A;

2. (лв)A = л(вA)

3. (л+в)A = лA + вA

4. л(A+B) = лA + лB

Задача №2. Для прямоугольной матрицы порятка n x m заменить заданным вектором строки матрицы, содержащие хотя бы один нулевой элемент

Обычно матрицу обозначают заглавной буквой латинского алфавита: пусть

,

тогда -- матрица, которая интерпретируется как прямоугольный массив элементов поля вида , где

· первый индекс означает индекс строки: ;

· второй индекс означает индекс столбца: ;

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

или просто:

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

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

Если необходимо дать развёрнутое представление матрицы в виде таблицы, то используют запись вида

Можно встретить как обозначения с круглыми скобками «(…)», так и обозначения с квадратными скобками «[…]». Реже можно встретить обозначения с двойными прямыми линиями "||…||").

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

-- это -тая строка матрицы ,

-- это -тый столбец матрицы .

Таким образом, матрица обладает двойственным представлением -- по строкам:

и по столбцам:



.

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

Транспонированная матрица

С каждой матрицей размера связана матрица размера вида

Такая матрица называется транспонированной матрицей для и обозначается так .

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

Диагональная матрица

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

Единичная матрица

Единичная матрица -- матрица, при умножении на которую любая матрица (или вектор) остается неизменной, является диагональной матрицей с единичными (всеми) диагональными элементами:



Для ее обозначения чаще всего используется обозначение I или E, а также просто 1 (или 1 специальным шрифтом).

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

при

Нулевая матрица

Для обозначения нулевой матрицы -- матрицы, все элементы которой нули (при сложении ее с любой матрицей та остается неизменной, а при умножении на любую получается нулевая матрица) -- используется обычно просто 0 или 0 специальным шрифтом, или буква, начертанием похожая на ноль, например .

Вектор-строка и вектор-столбец

Матрицы размера и являются элементами пространств и соответственно:

· матрица размера называется вектор-столбцом и имеет специальное обозначение:

· матрица размера называется вектор-строкой и имеет специальное обозначение:

Операции над матрицами

Умножение матрицы на число

Умножение матрицы на число (обозначение: ) заключается в построении матрицы , элементы которой получены путём умножения каждого элемента матрицы на это число, то есть каждый элемент матрицы равен

Сложение матриц

Складывать можно только матрицы одинакового размера.

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

Свойства сложения матриц:

· 1.коммутативность: A+B = B+A;

· 2.ассоциативность: (A+B)+C =A+(B+C);

· 3.сложение с нулевой матрицей: A + И = A;

· 4.существование противоположной матрицы: A + (-A) = И;

Все свойства линейных операций повторяют аксиомы линейного пространства и поэтому справедлива теорема:

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

Умножение матриц

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

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

Свойства умножения матриц:

· 1.ассоциативность (AB)C = A(BC);

· 2.некоммутативность (в общем случае): AB BA;

· 3.произведение коммутативно в случае умножения с единичной матрицей: AI = IA;

· 4.дистрибутивность: (A+B)C = AC + BC, A(B+C) = AB + AC;

· 5.ассоциативность и коммутативность относительно умножения на число: (лA)B = л(AB) = A(лB);

Умножение вектора на матрицу

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

для вектора-столбца v (получая новый вектор-столбец Av):

для вектора-строки s (получая новый вектор-строку sA):

Вектор-строка, матрица и вектор столбец могут быть умножены друг на друга, давая число (скаляр):

(Порядок важен: вектор-строка слева, вектор-столбец справа от матрицы).

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

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

Заметим, что обычной мотивировкой введения матриц и определения операции матричного умножения является именно введение их, начиная с умножения вектора на матрицу (которое вводится исходя из преобразований базиса или вообще линейных операций над векторами), а уже затем композиции преобразований сопоставляется произведение матриц. Действительно, если новый вектор Av, полученный из исходного вектора v преобразованием, представимым умножением на матрицу A, преобразовать теперь ещё раз, преобразованием, представимым умножением на матрицу B, получив B(Av), то, исходя из правила умножения вектора на матрицу, приведенного в начале этого параграфа (используя ассоциативность умножения чисел и меняя порядок суммирования), нетрудно увидеть в результате формулу, дающую элементы матрицы (BA), представляющую композицию первого и второго преобразований, и совпадающую с обычным определением матричного умножения.



Блок-схемы алгоритмов

алгоритм вектор матрица арифметический



Текст программы

Задача №1

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

Button1: TButton;

Edit1: TEdit;

Label1: TLabel;

Button2: TButton;

Memo1: TMemo;

Label3: TLabel;

Label4: TLabel;

Edit2: TEdit;

Edit3: TEdit;

Label2: TLabel;

Label5: TLabel;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

n:byte;

implementation

{$R *.dfm}

//создадим таблицы

procedure TForm1.Button1Click(Sender: TObject);

var i:byte;

begin

//размеры

n:=StrToInt(Edit1.Text);

StringGrid1.ColCount:=n+1;

StringGrid1.RowCount:=n+1;

for i:=1 to n do //шапка таблицы

StringGrid1.Cells[i,0]:=IntToStr(i);

for i:=1 to n do // подписи строк

StringGrid1.Cells[0,i]:=IntToStr(i);

StringGrid2.ColCount:=n+1;

StringGrid2.RowCount:=n+1;

for i:=1 to n do

StringGrid2.Cells[i,0]:=IntToStr(i);

for i:=1 to n do

StringGrid2.Cells[0,i]:=IntToStr(i);

end;

//создание матрицы, сортировака и вывод

procedure TForm1.Button2Click(Sender: TObject);

var x:array[1..20,1..20]of integer;

i,j,l:byte;

a:integer;

begin

l:=StrToInt(Edit2.Text);

a:=StrToInt(Edit3.Text);

//создаем матрицу

for i:=1 to n do

for j:=1 to n do

x[i,j]:=StrToInt(StringGrid1.Cells[j,i]);

//умножение столбца L на число a

for i:=1 to n do

for j:=1 to n do

if j = L then

x[i,j]:=x[i,j]* a;

//запись изменённой матрицы в таблицу 2

for i:=1 to n do

for j:=1 to n do

StringGrid2.Cells[j,i]:=IntToStr(x[i,j]);

end;

end.

Задача №2

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

Button1: TButton;

Edit1: TEdit;

Label1: TLabel;

Label2: TLabel;

Edit2: TEdit;

Button2: TButton;

Memo1: TMemo;

Label3: TLabel;

Label4: TLabel;

SG1: TStringGrid;

Label5: TLabel;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

n,m:byte;

implementation

{$R *.dfm}

//создадим таблицы

procedure TForm1.Button1Click(Sender: TObject);

var i:byte;

begin

//размеры с учетом фиксированных элемеентов

n:=StrToInt(Edit1.Text);

m:=StrToInt(Edit2.Text);

StringGrid1.ColCount:=m+1;

StringGrid1.RowCount:=n+1;

for i:=1 to m do //шапка таблицы

StringGrid1.Cells[i,0]:=IntToStr(i);

for i:=1 to n do // подписи строк

StringGrid1.Cells[0,i]:=IntToStr(i);

StringGrid2.ColCount:=m+1;

StringGrid2.RowCount:=n+1;

for i:=1 to m do

StringGrid2.Cells[i,0]:=IntToStr(i);

for i:=1 to n do

StringGrid2.Cells[0,i]:=IntToStr(i);

SG1.ColCount:=m+1;

for i:=1 to m do //шапка таблицы

SG1.Cells[i,0]:=IntToStr(i);

end;

//создание матрицы, сортировака и вывод

procedure TForm1.Button2Click(Sender: TObject);

var x:array[1..20,1..20]of integer;

y:array[1..20]of Integer;

i,j,k:byte;

begin

//создаем матрицу

for i:=1 to n do

for j:=1 to m do

x[i,j]:=StrToInt(StringGrid1.Cells[j,i]);

for i:=1 to m do

y[i]:=StrToInt(SG1.Cells[i,0]);

//замена столбца матрицы заданным вектором

for j:=1 to n do

for i:=1 to n do

if x[i,j]=0 then

for k:=1 to m do

begin

x[i,k] := y[k];

end;

//запись отсортированной матрицы в таблицу 2

for i:=1 to n do

for j:=1 to m do

StringGrid2.Cells[j,i]:=IntToStr(x[i,j]);

end;

end.

Скриншоты

Задача №1

Задача №2

Размещено на Allbest.ru