Алгоритмы циклической структуры с использованием одномерных массивов.

27. В массиве {Aj}, j=1, 2, 10 есть хотя бы один отрицательный элемент. Вычислить произведение элементов в массиве до первого отрицательного.

28. В массивеесть хотя бы один нуль.

а) Вычислить произведение элементов массива до первого нуля.

б) Вычислить сумму элементов массива до первого нуля.

29. В массиве существуют отрицательный и положительный элементы. Вычислить:

а) сумму положительных элементов;

б) сумму отрицательных элементов;

в) количество положительных элементов;

г) количество отрицательных элементов;

д) произведение положительных элементов;

е) произведение отрицательных элементов;

30. В массиве подсчитать количество элементов, больших 3.

31. Составить программу для вычисления суммы S элементов числовой последовательности А₁, А₂,..., А₁₀ по формуле S=A₁+A₂+...+A₁₀.

32. Составить программу для вычисления суммы элементов последовательности целых чисел Р₁, Р₂,..., Р₁₀, имеющих чётные индексы и произведение элементов последовательности Р₁, Р₂,..., Р₁₀, имеющих нечётные индексы.

Вычисление с хранением
последовательности значений

33. Даны действительные числа A₁,..., A_n, B₁,..., B_n. Вычислить (A₁+B_n)´(A₂+B_n-1)´...´(A_n+B₁).

34. Даны действительные числа A₁, А₂,..., A_2n. Получить:

а) A₁, A_n+1, A₂, A_n+2,..., A_n, A_2n;

б) A₁, A_2n, А₂, A_2n-1, A₃,..., A_n, A_n+1;

в) A₁+A_2n, A₂+A_2n-1,..., A_n+A_n+1.

35. Даны действительные числа A₁, А₂,..., A₁₇. Получить:

а) A₁₇, A₁, A₂,..., A₁₆;

б) A₁₁, A₁₂,..., A₁₇, A₁, A₂,..., A₁₀;

в) A₁₁, A₁₂,..., A₁₇, A₁₀, A₉,..., A₁;

г) A₁, A₃,..., A₁₇, A₂, A₄,..., A₁₆.

36. Даны действительные числа A₁,..., А_n. Если в результате замены отрицательных элементов последовательности их квадратами элементы будут образовывать неубывающую последовательность, то получить сумму элементов исходной последовательности; в противном случае их произведение.

37. Даны действительные числа A₁,..., А₁₀. Все числа попарно различны. Поменять в этой последовательности местами:

а) наибольший и наименьший элементы;

б) наибольший и последний элементы.

38. Дано натуральное число n. Сколько различных цифр встречается в его десятичной записи.

39. Даны действительные числа A₁,..., А₁₀. Вычислить A₁+A₂²+...+A₁₀¹⁰.

 

Практическая работа № 10

 

Тема: «Сортировка одномерных массивов»

 

Рассмотрим массив целых или действительных чисел А₁,..., А_n. Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по не убыванию А₁<=A₂<=...<=A_n. Эта задача называется задачей сортировки или упорядочения массива. Для решения этой задачи можно воспользоваться следующими алгоритмами:

I. Сортировка выбором

Найти элемент массива, имеющий наибольшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д.

II. Сортировка обменами (метод пузырька)

Последовательным просмотром чисел А₁,..., А_n найти наименьшее i такое, что А(i)>A(i+1). Поменять местами A(i) и A(i+1), возобновить просмотр с элемента A(i+1) и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.

III. Сортировка простыми вставками

Просматривать последовательно A2,..., An и каждый новый элемент Ai вставлять на подходящее место в уже упорядоченную совокупность A(1)...A(i-1). Это место определяется последовательным сравнением Ai с упорядоченными элементами A(1),..., A(i-1).

 

Примеры решений задач

1. Сортировка отбором.

Procedure otbor (Var x:arr; dlina: integer);

   Var mal: dano;

              Min, k,j: integer;

   Begin

              For k:=1 to dlina-1 do

                          Begin

                                      Mal:=x[k];

                                      Min:=k;

                                      For j:=k+1 to dlina do

                                                  If x[j]<mal then

                                                             Begin

                                                                         Mal:=x[j];

                                                                         Min:=j;

                                                             End;

              X[min]:=x[k];

              X[k]:=mal

   End

End

 

2. Сортировка методом пузырька.

Procedure Bubble (Var X:massiv; DLINA :integer);

   Var A:dannoe;

              J,R: integer;

              ZAMENA: boolean;

