Программирование на языке Паскаль Часть II Тема 1. Массивы

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 1. Массивы
  

• 

  2 слайд

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

• 

  3 слайд

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

• 

  4 слайд

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

• 

  5 слайд

  Объявление массивов
  Массивы других типов:
  Другой диапазон индексов:
  Индексы других типов:
  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 A: array ['A'..'Z'] of real;
  B: array [False..True] of integer;
  ...
  A['C'] := 3.14259*A['B'];
  B[False] := B[False] + 1;
  

• 

  6 слайд

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

• 

  7 слайд

  Массивы
  Объявление:
  Ввод с клавиатуры:
  Поэлементные операции:
  Вывод на экран:
  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;
  a[1] =
  a[2] =
  a[3] =
  a[4] =
  a[5] =
  5
  12
  34
  56
  13
  Почему
  write?
  ?
  for i:=1 to N do a[i]:=a[i]*2;
  writeln('Массив A:');
  for i:=1 to N do
  write(a[i]:4);
  Массив A:
  10 24 68 112 26
  

• 

  8 слайд

  Задания
  "4": Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива.
  Пример:
  Введите пять чисел:
  4 15 3 10 14
  среднее арифметическое 9.200
  "5": Ввести c клавиатуры массив из 5 элементов, найти минимальный из них.
  Пример:
  Введите пять чисел:
  4 15 3 10 14
  минимальный элемент 3
  

• 

  9 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 2. Максимальный
  элемент массива
  

• 

  10 слайд

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

• 

  11 слайд

  Максимальный элемент
  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]
  

• 

  12 слайд

  Программа
  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;
  случайные числа в интервале [50,150)
  поиск максимального
  

• 

  13 слайд

  Задания
  "4": Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем максимальный и минимальный элементы и их номера.
  Пример:
  Исходный массив:
  4 -5 3 10 -4 -6 8 -10 1 0
  максимальный a[4]=10
  минимальный a[8]=-10
  "5": Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем два максимальных элемента и их номера.
  Пример:
  Исходный массив:
  4 -5 3 10 -4 -6 8 -10 1 0
  максимальные a[4]=10, a[7]=8
  

• 

  14 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 3. Обработка массивов
  

• 

  15 слайд

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

• 

  16 слайд

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

• 

  17 слайд

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

• 

  18 слайд

  Задания
  "4": Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить инверсию отдельно для 1-ой и 2-ой половин массива.
  Пример:
  Исходный массив:
  4 -5 3 10 -4 -6 8 -10 1 0
  Результат:
  -4 10 3 -5 4 0 1 -10 8 -6
  "5": Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить инверсию для каждой трети массива.
  Пример:
  Исходный массив:
  4 -5 3 10 -4 -6 8 -10 1 0 5 7
  Результат:
  10 3 -5 4 -10 8 -6 -4 7 5 0 1
  

• 

  19 слайд

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

• 

  20 слайд

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

• 

  21 слайд

  Задания
  "4": Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг ВПРАВО.
  Пример:
  Исходный массив:
  4 -5 3 10 -4 -6 8 -10 1 0
  Результат:
  0 4 -5 3 10 -4 -6 8 -10 1
  "5": Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить циклический сдвиг ВПРАВО на 4 элемента.
  Пример:
  Исходный массив:
  4 -5 3 10 -4 -6 8 -10 1 0 5 7
  Результат:
  -4 -6 8 -10 1 0 5 7 4 -5 3 10
  

• 

  22 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 4. Сортировка массивов
  

• 

  23 слайд

  Сортировка
  Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …).
  Задача: переставить элементы массива в порядке возрастания.
  Алгоритмы:
  простые и понятные, но неэффективные для больших массивов
  метод пузырька
  метод вставки
  сложные, но эффективные
  "быстрая сортировка" (Quick Sort)
  сортировка "кучей" (Heap Sort)
  сортировка слиянием
  пирамидальная сортировка
  сложность O(N2)
  сложность O(N·logN)
  время
  N
  O(N2)
  O(N·logN)
  

