Основы программирования Массивы. - презентация

1 Основы программирования Массивы

2

3 3 Теперь мы приступаем к изучению массива - наиболее широко используемого структурированного типа данных, предназначенного для хранения нескольких однотипных элементов. Массив – это последовательность однотипных данных, объединенная общим именем, элементы (компоненты) которой отличаются (идентифицируются) индексами. Индекс элемента указывает место (номер) элемента в массиве. Количество элементов массива фиксировано и определено в его описании. К элементам массива можно обращаться только по их номеру (индексу). Все компоненты массива являются одинаково доступными. Значения элементам массива присваиваются также как и другим переменным с учетом типа массива.

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

5 5 Массивы A массив 3 15 НОМЕР элемента массива (ИНДЕКС) НОМЕР элемента массива (ИНДЕКС) A[1] A[2] A[3] A[4] A[5] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива: 2 ЗНАЧЕНИЕ элемента массива: 10

6 6 Объявление массивов Зачем объявлять? определить имя массива определить тип массива определить число элементов выделить место в памяти Массив целых чисел: Размер через константу: имя начальный индекс конечный индекс тип элементов тип элементов var A: array[1.. ] of integer; const N=5; N var A : array[ ] of integer ;

7 7 Объявление массивов Массивы других типов: Другой диапазон индексов: Индексы других типов: var X, Y: array [1..10] of real; C: array [1..20] of char; var X, Y: array [1..10] of real; C: array [1..20] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var A: array ['A'..'Z'] of real; B: array [False..True] of integer;... A['C'] := *A['B']; B[False] := B[False] + 1; var A: array ['A'..'Z'] of real; B: array [False..True] of integer;... A['C'] := *A['B']; B[False] := B[False] + 1;

8 8 Объявление массива Для того чтобы задать массив, необходимо в разделе описания переменных (var) указать его размеры и тип его компонент. Общий вид описания (одномерного) массива: array [ ] of ; Чаще всего это трактуется так: array [.. ] of ; array [.. ] of ;

9 9 Нумерация Нумеровать компоненты массива можно не только целыми числами. Любой порядковый тип данных (перечислимый, интервальный, символьный, логический, а также произвольный тип, созданный на их основе) имеет право выступать в роли нумератора. Таким образом, допустимы следующие описания массивов: type charrr = 'a','c'..'z'; (- отсутствует символ "b") var a1: array[charrr] of integer; - 25 компонент a2: array [char] of integer; целых компонент a3: array [shortint] of real; вещественных компонент type charrr = 'a','c'..'z'; (- отсутствует символ "b") var a1: array[charrr] of integer; - 25 компонент a2: array [char] of integer; целых компонент a3: array [shortint] of real; вещественных компонент

10 10 Нумерация Общий размер массива не должен превосходить байт. Следовательно, попытка задать массив a4:array[integer] of byte; не увенчается успехом, поскольку тип integer покрывает различных элементов. А про тип longint в данном случае лучше и вовсе не вспоминать.

11 11 Тип компонент Тип компонент массива может быть любым: var a4: array[10..20] of real; - массив из компонент простого типа a5: array[0..100] of record1; - массив из записей a6: array[ ] of ^string; - массив из указателей на строки a7: array[-1..1] of file; - массив из имен файловых переменных a8: array[1..100] of array[1..100] of char; - двумерный массив (массив векторов) var a4: array[10..20] of real; - массив из компонент простого типа a5: array[0..100] of record1; - массив из записей a6: array[ ] of ^string; - массив из указателей на строки a7: array[-1..1] of file; - массив из имен файловых переменных a8: array[1..100] of array[1..100] of char; - двумерный массив (массив векторов)

12 12 Что неправильно? var a: array[10..1] of integer;... A[5] := 4.5; var a: array[10..1] of integer;... A[5] := 4.5; [1..10] var a: array ['z'..'a'] of integer;... A['B'] := 15; var a: array ['z'..'a'] of integer;... A['B'] := 15; A['b'] ['a'..'z'] var a: array [0..9] of integer;... A[10] := 'X'; var a: array [0..9] of integer;... A[10] := 'X';

