10077
Общее понятие исполнителя и алгоритма. Смысл понятия правильный алгоритм. Примеры
Конспект
Информатика, кибернетика и программирование
Общее понятие исполнителя и алгоритма. Смысл понятия правильный алгоритм. Примеры. Алгоритм Алгоритм последовательность определенных действий или шагов для решения поставленной задачи. Программа запись алгоритма на языке исполнителя Свва алгорит...
Русский
2013-03-21
116.5 KB
25 чел.
Алгоритм -последовательность определенных действий или шагов для решения поставленной задачи.
Программа - запись алгоритма на языке исполнителя
Св-ва алгоритма: детерминированность (определённость): каждый шаг и переход от шага к шагу должны быть точно определены так, чтобы его мог выполнить любой другой человек или механическое устройство, Конечность (Алгоритм всегда должен заканчиваться за конечное число шагов, но это число не ограничено сверху), Массовость (алгоритм должен работать с любым допустимым значением переменной)
Исполнитель объект, который выполняет алгоритм.
Правильный алгоритм - если он дает верные результаты для любых допустимых исходных данных. Такого рода программы вполне можно использовать для решения прикладных задач.
%Нахождение разности
a = input ('введите уменьшаемое')
b = inbut ('введите вычитаемое')
res = a - b %разность
М-функции являются M-файлами, которые допускают наличие входных и выходных аргументов. Они работают с переменными в пределах собственной рабочей области, отличной от рабочей области системы MATLAB.
Пример
Функция average - это достаточно простой M-файл, который вычисляет среднее значение элементов вектора:
function y = average (x)
% AVERAGE Среднее значение элементов вектора.
% AVERAGE(X), где X - вектор. Вычисляет среднее значение элементов вектора.
% Если входной аргумент не является вектором, генерируется ошибка.
[m,n] = size(x);
if (~((m == 1) | (n == 1)) | (m == 1 & n == 1))
error('Входной массив должен быть вектором)
end
y =sum(x)/length(x); % Собственно вычисление
Подпрограммы (вспомогательные m-функции) также являются m-функцией, но они вызываются из основной m-функции.
Вспомогательный алгоритм тоже может вызывать другие вспомогательные, длина такой цепочки вызовов теоретически не ограничена. Здесь и далее следующие пары слов используются как синонимы: алгоритм и программа, вспомогательный алгоритм и подпрограмма, команда и оператор, программа и модуль. Вспомогательными и основными алгоритмы являются не сами по себе, а по отношению друг к другу.
Функции с параметрами функции, позволяющие производить определенные операции с переменными значениями.
Входные параметры параметры с которыми работает программа
Выходные параметры которые выводятся на экран после выполнения программы
Пример: zad16(x,y,dey); x,y,dey - фактические входные параметры
Фактический параметр аргумент, используемый как значение (число, символ и т. д.); Формальный параметр аргумент, используемый как ячейка памяти (название переменной, указатель на переменную), выступающее в качестве идентификатора этого значения, принимаемого функцией.
Локальные переменные действуют только внутри m-функции, глобальные действуют во всей программе. Локальные переменные не требуют объявления. Прежде чем переменной присвоить значение, необходимо убедиться, что всем переменным в правой части значения присвоены. Любая операция присваивания создает переменную, если это необходимо, или изменяет значение существующей переменной. Обычно каждая М-функция, задаваемая в виде M-файла, имеет собственные локальные переменные, которые отличны от переменных других функций и переменных рабочей области. Однако, если несколько функций и рабочая область объявляют некоторую переменную глобальной, то все они используют единственную копию этой переменной. Любое присваивание этой переменной распространяется на все функции, где она объявлена глобальной.
Каждой M-функции выделяется дополнительная область памяти, не пересекающаяся с рабочей областью системы MATLAB. Такая область называется рабочей областью функции.
При работе с системой MATLAB можно получить доступ только к переменным, размещенным в рабочей области системы или в рабочей области функции. Если переменная объявлена глобальной, то ее можно рассматривать как бы принадлежащей нескольким рабочим областям.
В программном пакете MATLAB возможно использование двух видов цикла: цикл for и цикл while.
for используется для организации вычислений с заданным количеством повторений. Цикл while используется, когда необходимо выполнять инструкции тела файла до тех пор, пока не выполнится заданное условие. Также существует оператор break, прекращающий работу последнего по вложению цикла.
Эта конструкция позволяет выполнить сомнительную операцию, а если операция приводит к фатальной ошибке, то вся программа не сломается, а пойдет дальше. После try запускаются некоторые инструкции. Если их невозможно выполнить, что берется программа действий из catch, а затем выполнение передается за оператор end. Очень похоже по принципу на if-else-end.
Позволяет дать ошибке имя, указать переменные, использование которых привело к ошибке. Похоже на функцию sprintf.
function test
disp('Мы вошли в цикл')
try
a = fopen('test.txt', 'r'); %открываем некоторый файл
r = fread(a); %пытаемся прочесть некоторый файл
catch
disp ('Файла нет')
end
disp ('Мы вышли из цикла')
end
function errtest1(x, y)
if nargin ~= 2 %кол-во аргументов не 2
error('myApp:argChk', 'Wrong number of input arguments') % название ошибки, суть ошибки
end
Значение - это константа, число или параметр присваиваемый переменной
Переменная это идентификатор, определяющий данные.Класс переменной определяет внутренний формат представления значения переменной и допустимые операции с этой переменной. Кроме того, переменная имеет имя.
Массив-совокупность чисел записанных в виде таблицы
Отличие состоит в способе нумерации: одномерные-1 индекс
пример:
x(1)=2; x(2)=4; x(3)=0; x(4)=-2;
получится вектор-строка:
2 4 0 -2
Двумерные- 2 индекса
y(1,1)=-2; y(1,2)=9; y(1,3)=-15; y(2,1)=1; y(2,2)=0; y(2,3)=2;
получится массив:
-2 9 -15
1 0 2
Класс выражения определяется классом значения-результата
double-используется для представления чисел с плавающей точкой
char-для представления символов
logical-для представления логических значений
cell-массивы ячеек
struct-массивы структур
Переменная создается путем присваивания
<имя переменной>=<значение>-частный случай
<имя переменной>=<выражение>-общий случай
Пример
x=2.3-класс double
h='b'-класс char
удаляются переменные так:
clear('x','h')
Существуют различные методы разработки алгоритмов (и программ), но наиболее важным является метод пошаговой детализации (или метод разработки « сверху - вниз »). При этом методе первоначально продумывается и фиксируется множество данных и результатов алгоритма без детальной проработки отдельных частей.
Задачу разбивают на автономные части, каждая из которых существенно проще. Может оказаться необходимым повторять процесс детализации многократно, но это определяется только сложностью решаемых задач. Конечным уровнем детализации алгоритма можно считать такой, при котором в алгоритме нет действий более крупных, чем: обращение к готовому алгоритму; вычисление арифметического выражения и присваивание значения переменной; сравнение арифметических выражений (или переменных); ввод (вывод) данных и т.п.
Перед комментарием ставится знак «%». Комментарии следует писать в начале функции, а так же, в случае надобности, среди кода для пояснения того, что делает код.
function a=findmin(x)
%Исходно: массив чисел
%Результат: минимум среди элементов с четными индексами
a=x(2);
l=length(x)
for i=2:2:l
if a<x(i)
a=x(i);
end
end
Рассмотрим числовую последовательность a1 a2 … ak.
Говорят, что последовательность задана рекуррентным соотношением, если задана функция f(x) такая, что для любого k a(k)=f(a(k+1)), и задано значение некоторого члена этой последовательности(например, а1).
Альтернативный способ задания последовательности - это задать выражение общего вида k-го члена последовательности.
Последовательность четных чисел
2 4 6 8 10 …
a1 a2 a3 a4 a5 …
a(k)=2*k
или
a(k+1)=a(k)+2
a1=2
Рекурсия это такой способ организации вычислительного процесса, при котором программа в ходе выполнения составляющих её операторов обращается сама к себе.
Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.
Под косвенной рекурсией понимают явление, когда рекурсивные функции вызывают друг друга (например, функция А вызывает B, а функция B вызывает A).
function res=factor(n)
%исходно:-x число которое надо возвести в факториал
%результат res-ответ
res=n
if n>1
res=res*factor(n-1)
end
ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ - математическая ПОСЛЕДОВАТЕЛЬНОСТЬ, каждый член которой является суммой двух предыдущих. Неэффективность заключается в том что, при зацикливании, или выполнении большого объема задач выделяется большой объём памяти, если происходит зацикливание, то выделяемый объем стремится к бесконечности
Инвариант цикла - некоторое утверждение, которое сохраняет свою истинность, после любого числа итераций (повторений) цикла, даже после 0.
пример алгоритма Евклида для вычисления НОД
условие до начала цикла a>0 и b>0, a~=b
условие после цикла
1) a=b
Или
2) a~=b
это и есть инвариант цикла на примере алгоритма Эвклида.
нод=наибольшее общее кратное
Вычисление суммы:
function s=zad9(x)
x=[1,2,3,4];
%инвар:s-сумма первых i элем. x
s=0;
i=0;
n=numel(x);
while i<n
i=i+1;
s=s+x(i);
end
%утв. i==n & инвариант
Подсчёта числа элементов массива, имеющих максимальное значение:
function s=v10_1(x)
x=[1,2,3,4,5,8,5,8]
maxm=x(end/2);
n=numel(x);
s=0;
for i=1:n
if x(i)>maxm
maxm=x(i);
s=0;
end
if x(i)==maxm
s=s+1;
end
end
Вычисления средне-квадратического отклонения заданной числовой последовательности:
function otk=zad10_2(x)
x=[1,2,3,4,5,6,7]
n=numel(x);
sr=0;
sk=0;
s=0;
for i=1:n
sr=sr+x(i)/n; %среднее
sk=sk+(x(i))^2; %сумма квадратов чисел
s=s+x(i); %сумма чисел
end
otk=sqrt((sk-2*sr*s+n*sr^2)/n);
Оценка числа операций, требуемых для выполнения алгоритма.
f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост
Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).
Алгоритм быстрого возведения в степень
Принцип - если степень N четна то можно возвести число в квадрат и в оставшуюся целую степень (N/2), иначе умножаем результат на возводимое число и уменьшаемстепень на 1.
function res=e11_2(t,k) %возведение числа t в степень k
res=1;
while k>0
if mod(k,2)==1
res=res*t
end
t = t*t;
k = fix(k/2); %целая часть от деления
end
Пузырьковая сортировка, является сортировкой квадратичной сложности, т.к. содержит 2 цикла, то есть n^2
function x=bubble(x)
n=length(x);
for j=1:1:n-1
% сравниваем каждый элемент со следующим и меняем местами
for i=1:1:n-1
if x(i)>x(i+1);
temp=x(i);
x(i)=x(i+1);
x(i+1)=temp;
end
end
end
Сортировка слиянием:
function p=sort_sl(m,n)
m=[1,2,3,4,5]
n=[1,2,3,4,5]
n1=numel(m);
n2=numel(n);
j=1;
L=1;
for i=1:(n1+n2)
if j>n1
p(i)=n(L);
L=L+1;
else
if L>n2
p(i)=m(j);
j=j+1;
else
if m(j)<=n(L)
p(i)=m(j);
j=j+1;
else
p(i)=n(L);
L=L+1;
end
end
end
end
Числовым рядом называют сумму из бесконечного числа слагаемых вида a1+a2+a3…, где a1+a2+a3…-некоторая числовая последовательность, элементы которой называют элементами числового ряда
n-ой частичной суммой числового ряда называют сумму первых n членов этого ряда
Sn=a1+a2+…+an
Говорят, что числовой ряд сходится, если существует lim Sn, принадлежащий R ( n стремиться к +бесконечности). Этот предел называют суммой ряда
Ряд, членами которого являются степенные функции аргумента x, называется степенным рядом:
В качестве примера может послужить второй типовик
function n=num_abcd(str)
str='abcdabcdasdasdkosakdabcd';
n=0;
s=0;
while ~isempty(str)
if s==0
if str(1)=='a'
s=1;
end
elseif s==1
if str(1)=='b'
s=2;
else
s=0;
end
elseif s==2
if str(1)=='c'
s=3;
else
s=0;
end
elseif s==3
if str(1)=='d'
n=n+1;
end
s=0;
end
str(1)=[];
end
Убывание степеней:
function p=zad15(x)
x=-1; %точка х
a=[1,1,2,1]; %коэффициенты полинома
q=a(1);
p=0; %производная
for i=2:length(a)
p=p.*x+q; %вычисление производной в точке х
q=q.*x+a(i); %вычисление значения ф-ии в точке х
end
Возрастание степеней:
function y=zad15_2(x)
x=-2; %точка х
a=[1,2,1,1]; %коэффициенты полинома
y=0;
p=1; %степень x
for k=1:length(a)
y=y+a(k).*p; %вычисление значения ф-ии в точке х
p=p.*x;
end
function s=zad16(x,y,dey)
%степень: n,n-1,...,2,1,0
x=[1,2,1];
y=[1,3];
dey=2; %1-сложение, все остальное умножение
if length(x)>length(y) %если длина вектора x больше длины вектора y, то дополняем нулями y
a=length(x); %a-длина х, но в данной задаче как длина самого длинного вектора
while length(x)~=length(y)
y=[0,y];
end
else
a=length(y);
while length(y)~=length(x) %если наоборот, то дополняем нулями x
x=[0,x];
end
end
%получили 2 одинаковых вектора готовых к сложению или умножению
if dey==1 %складываем
for i=1:a
m(i)=x(i)+y(i);
end
else %умножаем
m(1:(length(x)+length(y)-1))=0; %делаем нулевой массив m
for i=1:a
for j=1:a
m(i+j-1)=m(i+j-1)+x(i)*y(j);
end
end
end
%убираем нули в начале массива m.
i=1;
if m(1)==0 %если первый элемент массива m нулевой, тогда
while m(i)==0
s=m(i+1:end);
i=i+1;
end
else
s=m;
end
function d=det_1(x)
%det-библиотечная функция для вычисления определителя
%исх x-возвр. Матрица double
%рез d=определитель Х
x=[12,2,3;4,5,6;7,8,9];
n=length(x);
for i=1:n-1
x(i:end,i:end)=pol_nuli(x(i:end,i:end));
end
%x имеет ступентачатый вид
d=1;
for i=1:n
d=d*x(i,i);
end
function x=pol_nuli(x)
%исх: X-квадратная матрица double
% рез: выполняем превый шаг привидения к ступенчатому виду : x(1,1)~=0;x(2,2)~=0
imax=1;%индекс ведущей строки
n=length(x);
for i=2:n
if abs(x(i,1))>abs(x(imax,1))
imax=i;
end
end
t=x(1,:);
x(1,:)=x(imax,:);
x(imax,:)=t;
%x(1,1)-ведущий элемент в 1-ом столбце
for i=2:n
k=-x(i,1)/x(1,1);
x(i,:)=x(i,:)+k*x(1,:);
end
function d=det_2(x)
x=[12,2,3;4,5,6;7,8,9]
if length(x)==1
d=x
else
d=0;
sign=1;
end
for i=1:length(x)
d=d+sign*det(x(2:end,[1:i-1,i+1:end]))*x(1,i);
sign=-sign;
end
Обычные числа и переменные в MATLAB рассматриваются как матрицы размера 1x1, что дает единообразные формы и методы проведения операций над обычными числами и массивами. Данная операция обычно называется векторизацией. Векторизация обеспечивает и упрощение записи операций, производимых одновременно над всеми элементами вектрров и матриц, и существенное повышение скорости их выполнения.
Пусть x и y - массивы одинаковых размеров.
x.*y - перемножить все элементы x на соответствующие элементы y
x.^y - аналогично возвести в степень
x./y - аналогично деление
y=x(2:5) - присвоить массиву y массив элементов x со 2го элемента до 5го.
y=x(2:end) - то же самое, только не до 5го элемента, а до конца
Динамическим называется массив, размер которого может меняться во время исполнения программы. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. Обычные, не динамические массивы называют ещё статическими.
Формирование
»V=[1 2 3]
V=
1 2 3
задает вектор V, имеющий три элемента со значениями 1, 2 и 3.
» М=[1 2 3: 4 5 6; 7 8 9];
задает квадратную матрицу, которую можно вывести:
M =
1 2 3
4 5 6
7 8 9
Возможен ввод элементов матриц и векторов в виде арифметических выражений, содержащих любые доступные системе функции, например:
» V= [2+2/(3+4) exp(5) sqrt(l0)]:
V = 2.2857 148.4132 3.1623
Удаление столбцов и строк матриц
Для формирования матриц и выполнения ряда матричных операций возникает необходимость удаления отдельных столбцов и строк матрицы. Для этого используются пустые квадратные скобки [ ]. Проделаем это с матрицей М:
» М=[1 2 3; 4 5 6; 7 8 9]
Удалим второй столбец используя оператор : (двоеточие): » М(:.2)=[ ]
1 3
4 6
7 9
А теперь, используя оператор : (двоеточие), удалим вторую строку: » М(2.:)=[ ]
1 3
7 9
function z=zad17(a,b,eps)
%инвар: f(a)f(b)<0, корень ровно 1 на [a,b]
%a=0;
%b=2;
%eps=0.000001;
ya=f(a);
yb=f(b);
while b-a>2*eps
z=(a+b)/2;
yz=f(z);
if ya*yz<0
b=z;
yb=yz;
else
a=z;
ya=yz;
end
end
function y=f(x)
%y=cos(x)-x;
То, что было на консультации: Дан массив, отсортировать первый столбец по убыванию, вместе с этим отсортировать и строки, содержащие первый элемент
function y=prim_mat(x)
x=[1,2,3;0,2,4;7,9,12];
c=x(:,1);
n=length(c);
p=1:n;
%пузырьковая сортировка по убыванию
for i=1:n-1
for j=1:n-i
if c(j)<c(j+1)
t=c(j);
c(j)=c(j+1);
c(j+1)=t;
t=p(j);
p(j)=p(j+1);
p(j+1)=t;
end
end
end
y=x(p,:);
%другой вариант:
%i=1;
%while i<=n
% y(i,:)=x(p(i),:);
% i=i+1;
%end
А также другие работы, которые могут Вас заинтересовать | |||
56439. | The Beauty of the World Is in Danger | 90 KB | |
We discussed the problem of pollution at our previous lesson. And we have found out that many species of animals and plants are in danger. Your task was to find some information about them. Read your reports, please. | |||
56440. | The City | 42.5 KB | |
Now you can see that the title of topic is “City” Today at our lesson we’ll be travel agency. Imagine yourself travel agents indefinite routes. We are expecting a tourist, who whoud like to visit Ukrainian cities and interesting places. Your task is to give him this information. | |||
56441. | История древнего мира. Древняя Месопотамия | 82.5 KB | |
В древней Месопотамии существовали крупные города-государства со сложным управлением, развитыми ремеслами, искусствами и торговыми связями. Это делало регион нестабильным, поскольку их правители враждовали за земли, торговые пути и влияние | |||
56442. | Профессия: Электромонтёр по ремонту и обслуживанию электрооборудования | 497 KB | |
Естественное освещение, являясь с физиологической точки зрения наиболее благоприятным для человека, не может полностью обеспечить его нормальную жизнедеятельность, поэтому еще в доисторические времена у людей возникла потребность в искусственном освещении. | |||
56443. | Тіла Обертання. Об’єм тіл обертання.. Розв’язування задач | 2.9 MB | |
Систематизувати й узагальнити знання з теми; відпрацювати навички розв’язування задач; розвивати логічне мислення, уміння аналізувати, просторову уяву,самостійність; виховувати інтерес до предмета. | |||
56446. | Запалюємо «Тимурівські зірочки» | 318.5 KB | |
Наш проект Запалюємо Тимурівські зірочки передбачає відродження саме тимурівського руху як самостійного напрямку діяльності учнів. Мета проекту: відродження тимурівського руху як самостійного напрямку діяльності. | |||
56447. | Типы и структура урока технологии | 31 KB | |
По этим признакам выделяются: комбинированный урок теоретический урок практический урок уроклабораторная работа урок по решению технических задач контрольнопроверочный урок. Типы уроков технологии отличаются друг от друга своей структурой. Под этим понимается совокупность элементов входящих в урок их последовательность и взаимосвязь. | |||