Презентация, доклад на тему : Алгоритмизация и программирование2

двумерных массивов.

ряда

 

n!

с точностью до члена ряда
xn

каком n выполнится условие.

Для итерационных циклов число повторений зависит не от параметров цикла, а от некоторого промежуточного или окончательного результата.
Сравнивая два соседних члена ряда, можно заметить, что уn / yn-1=x/n.

= Уn-1
*x/n.
Для первого члена ряда У1 = У0 *x/1 задается У0
=1.
Параметр, изменяющийся в этом цикле – номер члена ряда n.
Формула для вычисления текущего члена ряда У=У* х/n.

2! 3! n!

õ, , ,...,

x2 x3 xn

 



n!

xn

Члены ряда У

n

Условие

завершения Ón

цикла

начальное значение У1 - первого члена ряда.
НЦ
Вычислить следующий член ряда
Уn =Уn *Х/n
Напечатать n и Уn.
Вычислить номер следующего члена ряда n=n+1.

n

3.4. Если У >ε то перейти к НЦ.

3.5. КЦ
4. Конец

Уn= Уn Х/n

n=n+1

Начало

Х,

Да

Yn=1, n=1

Уn >

n, Уn

Конец

КЦ

НЦ

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

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

том, что элементы массива располагаются в последовательных ячейках памяти.
При описании массива в программе указываются его имя и размер, то есть количество элементов в массиве.
Например, Х(N), массив с именем Х, содержит N элементов. Отдельные элементы этого массива запишутся так: Х(0), Х(1), Х(2),…, Х(N), то есть элементы имеют такое же имя как массив и отличаются друг от друга индексом.

быть константа или выражение.

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

хн, хк, h, a
Вычислим количество точек n=(Хк-Хн)/h+1 , для которых будут вычислены Х и У, n определяет размерность массивов.
Задаем начальное значение параметра цикла I=1 (I – это номер точки).

4. Задаем X(I)=x

н

5. НЦ1

Вычислим У(I)=a*X(I)2
Вычислим I=I+1
Вычислим X(I)=X(I-1)+h

5.4. Если I<=n идти к НЦ
КЦ1
НЦ2 Параметр цикла I изменяется от 1 до n с шагом 1.
7.1 Печать массивов Х(I), Y(I)
КЦ2
Конец.

НЦ1

НЦ2

КЦ1

КЦ2

хк, h, a
Вычислим количество точек n=(Хк-Хн)/h+1, для которых будут вычислены Х и У, n - определяет размерность массивов.
Задаем начальное значение X(1)=xn
Задаем начальное значение параметра цикла I=1 (I – это номер точки).
Задаем X(I)=xн
НЦ1 Параметр цикла I изменяется от 1 до n с шагом 1.
Вычислим У(I)=a*X(I)2
Вычислим X(I)=X(I-1)+h
КЦ1
НЦ2 Параметр цикла I изменяется от 1 до n с шагом 1.
8.1 Печать массивов Х(I), Y(I)
КЦ2
Конец.

НЦ1

НЦ2

КЦ2

КЦ1

Начало

X(1)= Хн

столбец или строка каких-либо величин обозначенных одним именем и индексом, указанным в скобках.
В математике аналогом одномерного массива является вектор-строка или вектор –столбец.

Шаг изменения I равен 1.
При N=5 элементы массива Х(1), Х(2), Х(3), X(4), X(5).

Вывод элементов одномерного массива У(N), I=1,…,N
Шаг изменения I равен 1. При N= 5 элементы массива Y(1), Y(2), Y(3), Y(4), Y(5).

Х(I)

N

Y(I)

КЦ

НЦ
I=1,N

КЦ

НЦ
I=1,N,1

А(М).
Входные данные: M, A(M).
Выходные данные: S – сумма элементов массива, SR – среднее значение.
Вспомогательные данные: I

Математическая постановка задачи

M

S

M

S   A(I ) SR 
I  1

I=1,M,1

S=S+A(I)

S=0

SR=S/M

Задание начального значения переменной суммы S=0.
НЦ Параметр цикла I изменяется

2.1.

от 1 до М с шагом 1.
Вычисление суммы S=S+А(I).
КЦ
Вычисление среднего SR=S/M.

Например: M=5, А(1)=3, А(2)=2, А(3)=-3, А(4)=7, А(5)=1 , тогда S=10, SR=2 16

НЦ

КЦ