• 

  24 слайд

  Метод пузырька
  Идея – пузырек воздуха в стакане воды поднимается со дна вверх.
  Для массивов – самый маленький ("легкий") элемент перемещается вверх ("всплывает").
  начиная снизу, сравниваем два соседних элемента; если они стоят "неправильно", меняем их местами
  за 1 проход по массиву один элемент (самый маленький) становится на свое место
  1-ый проход
  2-ый проход
  3-ий проход
  Для сортировки массива из N элементов нужен
  N-1 проход (достаточно поставить на свои места N-1 элементов).
  

• 

  25 слайд

  Программа
  1-ый проход:
  сравниваются пары
  A[N-1] и A[N], A[N-2] и A[N-1]
  …
  A[1] и A[2]
  A[j] и A[j+1]
  2-ой проход
  A[1] уже на своем месте!
  !
  for j:=N-1 downto 2 do
  if A[j] > A[j+1] then begin
  c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
  end;
  2
  for j:=N-1 downto 1 do
  if A[j] > A[j+1] then begin
  c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
  end;
  1
  i-ый проход
  for j:=N-1 downto i do
  ...
  i
  

• 

  26 слайд

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

• 

  27 слайд

  Метод пузырька с флажком
  Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны.
  Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход.
  repeat
  flag := False; { сбросить флаг }
  for j:=N-1 downto 1 do
  if A[j] > A[j+1] then begin
  с := A[j];
  A[j] := A[j+1];
  A[j+1] := с;
  flag := True; { поднять флаг }
  end;
  until not flag; { выход при flag=True }
  flag := False;
  flag := True;
  not flag;
  var flag: boolean;
  Как улучшить?
  ?
  

• 

  28 слайд

  Метод пузырька с флажком
  i := 0;
  repeat
  i := i + 1;
  flag := False; { сбросить флаг }
  for j:=N-1 downto 1 do
  if A[j] > A[j+1] then begin
  с := A[j];
  A[j] := A[j+1];
  A[j+1] := с;
  flag := True; { поднять флаг }
  end;
  until not flag; { выход при flag=True }
  i := 0;
  i
  i := i + 1;
  

• 

  29 слайд

  Метод вставки
  Идея:
  найти минимальный элемент и поставить на первое место (поменять местами с A[1])
  из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2]), и т.д.
  

• 

  30 слайд

  Метод вставки
  for i := 1 to N-1 do begin
  nMin = i ;
  for j:= i+1 to N do
  if A[j] < A[nMin] then nMin:=j;
  if nMin <> i then begin
  c:=A[i];
  A[i]:=A[nMin];
  A[nMin]:=c;
  end;
  end;
  N-1
  N
  нужно N-1 проходов
  поиск минимального от A[i] до A[N]
  если нужно, переставляем
  Можно ли убрать if?
  ?
  i+1
  i
  

• 

  31 слайд

  Задания
  "4": Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре.
  Пример:
  Исходный массив:
  14 25 13 30 76 58 32 11 41 97
  Результат:
  30 11 41 32 13 14 25 76 97 58
  "5": Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию.
  Пример:
  Исходный массив:
  14 25 13 30 76 58 32 11 41 97
  Результат:
  13 14 25 30 76 97 58 41 32 11
  

• 

  32 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 5. Поиск в массиве
  

• 

  33 слайд

  Поиск в массиве
  Задача – найти в массиве элемент, равный X, или установить, что его нет.
  Решение: для произвольного массива: линейный поиск (перебор)
  недостаток: низкая скорость
  Как ускорить? – заранее подготовить массив для поиска
  как именно подготовить?
  как использовать "подготовленный массив"?
  

• 

  34 слайд

  Линейный поиск
  nX := 0;
  for i:=1 to N do
  if A[i] = X then begin
  nX := i;
  break; {выход из цикла}
  end;
  nX := 0; { пока не нашли ...}
  for i:=1 to N do { цикл по всем элементам }
  if A[i] = X then { если нашли, то ... }
  nX := i; { ... запомнили номер}
  if nX < 1 then writeln('Не нашли...')
  else writeln('A[', nX, ']=', X);
  nX – номер нужного
  элемента в массиве
  Что плохо?
  ?
  Улучшение: после того, как нашли X, выходим из цикла.
  nX := 0; i := 1;
  while i <= N do begin
  if A[i] = X then begin
  nX := i; i := N;
  end;
  i := i + 1;
  end;
  break;
  i := N;
  