Begin

   Repeat

              ZAMENA:= false;

              For J:=2 to R do

                          If X[j-1]>X[J] then

                                      Begin

                                                  A:=X[J-1];

                                                  X[J-1]:=X[J];

                                                  X[J]:=A;

                                                  ZAMENA:= true

                                      End;

              R:=R-1

   Until not ZAMENA;

End.

3. Сортировка методом простых вставок.

Procedure simpins (Var a:arr);

   Var j,j,k: word;

              T: integer;

   Begin

              For i:=2 to n do

                          Begin

                                      T:=a[i];

                                      J:=1;

                                      While (t>=a[j]) and (j<i) do inc (j);

                                      If j<>i then

                                                  For k:=j-1 downto j do a[k+1]=a[k];

                                      A[j]:=t

                          End;

   End;

End.

4.Задача поиска места элемента. Для решения задачи полезен алгоритм, который называется алгоритмом деления пополам.

Пусть дан упорядоченный по неубыванию массив целых или действительных чисел А1<=А2<=Аn. Пусть дано некоторое число В (соответственно целое или действительное), для которого нужно найти такое место среди чисел А1,..., Аn, чтобы после вставки числа В на это место упорядоченность не нарушилась. Если вследствие равенства между собой некоторых элементов массива число В можно вставлять на разные места, то требуется определить ближайшее к началу массива место.

Список задач

1. Даны действительные числа А1,..., Аn, Р, натуральное число k (A1<=...<=An, k<=n). Удалить из А1,..., Аn элемент с номером k (т.е. Ak) и вставить элемент. равный Р, так, чтобы не нарушилась упорядоченность.

2. Даны действительные числа С1,..., Сp, D1,..., Dq. (С1<=C2<=...<=Сp, D1<=D2<=...Dq). Ввести единицу упорядоченности, получив F1, F2,..., Fp+q, что F1<=F2<=...<=Fp+q. Число сравнений не должно превосходить p+q.

3. Пусть дан массив А1,..., Аn. Требуется переставить А1,..., Аn так, чтобы в начале в массиве шла группа элементов, больших того элемента, который в исходном массиве располагался на первом месте, затем сам этот элемент, потом - группа элементов, меньших или равных ему.

4. Даны натуральное число n, целые числа А1,..., Аn. Найти наибольшее значение, встречающееся в последовательности А1,..., Аn, после выбрасывания одного из членов со значением max(A1,..., An).

5. Дана действительная матрица размером m´n; упорядочить строки матрицы:

а) по неубыванию значений первых элементов строк;

б) по невозрастанию сумм элементов строк;

в) по неубыванию значений наименьших элементов строк;

г) по невозрастанию значений наибольших элементов строк.

В заданиях б, в, г разрешается дополнительно определить числовой массив А1,..., Аn.

 

Практическая работа № 11

 

Тема: «Двумерные массивы. Преобразование и построение матриц»

 

Двумерные массивы являются аналогами матриц. Первый индекс элемента двумерного массива определяет номер строки, а второй – номер столбца, на пересечении, которых расположен элемент. Строки и столбцы нумеруются либо от единого заранее установленного минимального значения индекса, либо от граничного значения, заданного одновременно с объявлением массива.

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

Например:

Program Array_Full;

Const n=10;

Type mas = array [1..n, 1..n] of Integer;

Var m:mas;

Procedure Enter (Var tabl: mas);

Var i, j: Integer;

Begin

For i:= 1 to n do

   For j:= 1 to n do

     tabl[i,j]:=Random(10);

End;

Begin

Randomize;

Enter (m);

End.

С помощью процедуры Enter осуществляется ввод двумерного массива размерностью 10´10 случайными числами из диапазона от 0 до 10. Задание диапазона значений определяется константой n=10.

Описание двухмерного массива производится следующим образом:

Const

n=<ранг матрицы>;

Type

matr= array [1..n,1..n] of <тип элементов матрицы>;

Var

<имя матрицы>: matr;

Примеры решений задач

1. Процедура ввода матрицы.

Procedure Enter;

Var

  ii, jj: integer;

Begin

  For jj:=1 to n do

     For ii:=1 ot n do

        write('g[',ii,',',jj,']=>');readln (g[ii,jj]);  

End;

2. Процедура вывода матрицы на экран. (В данной процедуре используется процедура GotoXY, содержащаяся в модуле CRT. Поэтому необходимо при использовании этой процедуры указать имя библиотеки CRT в разделе описания библиотек Uses)

Program Name_Program;

Uses Crt;

...

Procedure List;

Var

  ii, jj: integer;