данные:
Р – произведение элементов массива.
Вспомогательные данные: I

Математическая постановка задачи

M

P   A(I )
I  1

I=1,M,1

P=P*A(I)

P=1

Задание начального значения переменной произведения Р=1.
НЦ Параметр цикла I изменяется от 1 до М с шагом 1.
вычислим произведение Р=Р*А(I)
3. КЦ

Например: M=5, А(1)=3, А(2)=2, А(3)=-3, А(4)=7, А(5)=1 , тогда P=-126

НЦ

КЦ

и В одинакового размера с суммированием элементов, имеющих одинаковые индексы
С(I)=A(I) +B(I)

Входные данные: M, A(M), B(M).
Выходные данные: C(M) – массив результатов.
Вспомогательные данные: I текущее значение индекса элементов массива.

I=1,M,1

C(I)=A(I)+B(I)

Например: M=5, Массив А: 3, 2, -3, 7, 1
Массив B: 4, 3, 1,-5, 5
Тогда
Массив С: 7, 5,-2, 2,6

НЦ

КЦ

М, удовлетворяющих условию A(I)>T.
Входные данные: M, A(M), T.
Выходные данные: K – количество элементов массива, удовлетворяющих условию.
Вспомогательные данные: I Математическая постановка
задачи

M

K   1 åñëè A(I )  T
I  1

I=1,M,1

K=K+1

K=0

A(I)>T

Да

Нет

Задание K=0.
НЦ Параметр цикла I изменяется от 1 до М с шагом 1.
2.1 Если А(I)>T то
2.2. К=К+1
3. КЦ

Например: M=5, Т= 2, А(1)=3, А(2)=2, А(3)=-3, А(4)=7, А(5)=1 , тогда К=2

НЦ

КЦ

удовлетворяющих условию B(I)>Z.
Входные данные: N, B(N), Z.
Выходные данные: S – Сумма элементов массива, удовлетворяющих условию.
Вспомогательные данные: I Математическая постановка задачи

M
S   B(I ) åñëè B(I )  Z
I  1

I=1,N,1

S=S+B(I)

S=0

B(I)>Z

Да

Нет

Задание начального значения переменной суммы S=0.
Формула в цикле(сумма) S=S+B(I)

Например: N=5, Z= 2, В(1)=4, В(2)=3, В(3)=1, В(4)=-5, В(5)=5 , тогда S=13

В одинакового размера М в один массив с чередованием элементов.
Нечетные элементы С(2*I-1)=A(I) Четные элементы С(2*I)=B(I)

Входные данные: M, A(M), B(M).
Выходные данные: C(2*M) – массив результатов.
Вспомогательные данные: I текущее значение индекса элементов массива.

I=1,M,1

C(2*I-1)=A(I)

C(2*I)=B(I)

Например: M=5, Массив А: 3, 2, -3, 7, 1
Массив B: 4, 3, 1,-5, 5
Тогда массив С С(1)=А(1)=3, С(6)=В(3)=1
С(2)=В(1)=4, С(7)=А(4)=7
С(3)=А(2)=2, С(8)=В(4)=-5
С(4)=В(2)=3, С(9)=А(5)=1
С(5)=А(3)=-3, С(10)=В(5)=5

N, с запоминанием его положения (индекса) в массиве.
Входные данные: N, B(N).
Выходные данные: BMAX – максимальный элемент массива, К
–номер индекса максимального элемента.
Вспомогательные данные: I

АНАЛОГИЧНО осуществляется поиск минимального элемента в массиве.

I=1,N

BMAX=B(I)

K= 1