• 

  35 слайд

  Двоичный поиск
  X = 7
  X < 8
  8
  4
  X > 4
  6
  X > 6
  Выбрать средний элемент A[c] и сравнить с X.
  Если X = A[c], нашли (выход).
  Если X < A[c], искать дальше в первой половине.
  Если X > A[c], искать дальше во второй половине.
  

• 

  36 слайд

  Двоичный поиск
  nX := 0;
  L := 1; R := N; {границы: ищем от A[1] до A[N] }
  while R >= L do begin
  c := (R + L) div 2;
  if X = A[c] then begin
  nX := c;
  R := L - 1; { break; }
  end;
  if x < A[c] then R := c - 1;
  if x > A[c] then L := c + 1;
  end;
  if nX < 1 then writeln('Не нашли...')
  else writeln('A[', nX, ']=', X);
  номер среднего элемента
  нашли
  Почему нельзя while R > L do begin … end; ?
  ?
  выйти из цикла
  сдвигаем границы
  

• 

  37 слайд

  Сравнение методов поиска
  

• 

  38 слайд

  Задания
  "4": Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск.
  
  "5": Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.
  

• 

  39 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 6. Символьные строки
  

• 

  40 слайд

  Чем плох массив символов?
  var B: array[1..N] of char;
  Это массив символов:
  каждый символ – отдельный объект;
  массив имеет длину N, которая задана при объявлении
  Что нужно:
  обрабатывать последовательность символов как единое целое
  строка должна иметь переменную длину
  

• 

  41 слайд

  Символьные строки
  длина строки
  рабочая часть
  s[1]
  s[2]
  s[3]
  s[4]
  var s: string;
  var s: string[20];
  Длина строки:
  n := length ( s );
  var i: integer;
  В Delphi это ограничение снято!
  !
  

• 

  42 слайд

  Символьные строки
  Задача: ввести строку с клавиатуры и заменить все буквы "а" на буквы "б".
  program qq;
  var s: string;
  i: integer;
  begin
  writeln('Введите строку');
  readln(s);
  for i:=1 to Length(s) do
  if s[i] = 'а' then s[i] := 'б';
  writeln(s);
  end.
  readln(s);
  writeln(s);
  Length(s)
  ввод строки
  длина строки
  вывод строки
  

• 

  43 слайд

  Задания
  "4": Ввести символьную строку и заменить все буквы "а" на буквы "б" и наоборот, как заглавные, так и строчные.
  Пример:
  Введите строку:
  ааббссААББСС
  Результат:
  ббаассББААСС
  "5": Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях).
  Пример: Пример:
  Введите строку: Введите строку:
  АБВГДЕ КАЗАК
  Результат: Результат:
  Не палиндром. Палиндром.
  

• 

  44 слайд

  Операции со строками
  Объединение: добавить одну строку в конец другой.
  Запись нового значения:
  var s, s1, s2: string;
  s := 'Вася';
  s1 := 'Привет';
  s2 := 'Вася';
  s := s1 + ', ' + s2 + '!';
  'Привет, Вася!'
  Подстрока: выделить часть строки в другую строку.
  s := '123456789';
  
  s1 := Copy ( s, 3, 6 );
  s2 := Copy ( s1, 2, 3 );
  '345678'
  '456'
  с 3-его символа
  6 штук
  

• 

  45 слайд

  Удаление и вставка
  Удаление части строки:
  Вставка в строку:
  s := '123456789';
  Delete ( s, 3, 6 );
  с 3-его символа
  6 штук
  строка
  меняется!
  '123456789'
  '129'
  s := '123456789';
  Insert ( 'ABC', s, 3 );
  Insert ( 'Q', s, 5 );
  куда вставляем
  что вставляем
  начиная с 3-его символа
  '12ABC3456789'
  '12ABQC3456789'
  

• 

  46 слайд

  Поиск в строке
  Поиск в строке:
  s := 'Здесь был Вася.';
  n := Pos ( 'е', s );
  if n > 0 then
  writeln('Буква е – это s[', n, ']')
  else writeln('Не нашли');
  n := Pos ( 'Вася', s );
  s1 := Copy ( s, n, 4 );
  var n: integer;
  s[3]
  3
  n = 11
  Особенности:
  функция возвращает номер символа, с которого начинается образец в строке
  если слова нет, возвращается 0
  поиск с начала (находится первое слово)
  