13 13 Массивы Объявление: Ввод с клавиатуры: Поэлементные операции: Вывод на экран: const N = 5; var a: array[1..N] of integer; i: integer; const N = 5; var a: array[1..N] of integer; i: integer; for i:=1 to N do begin write('a[', i, ']='); read ( a[i] ); end; for i:=1 to N do begin write('a[', i, ']='); read ( a[i] ); end; a[1] = a[2] = a[3] = a[4] = a[5] = Почему write ? ? for i:=1 to N do a[i]:=a[i]*2; writeln('Массив A:'); for i:=1 to N do write(a[i]:4); writeln('Массив A:'); for i:=1 to N do write(a[i]:4); Массив A:

14 14 Многомерные массивы Для краткости и удобства многомерные массивы можно описывать и более простым способом: var a9: array[1..10,1..20] of real; - двумерный массив 10 х 20 a10: array[boolean, -1..1, char, ] of word; - четырехмерный массив 2 х 3 х 256 х 21 var a9: array[1..10,1..20] of real; - двумерный массив 10 х 20 a10: array[boolean, -1..1, char, ] of word; - четырехмерный массив 2 х 3 х 256 х 21 Общее ограничение на размер массива - не более байт - сохраняется и для многомерных массивов. Количество компонент многомерного массива вычисляется как произведение всех его "измерений". Таким образом, в массиве а9 содержится 200 компонент, а в массиве а компонент.

15 15 Описание переменных размерностей Если ваша программа должна обрабатывать матрицы переменных размерностей (N по горизонтали и М по вертикали), то вы столкнетесь с проблемой изначального задания массива, ведь в разделе var не допускается использование переменных. Следовательно, самый логичный, казалось бы, вариант var m, n: integer; a: array[1..m, 1..n] of real; var m, n: integer; a: array[1..m, 1..n] of real; придется отбросить.

16 16 Описание переменных размерностей Если на этапе написания программы ничего нельзя сказать о предполагаемом размере входных данных, то не остается ничего другого, как воспользоваться техникой динамически распределяемой памяти

17 17 Описание переменных размерностей Предположим, однако, что известны максимальные границы, в которые могут попасть индексы обрабатываемого массива. Скажем, N и М заведомо не могут превосходить 100. Тогда можно выделить место под наибольший возможный массив, а реально работать только с малой его частью: const nnn=100; var a: array[1..nnn,1..nnn] of real; m, n: integer; const nnn=100; var a: array[1..nnn,1..nnn] of real; m, n: integer; !

18 18 Обращение к компонентам массива Массивы относятся к структурам прямого доступа. Это означает, что возможно напрямую (не перебирая предварительно все предшествующие компоненты) обратиться к любой интересующей нас компоненте массива. Доступ к компонентам линейного массива осуществляется так: [ ] а многомерного – так: [,..., ]

19 19 Обращение к компонентам массива Массив состоит из элементов, имеющих порядковые номера, т.е. элементы массива упорядочены. Таким образом, если объекты одного типа обозначить именем, например "A", то элементы объекта будут A[1], A[2] и т.д. В квадратных скобках указан номер элемента. Порядковый номер элемента массива, обычно не несет никакой информации о значении элемента, а показывает расположение элемента среди других.

20 20 Обращение к компонентам массива Правила употребления индексов при обращении к компонентам массива: 1)Индекс компоненты может быть константой, переменной или выражением, куда входят операции и вызовы функций. 2)Тип каждого индекса должен быть совместим с типом, объявленным в описании массива именно для соответствующего "измерения"; менять индексы местами нельзя. 3)Количество индексов не должно превышать количество "измерений" массива. Попытка обратиться к линейному массиву как к многомерному обязательно вызовет ошибку. А вот обратная ситуация вполне возможна: например, если вы описали N-мерный массив, то его можно воспринимать как линейный массив, состоящий из (N-1)-мерных массивов.