Begin

  For jj:=1 to n do

     For ii:=1 to n do begin

                                  gotoxy(3*ii, jj);          

                                   write (g[ii,jj]);  

                                  end;   

End;

Список задач

1. Даны действительная матрица размера n´(n+1), действительные числа A1,...,An+1, B1,..., Bn+1, натуральные числа p,q (p<=n, q<=n+1). Образовать новую матрицу размера (n+1)x(n+2) вставкой после строки с номером p данной матрицы новой строки с элементами A1,..., An+1, и последующей вставкой после столбца с номером q нового столбца с элементами B1,..., Bn+1.

2. Даны целые числа A1,..., A10, целочисленная квадратная матрица порядка n. Заменить нулями в матрице те элементы с четной суммой индексов, для которых имеются равные среди A1,..., A10.

3. Даны действительные числа A1,..., An, действительная квадратная матрица порядка n (n>=6). Получить действительную матрицу размера n´(n+1), вставив в исходную матрицу между пятым и шестым столбцами новый столбец с элементами A1,..., An.

4. Дана целочисленная матрица размера 6х9. Найти матрицу, получающуюся из данной:

а) перестановкой столбцов - первого и последнего, второй с пред­послед­ним и т.д.;

б) перестановкой строк - первого и последнего, второй с предпоследним и т.д.;

5. Дана действительная матрица [Aij], i, j=1,..., n. Получить действительную матрицу [Bij], i, j=1,..., n, элемент Bij который равен сумме элементов данной матрицы, расположенных в области, определяемой индексами i,j так, как показано на рис. (область заштрихована).

а)             б)                            в)                  г)

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

6. Дана действительная квадратная матрица порядка n. Преобразовать матрицу по правилу: строку с номером n сделать столбцом с номером n, столбец с номером n сделать строкой с номером n.

7. Даны две действительные квадратные матрицы порядка n. Получить новую матрицу:

а) умножением элементов каждой строки 1-й матрицы на наибольшее из значений элементов соответствующей второй матрицы;

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

8. В данной действительной матрице mxn (n>=3, m>=3) поменять местами:

а) строки с номерами 2 и n-1;

б) столбцы с номерами 3 и n-2.

9. Даны целочисленная матрица nx3, целые числа k, l (1<=k<=n, 1<=l<=n, k<>l).Преобразовать матрицу так, чтобы строка с исходным номером k непосредственно следовала за строкой с исходным номером l, сохранив порядок следования остальных строк.

10. В данной действительной квадратной матрице порядка n найти наибольший по модулю элемент. Получить квадратную матрицу порядка n-1 путем выбрасывания из исходной матрицы какой-нибудь строки и столбца, на пересечении которых расположен элемент с найденным значением.

11. Дана действительная квадратная матрица порядка n, все элементы которой различны. Найти наибольший элемент среди стоящих на главной и побочной диагоналях и поменять его местами с элементом, стоящим на пересечении этих диагоналей.

12. Построить квадратную матрицу порядка 2n.

 

13. Дано действительное число х. Получить квадратную матрицу порядка n=10. Середина заполняется нулями.

 

14. Даны действительные числа A1,..., An. Получить квадратную матрицу порядка n.

 

15. Получить целочисленную квадратную матрицу порядка 7, элементами которой являются числа 1, 2,..., 49, расположенные в ней по спирали.

 

16. Дана действительная квадратная матрица порядка 7. Найти последова­тельность действительных чисел B1,..., B49, получающихся при чтении данной матрицы по спирали (см. предыдущую задачу).

17. Дана действительная квадратная матрица порядка 2n. Получить новую матрицу, переставляя ее блоки размера n´n, и соответствии с рис а) или б).

18. Получить квадратную матрицу порядка n;

a)    б) в)            

г)     д
)

е)      ж) з)

и) к) л)

м) н)

Практическая работа № 12

 

Тема: «Матричная алгебра»

 

В данной лабораторной работе рассматриваются действия, совершаемые над матрицами.

Задача: найти произведение двух матриц.

 и .

Решение: Вычислим произведения АВ. Согласно правилу умножения матриц элемент матрицы АВ, стоящий в i-ой строке и j-м столбце (с_ij) равен сумме произведений элементов i-й строки матрицы А на соответствующие элементы j- го столбца матрицы В. Так, например,

С₂₃=(-1)*3+(-2)*6+(-4)*9=-51

Подсчитав таким образом все элементы матрицы АВ, находим:

.

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

Примеры решений задач

1. Составить программу нахождения произведения двух матриц А и В размером 2х3 и 3х3 соответственно.