• 

  47 слайд

  Примеры
  s := 'Вася Петя Митя';
  n := Pos ( 'Петя', s );
  Delete ( s, n, 4 );
  Insert ( 'Лена', s, n );
  'Вася Лена Митя'
  s := 'Вася Петя Митя';
  n := length ( s );
  s1 := Copy ( s, 1, 4 );
  s2 := Copy ( s, 11, 4 );
  s3 := Copy ( s, 6, 4 );
  s := s3 + s1 + s2;
  n := length ( s );
  'Вася Митя'
  14
  'Вася'
  'Митя'
  'Петя'
  'ПетяВасяМитя'
  12
  6
  

• 

  48 слайд

  Пример решения задачи
  Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату "фамилия-инициалы".
  Пример:
  Введите имя, фамилию и отчество:
  Василий Алибабаевич Хрюндиков
  Результат:
  Хрюндиков В.А.
  Алгоритм:
  найти первый пробел и выделить имя
  удалить имя с пробелом из основной строки
  найти первый пробел и выделить отчество
  удалить отчество с пробелом из основной строки
  "сцепить" фамилию, первые буквы имени и фамилии, точки, пробелы…
  

• 

  49 слайд

  Программа
  program qq;
  var s, name, otch: string;
  n: integer;
  begin
  writeln('Введите имя, отчество и фамилию');
  readln(s);
  n := Pos(' ', s);
  name := Copy(s, 1, n-1); { вырезать имя }
  Delete(s, 1, n);
  n := Pos(' ', s);
  otch := Copy(s, 1, n-1); { вырезать отчество }
  Delete(s, 1, n); { осталась фамилия }
  s := s + ' ' + name[1] + '.' + otch[1] + '.';
  writeln(s);
  end.
  

• 

  50 слайд

  Задания
  "4": Ввести имя файла (возможно, без расширения) и изменить его расширение на ".exe".
  Пример:
  Введите имя файла: Введите имя файла:
  qqq qqq.com
  Результат: Результат:
  qqq.exe qqq.exe
  "5": Ввести путь к файлу и "разобрать" его, выводя каждую вложенную папку с новой строки
  Пример:
  Введите путь к файлу:
  C:\Мои документы\10-Б\Вася\qq.exe
  Результат:
  C:
  Мои документы
  10-Б
  Вася
  qq.exe
  

• 

  51 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 7. Рекурсивный перебор
  

• 

  52 слайд

  Рекурсивный перебор
  Задача: Алфавит языка племени "тумба-юмба" состоит из букв Ы, Ц, Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры.
  1
  K
  в каждой ячейке может быть любая из 4-х букв
  4 варианта
  4 варианта
  4 варианта
  4 варианта
  Количество вариантов:
  

• 

  53 слайд

  Рекурсивный перебор
  1
  K
  Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K-1 букв.
  1
  K
  1
  K
  1
  K
  перебрать все варианты
  перебрать все варианты
  перебрать все варианты
  перебрать все варианты
  

• 

  54 слайд

  Процедура
  procedure Rec(p: integer);
  begin
  if p > K then begin
  writeln(s);
  count := count+1;
  end
  else begin
  s[p]:='Ы'; Rec ( p+1 );
  s[p]:='Ц'; Rec ( p+1 );
  s[p]:='Щ'; Rec ( p+1 );
  s[p]:='О'; Rec ( p+1 );
  end;
  end;
  1
  K
  p
  Глобальные переменные:
  var s: string;
  count, K: integer;
  s
  p+1
  рекурсивные вызовы
  А если букв много?
  ?
  окончание рекурсии
  

• 

  55 слайд

  Процедура
  procedure Rec(p: integer);
  const letters = 'ЫЦЩО';
  var i: integer;
  begin
  if p > k then begin
  writeln(s);
  count := count+1;
  end
  else begin
  for i:=1 to length(letters) do begin
  s[p] := letters[i];
  Rec(p+1);
  end;
  end;
  end;
  const letters = 'ЫЦЩО';
  for i:=1 to length(letters) do begin
  s[p] := letters[i];
  Rec(p+1);
  end;
  все буквы
  цикл по всем буквам
  локальная переменная
  