21 21 Описание переменных размерностей Примеры использования компонент массива: a1[1, 3]:= 0; a1[i, 2]:= a1[i, 2]-1; a2['z']:= a2['z']+1; a3[-10]:= 2.5; a3[i+j]:= a9[i, j]; a10[x>0, sgn(x), '!', abs(k*5)]:= 0; a1[1, 3]:= 0; a1[i, 2]:= a1[i, 2]-1; a2['z']:= a2['z']+1; a3[-10]:= 2.5; a3[i+j]:= a9[i, j]; a10[x>0, sgn(x), '!', abs(k*5)]:= 0;

22 22 Задание массива константой Чтобы не вводить массивы вручную во время отладки программы, можно пользоваться не только файлами. Существует и более простой способ, когда входные данные задаются прямо в тексте программы при помощи типизированных констант. Если массив линейный (вектор), то начальные значения для компонент этого вектора задаются через запятую, а сам вектор заключается в круглые скобки.

23 23 Задание массива константой Многомерный массив также можно рассматривать как линейный, предполагая, что его компонентами служат другие массивы. Т.о., для системы вложенных векторов действует то же правило задания типизированной константы: каждый вектор ограничивается снаружи круглыми скобками. Исключение составляют только массивы, компонентами которых являются величины типа char. Такие массивы можно задавать проще: строкой символов.

24 24 Задание массива константой Примеры задания массивов типизированными константами: type mass = array[1..3, 1..2] of byte; const a: array[-1..1] of byte = (0,0,0); {линейный} b: mass = ((1, 2),(3, 4),(5, 6)); {двумерный} s: array[0..9] of char = ' '; type mass = array[1..3, 1..2] of byte; const a: array[-1..1] of byte = (0,0,0); {линейный} b: mass = ((1, 2),(3, 4),(5, 6)); {двумерный} s: array[0..9] of char = ' ';

25 25 Поиск элемента в массиве

26 26 Пусть A = {a 1, a 2,...} – последовательность однотипных элементов и b – некоторый элемент, обладающий свойством P. Найти место элемента b в последовательности А. Постановка задачи

27 27 Постановка задачи Поскольку представление последовательности в памяти может быть осуществлено в виде массива, задачи могут быть уточнены как одна из следующих задач поиска элемента в массиве A: найти максимальный (минимальный) элемент массива; найти заданный элемент массива; найти k–ый по величине элемент массива. Наиболее простые и часто оптимальные алгоритмы основаны на последовательном просмотре массива A с проверкой свойства P на каждом элементе.

28 28 Максимальный элемент Задача: найти в массиве максимальный элемент. Алгоритм: Псевдокод: { считаем, что первый элемент – максимальный } for i:=2 to N do if a[i] > { максимального } then { запомнить новый максимальный элемент a[i] } { считаем, что первый элемент – максимальный } for i:=2 to N do if a[i] > { максимального } then { запомнить новый максимальный элемент a[i] } Почему цикл от i=2 ? ?

29 29 Максимальный элемент max := a[1]; { считаем, что первый – максимальный } iMax := 1; for i:=2 to N do { проверяем все остальные } if a[i] > max then { нашли новый максимальный } begin max := a[i]; { запомнить a[i] } iMax := i; { запомнить i } end; max := a[1]; { считаем, что первый – максимальный } iMax := 1; for i:=2 to N do { проверяем все остальные } if a[i] > max then { нашли новый максимальный } begin max := a[i]; { запомнить a[i] } iMax := i; { запомнить i } end; Дополнение: как найти номер максимального элемента? Как упростить? ? По номеру элемента iMax всегда можно найти его значение a[iMax]. Поэтому везде меняем max на a[iMax] и убираем переменную max. a[iMax]

30 30 program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin writeln('Исходный массив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end. program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin writeln('Исходный массив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end. for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } случайные числа в интервале [50,150) поиск максимального Максимальный элемент

