Методы программирования: Методическое пособие для выполнения лабораторных работ, страница 4

  A[k] := i;                

   конец цикла                              

Выдать полученную перестановку на экран или в файл.

Требования к реализации

Язык программирования, на котором следует выполнять работу – С.

Лабораторная работа № 6.  Поиск подстроки в строке

Задание

Написать программу, которая находит первое вхождение подстроки в за­дан­ную строку. Использовать алгоритм Бойера-Мура поиска подстроки в стро­ке, описанный в [1, 2].

Входные данные

На вход программе подаются две строки s и q. Длина s больше либо равна длине q.

Выходные данные

Нужно выдать на экран номер позиции элемента в строке s, с которого начи­нается первое вхождение строки q в строку s. Если q не является подстрокой s, то вывести 0.

Метод.Алгоритм Бойера-Мура

Пусть L — длина строки s, а M — длина строки q.

Шаг 1. Построить по q таблицу сдвигов D[0..255]такую, что:

   если литера, имеющая код i, не входит в q,

   то  D[i]:= М

   иначе D[i]:= М – j,

   где код q[j] равен i, 0<j<M, и нет такого k (j<k<M), что

 q[k] = q[j]

Шаг 2. Совместить начало строки q c началом строки s.

Пусть i — текущее положение первого элемента строки q

относительно строки s.

i := 1;

Шаг 3. Пусть j – счетчик элементов строки q, а k – счетчик элементов строки s.

j := M;        

 k := i + M – 1;  

Шаг 4. Сравнить поэлементно q и s:

пока (q[j] = s[k]) и ( j > 0) выполнять 

    //сдвинуться на одну позицию влево:

  j := j – 1;

  k := k – 1;

конец пока

если j = 0

     // первое вхождение строки q в строку s найдено

то 

   начало

     выдать i;

     перейти на Шаг 6;

   конец

иначе перейти на Шаг 5.

Шаг 5. Вычислить новый сдвиг начала образца q относительно оcновной строки s:

    i := i + D[ код(s[i + M – 1])]; 

 если i + M –1 £ L  //не вышли за границу строки s

 то переход на Шаг 3

 иначе выдать 0;   

       // – вхождение строки q в строкуsне найдено

Шаг 6. Конец работы алгоритма

Требования к реализации

Язык программирования, на котором следует выполнять работу – С.

Лабораторная работа № 7. Простые сортировки

Задание

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

Использовать два из следующих алгоритмов, описанных в [1, 2]:

-  сортировка выбором,

-  сортировка вставками,

-  сортировка обменом (шейкер-сортировка),

-  сортировка подсчетом.

Входные данные

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

Выходные данные

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

Методы

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

Пусть А – массив длины N, содержащий целые числа, который нужно отсортировать. Описанная ниже процедура Обмен(i, j) меняет местами элементы массива c номерами i и j.

процедура Обмен (i, j)

// i и j – номера элементов массива A  

начало процедуры

    // Пусть x — вспомогательная переменная, посредством

    // которой данные элементы меняются местами

   x := A[i];  

   A[i]:= A[j];

   A[j]:= x;          

конец процедуры

Метод 1. Сортировка выбором

Условно разделить массив А на отсортированную и несор­ти­ро­ванную части. Сначала весь массив — это несортированная часть.

цикл по i от 1 до N–1 с шагом 1 выполнять

   // i – номер первого элемента в несортированной

 // части массива

 r:= i;                                

// Найти минимальный элемент в несортированной

     // части массива:

    цикл по j от i+1 до N с шагом 1 выполнять

    если А[j] < A[r] то r:= j;           

 конец цикла

// Найденный минимальный элемент поменять местами с

// первым элементом несортированной части:

   если i ¹ r

   то Обмен (i, r);                

// Он будет последним элементом новой сортированной

// части массива A.

конец цикла