Элементы результирующей матрицы С (размером 2х3) определяются по формуле: , где n - число строк матрицы А; m – число столбцов матрицы А и число строк матрицы В; p – число столбцов В. В общем случае результирующая матрица С имеет n строк и p столбцов.

Program UM;

Var

   A,C,: aray [1..2,1..3] of real;

   B: aray [1...3,1..3] of real;

   I,J,K: integer;

Begin

   For I:=1 to 2 do

              For J:=1 to 3 do

                          Read (A[I,J]);

   For I:=1 to 3 do

              For J:=1 to 3 do

                          Read (B[I,J]);

   For I:=1 to 2 do

              For J:=1 to 3 do

                          Begin

                                      C[I,J]:=0;

                                      For K:=1 to 3 do

                                                  C[I,J]:=C[I,J]+A[I,K]*B[K,J];

              End;

Begin

Writeln (‘Массив С’);

              For J:=1 to 3 do

                          Write (C[I,J]:12:5)

   End

End.

2. Составьте программу вычисления скалярного произведения двух векторов U и V, состоящих из четырех элементов каждый, по формуле:

. Вычислите длину вектора .

 

Program SP;

Type

N:1..4;

Var

S,DV: real;

   U,V: array [N] of real;

   I:N;

Begin

For I:=1 to 4 do

              Read (V[I]);

For I:=1 to 4 do

              Readln (U[I]);

   S:=0;

   DV:=0;

   For I:=1 to 4 do

              Begin

                          S:=S+U[I]*V[I];

                          DV:=DV+U[I]*V[I];

              End;

   DV:= sqrt (DV );

   Writeln (‘Скалярное произведение=’,S);

   Writeln (‘Длина вектора=’);DV

End.

 

Список задач

1. Даны матрицы А и В размера k´m и m´l соответственно. Найти произведения АВ.

2. Дана квадратная матрица порядка n. Получить матрицу А².

3. Даны матрицы А и В порядка n. Получить матрицу АВ-ВА.

4. Дана квадратная матрица А порядка n. Получить матрицу АВ; элементы матрицы В вычисляются по формуле:

а) d_ij=1/(i+j-1);б)  

в)

5. Даны квадратная матрица А порядка n и вектор с n элементами. Получить вектор:

а) Ab;

б) A²b;

в) (A-E)b, где Е - единичная матрица порядка n.

6. Дана квадратная матрица порядка n. Получить вектор Ab, где вектор b- вектор, элементы которого вычисляются по формуле:

а) b_i=1/(i²+2); б)

7. Даны квадратная матрица А порядка n и вектор х и у с n элементами. Получить вектор А(х+у).

8. Даны квадратная матрица А, В, С порядка n. Получить матрицу (А+В)С.

9. Даны квадратные матрицы А и В порядка n. Получить матрицу
А(В–Е)+С, где Е- единичная матрица порядка n, а элементы матрицы С вычисляются по формуле: c_ij=1/(i+j), i,j=1, 2,..., n.

10. Дана матрица А размера m´n. Получить транспонированную матрицу А (m´n).

11. Дана матрица А:

а) размера m´m;

б) размера m´n;

Получить матрицу АА (m´m).

12. След квадратной матрицы равен сумме элементов, расположенных на главной диагонали. Даны квадратная матрица порядка m, натуральное число n. Вычислить следы матриц А, А²,..., Аⁿ.

13. Даны целые числа А₁, А₂, А₃. Получить целочисленную матрицу [B_ij], i, j = 1, 2, 3, для которой B_ij=Ai-3·Aj.

14. Получить [A_ij], i=1, 10, j=1, 12, где A_ij=i+2·j.

15. Получить [A_ij], i=1, n, где A_ij=1/(i+j).

16. Даны натуральное число n, действительная матрица n´9. Найти среднеарифметическое:

а) каждого из столбцов;

б) каждого из столбцов, имеющих четные номера.

17. Дана действительная матрица n´m. Определить числа B₁,..., B_m, равные соответственно:

а) сумме элементов строк;

б) произведениям элементов строк;

в) наименьшим значениям элементов строк;

г) значениям среднеарифметических элементов строк;

д) разностям наибольших и наименьших значений строк.

18. Дана матрица n´n. Получить последовательность главной диагонали.

19. Дана матрица 6´9. Найти среднеарифметическое наибольшего и наименьшего значений ее элементов

20. Дана матрица n´m. Найти сумму наибольших значений элементов ее строк.

21. В данной действительной квадратной матрице n´n найти сумму элементов строки, в которой расположен элемент с наибольшим значением. Предполагается, что такой элемент единственный.

Практическая работа № 13