31 © С.В.Кухта, Program Search_in_Array; Label 1; Const n = 100; Var A : Array[1..n] of Real; b : Real; Flag : Boolean; i : Integer; Begin Writeln(Введите массив); {Блок ввода массива} For i:=1 to n do Read (A[i]); Writeln(Введите элемент для поиска); Read (b); Flag := true; For i:=1 to n do If A[i] = b then begin { прерывание цикла } Flag := false; goto 1 end; 1: If Flag then Writeln(Элемента, b, в массиве нет) else Writeln(Элемент, b, стоит на, i, –м месте); End. Program Search_in_Array; Label 1; Const n = 100; Var A : Array[1..n] of Real; b : Real; Flag : Boolean; i : Integer; Begin Writeln(Введите массив); {Блок ввода массива} For i:=1 to n do Read (A[i]); Writeln(Введите элемент для поиска); Read (b); Flag := true; For i:=1 to n do If A[i] = b then begin { прерывание цикла } Flag := false; goto 1 end; 1: If Flag then Writeln(Элемента, b, в массиве нет) else Writeln(Элемент, b, стоит на, i, –м месте); End. Поиск заданного элемента в массиве

32 32 Обработка массивов

33 33 Реверс массива Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять местами A[1] и A[N], A[2] и A[N-1], … Псевдокод: 35…97 79…53 12…N-1N 12… N for i:=1 to N do { поменять местами A[i] и A[N+1-i] } for i:=1 to N do { поменять местами A[i] и A[N+1-i] } сумма индексов N+1 Что неверно? ? N div 2 do

34 34 Как переставить элементы? Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти ? ? x y c c := x; x := y; y := c; c := x; x := y; y := c; x := y; y := x; x := y; y := x; Можно ли обойтись без c ? ?

35 35 Программа program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end; for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end;

36 36 Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего. Алгоритм: A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N]; Цикл: 3581… …N-1N 581…973 for i:=1 to N-1 do A[i]:=A[i+1]; for i:=1 to N-1 do A[i]:=A[i+1]; Что неверно? ? почему не N ?

37 37 Программа program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c; c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c;

38 38 Способы перебора элементов массивов

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

40 40 В массиве одновременно можно обрабатывать один, два, три и т.д. элемента. Часто в качестве параметра цикла используется индекс массива. Обратите внимание также на то обстоятельство, что после изменения индекса его необходимо сразу же проверить на попадание в заданный диапазон, иначе возможны ошибки.

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

42 42 Перебрать элементы массива по одному, двигаясь от начала массива к концу. Случай 1 Здесь индекс начального элемента 1, индекс последнего обрабатываемого элемента n, шаг перебора 1. Конечное значение (кз) параметра цикла при условии проверки окончания с помощью сравнения

43 43 Случай 1 Схема перебора может быть представлена в виде: for i:=1 to n do { обработка a[i] } for i:=1 to n do { обработка a[i] } или: i:=1; while i

44 44 Случай 1 Если условие окончания проверяется с помощью сравнения

45 45 Перебрать элементы массива по одному, двигаясь от конца массива к началу. Случай 2 for i:=n downto 1 do { обработка a[i] } for i:=n downto 1 do { обработка a[i] } или: i:=n; while i>=1 do begin { обработка a[i] } i:=i-1 end; i:=n; while i>=1 do begin { обработка a[i] } i:=i-1 end;

46 46 Обработать массив по одному элементу, двигаясь с обоих концов к середине массива. Случай 3 i:=1; {установка нижней границы} j:=n; {установка верхней границы} while i

47 47 Случай 4 Вариант 1. Здесь индекс начинает изменяться с четного числа, величина шага, равная двум, обеспечивает сохранение четности индекса. i:=2; while i

48 48 Случай 5 Вариант 1. Здесь установка начального значения - не простое присваивание, а условный оператор, позволяющий отыскать последний элемент массива с четным индексом. if n mod 2 =0 then i:=n else i:=n-1; while i>0 do begin { обработка a[i] } ; i:=i-2 end; if n mod 2 =0 then i:=n else i:=n-1; while i>0 do begin { обработка a[i] } ; i:=i-2 end; Перебрать элементы массива с четными индексами, двигаясь от конца массива к началу.