• 

  56 слайд

  Программа
  program qq;
  var s: string;
  K, i, count: integer;
  begin
  writeln('Введите длину слов:');
  read ( K );
  s := '';
  for i:=1 to K do s := s + ' ';
  count := 0;
  Rec ( 1 );
  writeln('Всего ', count, ' слов');
  end.
  procedure Rec(p: integer);
  ...
  end;
  процедура
  s := '';
  for i:=1 to K do s := s + ' ';
  строка из K пробелов
  глобальные переменные
  

• 

  57 слайд

  Задания
  Алфавит языка племени "тумба-юмба" состоит из букв Ы, Ц, Щ и О. Число K вводится с клавиатуры.
  "4": Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество.
  "5": Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество.
  

• 

  58 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 8. Матрицы
  

• 

  59 слайд

  Матрицы
  Задача: запомнить положение фигур на шахматной доске.
  1
  2
  3
  4
  5
  6
  c6
  A[6,3]
  

• 

  60 слайд

  Матрицы
  Матрица – это прямоугольная таблица чисел.
  Матрица – это массив, в котором каждый элемент имеет два индекса (номер строки и номер столбца).
  A
  строка 2
  столбец 3
  ячейка A[3,4]
  

• 

  61 слайд

  Матрицы
  Объявление:
  const N = 3;
  M = 4;
  var A: array[1..N,1..M] of integer;
  B: array[-3..0,-8..M] of integer;
  Q: array['a'..'d',False..True] of real;
  Ввод с клавиатуры:
  for i:=1 to N do
  for j:=1 to M do begin
  write('A[',i,',',j,']=');
  read ( A[i,j] );
  end;
  Если переставить циклы?
  ?
  A[1,1]=
  25
  A[1,2]=
  14
  A[1,3]=
  14
  ...
  A[3,4]=
  54
  i
  j
  for j:=1 to M do
  for i:=1 to N do begin
  

• 

  62 слайд

  Матрицы
  Заполнение случайными числами
  for i:=1 to N do
  for j:=1 to M do
  A[i,j] := random(25) - 10;
  Какой интервал?
  ?
  цикл по строкам
  цикл по столбцам
  Вывод на экран
  for i:=1 to N do begin
  for j:=1 to M do
  write ( A[i,j]:5 );
  writeln;
  end;
  в той же строке
  перейти на новую строку
  вывод строки
  Если переставить циклы?
  ?
  

• 

  63 слайд

  Обработка всех элементов матрицы
  Задача: заполнить матрицу из 3 строк и 4 столбцов случайными числами и вывести ее на экран. Найти сумму элементов матрицы.
  program qq;
  const N = 3; M = 4;
  var A: array[1..N,1..M] of integer;
  i, j, S: integer;
  begin
  ... { заполнение матрицы и вывод на экран}
  S := 0;
  for i:=1 to N do
  for j:=1 to M do
  S := S + A[i,j];
  writeln('Сумма элементов матрицы ', S);
  end;
  

• 

  64 слайд

  Задания
  Заполнить матрицу из 8 строк и 5 столбцов случайными числами в интервале [-10,10] и вывести ее на экран.
  "4": Найти минимальный и максимальный элементы в матрице их номера. Формат вывода:
  Минимальный элемент A[3,4]=-6
  Максимальный элемент A[2,2]=10
  "5": Вывести на экран строку, сумма элементов которой максимальна. Формат вывода:
  Строка 2: 3 5 8 9 8
  

• 

  65 слайд

  Операции с матрицами
  Задача 1. Вывести на экран главную диагональ квадратной матрицы из N строк и N столбцов.
  A[1,N]
  A[2,2]
  A[3,3]
  A[N,N]
  for i:=1 to N do
  write ( A[i,i]:5 );
  Задача 2. Вывести на экран вторую диагональ.
  A[N,1]
  A[N-1,2]
  A[2,N-1]
  for i:=1 to N do
  write ( A[i, ]:5 );
  N+1-i
  сумма номеров строки и столбца N+1
  A[1,1]
  

• 

  66 слайд

  Операции с матрицами
  Задача 3. Найти сумму элементов, стоящих на главной диагонали и ниже ее.
  Одиночный цикл или вложенный?
  ?
  строка 1: A[1,1]
  строка 2: A[2,1]+A[2,2]
  ...
  строка N: A[N,1]+A[N,2]+...+A[N,N]
  S := 0;
  for i:= 1 to N do
  for j:= 1 to i do
  S := S + A[i,j];
  цикл по всем строкам
  складываем нужные элементы строки i
  

