Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Усовершенствованные сортировки

1) Дан текстовый файл, каждая строка которого состоит из множества слов. Необходимо сформировать другой файл, содержащий строки исходного в порядке соответствующем количеству слов в строках. В качестве упрощения задачи предположим, что количество строк в файле не превышает максимальный возможный размер массива в памяти (внимание, сам файл целиком в памяти не умещается). В качестве алгоритма для сортировки следует применять метод сортировки Шелла.

2) На лекции я упоминал, что во всех изданиях настоятельно не рекомендуется выполнять сортировку Шелла использую числа, которые являются множителями друг друга или кратны двум. Мы попытаемся опровергнуть или доказать данное утверждение (ну тут как получится). Необходимо будет взять фунцию сортировки Шелла, добавить в качестве входного параметра к этой функции возможность передать массив шагов расстояний на которые будет выполняться перестановка элементов. И сравнить скорости сортировки для массива из 10^6 элементов случайных чисел с разными шагами:

 • 1, 2, 4, 8 , …
 • 1, 4, 13, …
 • формула Седжвика.

 Для алгоритма Шелла наиболее эффективно использовать следующий набор шагов приращений. (формула Седжвика)

 По этой формуле следует провести предварительное вычисление шагов в зависимости от того 
 каков размер массива, 
 обратите внимание, на то, что последовательность вычисляется в порядке, противоположном используемому: 
 inc[0] < inc[1] < inc[2] ... 
 Формула дает сначала меньшие числа, затем все большие и большие, 
 в то время как расстояние между сортируемыми элементами, наоборот, должно уменьшаться. 
 Поэтому массив приращений inc вычисляется перед запуском собственно сортировки 
 до максимального расстояния между элементами, 
 которое будет первым шагом в сортировке Шелла. Потом его значения используются в обратном порядке. 
 При использовании формулы Седжвика следует остановиться на значении 
 <em>inc[s-1]</em>, если <em>3*inc[s] > size</em>.

3) В предыдущем задании мы уже пробовали решать задачу поиска подстроки внутри другой строки. Сейчас мы попробуем решить задачу нечеткого поиска. В практике это можно свести к помощи, например, наборщику в типографии в поиске ошибок. Представьте себе, что у нас заданы две строки S = S1…SN, и S1=S1..SM, разумеется, что N >= M. Введем понятие близости двух строк: две строки SA и SB имеют близость измеряемую целым числом и являющуюся количеством несовпадающих символов в соответствующих позициях. Представьте себе, что наш наборщик только ошибался при написании букв, заменял одну другой, но не пропускал буквы и не вставлял лишние. Вам необходимо написать программу, которая получает на вход две строки и возвращает позиции, с которых в строке S начинаются подстроки S1, близость между которыми не превышает заданного значения X, указываемого при запуске программы вместе с исходными строками.

4) Данное задание посвящено сортировкам с использованием “слияния” (мы уже сортировали массивы с помощью подобного приема в предыдущей лабораторной работе). Алгоритм слияния не слишком хорош для сортировки массивов, но принципы, заложенные в нем отлично проявляются при сортировке файлов (так называемая внешняя сортировка). Задан текстовой файл содержащий целые числа (количество порядка 10^5, сами числа сгенерируйте случайным образом в диапазоне от –10000 до +10000). Необходимо выполнить сортировку данного файла. Подсказка: для решения данной задачи вам будет необходимо использовать вспомогательные файлы. Один файл – источник данных. Также потребуется сформировать два файла в каждом из которых будет храниться подчасти файла подлежащие слиянию. И четвертый файл, куда будет помещаться результат.

5) Данная задача будет очень проста и более будет служить для демонстрации того, насколько усовершенствованные алгоритмы сортировок превосходят простейшие. Вам необходимо будет создать шаблонную версию функции сортировки некоторого типа данных с помощью метода пирамиды. Из первой лабораторной работы вы возьмете созданную там версию функции шаблонной сортировки методом прямого выбора (наилучшую в среднем среди остальных) и сравните скорость работы этих двух алгоритмов для массива целых чисел размером 10^5, диапазон случайных чисел любой. На экран выводятся два значения – результаты скорости работы.

6) В файле содержатся итоги соревнований по прыжкам с трамплина. Правила: каждому участнику дается три попытки. Результат каждой попытки измеряется в метрах и сантиметрах. Необходимо определить тех, кто займет первое, второе и третье место по следующим правилам. Участник, который получил травму или отказался от прыжка не может занять никакого места (т.к. он снимается с соревнований). Место распределяется по лучшим результатам длины прыжка, но в случае, когда у нас два спортсмена показали одинаковый результат, то победителем будет считаться тот, кто достиг этого результата с более ранней попытки.

Исходные данные рекомендуются не вводить с клавиатуры а хранить в текстовом файле, в следующем формате:

 N – количество участников соревнований
 ФИО – фио первого участника
 K1 – количество попыток которые сделал 1-ый спортсмен.
 R1 -  результат третей попытки для первого спортсмена.
 R2 -  результат третей попытки для первого спортсмена.
 R3 -  результат третей попытки для первого спортсмена.
 ФИО – фио второго участника
 …….

На выходе работы программы должны три ФИО тех спортсменов, которые и заняли первые три места. Было бы неплохо если бы вы использовали для чтения данных не функции стандартного С (fopen, fscanf, fprintf) а классы потоков из stl – ifstream, ofstream. При чтении данных сложной структуры из файла или из базы данных всегда принято переносить их в форму классов C++, так здесь можно было бы создать класс
и затем применить для сортировки данного массива спортсменов метод Пирамиды, который вы согласно моей рекомендации сделали в виде шаблона в предыдущем задании.

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

7) Задача “Столица” (Всероссийская командная олимпиада среди школьников 2002)

В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.

Император решил построить n+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

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

Формат входных данных:

Первая строка входного файла содержит число N - количество городов (1 <= N <= 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.

Формат выходных данных: Выведите на экран два целых числа: координаты по оси X и оси Y для столицы.

« Структуры данных и алгоритмы. Практика. Простейшие алгоритмы сортировок (сортировка методом пузырька, вставки, выборки). Часть 2

Структуры данных и алгоритмы. Практика. Основы рекурсии »