49 49 Случай 5 Вариант 2. Условный оператор, устанавливающий начальное значение индекса, можно внести в тело цикла. i:=n; while i>0 do begin if i mod 2 =0 then { обработка a[i] } ; i:=i-1 end; i:=n; while i>0 do begin if i mod 2 =0 then { обработка a[i] } ; i:=i-1 end;

50 50 Случай 6 Для решения этой задачи соединим схемы перебора, рассмотренные в случаях 4 и 5: i:=2; if n mod 2 =0 then j:=n else j:=n-1; while i

51 51 Случай 7 Для решения этой задачи соединим схемы перебора, рассмотренные в случаях 4 и 5: i:=k; while i

52 52 Случай 8 Для массива из 5 элементов нужно последовательно обработать пары: a[1] и a[2], a[2] и a[3], a[3] и a[4], a[4] и a[5]. Вариант 1. for i:=1 to n-1 do { обработать a[i] и a[i+1] } ; for i:=1 to n-1 do { обработать a[i] и a[i+1] } ; Перебрать соседние элементы массива, двигаясь от начала массива к концу (случай двух соседей). Вариант 2. for i:=1 to n-1 do { обработать a[i-1] и a[i] } ; for i:=1 to n-1 do { обработать a[i-1] и a[i] } ;

53 53 Случай 8 Для массива из 5 элементов нужно последовательно обработать пары: a[1]-a[2]-a[3], a[2]-a[3]-a[4], a[3]-a[4]-a[5]. Вариант 1. for i:=1 to n-2 do { обработать a[i] - a[i+1] - a[i+2] } ; for i:=1 to n-2 do { обработать a[i] - a[i+1] - a[i+2] } ; Перебрать соседние элементы массива, двигаясь от начала массива к концу (случай трех соседей). Вариант 2. for i:=2 to n-1 do { обработать a[i-1] - a[i] - a[i+1] } ; for i:=2 to n-1 do { обработать a[i-1] - a[i] - a[i+1] } ; Вариант 3. for i:=3 to n do { обработать a[i-2] - a[i-1] - a[i] } ; for i:=3 to n do { обработать a[i-2] - a[i-1] - a[i] } ;

54 54 Примеры решения некоторых типовых задач

55 55 Задача 1 Последовательность элементов задана формулой общего члена a i =sin(i+i/n), где i изменяется от 1 до n. Написать программу для нахождения первого элемента последовательности, большего заданного числа Z.

56 56 Задача 1: решение Исходными данными для решения задачи являются элементы последовательности: a 1 =sin(1+1/n), a 2 =sin(2+2/n),..., a n =sin(n+n/n). В результате получаем либо номер элемента, большего заданного Z, либо ответ: «Такого элемента нет». Решение этой задачи может закончиться по двум причинам: 1)перебрали все элементы последовательности и не нашли нужного элемента; 2)в процессе перебора обнаружился элемент, больший Z. В этом случае перебор прекращается и формируется ответ. Первую причину окончания можно определить, проверив условие: i > n, где i - текущий элемент последовательности, а n - количество элементов в ней.

57 57 Задача 1: решение Вторая причина имеет два значения: «найдено» или «не найдено». Поэтому ее можно изображать логическим значением, где true соответствует найдено, а false - не найдено. Таким образом, условие окончания поиска может быть записано в виде (i>n) or f, что соответствует фразе русского языка: «Просмотрены все элементы или найдено». Просмотр элементов последовательности в цикле будет выполняться в случае ложности приведенного условия.