• 

  67 слайд

  Операции с матрицами
  Задача 4. Перестановка строк или столбцов. В матрице из N строк и M столбцов переставить 2-ую и 4-ую строки.
  2
  4
  j
  A[2,j]
  A[4,j]
  for j:=1 to M do begin
  c := A[2,j];
  A[2,j] := A[4,j];
  A[4,j] := c;
  end;
  Задача 5. К третьему столбцу добавить шестой.
  for i:=1 to N do
  A[i,3] := A[i,3] + A[i,6];
  

• 

  68 слайд

  Задания
  Заполнить матрицу из 7 строк и 7 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. Обнулить элементы, отмеченные зеленым фоном, и вывести полученную матрицу на экран.
  "4": "5":
  

• 

  69 слайд

  Программирование
  на языке Паскаль
  Часть II
  Тема 9. Файлы
  

• 

  70 слайд

  Файлы
  Файл – это область на диске, имеющая имя.
  Файлы
  только текст без оформления,
  не содержат управляющих символов (с кодами < 32)
  ACSII (1 байт на символ)
  UNICODE (2 байта на символ)
  *.txt, *.log,
  *.htm, *.html
  могут содержать любые символы кодовой таблицы
  *.doc, *.exe,
  *.bmp, *.jpg,
  *.wav, *.mp3,
  *.avi, *.mpg
  Текстовые
  Двоичные
  Папки
  (каталоги)
  

• 

  71 слайд

  Принцип сэндвича
  I этап. открыть файл :
  связать переменную f с файлом
  открыть файл (сделать его
  активным, приготовить к работе)
  assign(f, 'qq.dat');
  reset(f); {для чтения}
  rewrite(f); {для записи}
  II этап: работа с файлом
  Переменная типа "текстовый файл":
  var f: text;
  III этап: закрыть файл
  close(f);
  read ( f, n ); { ввести значение n }
  write ( f, n ); { записать значение n }
  writeln ( f, n );{c переходом на нов.строку }
  

• 

  72 слайд

  Работа с файлами
  Особенности:
  имя файла упоминается только в команде assign, обращение к файлу идет через файловую переменную
  файл, который открывается на чтение, должен существовать
  если файл, который открывается на запись, существует, старое содержимое уничтожается
  данные записываются в файл в текстовом виде
  при завершении программы все файлы закрываются автоматически
  после закрытия файла переменную f можно использовать еще раз для работы с другим файлом
  

• 

  73 слайд

  Последовательный доступ
  при открытии файла курсор устанавливается в начало
  чтение выполняется с той позиции, где стоит курсор
  после чтения курсор сдвигается на первый непрочитанный символ
  12 5 45 67 56●
  конец файла
  (end of file, EOF)
  12 5 45 67 56●
  assign ( f, 'qq.dat' );
  reset ( f );
  read ( f, x );
  

• 

  74 слайд

  чтение до конца строки
  как вернуться назад?
  Последовательный доступ
  close ( f );
  reset ( f ); { начать с начала }
  readln ( f, x );
  12 5 45¤ 36 67¤ 56●
  конец строки
  (end of line, EOL)
  

• 

  75 слайд

  Пример
  Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно. Записать в файл output.txt их сумму.
  Алгоритм:
  Открыть файл input.txt для чтения.
  S := 0;
  Если чисел не осталось, перейти к шагу 7.
  Прочитать очередное число в переменную x.
  S := S + x;
  Перейти к шагу 3.
  Закрыть файл input.txt.
  Открыть файл output.txt для записи.
  Записать в файл значение S.
  Закрыть файл output.txt.
  Можно ли обойтись без массива?
  ?
  цикл с условием
  "пока есть данные"
  

• 

  76 слайд

  Программа
  program qq;
  var s, x: integer;
  f: text;
  begin
  assign(f, 'input.txt');
  reset(f);
  s := 0;
  while not eof(f) do begin
  readln(f, x);
  s := s + x;
  end;
  close(f);
  assign(f, 'output.txt');
  rewrite(f);
  writeln(f, 'Сумма чисел ', s);
  close(f);
  end.
  f: text;
  eof(f)
  логическая функция, возвращает True, если достигнут конец файла
  запись результата в файл output.txt
  

