Методические указания к лабораторным работам по дисциплине «Программирование на языке высокого уровня» (стр. 3 из 10)
Пример 1.7
| /*РАЗЛОЖИТЬ ЧИСЛО НА МНОЖИТЕЛИ */ #include <stdio.h> main() { int M,i=3; printf("ВВЕДИ M\n"); scanf("%d",&M); printf("%d=1",M); while(M%2==0) { printf("*%d",2); M=M/2; } while(i <=M) { if(M%i==0) { printf("*%d",i); M=M/i; } else i=i+2 } } |
Иногда структуры со вложенными друг в друга операторами повторения называются циклами. Следующая программа простая, хотя и содержит вложенные циклы. Она выводит на экран заполненный символом * треугольник, высота которого равна N.
Во внешнем цикле устанавливается очередная строка вывода (параметр i ), а во внутреннем (параметр j ) в очередную строку вводится ровно i символов " * " Вызов функции printf("\n") обеспечивает в нужный момент переход на новую строку. Обратите внимание, что для вывода одного символа в форматной строке функции printf используется спецификация %c.
Пример 1.8
| #include <stdio.h> main() { int i,j,N; printf("ВВЕДИ N \n"); scanf("%d",&N); i=1; while(i <=N) { j=1; while(j <=i) { printf("%c",'*'); j=j+1; } i=i+1; printf("\n"); } } |
Рассмотрим еще один пример, в котором используется сложный цикл. Программа позволяет найти в заданном интервале все совершенные числа. Напомним, что натуральное число называется совершенным, если оно равно сумме всех своих делителей, считая его самого. Известно, что все совершенные числа - четные и что первое совершенное число из натурального ряда чисел равно 6. Этим объясняется начальное значение параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S=1. Во внутреннем цикле организуется перебор всех множителей текущего значения N. Из теории чисел известно, что такому испытанию имеет подвергать числа от 2 до N/2, либо даже до корень из N. Это очень несовершенный алгоритм и если вы захотите его выполнить на ЭВМ, имейте ввиду, что программа работает слишком долго. Более эффективно алгоритм будет реализован попозже.
Пример 1.9
| #include <stdio.h> main() { int j,N,M,S; printf("ВВЕДИ M\n"); scanf("%d",&M); N=4; while(N<=M) { S=1;j=2; while(j<=N/2) { if(N%j==0) S=S+j; j=j+1; } if(N==S) printf("%d- СОВЕРШЕННОЕ ЧИСЛО\n",N); N=N+2; } } |
Варианты задач
Вычислить значение функции при заданных значениях параметров. Значения параметров задаются пользователем с клавиатуры.
1. z=2n, n
2. p= n!; n
3.
4.
5. M=a(a+1)…(a+n-1);
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17. 
18. 
19. 
20. 
Лабораторная работа №4
Тема: Алгоритмы сортировки и поиска
Постановка задачи.
Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Варианты заданий приведены в табл. 3.
Таблица 3
Варианты заданий
| №. | Метод сортировки (поиска) |
| 1 | Сортировка простой (линейной) вставкой |
| 2 | Бинарный поиск |
| 3 | Сортировка слиянием (метод фон Неймана) |
| 4 | Сортировка методом бинарной вставки без использования рабочего массива |
| 5 | Сортировка Шелла (слияние с обменом) |
| 6 | Быстрая сортировка (метод Хоара) |
| 7 | Комбинированный метод быстрой сортировки с методом «пузырька» |
| 8 | Внешняя двухфазная сортировка прямым слиянием |
| 9 | Челночная сортировка (сортировка с просеиванием) |
| 10 | Интерполяционный поиск |
| 11 | Сортировка методом центрированной вставки (нахождение медианы) |
| 12 | Шейкер – сортировка |
| 13 | Сортировка методом бинарной вставки с использованием рабочего массива |
| 14 | Обменная сортировка |
| 15 | Внешняя однофазная сортировка прямым слиянием |
| 16 | Внешняя сортировка естественным слиянием |
| 17 | Сортировка Шелла (слияние с обменом) |
| 18 | Внешняя сортировка сбалансированным слиянием |
| 19 | Сортировка простой (линейной) вставкой |
| 20 | Бинарный поиск |
Методические указания
Алгоритмы сортировки и поиска приведены ниже. В приведенных алгоритмах массивы упорядочиваются по возрастанию. Пример программы, выполняющей сортировку массива методом «пузырька», приведен на рис.2.
Обменная сортировка.
Последовательно сравнивается элемент а0 с каждым последующим ai и, если ai< а0, то эти два элемента меняются местами; таким образом наименьший элемент оказывается на своем месте в начале массива. Затем этот метод применяется к элементу а1 и т. д.
Шейкер – сортировка.
В этом методе проходы массива выполняются поочередно: слева направо, а потом справа налево. Последовательно сравниваются пары соседних элементов (а0 и а1, а1 и а2, и т.д.) и, если надо, переставляются. Запоминается индекс последнего переставляемого элемента (right). Далее массив просматривается справа налево, начиная с индекса right. В этом проходе массива также выполняются сравнения соседних элементов и их перестановка. Запоминается индекс последнего переставляемого элемента (left). Далее опять выполняется проход слева направо от индекса left до индекса right и т.д.
Сортировка Шелла.
Выбирается интервал d между сравниваемыми элементами, и выполняется сортировка массива методом «пузырька», но с шагом d. После этапа сортировки массива с выбранным интервалом, этот интервал уменьшается и опять выполняется сортировка массива методом «пузырька». Рекомендуется следующая последовательность значений d: 1, 3, 7, 15, 31, … ,т.е.
dk=(dk-1-1)/2
Максимальное значение d не должно превышать длину массива. Таким образом, в этом алгоритме вначале сравниваются и, если надо переставляются далеко стоящие элементы, а на последнем проходе – соседние.
Челночная сортировка.
Последовательно сравниваются пары соседних элементов а0 и а1, а1 и а2, и т.д. и если аi>ai+1, то элемент ai+1 продвигается влево насколько это возможно: он сравнивается со своим предшественником и, если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда передвигаемый влево элемент встречает меньшего предшественника, то процесс передвижения влево прекращается и возобновляется просмотр массива слева направо с той позиции, с которой выполнялся обмен при продвижении слева направо.
Быстрая сортировка (метод Хоара).
Идея метода заключается в том, что вначале переставляются элементы, которые находятся друг от друга на больших расстояниях. Выбирается элемент массива (например, центральный), который разбивает массив на два подмножества. Пусть значение этого элемента х. Элементы массива переставляются таким образом, чтобы слева от x находились элементы аi<=x, а справа aj>=x. После перестановок элемент x будет находиться на своем месте. Далее этот алгоритм разделения массива на левую и правую части применяется к левой, а затем к правой частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из единственного элемента. Таким образом, в этой сортировке используется рекурсия. Алгоритм разделения элементов массива начиная с элемента с индексом left до элемента с индексом right относительно «центрального» элемента x: вводятся два индекса i и j, i=left; j=right. Элементы просматриваются слева направо до тех пор, пока не обнаружится элемент ai>=x, затем массив просматривается справа налево, пока не обнаружится элемент aj<=x. После этого элементы меняются местами. Далее процесс просмотра и перестановки повторяется до тех пор, пока не станет i>j.