58 © С.В.Кухта, Задача 1: программа program pr4; varn, i : integer; z: real; { заданное число } f: boolean; { true, если найден искомый элемент } Begin write('Введите n и z '); readln(n, z); i:=1; f:=false; while (iz then f:=true { искомый элемент найден } else i:=i+1; { переходим к след. элементу } if f then writeln('Номер 1-го элемента больше ', z, ' =', i) else writeln('Нет элементов больших ', z); end. program pr4; varn, i : integer; z: real; { заданное число } f: boolean; { true, если найден искомый элемент } Begin write('Введите n и z '); readln(n, z); i:=1; f:=false; while (iz then f:=true { искомый элемент найден } else i:=i+1; { переходим к след. элементу } if f then writeln('Номер 1-го элемента больше ', z, ' =', i) else writeln('Нет элементов больших ', z); end.

59 59 Задача 2 Вычислить значение выражения: y=cos(1+cos(2+cos(3+...+cos(n-1+cos(n)...)).

60 60 Задача 2: решение Для начала запишем заданную формулу при различных значениях n. Для n=3 получим y=cos(1+cos(2+cos(3))). Для n=5 получим y=cos(1+cos(2+cos(3+cos(4+cos(5))))). Чтобы вычислить это выражение без компьютера, «вручную», нужно начать вычисления с самых вложенных скобок: 1. y1=cos(5) 2. y2=cos(4+cos(5)) или с учетом первого шага y2=cos(4+y1) 3. y3=cos(3+y2) 4. y4=cos(2+y3) 5. y5=cos(1+y4) Таким образом, в теле цикла будет повторяться оператор y=cos(i+y), где i изменяется от n до 1.

61 61 Задача 2: программа y:=0; for i:=n downto 1 do y:=cos(i+y); y:=0; for i:=n downto 1 do y:=cos(i+y); Фрагмент программы решения задачи:

62 62 Задача 3 Вычислить для произвольного натурального n Решение. Этот пример очень похож на предыдущий, однако здесь вместо функции cos(x) используется квадратный корень и натуральные числа под корнями уменьшаются. Отсюда получаем фрагмент программы: y:=0; for i:=1 to n do y:= sqrt(i+y); y:=0; for i:=1 to n do y:= sqrt(i+y);

63 63 Задача 4 Вычислить для произвольного натурального n Решение. Этот пример также похож на предыдущие. В нем используются функция деления и натуральные числа от 1 до n. Аналогично предыдущим примерам, здесь повторяется следующий оператор: y=i+p/y, где р - степень х. Степень можно получить последовательными умножениями на х. y:=1; p:=1; { степени x } for i:=n downto 1 do begin p:=p*x; y:=i+p/y end; y:=1; p:=1; { степени x } for i:=n downto 1 do begin p:=p*x; y:=i+p/y end;

64 64 Задача 5 Дано натуральное число n. Поменять порядок цифр числа n на обратный. Решение. Например, для n=1829 должно получиться m=9281. Для определения последней цифры числа нужно найти остаток от деления этого числа на 10, а для отбрасывания этой цифры - найти частное от деления целых чисел. Но последовательно получаемые цифры числа не отбрасываются, а результат m домножается на 10 и цифра прибавляется к результату. Цикл выполняется до тех пор, пока есть цифры в исходном числе. s:=0; { сумма цифр числа n } while n>0 do begin { пока есть цифры в числе n } s:=s+n mod 10; { прибавить последнюю цифру к сумме } n:=n div 10 { отбросить последнюю цифру } end; s:=0; { сумма цифр числа n } while n>0 do begin { пока есть цифры в числе n } s:=s+n mod 10; { прибавить последнюю цифру к сумме } n:=n div 10 { отбросить последнюю цифру } end;

65 65 Задача 6 Решение. Первый элемент последовательности объявляем кандидатом на максимум. Последовательно сравниваем все остальные элементы последовательности с кандидатом на максимум: если очередной элемент меньше или равен кандидату, то переходим к следующему элементу; если очередной элемент больше кандидата, то заменяем им кандидата и продолжаем сравнения. Последовательность элементов задана формулой общего члена a i =sin(i+i/n), где i изменяется от 1 до n (n - натуральное). Найти максимальный элемент и его номер в последовательности.

66 © С.В.Кухта, Задача 6: программа program primer; varn, i : integer; a: real; { элемент последовательности } max: real; { максимальный элемент } mi: integer; { номер максимального элемента } begin write('введите число '); readln(n); max:=sin(1+n/1); mi:=1; i:=2; while i

67 67 Задача 7 Решение. Чтобы вычислить дневной путь баржи, начиная с шестого дня, необходимо знать расстояния, пройденные баржей за предыдущие пять дней. Введем обозначения: y i - a, y i-1 - b, y i-2 - c, y i-3 - d, y i-4 - e, y i-5 - f. Необходимо найти путь баржи за n дней (сумма расстояний) и сравнить его с z. Баржа, двигаясь по реке, ежедневно проходит расстояние, определяемое формулой Определить, сможет ли баржа за n дней пройти расстояние в z километров, если в каждый из первых пяти дней она проходила по одному километру.

68 © С.В.Кухта, Задача 7: программа Var a, b, c, d, e, f: real; i, n: integer; { i - счетчик, n - количество дней } s: real; { сумма расстояний, пройденных за n дней } z: real; { расстояние для сравнения } begin f:=1; e:=1; d:=1; c:=1; b:=1; s:=5; write('Введите количество дней '); readln(n); for i:=5 to n do begin if i mod 2=0 then a:=b+0.5*c else a:=0.7*f-0.2*e; f:=e;e:=d;d:=c;c:=b;b:=a; s:=s+a; end; writeln('Пройденное расстояние ', s) if s>z then write(' больше ', z) else if s=z then write(' равно ', z) else write(' меньше ', z) end. Var a, b, c, d, e, f: real; i, n: integer; { i - счетчик, n - количество дней } s: real; { сумма расстояний, пройденных за n дней } z: real; { расстояние для сравнения } begin f:=1; e:=1; d:=1; c:=1; b:=1; s:=5; write('Введите количество дней '); readln(n); for i:=5 to n do begin if i mod 2=0 then a:=b+0.5*c else a:=0.7*f-0.2*e; f:=e;e:=d;d:=c;c:=b;b:=a; s:=s+a; end; writeln('Пройденное расстояние ', s) if s>z then write(' больше ', z) else if s=z then write(' равно ', z) else write(' меньше ', z) end.

69 69 Задача 8 Решение. Для решения задачи нужно m раз выполнить вычисление очередного члена последовательности. Для его вычисления необходим еще один цикл, в котором цифры последовательно отделяются от очередного члена последовательности и находится сумма их квадратов. Последовательность (a n ) задается так: a 1 - некоторое натуральное число, a n+1 - сумма квадратов цифр числа a n, n>=1. Найти m-й член последовательности.

70 70 Задача 8: программа var a, { член последовательности } s: integer; { сумма квадратов цифр предыдущего члена посл-сти } i, m: integer; begin write('Введите 1-й член посл-сти и m'); readln(a, m); for i:=2 to m do begin s:=0; { находим сумму квадратов цифр } While a>0 do begin s:=s + sqr(a mod 10); a:=a div 10 end; a:=s { запоминаем новый член последовательности } end; end. var a, { член последовательности } s: integer; { сумма квадратов цифр предыдущего члена посл-сти } i, m: integer; begin write('Введите 1-й член посл-сти и m'); readln(a, m); for i:=2 to m do begin s:=0; { находим сумму квадратов цифр } While a>0 do begin s:=s + sqr(a mod 10); a:=a div 10 end; a:=s { запоминаем новый член последовательности } end; end.

71 71 Задача 9 Решение. Здесь признаком окончания ввода является число 0, заранее количество вводимых данных неизвестно, поэтому организуем итерационный цикл. Исходные данные для этой задачи могут быть такими: Нужно получить: 2! 4! 7! 9! 13!. Заметим, что для вычисления факториала следующего числа можно использовать факториал предыдущего числа (по условию числа возрастают!). Введем следующие обозначения: a - введенное число, b - число, с которого нужно продолжить вычисление факториала, i - счетчик выполненных умножений, p - факториал числа. Возрастающая последовательность натуральных чисел вводится с клавиатуры до ввода числа 0. Вычислить и напечатать факториал каждого введенного числа.

72 72 Задача 9: фрагмент программы p:=1; b:=1; read(a); while a0 do begin for i:=b to a do p:=p*i; write('факториал ', a, ' = ', p, ' '); b:=a+1; read(a) end; p:=1; b:=1; read(a); while a0 do begin for i:=b to a do p:=p*i; write('факториал ', a, ' = ', p, ' '); b:=a+1; read(a) end;

73 73 Задача 10 Решение. Для ввода данных нужно организовать арифметический цикл по счетчику до ввода n чисел. Для работы на каждом шаге цикла нужно хранить два соседних числа. Начальным значением для максимума и минимума может быть значение x 1. Последовательность из n положительных чисел вводится с клавиатуры. Найти сумму максимального и минимального элементов последовательности: x 1, x 2 +1/x 1, x 3 +1/x 2,..., x n+1 /x n-1, где x i - введенное число.

74 74 Задача 10: фрагмент программы read(a); { вводим первое число посл-сти } max:=a;min:=a; for i:=2 to n do begin read(b); c:=b+1/a; { вычисляем элемент заданной посл-сти } { находим max и min } if maxc then min:=c; a:=b { запоминаем предыдущий элемент } end; write(max + min); read(a); { вводим первое число посл-сти } max:=a;min:=a; for i:=2 to n do begin read(b); c:=b+1/a; { вычисляем элемент заданной посл-сти } { находим max и min } if maxc then min:=c; a:=b { запоминаем предыдущий элемент } end; write(max + min);

75 75 Задача 11 Решение. Например, числу 1234 соответствует дробь 0,0081, а числу ,003. Для перебора всех четырехзначных чисел организуем четыре вложенных цикла: в первом цикле будут перебираться цифры тысяч от 1 до 9 (ноль исключается, потому что число заведомо четырехзначное), во втором - сотни от 0 до 9, в третьем - десятки от 0 до 9, в четвертом цикле - единицы от 0 до 9. Исходным значением искомого отношения может быть ноль. Для каждого четырехзначного числа составляется дробь: отношение суммы цифр числа к самому числу. Найти четырехзначное число, для которого эта дробь наибольшая.

76 76 Задача 11: фрагмент программы y:=0; { начальное значение отношения } a:=0; { искомое число } for i:=1 to 9 do for j:=0 to 9 do for k:=0 to 9 do for m:=0 to 9 do begin s:=I + j + k + m; x:=((10 * I + j) * 10 + k) * 10 + m; if y

77 77 Задача 12 Решение. Простое решение можно получить по аналогии с предыдущим: Найти все натуральные трехзначные числа, каждое из которых обладает двумя следующими свойствами: - первая цифра в три раза меньше последней его цифры; - сумма самого числа с числом, получающимся из него перестановкой второй и третьей его цифр, делится на 8 без остатка. for i:=1 to 9 do { цифра сотен } for j:=0 to 9 do { цифра десятков } for k:=0 to 9 do begin { цифра единиц } c:=100*i+10*j+k; if (3*i=k) and ((c+100*i+10*k+j) mod 8=0) then write(c:4); for i:=1 to 9 do { цифра сотен } for j:=0 to 9 do { цифра десятков } for k:=0 to 9 do begin { цифра единиц } c:=100*i+10*j+k; if (3*i=k) and ((c+100*i+10*k+j) mod 8=0) then write(c:4);

78 78 Задача 13 Решение. Значение количества выданных троек не может превысить n div 3, а значение количества выданных пятерок не может превысить n div 5. Исходя из этого, организуем циклы перебора: Любую целочисленную сумму денег большую 7 рублей можно выплатить без сдачи трешками и пятерками. По заданному целому положительному n определить пару целых неотрицательных чисел a и b, таких, что n=3 a+5 b.

79 79 Задача 13: фрагмент программы repeat write('Введите значение n>7 '); readln(n); Until n>7; for a:=0 to n div 3 do for b:=0 to n div 5 do if n=3*a+5*b then writeln('3*', a, '+5*', b, '=', n); repeat write('Введите значение n>7 '); readln(n); Until n>7; for a:=0 to n div 3 do for b:=0 to n div 5 do if n=3*a+5*b then writeln('3*', a, '+5*', b, '=', n);