• 

  77 слайд

  Задания
  В файле input.txt записаны числа, сколько их – неизвестно.
  "4": Найти среднее арифметическое всех чисел и записать его в файл output.txt.
  "5": Найти минимальное и максимальное числа и записать их в файл output.txt.
  

• 

  78 слайд

  Обработка массивов
  Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt.
  Проблемы:
  для сортировки надо удерживать в памяти все числа сразу (массив);
  сколько чисел – неизвестно.
  Решение:
  выделяем в памяти массив из 100 элементов;
  записываем прочитанные числа в массив и считаем их в переменной N;
  сортируем первые N элементов массива;
  записываем их в файл.
  Можно ли обойтись без массива?
  ?
  

• 

  79 слайд

  Чтение данных в массив
  var A: array[1..100] of integer;
  f: text;
  function ReadArray: integer;
  var i: integer;
  begin
  assign(f, 'input.txt');
  reset(f);
  i := 0;
  while (not eof(f)) and (i < 100) do begin
  i := i + 1;
  readln(f, A[i]);
  end;
  close(f);
  ReadArray := i;
  end;
  Глобальные переменные:
  Функция: ввод массива, возвращает число элементов
  ReadArray := i;
  цикл заканчивается, если достигнут конец файла или прочитали 100 чисел
  

• 

  80 слайд

  Программа
  program qq;
  var A: array[1..100] of integer;
  f: text;
  N: integer;
  Begin
  N := ReadArray;
  ... { сортировка первых N элементов }
  assign(f, 'output.dat');
  rewrite(f);
  for i:=1 to N do
  writeln(f, A[i]);
  close(f);
  end.
  function ReadArray: integer;
  ...
  end;
  вывод отсортированного массива в файл
  

• 

  81 слайд

  Задания
  В файле input.txt записаны числа (в столбик), известно, что их не более 100.
  "4": Отсортировать массив по убыванию последней цифры и записать его в файл output.txt.
  "5": Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.
  

• 

  82 слайд

  Обработка текстовых данных
  Задача: в файле input.txt записаны строки, в которых есть слово-паразит "короче". Очистить текст от мусора и записать в файл output.txt.
  Файл input.txt :
  Мама, короче, мыла, короче, раму.
  Декан, короче, пропил, короче, бутан.
  А роза, короче, упала на лапу, короче, Азора.
  Каждый, короче, охотник желает, короче, знать, где ...
  Результат - файл output.txt :
  Мама мыла раму.
  Декан пропил бутан.
  А роза упала на лапу Азора.
  Каждый охотник желает знать, где сидит фазан.
  

• 

  83 слайд

  Обработка текстовых данных
  Алгоритм:
  Прочитать строку из файла (readln).
  Удалить все сочетания ", короче," (Pos, Delete).
  Перейти к шагу 1.
  Обработка строки s:
  Особенность:
  надо одновременно держать открытыми два файла (один в режиме чтения, второй – в режиме записи).
  
  пока не кончились данные
  repeat
  i := Pos(', короче,', s);
  if i <> 0 then Delete(s, i, 9);
  until i = 0;
  искать ", короче,"
  удалить 9 символов
  

• 

  84 слайд

  Работа с файлами
  program qq;
  var s: string;
  i: integer;
  fIn, fOut: text;
  begin
  assign(fIn, 'instr.txt');
  reset(fIn);
  assign(fOut, 'outstr.txt');
  rewrite(fOut);
  ... { обработать файл }
  close(fIn);
  close(fOut);
  end.
  fIn, fOut: text;
  файловые переменные
  открыть файл для чтения
  открыть файл
  для записи
  

• 

  85 слайд

  Полный цикл обработки файла
  while not eof(fIn) do begin
  readln(fIn, s);
  writeln(fOut, s);
  end;
  repeat
  i := Pos(', короче,', s);
  if i <> 0 then
  Delete(s, i, 9);
  until i = 0;
  пока не достигнут конец файла
  обработка строки
  запись "очищенной" строки
  

• 

  86 слайд

  Задания
  В файле input.txt записаны строки, сколько их – неизвестно.
  "4": Заменить все слова "короче" на "в общем" и записать результат в файл output.txt.
  "5": Вывести в файл output.txt только те строки, в которых больше 5 слов (слова разделены одним пробелом).