BMAX>B(I

Да

Нет

BMA=B(1)

K= I

Задание начального значения переменной суммы BMAX=B(1), K=1.
Формула в цикле ВМАХ=B(I), K=I, если ВМАХ>B(I)

Например: N=5, B(1)=3, B(2)=2, B(3)=-3, B(4)=7, B(5)=1 , тогда BMAX=7, K=4

начального значения индекса нового массива J=0.
Формулы в цикле: J=J+1 и В(J)=A(I), если А(I)

Сформировать новый массив В из элементов массива А размерностью N, удовлетворяющих условию A(I)Входные данные: N, A(N), T.
Выходные данные: B(J), J – массив В и количество элементов массива.
Вспомогательные данные: I Математическая постановка задачи
N

åñëè A(I )  T

J  J  1,

B(J )   A(I )
I  1

Например: N=5, Т= 2, Массив А:3, 2, -3, 7,1, тогда массив В(1)=-3, В(2)=1

М.
Удалить К элемент из массива можно сдвинув весь «Хвост» массива, начиная с К+1 элемента на одну позицию влево, выполняя операцию: А(I)=A(I+1), I=K, K+1,…,M
Входные данные: M, A(M), К.
Выходные данные: А(M-1) – массив результата (на один элемент меньше исходного).
Вспомогательные данные: I текущее значение индекса элементов массива.

A(I)=A(I+1)

Например: M=5, К=2 Массив А: 3, 6, -3, 7, 1
Тогда результат Массив А: 3, -3, 7, 1

Параметр цикла I изменяется от К до М-1.
Формула в цикле: A(I)=A(I +1).


I=K, M-1

в К позицию массива А размерностью М.
Перед включением элемента нужно раздвинуть массив, начиная с К позиции, т.е. сдвинуть весь «хвост» массива, начиная с К+1 элемента на одну позицию вправо, выполняя операцию: А(I+1)=A(I), I=M, M -1,…,K,
( шаг изменения I= -1)
Перемещение элементов нужно начинать с конца.
Входные данные: M, A(M), К,D.
Выходные данные: А(M+1) – массив результата (на один элемент больше исходного).
Вспомогательные данные: I текущее значение индекса элементов массива.

A(I+1)=A(I)

A(K)=D

M=M+1

Например: M=5, К=2, D=8 Массив А: 3, 2, -3, 7, 1
Тогда результат

Параметр цикла I изменяется от М до К с шагом -1.
Формула в цикле: A(I+1)=A(I). Включение в К позицию массива значения переменной D
A(K)=D, увеличение размера массива М=М+1

I=M, K,-1

размерностью М местами.
Перезапись осуществляется с использованием вспомогательной переменной Р, в которую временно помещается один из элементов массива.
Например, в Р записывается К-й элемент массива, затем в К-й элемент записывается L-й, в L-й из переменной Р переписывается K-й.
Входные данные: M, A(M), K, L.
Выходные данные: А(M) –массив c переставленными элементами.
Вспомогательные данные: I , Р

P=A(K)

A(K)=A(L)

A(L)=P

Например: M=5, К=2, L=4 Массив А: 3, 2, -3, 7, 1
Тогда результат Массив А: 3, 7, -3, 2, 1

массива в обратном порядке.

Перезапись осуществляется с использованием вспомогательной переменной Р, в которую вначале записывается 1-й элемент массива, затем в 1 элемент записывается М-й, в M-й из переменной Р переписывается 1-й.
Входные данные: M, A(M).
Выходные данные: А(M) – инвертированный массив.
Вспомогательные данные: I , Р и N=INT(M/2) – средина массива.

INT – функция выделения целой части числа.

I=1, N

P=A(I)

N=INT(M/2)

A(I)=A(M-I+1)

A(M –I+1)=P

Например: M=5, К=2 Массив А: 3, 2, -3, 7, 1
Тогда результат Массив А: 1, 7, -3, 2, 3

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

В(N), расположив их в порядке возрастания в том же массиве.
Для решения используется алгоритм, состоящий из двух циклов:
Внешний цикл – это номер просмотра массива или его части и перестановки найденного во внутреннем цикле минимального элемента массива с первым .
Во внутреннем цикле первый элемент массива или его части сравнивается со всеми последующими элементами. И находится минимальный элемент.
Для упорядочения всех элементов массива внешний цикл повторяется К=1,…, N-1 раз. Количество повторений внутреннего цикла на каждом шаге внешнего цикла равно N – К раз. Когда остается в массиве последний элемент сортировка завершена.

возрастания значений элементов массива.

Для сортировки по возрастанию нужно во внутреннем цикле находить минимальный элемент массива и переставлять его местом с первым.
Входные данные: N, B(N).
Выходные данные: В(N) – упорядоченный массива.
Вспомогательные данные: I, J, K, BMIN

I=J+1,N

BMIN=B(I)

K= J

Да

Нет
BMIN

BMIN=B(J)

K= I

J=1,N-1

B(J)=BMIN

B(K)=B(J)

Например: N=5, Массив B: 3, 2, -3, 7, 1
Упорядоченный массив В: -3, 1, 2, 3, 7

нескольких строк и столбцов. В математике аналогом является матрица.
Каждый элемент двумерного массива имеет тоже имя, что и весь массив и отличается от другого элемента номером строки и номером столбца, на пересечении которых он находится.
Номер строки и номер столбца называются индексами.
Индексы в двумерном массиве записываются в скобках через запятую. На первом месте стоит индекс строки, на втором месте – индекс столбца.
Например, В(I,J) –элемент двумерного массива с именем В, стоящий на пересечении I строки и J столбца.

изменения I и J равен 1. Пусть N=2, M=3.
При I=1, изменения J=1,2,…,3 вводятся элементы массива Х(1,1), Х(1,2), Х(1,3)
При I=2, изменения J=1,2,…,3 вводятся элементы массива X(2,1), X(2,2), X(2,3)

АНАЛОГИЧНО
Вывод элементов двумерного массива У(N,M), I=1,…,N, J=1,2,…,M
Шаг изменения I и J равен 1.
При N= 3 и M=2 элементы массива Y(1,1), Y(1,2), Y(2,1), Y(2,2), Y(3,1),У(3,2)

J=1,M,1

Х(I,J)

N,M

I=1,N,1

Y(I,J)

I=1,N

I=1,N

массива А(N,М) по строкам.
Входные данные: N,M, A(N,M).
Выходные данные: S(N) – сумма элементов массива по строкам, SR(N) – средние значения по строкам.
Вспомогательные данные: I,J Математическая постановка задачи

M

M

S (I )

SR(I ) 

S (I )   A(I , J )
j  1

J=1,M,1

S(I)=S(I)+A(I,J)

S(I)=0

SR(I)=S(I)/M

I=1,N,1

Задание начального значения суммы S(I)=0. Формула в цикле(сумма) S(I)=S(I)+А(I,J).
Среднее SR(I)=S(I)/M

А(1,1) А(1,2) А(1,3) S(1) SR(1)
А(2,1) А(2,2) A(2,3) S(2) SR(2)
А(3,1) А(3,2) А(3,3) S(3) SR(3)
А(4,1) А(4,2) A(4,3) S(4) SR(4)

массива А(N,М) по столбцам.
Входные данные: N,M, A(N,M).
Выходные данные: S(M) – сумма элементов массива по строкам, SR(M) – средние значения по строкам.
Вспомогательные данные: I,J Математическая постановка задачи

N

SR(J )  S (J )

N
S (J )   A(I , J )

I=1,N,1

S(J)=S(J)+A(I,J)

S(J)=0

SR(J)=S(J)/N

J=1,M,1

Задание начального значения суммы S(J)=0. Формула в цикле(сумма) S(J)=S(J)+А(I,J).
Среднее SR(J)=S(J)/M

i 1
А(1,1) А(1,2) А(1,3)

А(2,1) А(2,2) A(2,3)
А(3,1) А(3,2) А(3,3)
А(4,1) А(4,2) A(4,3) S(1) S(2) S(3)
SR(1) SR(2) SR(3)

а столбцов – строками.
Транспонированная матрица
В(M,N) = A(N,M)
Входные данные: N,M, A(N,M).
Выходные данные: B(M,N) – Вспомогательные данные: I,J
Математическая постановка задачи

B(J , I )  A(I , J )

I=1,N,1

B(J,I)=A(I,J)

J=1,M,1

Формула в цикле B(J,I)=А(I,J)

А(1,1) А(1,2) А(1,3)
А(2,1) А(2,2) A(2,3)

B(1,1) B(1,2)
B(2,1) B(2,2)
B(3,1) B(3,2)

данные: C(N) – вектор результата.
Вспомогательные данные: I,J Математическая постановка

задачи

M

j  1

C(I )   A(I , J ) * B(J )

J=1,M,1

C(I)=C(I)+A(I,J)*B(J)

C(I)=0

I=1,N,1

Задание начального значения переменной C(I)=0.
Формула во внутреннем цикле С(I)=C(I)+А(I,J)*B(J).

С(1)
C(2)
C(3)

А(1,1) А(1,2) А(1,3)
А(2,1) А(2,2) A(2,3)
А(3,1) А(3,2) А(3,3)
B(1) B(2) B(3)

N,M, A(N,M).
Выходные данные: X(N*M) – вектор, в который последовательно переписаны строки массива А.
Вспомогательные данные: I,J Математическая постановка задачи

L  (I  1) * M  J X (L)  A(I , J )

J=1,M,1

X(L)=A(I,J)

I=1,N,1

L=(I-1)*M+J

Формулы в цикле: Вычисление значения индекса массива Х L=(I-1)*M+J
Запись элемента X(L)=A(I,J)

А(1,1) А(1,2) А(1,3)
А(2,1) А(2,2) A(2,3)

N=2, M=3 N*M=6

X(1) X(2) X(3) X(4) X(5) X(6) I=2, J=1, M=3
L=(I-1)*M+J=(2-1)*3+1=4 X(4)=A(2,1)

MAX(I)

Задание начальных значений
MAX(I)=B(I,1), IMAX(I)=1.
Формулы в цикле МАХ(I)=B(I,J) и IMAX(I)=J , если МАХ(I)>B(I,J)

1, J )

