Схема алгоритма
1
18 Программа на языке Си
#include int main (void)
{ int a[20], n, i; char flag=0; printf (Введите число элементов массива scanf (″%d″, &n); if (n>20) n=20; printf (Введите значения элементов for (i=0; i { printf (″a[%d]=″, i); scanf (″%d″, &a[i]);
} for (i=0; i -999<=a[i] && a[i]<=-100)
1
19
{ flag=1; break;
} if (flag) printf (В массиве есть трехзначные числа else printf (Трехзначных чисел в массиве нет return 0;
} Программа на языке Паскаль
Program Pr_3; var a : array [1..20] of integer; n, i : integer; flag : boolean; begin writeln (Введите число элементов массива read (n); if n>20 then n:=20; writeln (Введите значения элементов for i:=1 to n do begin write ('a[’, i, ']=’); read (a[i]) end; flag:=false; for i:=1 to n do if (100<=a[i]) and (a[i]<=999) or
(-999<=a[i]) and (a[i]<=-100) then begin flag:=true; break end; if flag then В массиве есть трехзначные числа) else Трехзначных чисел в массиве нет) end. Программа на языке Фортран
Program Pr_3
Implicit none integer a(20), n, i logical flag print *, Введите число элементов массива read *, n if (n>20) n=20 print *, Введите значения элементов do i=1, n
20 print *, 'a[’, i, ']=’ read *, a(i) enddo flag=.false. do i=1, n if (100<=a(i).and.a(i)<=999.or. &
-999<=a[i].and.a[i]<=-100) then flag=.true. exit endif enddo if (flag) then print *, ' В массиве есть трехзначные числа ' else print *, ' Трехзначных чисел в массиве нет ' endif end Программа на языке Python Введите число элементов массива 1<=N<=20 ")
N=int(input()) if N > 20:
N = 20
A = [] # Создаем пустой список for i in range(N): # i = 0, ... , N-1 -- всего N Введите й элемент ".format(i+1))
A.append(float(input())) flag = False for i in range(N): # i = 0, ... , N-1 -- всего N if -999 <=A[i] <= -100 or 100 <= A[i] <= 999: flag = True break if flag: В массиве есть трехзначные числа) else: Трехзначных чисел в массиве нет) Программа в системе Матлаб Введите число элементов массива if n>20 n=20; end for i=1:n
A(i)=input(' A(i)='); end flag=false; for i=1:n if 100<=A(i) && A(i)<=999 || …
21
-999<=A(i) && A(i)<=-100 flag=true; break; end end if flag disp(' В массиве есть трехзначные числа ') else disp(' Трехзначных чисел в массиве нет ') end С использованием векторных функций Введите число элементов массива if n>20 n=20; end for i=1:n
A(i)=input(' A(i)='); end if length(A(100<=abs(A) & abs(A)<=999))=0 disp(' В массиве есть трехзначные числа ') else disp(' Трехзначных чисел в массиве нет ') end Задача 4. Вычисление значения полинома Условие задачи. Для заданного x вычислить значение полинома
5 3
2 2
3 4
x
x
x
x
P
по схеме Горнера.
В общем случае полином степени n представляет собой многочлен. Для вычисления его значения при заданном х по схеме Горнера предварительно выполняется деление исходного полинома с остатком на x, в результате чего он приводится к виду) = (( …( …(((a
0
)x + a
1
)x+ a
2
)x + … +a
k
)x + …+ a
n-3
)x + a
n-2
)x + a
n-1
)x + При такой форме представления полинома для вычисления его значения при конкретном значении x можно, начав с самой внутренней пары скобок, задать p
0
= a
0
, а далее в результате повторения однотипных действий последовательно вычислять
p
1
= p
0
x + a
1
,
p
2
= p
1
x + a
2
,
…
p
k
= p
k-1
x + a
k
,
…
p
n
= p
n-1
x + a
n
.
22 Значение будет значением полинома при конкретном значении
x. Такой прием позволяет избежать трудоемких операций по возведению х в разные степени.В общем виде такой вычислительный процесс можно записать как рекуррентную зависимость
p
0
= a
0
,
p
k
= p
k-1
x + a
k
, k = 1,2, … , Тогда для задания и хранения коэффициентов полинома удобно использовать массив (указывая 0 для коэффициентов при отсутствующих степенях, например, при степени 1 в условии данной задачи, причем удобнее, если его элементы будут иметь индексы от 0 до n, если это позволяет язык программирования, на котором реализуется алгоритм. Для полинома, заданного в условии данной задачи,
5 3
2 2
3 4
x
x
x
x
P
, степеньполинома n=4, а коэффициенты имеют значения 2, 3, -1, 0 и 5, следовательно, элементы массива а от
a[0] до a[4] должны иметь перечисленные значения. Для вычисления собственно значения полинома можно использовать единственную переменную p, так как вычисляемое на каждом шаге значение p
k
зависит только от предыдущего значения p
k-1
, очередного коэффициента полинома a
k
и заданного значения x. Структурированная запись алгоритма 4
1. n = 4.
2. Создать массив коэффициентов полинома a из n + 1 элементов, проиндексированный от 0 дои инициализировать его значениями согласно заданию.
3. Ввести значение x.
4. p = a[0].
5. Повторить для k от 1 до n:
5.1. p = p * x + a[k].
6. Вывести сообщение Значение полинома при заданном x равно и значение p. Схема алгоритма
1
Программа на языке Си
#include
#include
#define n 4 double a[n+1]={2.0, 3, -1.0, 0, 5.0}; int main(int argc, char *argv[])
{ int k; double p, x; Введите значение параметра x: ");
1
24 scanf("%lf",&x); p=a[0]; for(k=1;k<=n;k++) p = p*x + a[k]); Значение полинома P( %lg) = %lg ",x,p); system("pause"); return 0;
} Программа на языке Паскаль
Program Pr_4;
Const n = 4; a: array [0..n] of real = (2, 3, -1, 0, 5);
Var x, p: real; k: integer; begin Введите х readln(x); p:=a[0]; for k:=1 to n do p:=p*x+a[k]; Значение полинома = ’, p:5:2) end. Программа на языке Фортран
Program Pr_4
Implicit none real, parameter :: n = 4 real x, p, a(0:n) /2, 3, -1, 0, 5/ integer k print *, Введите х read *, x p=a(0) do k=1, n p=p*x+a(k) enddo print Значение полинома = ’, p end Программа на языке Python Введите значение параметра x: ") x=float(input()) n = 4 # степень полинома
A = [2.0, 3, -1.0, 0, 5.0] # Инициализация списка
# коэффициентов полинома по заданию
25
P = A[0] for i in range(1,n+1): # i = 1, ... , n
P = P*x + A[i] print("P( {0} ) = {1} ".format(x,P)) Программа в системе Матлаб
n=4;
A=[2 3 -1 0 5]; Введите х p=A(1); for k=2:n+1 p=p*x+A(k); end Значение полинома =’) disp(p) С использованием векторных операций
A=[2 3 -1 0 5]; Введите х p=polyval(A,x); Значение полинома =’) disp(p) Задача 5. Поиск максимального элемента в массиве Условие задачи. Найти значение максимального элемента заданного массива. Исходные данные представлены массивом Хи его размером п. Результатом будет максимальный элемент массива Max. Метод определения максимального элемента состоит в следующем поиск начинается с первого элемента массива X[1]. Для этого значение первого элемента массива запоминается в переменной Max. Она будет служить эталоном для сравнения с другими элементами массива. Далее в цикле просматриваются все элементы массива от второго до последнего и значение каждого из них (X[i]) сравнивается со значением переменной Max. Если значение очередного элемента массива X[i]
больше, чем переменной Max, тов запоминается значение этого большего элемента X[i], так как оно будет максимальным среди уже проверенных элементов. Затем переходим к следующему элементу массива. Сравнения будут продолжаться до тех пор, пока не будут проверены все элементы массива Х. По завершении работы цикла в переменной Max останется значение самого большого элемента из всех и его надо вывести на экран как результат.
26 Структурированная запись алгоритма 5
1. Ввести количество элементов массива п.
2. Повторять для i от 1 доп. Ввод элементов массива Х
3. Запомнить значение первого элемента в переменной
Max= Х
4. Повторять для i от 2 доп. Если X[i] > М то выполнить
4.1.1 М Х
5. Вывести сообщение Максимальный элемент массива =” и значение переменной М. Схема алгоритма
Программа на языке Си
#include
#define N 50 int main (void)
{ int n, i; double x[N], max; printf (Введите количество элементов массива scanf ("%d", &n); for (i=0; i { printf (Введите элемент массива scanf ("%lf", &x[i]);
} max=x[0]; for (i=1; imax) max=a[i]; printf ("max=%lf\n", max); return 0;
} Программа на языке Паскаль
Program Pr_5;
Var x: array of real; Динамический массив n,i:integer; max:real; begin Введите количество элементов readln(n); Выделение памяти под массив writeln (' Введите элементы массива for i:=0 to n-1 do Индексация от 0 до n-1} readln(x[i]); max:=x[0]; for i:=1 to n-1 do if x[i]> max then max:=x[i]; writeln (' Максимальный элемент =’, max); x:=nil; end. Программа на языке Фортран
Program Pr_5
Implicit none real, allocatable :: x(:), max ! Динамический массив
28 integer i, n print Введите количество элементов n’ read *, n allocate (x(n)) ! Выделение памяти print *,’ Введите элементы массива read *, (x(i), i=1,n) ! Индексация от 1 до n max = x(1) do i = 2, n if (x(i)>max) then max = x(i) endif enddo print *,’max =’, max deallocate (x) end Программа на языке Python Введите число элементов массива) print(" (если N<1 то N=50)")
N=int(input()) if N < 1:
N = 50
X = [] # Создаем пустой список for i in range(N):
# i = 0, ... , N-1 -- всего N Введите й элемент ".format(i+1))
X.append(float(input()))
Max = X[0] for i in range(1,N):
# i = 1, ... , N-1 -- всего N-1 сравнений if X[i] > Max:
Max = X[i] Максимальный элемент в массиве = ", Max) Программа в системе Матлаб Введите число элементов массива '); Введите элементы массива for i=1:N disp(sprintf('x(%g)=',i)) x(i)= input(' '); end max=x(1); for i=2:N if x(i)>max max=x(i); end end Максимальный элем)
С использованием матричных функций Введите число элементов массива '); Введите элементы массива for i=1:N disp(sprintf('x(%g)=',i)) x(i)= input(' '); end max_el=max(x); Максимальный элемент) Задача 6. Поиск минимума в массиве и его перестановка Условие задачи. В заданном массиве поменять местами минимальный элемент с первым. Известно, что в массиве имеется только один элемент с минимальным значением.
Для того чтобы поменять местами два элемента массива, необходимо знать их индексы (номера. По условию задачи требуется
поменять местами й элемент массива с минимальным, поэтому наша задача сначала найти позицию минимального элемента, а затем осуществить перестановку. Алгоритм поиска наименьшего элемента массива аналогичен алгоритму поиска максимума, его конкретное применение к этой задаче рассмотрим ниже. Обычно обмен местами, или перестановка, значений двух переменных осуществляется с использованием вспомогательной переменной следующим образом. В эту вспомогательную переменную записывается любое из двух перестав- ляемых местами значений, например, первое из них, затем на место первой переменной помещается значение второй переменной, а на место второй переменной переносится содержимое вспомогательной переменной, в которой сохранено исходное значение первой переменной. Аналогичным образом осуществляют перестановку значений двух элементов массива. Например, нам надо переставить элементы массива
X с номерами
k и
p. Выберем переменную, например
buf, в нее запишем значение элемента массива с номером
k (
buf=X[k]) , на место этого элемента поместим элемент с номером
p (
X[k]= X[p]), а на место элемента с номером p поместим значение переменной
buf, в которой сохранено исходное значение
X[k] (
X[p]=buf). В нашей задаче нужно поменять местами первый элемент массива с наименьшим. Для поиска минимального значения и его номера предусмотрим переменные
min и
pmin. В переменную
min поместим первый элемент массива (min=X[1]), а в pmin
его номер (pmin=1). Далее в цикле i=2, n, со второго элемента массива до последнего, будем последовательно сравнивать каждый элемент массива с содержимым ячейки min. Если очередной элемент массива X[i], окажется меньше, чем значение min, тов переменную min записывается элемента в pmin запоминается его номер (pmin=i). Так будет продолжаться n-1 раз, пока все элементы массива не будут проверены. В результате в переменной min окажется наименьший элемент массива, а в pmin
его номер. Как мы уже знаем, перестановка элементов массива производится через вспомогательную переменную. Однако в нашем случае мы определили и позицию минимального элемента (pmin), и само его значение (min), поэтому в качестве вспомогательной переменной можно использовать переменную min, в которой уже хранится значение минимума. Для перестановки можно выполнить следующие действия в элемент массива с номером pmin на место минимума) занести первый элемент массива
(X[pmin]=X[1]), а на место первого элемента
значение минимального элемента (X[1]=min). Теперь нужно вывести измененный массив. Структурированная запись алгоритма 6
1. Ввести количество элементов массива n и значения элементов массива X.
2. Для контроля вывести исходный массив X.
3. В переменную pmin записать номер первого элемента массива в min – значение этого элемента (min=X[1]).
4. В цикле для i=2, n повторять
4.1. Если X[i]4.1.1. min=X[i]
4.1.2. pmin=i
5. Выполнить перестановку элементов X[pmin]=X[1]; X[1]=min.
6. Вывести массив Х после перестановки элементов. Схема алгоритма
31 1
1
32 Программа на языке Си
#include
#define N 20 int main()
{ int i, n, pmin; double X[N], min; printf("n="); scanf("%d",&n); printf("\n Введите элементы массива for(i=0; i { min=X[i]; pmin=i;
}
X[pmin]=X[0];
X[0]=min; printf("\n Измененный массив for(i=0; i} Программа на языке Паскаль
Program main_6;
Var
X:array of real; min:real; n,i,pmin:integer; begin Введите n'); readln(n); setlength(X,n); Введите массив for i:=0 to n-1 do readln (X[i]); pmin:=0; min:=X[0]; for i:=1 to n-1 do if x[i]
33
end;
X[pmin]:=X[0];
X[0]:=min; Измененный массив for i:=0 to n-1 do write(X[i]:3:0,' '); writeln;
X:=nil; end. Программа на языке Фортран
Program main
Implicit none real, allocatable :: X(:) integer i ,n,pmin real min Введите n' read*,n allocate(X(n)) Введите массив' read*,(X(i), i=1,n) print *, 'Исходный массив' print '((F4.1,2x))',(X(i),i=1,n) min=X(1) pmin=1 do i=2,n if (X(i) X(pmin)=X(1)
X(1)=min print *, 'Измененный массив' print '((F4.1,2x))',(X(i),i=1,n) deallocate(X) end Программа на языке Python Введите число элементов массива) print(" (если N<1 то N=50) ")
N=int(input()) if N < 1:
N = 50 Х = [] # Создаем пустой список for i in range(N): # i = 0, ... , N-1 -- всего N
34 Введите й элемент : ".format(i+1))
Х)
K=0
Min = Х for i in range(1,N):
# i = 1, ... , N-1 -- всего N-1 сравнений if Х K = i
Min = Х Х = Х Х = Min Измененный массив ") for i in range(N): Х = {1} "Х) Программа в системе Матлаб Введите n='); for i=1:n
X(i)=input('X(i)='); end pmin=1; min=X(1); for i=2:n if X(i)X(pmin)=X(1);
X(1)=min; Измененный массив disp(X) С использованием векторных операций и функций Введите n='); for i=1:n
X(i)=input('X(i)='); end
[minx,pmin]=min(X);
X(pmin)=X(1);
X(1)=minx; Измененный массив disp(X)
Задача 7. Поиск минимального из элементов, удовлетворяющих условию Условие задачи. Найти минимальный из положительных элементов заданного массива. Считается, что в массиве только один элемент с таким значением. Когда поиск минимального значения осуществляется среди всех элементов массива, в качестве начального
значения минимума берется первый элемент, затем с этим значением в цикле сравниваются все элементы и при нахождении элемента, меньшего минимального, значение эталона меняется. Поиск среди элементов массива, удовлетворяющих некоторым критериям, осуществляется подобным же образом. Но за начальное значение эталона надо взять первый удовлетворяющий критериям элемент, затем в цикле сравнивать с этим значением остальные подходящие элементы, те. только те, которые удовлетворяют тем же критериям. Поиск первого элемента с нужными характеристиками осуществляется последовательным перебором элементов, начиная с первого, до тех пор, пока не будет найден элемент, удовлетворяющий условиям, или не будет достигнут конец массива. В последнем случае можно сказать, что подходящих элементов в массиве вообще нет, в этом случае получить корректное значение минимума не удастся. Нужно непросто найти значение минимума, а указать его позицию в массиве, поэтому при задании начального значения эталона нужно запомнить индекс первого удовлетворяющего критериям элемента, а каждый раз при изменении значения эталона на меньшее значение запоминать и индекс меньшего элемента. Исходным данным в этой задаче является некоторый массив, причем не указано ни количество элементов в нем, ни их тип. Поскольку минимум – понятие математическое, можно сделать вывод, что в массиве содержатся числа. Числа могут быть любыми, значит, необходимо использовать вещественный тип элементов. Количество элементов массива, очевидно, будет задаваться пользователем. Это значение должно быть натуральным числом. Введем обозначения количество элементов массива
N, массив А, индекс элемента массива
i, значение минимума
min, индекс минимального элемента Структурированная запись алгоритма 7
1. Ввести количество элементов массива
N.
2. Повторять
N разв цикле
i=1,N:
2.1. Ввести значение элемента массива
A[i].
36 3. i=1.
4. Повторять, пока i≤N и A[i]≤0:
4.1. i=i+1.
5. Если i>N, то вывести сообщение В массиве нет положительных элементов и закончить выполнение алгоритма.
6. Запомнить индекс найденного положительного числа i_min=i.
7. Запомнить значение найденного положительного числа
min=A[i_min].
8. Повторять в цикле i=i_min+1,N.
8.1. Если A[i]>0 и A[i], то. запомнить новое значение эталона min=A[i].
8.1.2. запомнить индекс текущего элемента i_min=i.
9. Вывести на экран значение минимального положительного элемента min и его индекс i_min. Схема алгоритма
Программа на языке Си
38
#include int main (void)
{ double a[20], min; int n, i, i_min; printf (Введите число элементов массива scanf (″%d”, &n); if (n>20) n=20; printf (Введите значения элементов for (i=0; i { printf (″a[%d]=”, i); scanf (″%lf”, &a[i]);
} for (i=0; i { printf (Положительных элементов нет return 0;
} i_min=i; min=a[i_min]; for (i=i_min+1; i0 && a[i] { min=a[i]; i_min=i;
} printf (Минимальный положительный элемент a[%d] = %lf”, i_min, min); return 0;
} Программа на языке Паскаль
Program Pr_7; var a : array [1..20] of real; min : real; n, i, i_min : integer; begin writeln (Введите число элементов массива read (n); if n>20 then n:=20; writeln (Введите значения элементов for i:=1 to n do begin write (’a[’, i, ’]=’); read (a[i]) end; i:=1; while (i<=n) and (a[i]<=0) do
39
i:=i+1; if i>n then begin write (Положительных элементов нет halt end; i_min:=i; min:=a[i_min]; for i:=i_min+1 to n do if (a[i]>0) and (a[i]
Program Pr_7
Implicit none real, allocatable :: a(:) real min integer n, i, i_min print *, Введите число элементов массива read *, n allocate(a(n)) print *, Введите значения элементов do i=1, n print *,’a(’, i, ’)=’ read *, a(i) enddo i=1 do while (i<=n.and.a(i)<=0) i=i+1 enddo if (i>n) then print *, Положительных элементов нет stop endif i_min=i min=a(i_min) do i=i_min+1, n if (a(i)>0.and.a(i)
40 i_min, ’)=’, min deallocate(a) end Программа на языке Python Введите N -- число элементов массива ")
N=int(input())
A = [] # Создаем пустой список for i in range(1,N+1): # i = 1, ... , N -- всего N Введите й элемент : ".format(i))
A.append(float(input())) i = 1 while i <= N and A[i-1] <= 0: i = i + 1 if i > N: В массиве нет положительных элементов) else: i_min = i min = A[i_min-1] for i in range(i_min + 1, N+1):
# i = i_min+1, ..., N -- N-i_min элементов if A[i-1] > 0 and A[i-1] < min: min = A[i-1] i_min = i Минимальный положительный элемент, min) Его индекс, i_min) Программа в системе Матлаб введите n='); for i=1:n
A(i)=input('A(i)='); end i=1; while i<=n && A(i)<=0 i=i+1; end if i>n Положительных элементов нет) else i_min=i; min=A(i_min); for i=i_min+1:n if A(i)>0 && A(i)
41
disp( min ) Его индекс) disp( i_min ) end С использованием векторных операций и функций введите n='); for i=1:n
A(i)=input('A(i)='); end
B=A(A>0); if length(B)==0 Положительных элементов нет) else
[min,i_min]=min(B); Минимальный положительный элемент) disp( min ) Его индекс) disp( i_min ) end Задача 8. Удаление максимального элемента из массива Условие задачи. Удалить максимальный элемент из заданного массива. Считать, что в массиве имеется только один элемент с максимальным значением. Для того чтобы из некоторого массива
X из
n элементов удалить какой-либо элемент, надо знать номер этого элемента, назовем его
pos. Элементы,
расположенные передним надо оставить без изменения, а все остальные, начиная с элемента с номером
pos+1, необходимо сдвинуть влево на одну позицию, те. на место каждого элемента от
pos до
n-1 поставить следующий элемент. Это можно сделать в цикле
i=pos,n-1, выполняя операцию
X[i]=X[i+1]. В результате сдвига получается, что элемент с номером
pos замещается, все последующие элементы сдвигаются на одну позицию влево, но последний элемент в массиве повторяется два раза. Физический размер массива остается прежним, а по смыслу после удаления одного элемента количество элементов в массиве уменьшается на 1. Поэтому, чтобы в дальнейшем можно было работать с реальным размером массива, количество элементов массива уменьшают на 1 (
n= n-1). Рассмотрим теперь нашу задачу. Количество элементов массива
n и сам массив X – исходные данные в этой задаче. Например, пусть
n =8, а элементы массива имеют значения 8, 3, 9, 100, 4, 70, 2, -5. Для решения этой задачи, необходимо сначала найти индекс (номер) максимального элемента. Это можно сделать двумя способами. Можно использовать традиционный алгоритм. Выделить переменную, например max, в которую следует помесить й элемент массива, и переменную для хранения номера элемента – pmax. Затем в цикле сравнить все остальные элементы массива X[i] с содержимым переменной, и если X[i] окажется больше
max, тов поместить этот элемента в
pmax его номер. В результате для нашего примера окажется, что
pmax=4, max=
100. Второй способ не требует хранения значения максимального элемента в переменной
max, а требует запоминания только его номера. Для этого в переменную
pmax сначала следует записать
1 – номер первого элемента (
pmax=1). Затем в цикле
(i=2,n) последовательно каждый очередной элемент массива X[i] сравнить c элементом с номером) и если X[i] окажется больше X[pmax], то номер этого элемента поместить в переменную pmax (pmax=i). Прибудем сравнивать X[2] и X[pmax]. В нашем случае x[2]=3 и x[1]=8. 3 не больше 8, поэтому значение pmax не изменяется и дальше будем сравнивать следующую пару X[3] и X[pmax], те. 9 и 8. Третий элемент, равный 9, больше 8, поэтому pmax получает значение 3, и далее сравниваем очередную пару X[4] и X[pmax], это 100 и 9. 100>9, поэтому в переменную pmax запишем номер этого элемента
4
(pmax=4), и далее следующие элементы сравниваем четвёртым. Для нашего примера далее не будет элемента большего 100, и по окончании проверки всех элементов массива в переменной pmax останется значение, равное 4 (pmax=4). Это значение будет номером максимального элемента. Теперь, когда мы знаем индекс удаляемого элемента массива
pmax, можно осуществить сдвиг. Для этого организуем цикл попеременной, которая будет изменяться от i=pmax дои последовательно на е место будем записывать элемент, стоящий правее (X[i]=X[i+1]). На первом шаге при i = pmax на место элемента запишется элемент X[pmax+1] (X[4]= X[5], те на место числа 100 запишется 4) и т.д. В результате сдвига получим измененный массив 8, 3, 9, 4, 70, 2, -5, -5, в котором последний элемент повторяется. Физически удалить последний элемент затруднительно, поэтому просто считаем, что размер массива стал на один элемент меньше n=n-1. Теперь остается только вывести измененный массив. Структурированная запись алгоритма 8
1. Ввести количество элементов массива n и значения элементов массива X.
43 2. В переменную pmax записать номер первого элемента массива. В цикле для i=2, n повторять
3.1. Если X[i]>X[pmax], тов переменной pmax запомнить номер этого элемента (pmax=i).
4. В цикле для i=pmax, n -1 повторять
4.1. Сдвиг элементов X[i]=X[i+1].
5. Уменьшить количество элементов массива на 1 (n=n-1).
6. Вывести измененный массив. Схема алгоритма
1
44 Программа на языке Си
#include
#define N 20 int main()
{ double X[N]; int i,n,pmax; printf("n="); scanf("%d",&n); printf("\n Введите массив for(i=0;iX[pmax]) pmax=i; for(i=pmax;i X[i]=X[i+1]; n=n-1; printf("\n Измененный массив
1
45
for(i=0;i } Программа на языке Паскаль
Program main_8;
Var
X:array of integer; n,i,pmax:integer; begin Введите n'); readln(n); setlength(X,n); Введите массив for i:=0 to n-1 do readln (X[i]); pmax:=0; for i:=1 to n-1 do if X[i]>X[pmax] then pmax:=i; for i:=pmax to n-2 do X[i]:=X[i+1]; n:=n-1; for i:=0 to n-1 do write(X[i],' ');
X:=nil; end. Программа на языке Фортран
Program main_8
Implicit none integer, allocatable :: X(:) integer i ,n, pmax, max Введите n' read*,n allocate(X(n)) Введите массив' read*,(X(i), i=1, n) pmax=1 do i=2,n if (X(i)>X(pmax)) pmax=i enddo do i=pmax,n-1
X(i)=X(i+1) enddo n=n-1 print 'Измененный массив, &
(X(i),i=1,n) deallocate(X) end
46 Программа на языке Python Введите N -- число элементов массива ")
N=int(input())
X = [] # Создаем пустой список for i in range(1,N+1): Введите й элемент ".format(i))
X.append(float(input())) k = 0 # В Python списки индексируются с 0, for i in range(0, N): # i = 0, ... , N-1 if X[i] > X[k]: k = i for i in range(k, N-1):
X[i] = X[i + 1] for i in range(0, N-1): print("X[{0}]={1}".format(i+1, X[i])) Программа в системе Матлаб введите n='); for i=1:n
X(i)=input('X(i)='); end pmax=1; for i=1:n if X(i)>X(pmax) pmax=i; end end for i=pmax:n-1
X(i)=X(i+1); end n=n-1; Измененный массив disp(X(1:n)); С использованием матричных функций введите n='); for i=1:n
X(i)=input('X(i)='); end вместо переменной max используем xmax
[xmax,pmax]=max(X);
X(pmax)=[]; Измененный массив disp(X)
Задача 9. Вставка элемента в массив Условие задачи.В заданном целочисленном массиве вставить элемент, равный сумме первого и последнего элементов, перед третьим элементом. Для того чтобы в массив из n элементов вставить новый элемент перед элементом массива x с номером k, необходимо выполнить следующие действия первые k-1 элементов массива оставить без изменения, а все элементы, начиная с го до го, сдвинуть на одну позицию вправо. Причём сдвиг элементов надо начинать с конца, чтобы при сдвиге не потерять (не затереть) элементы. Для этого используется цикл, в котором управляющая переменная изменяется от большего значения к меньшему с отрицательным шагом -1. Затем на место элемента с номером k записать необходимое значение. В задачах, где необходимо вставить в массив новый элемент следует учесть, что количество элементов массива после вставки будет на один элемент больше, те. если в исходном массиве было n элементов, то при объявлении массива в программе нужно предусмотреть место для n+1 элемента. Количество элементов массива n и сам массив x – исходные данные в этой задаче. Например, пусть n =6, а элементы массива имеют значения 9, 3, 8, 4, 7, 2. Нужно выделить переменную, в которую поместить сумму го и последнего элементов s=x[1]+x[6]. При таких данных s= 11. Таким образом, после элемента с номером 2 надо вставить значение 11. Для того чтобы вставить элемент со значением 11 перед третьим элементом, организуем цикл с отрицательным шагом
i=6, 3, -1 для перемещения элементов вправо. В цикле будем на е место записывать й элемент (x[i+1]=x[i]). Так на первом шаге при i=6 на е место в встанет й элемент 2, при i=5 на е место – й элемент 7 и т.д. Таким образом, после сдвига получим массив 9,
3, 8, 8, 4, 7, 2. Теперь в элемент с номером 3 запишем 11(x[3])=s). Измененный массив будет иметь значения 9, 3, 11, 8, 4, 7, 2. Размер массива станет на 1 больше. Заметим, что если бы сдвиг элементов производился слева направо в цикле i=3,6, то при i=3 на е место попало значение го элемента, а прежнее значение го элемента пропало, затем при i=4 на е место попало бы значение го элемента, а оно теперь станет равными т.д. Тогда после сдвига элементов массив будет содержать значения 9, 3, 8, 8, 8, 8, 8, что, конечно, будет неправильно. Следовательно, для решения задачи потребуется следующие последовательность действий. С клавиатуры введем количество элементов массива n и массив х В программной реализации при объявлении массива надо учесть, что при решении задачи количество элементов массива увеличится на 1. В переменную s запишем сумму первого и последнего элементов массива s=x[1]+x[n]. Для того чтобы вставить элемент, равный s, в массив, необходимо предусмотреть место для нового элемента, те. раздвинуть массив. Первые два элемента по условию задачи должны остаться без изменения, а остальные элементы, начиная с го надо сдвинуть на одну позицию вправо. Для этого организуем цикл i=n,3,-1, в котором управляющая переменная i изменяется от n до 3 с отрицательным шагом -1. В теле цикла для каждого значения i выполняется оператор в результате которого происходит перестановка (сдвиг) элементов. После завершения цикла на место го элемента массива записшем значение суммы первого и последнего элементов x[3]=s. Так как размер массива после вставки увеличился на единицу, то значение n изменяется n=n+1. В заключение полученный массив выводится на экран. Структурированная запись алгоритма 9
1. Ввод количества элементов массива n и значений элементов массива x.
2. В переменную s записывается сумма первого и последнего элементов массива s=x[1]+x[n].
3. В цикле для i=n, 3, -1 повторять
3.1. Сдвиг элементов x[i+1]=x[i].
4. На место го элемента массива записывается новое значение
x[3]=s.
5. n=n+1.
6. Вывод массива. Схема алгоритма
1
Программа на языке Си
#include
#define N 20 int main()
{ int i,n,s,x[N]; printf("n="); scanf("%d",&n); printf("\n Введите массив \n"); for(i=0;i=2;i--)
1
50 x[i+1]=x[i]; x[2]=s; printf("\n Новый массив \n"); n++; for(i=0;i} Программа на языке Паскаль
Program main_9;
Var x: array [1..20] of integer; i,n,s:integer; begin writeln('n='); readln(n); Введите массив for i:=1 to n do readln (x[i]); Исходный массив for i:=1 to n do write(x[i]:3,' '); writeln; s:=x[1]+x[n]; for i:=n downto 3 do x[i+1]:=x[i]; x[3]:=s; n:=n+1; Новый массив for i:=1 to n do write(x[i]:3,' '); end. Программа на языке Фортран
Program main_9
Implicit none integer, allocatable::x(:) integer i,n,s print*,'n=' read*,n allocate(x(n+1)) Введите массив' read*,(x(i), i=1, n) print Исходный массив) s=x(1)+x(n) do i=n,3,-1 x(i+1)=x(i) enddo x(3)=s n=n+1 print Новый массив ',x
51
deallocate (x) end program main_9 Программа на языке Python Введите N -- число элементов массива ") n=int(input()) x = [] # Создаем пустой список for i in range(1,n+1): # i = 1, ... , N -- всего N Введите й элемент массива ".format(i)) x.append(float(input())) Исходный массив ") for i in range(0, n): print("A[{0}]={1}".format(i+1, x[i])) s = x[0] + x[n-1] # В алгоритме s = x(1) + x(n)
# нов списки индексируются с 0 x.append(0.0) # добавляем в список еще один элемент, for i in range(n-1, 1, -1):
# i = n-1, ... , 2 -- 2 - индекс третьего элемента x[i + 1] = x[i] x[2] = s n = n + 1 Новый массив ") for i in range(0, n): print("A[{0}]={1}".format(i+1, x[i])) Программа в системе Матлаб введите n='); for i=1:n
X(i)=input('X(i)=');
End исходный массив)
Disp(X) s=X(1)+X(n); for i=n:-1:3
X(i+1)=X(i); end
X(3)=s; n=n+1; Измененный массив for i=1:n disp(X(i)); end С использованием векторных операций введите n='); for i=1:n
X(i)=input('X(i)='); end s=X(1)+X(n);
52
X(4:n+1)=X(3:n);
X(3)=s; Измененный массив disp(X) Задача 10. Формирование нового массива на основе исходного Условие задачи.Дан одномерный массив А целых чисел и два числа x и y. Сформировать массив Виз элементов исходного, лежащих в интервале от x до y. Исходными данными являются количество элементов массива n, элементы массива Аи два числа x и y, задающие начало и конец интервала. Результатом будет одномерный массив В. Количество элементов исходного массива n вводится, а количество элементов результирующего массива заранее неизвестно, оно зависит от исходных данных и может быть иное, чем y исходного. Элементы исходного массива А, принадлежащие заданному интервалу (x,y), должны быть записаны в массив В под другими номерами, нежели в исходном массиве. Например, пусть дан числовой массив из 10 элементов Аи интервал (2,5). Проверка исходного массива начинается с первого элемента А, он не попадает в интервал и его в массив В заносить не надо. Проверяем второй элемент А, он тоже не попал в интервал, значит, и его заносить в массив Вне надо. Проверяем третий элемент А , он попадает в интервал, следовательно, его надо занести в массив В Если делать это, используя присваивание В[i]=А[i], и помещать его в массив В под тем же номером 3, то первые два элемента будут заполнены неопределенными значениями (в лучшем случае нулями) и таких элементов может быть много. Это зависит оттого, сколько элементов массива А попадут в интервал. В приведенном примере массив В получится таким {0,0,3,0,0,4,0,0,0,0}. Поэтому новый массив В надо заполнять, начиная с первого элемента, а для номеров элементов необходимо предусмотреть дополнительную переменную
k, которую надо увеличивать на 1 каждый раз, перед тем как заносить новый элемент в массив В. Тогда полученный массив В будет содержать значения {3,4}. Переменная k будет не только номером элемента нового массива В, но после окончания формирования массива будет определять реальное количество элементов в нем. Это надо учитывать при выводе массива В. Для обозначения индексов элементов массива А возьмем переменную i. До цикла переменной k присваивается начальное
значение, равное 0, затем, в цикле для i, изменяющейся от 1 до n, каждый элемент массива А проверяется на принадлежность интервалу (х,у). Если условие выполняется, то формируется следующий номер элемента нового массива k=k+1 ив В заносится проверенный элемент исходного массива А. После выхода из цикла значение k будет определять количество элементов нового массива В. Если значение осталось равным нулю, значит в массиве Ане оказалось элементов, удовлетворяющих заданному условию. Следовательно, перед выводом необходимо выполнить проверку значения k. Если k=0, то выдается соответствующее сообщение на экран, в противном случае
k элементов полученного массива выводятся на экран с использованием оператора цикла с параметром, изменяющимся от 1 до k. Структурированная запись алгоритма 10
1. Ввести значения границ интервала x и y.
2. Ввести количество элементов исходного массива n.
3. Ввести элементы массива А.
4. Задать начальное значение индексу нового массива k=0.
5. Повторять n раз для i=1, n следующее действие
5.1. Проверить каждый элемент исходного массива A[i] на принадлежность заданному диапазону хи. Если условие выполняется, то значение индекса k надо изменить на 1 и записать элемент A[i] в элемент массива В k=k+1; В = A[i].
6. Проверить значение k. Если оно равно нулю,
6.1. то вывести сообщение Нужных элементов в исходном массиве нет,
6.2. иначе в цикле от 1 до k вывести элементы полученного массива. Схема алгоритма
1
54 Программа на языке Си
#include
#define N 50 int main (void)
{ int A[N], B[N], n, k=-1, i, x, y; Введите x,y\n"); scanf("%d",&x); scanf("%d",&y); Введите n\n"); scanf("%d", &n); Введите элементы массива A\n"); for (i=0; i1
55
scanf ("%d", &A[i]); for (i=0; ix && A[i] { k++; B[k]=A[i];
} if (k==(-1)) Нужных элементов в массиве нет else
{ printf (Полученный массив for (i=0; i<=k; i++) printf ("%d\t", B[i]); printf("\n");
} return 0;
} Программа на языке Паскаль
Program Main_10;
Var a,b: array of integer; i,n,k,x,y: integer; begin Введите интервал (x,y)'); readln(x,y); Введите кол-во эл-тов масс readln(n); setlength(a,n); setlength(b,n); Введите элементы массива for i:=0 to n-1 do readln(a[i]); k:=-1; for i:=0 to n-1 do if (a[i]>x) and (a[i]
56 Программа на языке Фортран
Program main_10 implicit none integer, allocatable :: A(:), B(:) integer i, n, k, x, y print Введите хи' Введите количество элементов массива' read *, n allocate (A(n)) allocate (B(n)) print *,' Введите элементы массива A' read *, (A(i), i=1,n) k=0 do i =1, n if (A(i)>x .and. A(i) B(k)=A(i) endif enddo if (k==0) then print Нужных элементов в массиве нет' else print *, 'Полученный массив' print *, (B(i), i=1,k) endif deallocate(A) deallocate(B) end Программа на языке Python
# В качестве массива используется
# стандартный тип list (список) Введите x -- левую границу диапазона) x= float(input()) Введите y -- правую границу диапазона) y= float(input()) Введите N -- число элементов массива A: ") n=int(input())
A = [] # Создаем пустой список for i in range(1,n+1): # i = 1, ... , N -- всего N Введите й элемент : ".format(i))
A.append(float(input()))
B = [] # Создаем второй пустой список k = 0
# в Python списки индексируются с 0,
# следовательно k=0 -- это не индекса число элементов во втором списке
# (а индекс будет k-1) for i in range(0, n): if x < A[i] < y: k = k + 1
B.append(0)
# Физически добавляем элемент со значением 0 вконец Нужных элементов в исходном массиве нет) else: Полученный массив) for i in range(0, k): print("B[{0}]={1}".format(i+1, B[i])) Программа в системе Матлаб Введите левую границу интервала '); Введите правую границу интервала '); Введите число элементов массива '); Введите элементы массива for i=1:n disp(sprintf('a(%g)=',i)) a(i)= input(' '); end k=0; for i=1:n if a(i)>x & a(i)x & a
58 else Новый массив) disp(b); end Задача 11. Перебор всех пар элементов в массиве. Вложенные циклы Условие задачи. Дан целочисленный массив. Найти в нём пару чисел, наиболее близких друг другу по значению.
Исходные данные – количество элементов заданного массива
N и сами целочисленные элементы массива А, результаты – номера и значения двух элементов, удовлетворяющих условию. Наиболее близкими по значению являются элементы, для которых модуль разности минимален. Иначе говоря, нужно перебрать всевозможные пары элементов, вычислить разность между элементами каждой пары (точнее, модуль этой разности) и из всех модулей разности найти минимальную, при этом зафиксировать, для каких элементов найдена эта разность. Перебор всех возможных пар элементов требует организации двух циклов, вложенных друг в друга. Так, первый элемент должен быть рассмотрен в паре со всеми остальными элементами – со второго до последнего. Для второго элемента пары будут составлять все элементы, кроме него самого, нов паре с первым он уже был рассмотрен, поэтому остаётся перебрать только элементы с третьего до последнего. Третий элемент уже рассмотрен в паре с первыми двумя, и для него остаётся перебрать элементы с четвёртого до последнего, и т.д. Когда дело дойдёт до последнего элемента, окажется, что он уже рассмотрен в паре со всеми предыдущими. Таким образом, для полного перебора всех пар каждый элемент
A[i] (его номер
i будет изменяться от 1 до
N-1) нужно сопоставлять со всеми элементами стоящими правее него, где
j будет изменяться от
i+1 до
N. Переменная будет
управляющей переменной внешнего цикла,
j – внутреннего. Как всегда делается при поиске минимума, сначала надо задать начальные значения переменной
Min – модуль разности первых двух элементов, переменными номера этих элементов (1 и 2). Далее во вложенных циклах (
i=1,
N-1 и
j=
i+1
,N) надо для всех пар элементов вычислять модуль их разности
R=
abs(
A[i]-
A[j]) и сравнивать его с текущим значением
Min, если очередная разность элементов окажется меньше
Min, тов переменную
Min надо занести эту
меньшую разность R для последующих сравнений, а в переменные
Pos1 и Pos2 – номера элементов, для которых вычислялась эта разность и j). Тогда по окончании всех переборов в переменной Min окажется самая маленькая разность между элементами, взятая по модулю, а в переменных Pos1 и Pos2 – номера этих двух элементов. В качестве результата нужно вывести найденные номера элементов и Pos2, а также их значения A[Pos1] и A[Pos2]. Структурированная запись алгоритма 11
1. Ввести размер массива N и сам массив А.
2. Задать начальные значения Min=abs(A[1]-A[2]); Pos1=1; Pos2=2.
3. Повторять в цикле для i=1,N-1:
3.1. Повторять в цикле для j=i+1,N:
3.1.1. Вычислять R=abs(A[i]-A[j]).
3.1.2. Сравнивать R c Min: если R < Min, то
3.1.2.3. Min=R.
3.1.2.4. Pos1=i; Pos2=j.
4. Вывести Pos1, A[Pos1], Pos2, A[Pos2]. Схема алгоритма
1
60 Программа на языке Си
#include
#include
#define N 25 int main (void)
{ int a[N], n, i, j, min, r, pos1, pos2; printf (Введите количество элементов массива scanf ("%d", &n); printf (Введите элементы массива for (i=0; i {
1
61
r=abs(a[i]-a[j]); if (r { r=min; pos1=i; pos2=j;
}
} printf (Наиболее близкие элементы a[%d]=%d и \ a[%d]=%d\n", pos1,a[pos1],pos2,a[pos2]); return 0;
} Программа на языке Паскаль
Program Pr_11;
Var
A: array of integer; i, N, j, Pos1, Pos2, Min, R: integer; begin Введите количество элементов массива readln(N);
SetLength(A,N+1);
{ Памяти выделено на 1 элемент больше, чтобы использовать более удобную индексацию элементов от 1 до N, а не от 0 до N-1 } Введите элементы массива for i:=1 to N do readln(A[i]);
Min:=abs(A[1]-A[2]);
Pos1:=1; Pos2:=2; for i:=1 to N-1 do for j:=i+1 to N do begin
R:=abs(A[i]-A[j]); if R Min:=R; Pos1:=i; Pos2:=j end; end; Наиболее близкие элементы A[',Pos1,’]=’,
A[Pos1],’ и A[',Pos2,’]=’,A[Pos2]);
A:=Nil end. Программа на языке Фортран
Program Pr_11
Implicit none integer, allocatable :: A(:) integer i, N, j, Pos1, Pos2, Min, R print *, 'Введите количество элементов массива' read *, N
62 allocate(A(N)) print *, 'Введите элементы массива' read *, A
Min=abs(A(1)-A(2))
Pos1=1
Pos2=2 do i=1, N-1 do j=i+1, N
R=abs(A(i)-A(j)) if (R
Min=R
Pos1=i
Pos2=j endif enddo enddo print Наиболее близкие элементы A[',Pos1, &
’]=’,A(Pos1),’ и A[',Pos2,’]=’,A(Pos2)
Скачать 1.6 Mb.