Удаление К строки из матрицы А(N,М).
Все строки, начиная с К+1 переместить вверх. Число строк уменьшится на 1.
Входные данные: N,M, К, A(N,M).
Выходные данные: А(N-1,M) Вспомогательные данные: I,J
Математическая постановка задачи

J=1,M,1

A(I,J)=A(I+1,J)

I=K,N,1

N=N-1

Формула в цикле A(I,J)=А(I+1,J)

100 100 100

1 200 200

300 300 300

1 400 400

100 100 100

K=3
1 100 100
2 200 200

3 400 400

100 100 100

К тую строку.
Входные данные: N, M, К, A(N,M), X(M).
Выходные данные: A(N+1,M) – массив, в котором строки с 1 по К -1 остались прежними, К строка переписана из массива Х(М), а строки , начиная с К+1 вновь из массива А.
Вспомогательные данные: I,J

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

J=1,M,1

I=N,K,-1

A(I+1,J)=A(I,J)

J=1,M,1

A(K,J) =X(J)

N=N+1

Формулы в цикле:
Сдвиг строк «хвоста» массива на 1: А(I+1,J)= A(I,J)
Запись элементов X в строку A(K,J)=X(J)

1 300 300
400 400 400

1 100 100 K=3
200 200 200 500 500 500
1 100 100
200 200 200

1 300 300
300 300 300
400 400 400

1 100 100
200 200 200
500 500 500
300 300 300

Переписали
«Хвост» массива на одну строку в конец

Вставили в К-ую строку массив X

записывается J элемент K строки,
в J-й элемент K строки записывается элемент из переменной Р .

Алгоритм перестановки строк в матрице

Перестановка L и K строк в матрице А(N,M) осуществляется с использованием вспомогательной переменной Р:

Входные данные: N, M, A(N,M).
Выходные данные: А(N,M) – c переставленными строками.
Вспомогательные данные: I , J, Р, К.

J=1, M

P=A(L,J)

A(L,J)=A(K,J)

A(K,J)=P

L=2, K=4

4 40 40 40

50 50 50 50

L=2,K=4

1 10 10 10
2 20 20 20
3 30 30 30

P

1 10 10 10
40 40 40 40
1 30 30 30
20 20 20 20
50 50 50 50

РЕЗУЛЬТАТ

строк второй матрицы)

Умножить матрицы А(N,K) и B(K,M)
Входные данные: N,M, К, A(N,K), B(K,M)
Выходные данные: C(N,M) – матрица результата.
Вспомогательные данные: I,J Математическая постановка задачи

K

C(I , J )   A(I , L) * B(L, J )
l  1

L=1,K,1

C(I,J)=C(I,J)+A(I,L)*B(L,J)

C(I,J)=0

J=1,M,1

I=1,N,1

N=3 K=2

А(1,1) А(1,2)
А(2,1) А(2,2)
А(3,1) А(3,2)

K=2 M=4

B(1,1) B(1,2) B(1,3) B(1,4)
B(2,1) B(2,2) B(2,3) B(2,4)

N=3 M=4

C(1,1) C(1,2) C(1,3) C(1,4)

C(1,1)=A(1,1)*B(1,1)+ A(1,2)*B(2,1)
C(1,2)=A(1,1)*B(1,2)+ A(1,2)*B(2,2)

C(2,1) C(2,2) C(2,3) C(2,4) C(1,3)=A(1,1)*B(1,3)+ A(1,2)*B(2,3)
C(3,1) C(3,2) C(3,3) C(3,4) C(1,4)=A(1,1)*B(1,4)+ A(1,2)*B(2,4)