Некоммерческое акционерное общество

Некоммерческое акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра «Информационные системы»

АЛГОРИТМЫ, СТРУКТУРЫ ДАННЫХ И ПРОГРАММИРОВАНИЕ

Методические указания к выполнению расчетно-графических работ

(для студентов специальности 5В070300 - Информационные системы)

Алматы 2013

Составитель: А.Г. Ни. Алгоритмы, структуры данных и программирование. Методические указания к выполнению расчетно-графических работ (для студентов специальности 5В070300 - «Информационные системы»)–Алматы: АУЭС, 2013– 46 с.

Методические указания содержат указания и задания к выполнению расчетно-графических работ, требования к содержанию и оформлению отчета к расчетно-графической работе, контрольные вопросы и перечень рекомендуемой литературы.

Методические указания предназначены для студентов всех форм обучения специальности 5В070300 - «Информационные системы».

Ил.7, библиогр. – 14 назв.

Рецензент: канд. техн. наук, доцент М.В. Башкиров

Печатается по плану издан НАО «Алматинский университет энергетики и связи» на 2013 г.

Содержание
Введение		4
1	Общие указания к выполнению расчетно-графических работ
1.1	Содержание отчета	7
1.2	Общие требования к оформлению отчета	7
1.3	Общие требования к защите РГР	7
2	Варианты заданий к расчетно-графическим работам	8
2.1	Расчетно-графическая работа №1. Графическая и программная реализация алгоритмов обработки простых структур данных	8
2.2	Расчетно-графическая работа №2. Графическая и программная реализация алгоритмов обработки сложных структур данных.	19
2.3	Расчетно-графическая работа №3. Графическая и программная реализация алгоритмов сортировок данных.	34
Заключение		40
Приложение А. Образец титульного листа отчета по РГР		41
Приложение Б. Образец содержания		42
Приложение В. Образец схемы пользовательского интерфейса		43
Приложение Г. Образец результата решения задачи Список литературы		44 45

Введение

Дисциплина “Алгоритмы, структуры данных и программирование” входит в число базовых дисциплин специальности 5B070300 - Информационные системы. При изучении дисциплины учебной программой предусмотрены две формы занятий: лекции и лабораторные. В связи с отсутствием в программе часов на проведение практических занятий написание расчетно – графической работы (РГР) является одной из основных форм самостоятельной работы по дисциплине «Алгоритмы, структуры данных и программирование».

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

- приобретение опыта работы с литературой и другими источниками информации;

- выработка умения применять информационные и компьютерные технологии для решения задач;

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

Согласно рабочему учебному плану специальности 5B070300 - Информационные системы изучение дисциплины “ Алгоритмы, структуры данных и программирование ” предусматривает выполнение студентами трех РГР.

В настоящей работе разработаны индивидуальные задания к трем расчетно-графическим работам по следующим темам:

- графическая и программная реализация алгоритмов обработки простых структур данных;

- графическая и программная реализация алгоритмов обработки сложных структур данных;

- графическая и программная реализация алгоритмов сортировок данных.

Каждая РГР включает в себя два задания А и В, отличающиеся по уровню сложности. При выборе первого задания студент при защите может получить максимальный балл, равный 80%, при защите второго задания – 100%. К защите второго задания студент допускается только при условии защиты первого задания на максимальный балл.

В каждой РГР даются краткие методические указания и примеры решения подобных задач и затем приводятся индивидуальные для каждого задания варианты (всего разработано по 25 различных вариантов). Вариант задания выдается преподавателем.

В настоящей работе также разработаны общие требования к выполнению РГР, которые включают в себя требования к содержанию и оформлению отчета, а также к защите отчета.

С целью приобретения навыка работы с литературой и другими источниками информации при выполнении РГР студент должен самостоятельно провести теоретическое исследование литературных источников по теме РГР, результаты которого должны быть изложены в отчете.

Теоретический материал для выполнения заданий содержится в конспекте лекции по дисциплине, в методических указаниях к лабораторным работам и в литературе, указанной в рабочей программе дисциплины. Часть теоретического материала, которым студенты могут воспользоваться, находится в электронном виде на кафедре «Информационные системы».

1 Общие указания к выполнению расчетно-графических работ

В расчетно-графической работе должны быть выполнены и документально оформлены основные этапы по созданию программы: спецификация, проектирование и реализация.

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

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

На этапе реализации программы производится перевод пошагового алгоритма в пошаговую программу, записанную на языке программирования С/С++.

1.1 Содержание отчета

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

- титульный лист;

- содержание с указанием страниц разделов;

- введение;

- теоретическая часть;

- проектная часть;

- прикладная часть;

- заключение;

- список использованных источников.

Титульный лист оформляется по форме, представленной в приложении А.

В «Содержании» указываются номера разделов и номера их начальных страниц. Образец содержания приведен в приложении Б.

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

В теоретической части должен быть приведен краткий обзор литературы по теме расчетно-графической работы.

В разделе «Проектная часть» должна быть сформулирована содержательная постановка задачи, разработана блок-схема алгоритма решения задачи, описаны входные и выходные данные и разработана схема пользовательского интерфейса. Образец схемы пользовательского интерфейса приведен в приложении В.

В разделе «Прикладная часть» должен быть описан текст программы на языке программирования С/С++, комментарии к тексту программы, результат решения задачи должен быть представлен в виде скриншота экрана с результатами работы программы. Образец приведен в приложении Г.

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

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

1.2 Общие требования к оформлению отчета

Отчет должен быть выполнен печатным способом с использованием компьютера и принтера на одной стороне листа белой бумаги формата А4 через один интервал. Шрифт - обычный, кегль - 14. Текст отчета следует печатать, соблюдая следующие размеры полей: левое - 30 мм, верхнее - 20 мм, правое – 1,5 мм и нижнее - 25 мм. Выравнивание - по ширине страницы.

Заголовки структурных элементов следует печатать прописными (заглавными) буквами в середине строки без точки.

Заголовки разделов, подразделов и пунктов следует печатать с абзацного отступа (1,25 см.) с прописной буквы без точки в конце, не подчеркивая. Если заголовок состоит из двух предложений, их разделяют точкой. Переносы слов в заголовках не допускаются.

Каждый структурный элемент и раздел начинать с новой страницы.

Таблицы должны иметь заголовки и нумероваться. Блок-схемы и схемы пользовательского интерфейса должны иметь подписи и нумероваться.

Страницы отчета следует нумеровать арабскими цифрами, соблюдая сквозную нумерацию по всему тексту отчета. Номер страницы проставляют в центре нижней части листа без точки. Отчет о выполнении РГР оформляется в электронном и печатном виде.

1.3 Общие требования к защите РГР

Студент допускается к защите РГР при выполнении следующих условий:

- программа, реализованная на языке программирования С/С++, должна быть протестирована преподавателем;

- отчет по расчетно-графической работе должен быть оформлен соответственно вышеприведенным требованиям.

Дата защиты РГР назначается преподавателем. В случае несвоевременной защиты оценка снижается на 30 баллов.

2 Варианты заданий к расчетно-графическим работам

2.1 Расчетно-графическая работа №1. Графическая и программная реализация алгоритмов обработки простых структур данных

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

Методические рекомендации. При выполнении задания изучить теоретический материал по теме расчетно-графической работы, разработать алгоритм решения задачи, построить блок-схему и оформить отчет в соответствии с требованиями, указанными в настоящих методических указаниях.

Задание А. Разработать и программно реализовать алгоритм линейных вычислительных процессов.

Варианты задания А:

1. Дано целое трехзначное число. Найти сумму его цифр.

2. Дано целое трехзначное число. Найти среднее арифметическое его цифр.

3. Дана площадь круга. Найти площадь квадрата, вписанного в круг. В качестве значения Pi использовать 3.14.

4. Дана площадь круга. Найти площадь квадрата, в который вписан круг. В качестве значения Pi использовать 3.14.

5. Дана площадь круга. Найти площадь равнобедренного треугольника, вписанного в круг. Основанием треугольника является диаметр круга. В качестве значения Pi использовать 3.14.

6. Найти периметр и площадь прямоугольного треугольника, если даны длины его катетов a и b.

7. Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем этого куба.

8. Найти длину окружности и площадь круга заданного радиуса R. В качестве значения Pi использовать 3.14.

9. Найти площадь кольца, внутренний радиус которого равен R1, а внешний радиус равен R2 (R1 < R2). В качестве значения Pi использовать 3.14.

10. Дана сторона равностороннего треугольника. Найти площадь этого треугольника и радиусы вписанной и описанной окружностей.

11. Дана длина окружности. Найти площадь круга, ограниченного этой окружностью. В качестве значения Pi использовать 3.14.

12. Дана площадь круга. Найти длину окружности, ограничивающей этот круг. В качестве значения Pi использовать 3.14.

13. Найти периметр и площадь равнобедренной трапеции с основаниями a и b (a > b) и углом alpha при большем основании (угол дан в радианах).

14. Найти периметр и площадь прямоугольной трапеции с основаниями a и b (a > b) и острым углом alpha (угол дан в радианах).

15. Найти расстояние между двумя точками с заданными координатами (x1, y1) и (x2, y2).

16. Даны координаты трех вершин треугольника (x1, y1), (x2, y2), (x3, y3). Найти его периметр и площадь.

17. Найти корни квадратного уравнения A·x2 + B·x + C = 0, заданного своими коэффициентами A, B, C (коэффициент A не равен 0), если известно, что дискриминант уравнения неотрицателен.

18. Найти решение системы уравнений вида A1·x + B1·y = C1, A2·x + B2·y = C2, заданной своими коэффициентами A1, B1, C1, A2, B2, C2, если известно, что данная система имеет единственное решение.

19. Дано целое четырехзначное число. Найти сумму его цифр.

20. Дано целое четырехзначное число. Найти произведение его цифр.

21. Даны два ненулевых числа. Найти их сумму, разность, произведение и частное.

22. Даны два числа. Найти среднее арифметическое их квадратов и среднее арифметическое их модулей.

23. Скорость лодки в стоячей воде V км/ч, скорость течения реки U км/ч (U < V). Время движения лодки по озеру T1 ч, а по реке (против течения) — T2 ч. Определить путь S, пройденный лодкой.

24. Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили удаляются друг от друга.

25. Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили первоначально движутся навстречу друг другу.

Задание Б. Разработать и программно реализовать алгоритм разветвляющихся и циклических вычислительных процессов. Для вариантов 1-4 найти алгоритм решения задачи и реализовать его с помощью оператора (операторов) if-then-else. Используя оператор выбора, составить программы решения задач вариантов 5-8. Для вариантов 9-10 составить программу проверки. Для вариантов 11-25 вычислить и вывести на экран значения функции F на интервале от Xнач. До Хкон. с шагом dX. a, b, c – действительные числа. Значения a, b, c, Хнач., Хкон., dX ввести с клавиатуры.

Варианты задания Б:

Вариант 1.

Составить программу, реализующую эпизод сказки: машина спрашивает, куда пойдет герой, и в зависимости от ответа (налево – (-1), прямо – 0, направо – 1), печатает, что произойдет с героем.

Вариант 2.

Морской бой. Машина задумывает два числа от 0 до 9. Игрок пытается их угадать, вводя свои два числа. Если они совпали (в любом сочетании), то игрок выиграл.

Вариант 3.

В Атлантическом океане терпит бедствие пассажирский теплоход «Посудина». Все пассажиры будут спасены, если на помощь успеют два судна. Судно продержится на плаву t часов. Скорость судов-спасателей 40 узлов. Составить программу, определяющую спасутся ли пассажиры. Известны расстояния от трех судов-спасателей до тонущего судна.

Вариант 4.

Через старый мост движется поток автомашин. Одновременно на мосту могут находиться 3 машины. Если на мост въедут 3 легковых или 2 легковых и грузовик – мост выдержит. Если 2 грузовика и легковая или 3 грузовика – рухнет.

Вариант 5.

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

Вариант 6.

По номеру месяца указать, к какому времени года он относится.

Вариант 7.

По номеру месяца вывести на печать количество дней в нем.

Вариант 8.

Единицы массы пронумерованы следующим образом: 1 — килограмм, 2 — миллиграмм, 3 — грамм, 4 — тонна. Дан номер единицы массы и масса тела M в этих единицах (M - вещественное число). Вывести массу данного тела в килограммах.

Вариант 9.

Даны действительные числа a, b, c, x, y. Выяснить, пройдет ли кирпич с ребрами a,b,c в прямоугольное отверстие со сторонами x и y. Просовывать кирпич в отверстие разрешается только так, чтобы каждое из его ребер было параллельно или перпендикулярно каждой из сторон отверстия.

Вариант 10.

Сможет ли шар радиуса R пройти в ромбообразное отверстие со стороной P и острым углом Q?

Вариант 11.

ax² + при х < 1 и c ¹ 0

F =

при х > 1,5 и c = 0

в остальных случаях

Вариант 12.

ax² + b² + c при х < 0,6 и b + c ¹ 0

F =

при х > 0,6 и b + c = 0

+ в остальных случаях

Вариант 13.

ax² + b при x - 1 < 0 и b - x ¹ 0

F =

при х – 1 > 0 и b+x = 0

в остальных случаях

Вариант 14.

- ax² - b при x + c < 0 и a ¹ 0

F =

при х + c > 0 и a = 0

+ в остальных случаях

Вариант 15.

- ax² + b при x < 0 и b ¹ 0

F = (x + c)² - b + 5,5 при х > 0 и b = 0

в остальных случаях

Вариант 16.

a(x + c)² - b при x < 0 и b ¹ 0

F =

при х > 0 и b = 0

a + в остальных случаях

Вариант 17.

ax² – cx + b при x + 10 < 0 и b ¹ 0

F =

при х + 10 > 0 и b = 0

в остальных случаях

Вариант 18.

ax³ + bx² при x < 0 и b ¹ 0

F =

при х > 0 и b = 0

в остальных случаях

Вариант 19.

a(x + 7)² - b при x < 5 и b ¹ 0

F =

при х > 5 и b = 0

в остальных случаях

Вариант 20.

- при x < 0 и b ¹ 0

F =

при х > 0 и b = 0

- + в остальных случаях

Вариант 21.

a - при х < 0 и b ¹ 0

F =

при х > 0 и b = 0

3x + в остальных случаях

Вариант 22.

ax² + b²x при c < 0 и b ¹ 0

F =

при c > 0 и b = 0

в остальных случаях

Вариант 23.

сх - ax² - b при х < 5 и с ¹ 0

F =

при х > 5 и с = 0

в остальных случаях

Вариант 24.

- ax² +bх при х < 0 и b ¹ 0

F =

при х > 0 и b = 0

в остальных случаях

Вариант 25.

ax² при a < 0 и x ¹ 0

F = x -

при a > 0 и x = 0

cos(x) + в остальных случаях

Демонстрационный пример задания А.

Найти площадь кольца, внутренний радиус которого равен R1, а внешний радиус равен R2 (R1<R2). В качестве значения Пи использовать 3,14.

Словесное описание алгоритма:

1) ввести R1, R2;

2) вычислить S1=3.14*(R1^2);

3) вычислить S2=3.14*(R2^2);

4) вычислить S3=S2 – S1;

5) вывести S3.

Графическое описание алгоритма:

$C:\Users\Sanek\Desktop\Тупые файлы\Тупые файлы\Безымянный2.bmp$

Рисунок 2.1 - Блок-схема решения задания А

Программное описание алгоритма:

#include <stdio.h>

#include <math.h>

void main(void)

{

int R1,R2;

float S1,S2,S3;

printf ("\введите R1 \n R1 =");

scanf("%f",& R1);

printf ("\n введите R2 \n R2 =");

scanf("%f",& R2);

puts("РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА N1 - ЛИНЕЙНАЯ ПРОГРАММА ");

puts("============================================");

S1=3.14*pow(R1,2);

S2=3.14*pow(R2,2);

S3=fabs(S1-S2);

printf("\a\n ОТВЕТ: S =%f", S);

getch( ); /* задержка экрана */

}

Результат выполнения программы:

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА N1 - ЛИНЕЙНАЯ ПРОГРАММА ============================================

введите R1

R1 =3.

введите R2

R2 =4.

ОТВЕТ: S =8.437500

Демонстрационный пример задания Б. Вычислить и вывести на экран значения функции F на интервале от Xнач. До Хкон. с шагом dX. a, b, c – действительные числа. Значения a, b, c, Хнач., Хкон., dX ввести с клавиатуры.

в остальных случаях

при x > 0 и b = 0

при x < 0 и b ¹ 0

Словесное описание алгоритма решения задания Б:

1) ввести a, b, c, Хнач., Хкон., dX ;

2) начало цикла х= Хнач;

3) если x меньше нуля и b не равно нулю, то вычислить значение F=ax²+b и перейти к п. 6, в противном случае перейти к п.7;

4) если x меньше нуля и b не равно нулю, то вычислить значение и перейти к п. 6. в противном случае перейти к п.7;

5) вычислить значение ;

6) вывод F;

7) увеличить шаг цикла х=х+ dX;

8) проверить: если х меньше или равно Хкон., то перейти к п. 3, иначе перейти к п.9;

9) конец цикла;

10) конец алгоритма.

Графическое описание алгоритма решения задания Б

Рисунок 2.2 - Блок-схема решения задания Б

Программное описание алгоритма решения задания Б

#include <stdio.h>

#include <math.h>

int main()

{

float a, b, c;

float StartX, EndX, dX;

float F;

/* Вводим значения переменных */

printf("Введите:");

printf("\ta = "); scanf("%f", &a);

printf("\tb = "); scanf("%f", &b);

printf("\tc = "); scanf("%f", &c);

/* Вводим параметры цикла */

printf("\tX нач. = "); scanf("%f", &StartX);

printf("\tX кон. = "); scanf("%f", &EndX);

printf("\tdX = "); scanf("%f", &dX);

/* Выполняем цикл от начального значения Х до конечного значения Х с шагом dX */

for (float x = StartX; x <= EndX; x += dX)

{

/* Вычисляем значение функции F, исходя из заданных условий */

if (x < 0 && b != 0)

F = a * (float)pow(x, 2) + b;

else if (x > 0 && b == 0)

F = (x - a) / (x - c);

else

F = x / c;

printf("x = %.2f\tF = %.2f\n", x, F);

}

return 0; /* Успешное завершение программы */

}

Результат выполнения программы:

Введите:

a = 3.5

b = 8

c = 293

X нач. = -4

X кон. = 2.5

dX = 0.5

x = -4.00 F = 64.00

x = -3.50 F = 50.88

x = -3.00 F = 39.50

x = -2.50 F = 29.88

x = -2.00 F = 22.00

x = -1.50 F = 15.88

x = -1.00 F = 11.50

x = -0.50 F = 8.88

x = 0.00 F = 0.00

x = 0.50 F = 0.00

x = 1.00 F = 0.00

x = 1.50 F = 0.01

x = 2.00 F = 0.01

x = 2.50 F = 0.01

Контрольные вопросы:

1) Что такое алгоритм?

2) Какие виды алгоритмов вы знаете?

3) Что такое структура данных?

4) Какие структуры данных вы знаете?

5) Характерные черты линейного алгоритма.

6) Характерные черты циклического алгоритма.

7) Характерные черты разветвляющегося алгоритма.

8) Какие виды циклов вы знаете?

9) Алгоритм цикла с параметром.

10) Алгоритм цикла с предусловием.

11) Алгоритм цикла с постусловием.

2.2 Расчетно-графическая работа №2. Графическая и программная реализация алгоритмов обработки сложных структур данных

Цель: закрепить навыки разработки и программирования на языке Си алгоритмов обработки сложных структур данных: одномерных массивов и матриц. Приобрести навыки программирования с переменными типа указатель.

Задание А.

Составить блок-схему и программу обработки одномерного массива. Элементы массива заполнить, используя функцию генератора случайных чисел. Программу написать двумя способами: 1) осуществляя доступ к элементам массива с помощью индексов; 2) осуществляя доступ к элементам массива с помощью указателей.

Варианты задания А

1. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N] следующим образом: вначале заполнить элементами с четными индексами, а затем — с нечетными. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов.

2. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N] следующим образом: вначале заполнить элементами с |нечетными индексами, а затем —с четными. Осуществить сдвиг вправо на k позиций, где k – число отрицательных элементов.

3. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N], которые удовлетворяют двойному неравенству: A[1] < A[i] < A[10]. Незаполненные элементы массива В[N] заполнить оставшимися элементами массива A[N]. Осуществить сдвиг влево на k позиций, где k – число оставшихся элементов массива A[N].

4. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N], которые удовлетворяют двойному неравенству: A[1] < A[i] или A[i] < A[10]. Незаполненные элементы массива В[N] заполнить оставшимися элементами массива A[N]. Осуществить сдвиг вправо на k позиций, где k – число оставшихся элементов массива A[N].

5. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам первый элемент. Первый элементы массива не изменять. Осуществить сдвиг вправо на k позиций, где k – число четных элементов.

6. Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам первый элемент. Первый элемент массива не изменять. Осуществить сдвиг вправо на k позиций, где k – число четных элементов.

7. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам последний элемент. Последний элемент массива не изменять. Осуществить сдвиг влево на k позиций, где k – число нечетных элементов.

9. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам первый элемент. Первый элемент массива не изменять. Осуществить сдвиг вправо на k позиций, где k – число нечетных элементов.

10. Поменять местами минимальный и максимальный элементы массива размера 10. Осуществить сдвиг вправо на k позиций, где k – число элементов, расположенных между его минимальным и максимальным элементами.

11. Дан массив A[N]. Все положительные элементы уменьшить на значение минимального элемента. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов.

12. Дан массив A[N]. Все отрицательные элементы увеличить на значение максимального элемента. Осуществить сдвиг влево на k позиций, где k – число отрицательных элементов.

13. Дан массив размера 10. Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами. Осуществить циклический сдвиг элементов массива влево на k позиций, где k – k – число элементов, расположенных между его минимальным и максимальным элементами.

14. Дан массив размера N. Осуществить циклический сдвиг элементов массива влево на k позиций, где k – индекс минимального элемента.

15. Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента.

16. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения положительных элементов массива A[N].

17. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения отрицательных элементов массива A[N].

18. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения четных элементов массива A[N].

19. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения нечетных элементов массива A[N].

20. Дан массив A[N]. Все отрицательные элементы уменьшить на значение минимального элемента. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов.

21. Дан массив A[N]. Все четные элементы уменьшить на значение максимального элемента. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов.

22. Дан массив A[N]. Все нулевые элементы увеличить на значение максимального элемента. Осуществить сдвиг влево на k позиций, где k – число отрицательных элементов.

23. Дан массив размера 10. Поменять местами минимальный и максимальный элементы. Осуществить циклический сдвиг элементов массива влево на k позиций, где k – k – число элементов, расположенных между его минимальным и максимальным элементами.

24. Дан массив A[N]. Заполнить массив В[N] сначала четными элементами массива A[N], а потом нечетными. Осуществить циклический сдвиг элементов массива влево на k позиций, где k – индекс минимального элемента.

25. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N], сначала с четными индексами, а потом с нечетными. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента.

Задание Б.

Составить блок-схему и программу обработки матрицы. Элементы матрицы заполнить, используя функцию генератора случайных чисел.

Программу написать двумя способами:

1) осуществляя доступ к элементам матрицы с помощью индексов;

2) осуществляя доступ к элементам матрицы с помощью указателей.

Варианты задания Б.

1. Дана целочисленная прямоугольная матрица. Определить:

а) количество строк, не содержащих ни одного нулевого элемента;

б) максимальное из чисел, встречающихся в заданной матрице более одного раза.

2. Дана целочисленная прямоугольная матрица.

а) Определить количество столбцов, не содержащих ни одного нулевого элемента.

б) Характеристикой строки целочисленной матрицы назовем сумму ее положительных четных элементов. Переставляя строки заданной матрицы, расположить их в соответствии с ростом характеристик.

3. Дана целочисленная прямоугольная матрица. Определить:

а) количество столбцов, содержащих хотя бы один нулевой элемент;

б) номер строки, в которой находится самая длинная серия одинаковых элементов.

4. Дана целочисленная квадратная матрица. Определить:

а) произведение элементов в тех строках, которые не содержат отрицательных элементов;

б) максимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

5. Дана целочисленная квадратная матрица. Определить:

а) сумму элементов в тех столбцах, которые не содержат отрицательных элементов;

б) минимум среди сумм модулей элементов диагоналей, параллельных побочной диагонали матрицы.

6. Дана целочисленная прямоугольная матрица. Определить:

а) сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент;

б) номера строк и столбцов всех седловых точек матрицы.

Примечание:

Матрица А имеет седловую точку А_ij, если A_ij является минимальным элементом в i-й строке и максимальным в j-м столбце.

7. Для заданной матрицы размером 8 на 8:

а) найти такие k, что k-я строка матрицы совпадает с k-м столбцом;

б) найти сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент.

8. Характеристикой столбца целочисленной матрицы назовем сумму модулей его отрицательных нечетных элементов.

а) переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик;

б) найти сумму элементов в тех столбцах, которые содержат хотя бы один отрицательный элемент.

9. Соседями элемента Аij в матрице назовем элементы А_i_-1,_j_-1. А_i_-1,_j_, А_i_-1,_j_+1, А_i_,_j_-1, А_i_,_j_+1, А_i_+1,_j_-1. А_i_+1,_j_, А_i_+1,_j_+1.Операция сглаживания матрицы дает новую матрицу того же размера, каждый элемент которой получается как среднее арифметическое имеющихся соседей соответствующего элемента исходной матрицы:

а) построить результат сглаживания заданной вещественной матрицы размером 10 на 10;

б) в сглаженной матрице найти сумму модулей элементов, расположенных ниже главной диагонали.

10. Элемент матрицы называется локальным минимумом, если он строго меньше всех имеющихся у него соседей.

а) подсчитать количество локальных минимумов заданной матрицы размером 10 на 10;

б) найти сумму модулей элементов, расположенных выше главной диагонали.

11. Коэффициенты системы линейных уравнений заданы в виде прямоугольной матрицы.

а) с помощью допустимых преобразований привести систему к треугольному виду;

б) найти количество строк, среднее арифметическое элементов которых меньше заданной величины.

12. Дана действительная квадратная матрица порядка n.

а) уплотнить заданную матрицу, удаляя из нее строки и столбцы, заполненные нулями;

б) найти номер первой из строк, содержащих хотя бы один положительный элемент.

13. Дана действительная квадратная матрица порядка n.

а) осуществить циклический сдвиг элементов прямоугольной матрицы на п элементов вправо или вниз (в зависимости от введенного режима). n может быть больше количества элементов в строке или столбце;

б) найти номер последней из строк, содержащих хотя бы один ненулевой элемент.

14. Дана действительная квадратная матрица порядка n.

а) осуществить циклический сдвиг элементов квадратной матрицы размерности МхN вправо на k элементов таким образом: элементы 1-й строки сдвигаются в последний столбец сверху вниз, из него - в последнюю строку справа налево, из нее - в первый столбец снизу вверх, из него - в первую строку; для остальных элементов - аналогично;

б) найти сумму положительных элементов нечетных строк.

15. Дана целочисленная прямоугольная матрица:

а) определить номер первого из столбцов, содержащих хотя бы один нулевой элемент;

б) характеристикой строки целочисленной матрицы назовем сумму ее отрицательных четных элементов. Переставляя строки заданной матрицы, расположить их в соответствии с убыванием характеристик.

16. Дана целочисленная прямоугольная матрица.

а) упорядочить строки целочисленной прямоугольной матрицы по возрастанию количества одинаковых элементов в каждой строке;

б) найти номер первого из столбцов, не содержащих ни одного отрицательного элемента.

17. Дана квадратная вещественная матрица.

а) путем перестановки элементов матрицы добиться того, чтобы ее максимальный элемент находился в левом верхнем углу, следующий по величине - в позиции (2,2), следующий по величине - в позиции (3,3) и т. д., заполнив таким образом всю главную диагональ;

б) найти номер первой из строк, не содержащих ни одного положительного элемента.

18. Дана целочисленная прямоугольная матрица. Определить:

а) количество строк, содержащих хотя бы один нулевой элемент;

б) номер столбца, в которой находится самая длинная серия одинаковых элементов.

19. Дана целочисленная квадратная матрица. Определить:

а) сумму элементов в тех строках, которые не содержат отрицательных элементов;

б) минимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

20. Дана целочисленная прямоугольная матрица. Определить:

а) количество отрицательных элементов в тех строках, которые содержат хотя бы один нулевой элемент;

а) номера строк и столбцов всех седловых точек матрицы.

Примечание: Матрица A имеет седловую точку Aij если Аij является минимальным элементом в i-й строке и максимальным в j-м столбце.

21. Среди столбцов заданной целочисленной матрицы, содержащих только такие элементы, которые по модулю не больше 10, найти столбец с минимальным произведением элементов.

22. Среди строк заданной целочисленной матрицы, содержащих только нечетные элементы, найти строку с максимальной суммой модулей элементов.

23. Напечатать элементы заданной матрицы размером 10 10 в следующем порядке:

24. Напечатать элементы заданной матрицы размером 10 10 в следующем порядке:

25. Характеристикой столбца целочисленной матрицы назовем сумму модулей его отрицательных нечетных элементов. Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик.

Демонстрационный пример задания А.

Дан массив a[n].Заполнить массив b[n] элементами массива a[n] , начиная с последнего и осуществить сдвиг вправо на К позиций, где К-число положительных элементов.

Словесное описание алгоритма задания А:

1) начало алгоритма;

2) заполнить массив а[n] случайными числами;

3) обнулить переменную pol и j=n;

4) организовать цикл с заданными параметрами от i=1; n;1:

- элементу массива b[n] присвоить элемент массива а[n], то есть b[j]=а[i];

- j= j-1;

- проверить: если b[j]>=0, то число положительных элементов увеличить на 1, т.е. pol= pol+1 иначе перейти к следующему шагу цикла;

5) вывести число положительных элементов массива b[n];

6) вывести элементы массива b[n];

7) организовать цикл с заданными параметрами от i=1; pol;1:

- запомнить последний элемент buf= b[n]

- организовать цикл с заданными параметрами от j = n; 1;-1. Внутри цикла:

- последующему элементу присвоить предыдущий, то есть b[j]=b[j-1];

- по окончании цикла по j первому элементу присвоить значение последнего, то есть b[1]= b[n] и перейти к следующему циклу по i;

8) Вывести элементы массива b[n] ;

9) конец алгоритма.

Графическое описание алгоритма задания А:

Рисунок 2.3 - Блок-схема решения задания А

Программное описание алгоритма задания А:

(доступ к элементам массива с помощью индексов)

#include <stdlib.h>

# include <conio.h>

# include <stdio.h>

#define n 10

int main ()

{ int buf,j,pol,i,b[n], a[n];

for (i = 0; i < n; i++)

a[i]=rand()%10-5;

pol=0;

printf ("\n \n Сгенерированный массив a[n] \n");

for (i=0;i< n;i++)

printf ("%d ",a[i]);

j=n-1;

for (i=0;i< n;i++)

{b[j]=a[i];

j=j-1;

if (a[i]>=0)pol++;

}

printf ("\n Число положительных элементов \n pol=%d",pol);

printf ("\n \n вывод массива b[n] \n");

for (i=0;i< n;i++)

printf ("%d ",b[i]);

for (i=0;i<pol;i++)

{ buf=b[n-1];

for(j=n-1;j>0;j--)

b[j]=b[j-1];

b[0]=buf;

}

printf ("\n \n Сдвиг элементов массива b[n] на %d позиций \n", pol);

for (i=0;i< n;i++)

printf ("%d ",b[i]);

printf ("\n");

system("PAUSE");

return 0;

}

Программное описание алгоритма задания А:

(доступ к элементам массива с помощью указателя)

#include <stdlib.h>

# include <conio.h>

# include <stdio.h>

#define n 10

int main ()

{ int buf,j,pol,i,b[n], *pa,*pb,*p, a[n];

for (i = 0; i < n; i++)

a[i]=rand()%10-5;

pol=0;

pa=&a[0];

pb=&b[9];

printf ("\n \n Сгенерированный массив a[n] a[n] \n");

for (i=0;i< n;i++)

printf ("%d ",*pa++);

pa=&a[0];

for (i=0;i< n;i++)

{*pb=*pa;

if (*pa>=0)pol++;

--pb;

++pa;

}

printf ("\n Число положительных элементов \n pol=%d",pol);

printf ("\n \n вывод массива b[n] \n");

pb=&b[0];

for (i=0;i<n;i++)

printf ("%d ",*pb++);

pb=&b[9];

p=&b[0];

for (i=0;i<pol;i++)

{ buf=*pb;

for(j=0;j<n;j++)

*pb=*(--pb);

*p=buf;

p=&b[0];

pb=&b[9];

}

printf ("\n \n Сдвиг элементов массива b[n] на %d позиций \n", pol);

pb=&b[0];

for (i=0;i< n;i++)

printf ("%d ",*pb++);

printf ("\n");

system("PAUSE");

return 0;

}

Результат выполнения программы задания А:

Сгенерированный массив a[n]

1 2 3 -4 -5 -1 -2 -3 -7 9

Число положительных элементов

pol=4

вывод массива b[n]

9 -7 -3 -2 -1 -5 -4 3 2 1

Сдвиг элементов массива b[n] на 4 позиций

-4 3 2 1 9 -7 -3 -2 -1 -5

Демонстрационный пример задания Б.

Дана целочисленная матрица размером 8 на 8. Найти:

1) такие k, что k-я строка матрицы совпадает с k-м столбцом;

2) сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент.

Словесное описание алгоритма задания Б:

1) начало алгоритма;

2) задать размерность матрицы;

3) заполнить массив а[n][m] случайными числами;

4) вывести элементы массива а[n][m] ;

5) организовать цикл с заданными параметрами от i=1; n;1. Внутри цикла по i:

- признаку совпадения присвоить единицу Р=1;

- организовать цикл с заданными параметрами от j =1;m;1. Внутри цикла по j:

- проверить: если а[i][j]= а[j][i], то перейти к следующему шагу

цикла по j, иначе перейти к следующему шагу цикла по i;

- по окончании цикла по j проверить: если Р=1, то вывести номер совпадающих строки и столбца;

- перейти к следующему шагу цикла по i;

6) по окончании цикла по i вновь организовать цикл с заданными параметрами от i=1; n;1. Внутри цикла по i:

- признаку наличия хотя бы одного отрицательного элемента в строке присвоить нуль Р1=0 и обнулить сумму s=0;

- организовать цикл с заданными параметрами от j =1;m;1. Внутри цикла по j:

- суммировать элементы строки;

- проверить: если а[i][j]<0, то Р1=1 и перейти к следующему шагу

цикла по j;

- по окончании цикла по j проверить: если Р1=1, то вывести сумму элементов i –ой строки;

- перейти к следующему шагу цикла по i;

7) конец алгоритма

Графическое описание алгоритма задания Б:

Рисунок 2.4 -Блок-схема решения задания Б

Программное описание алгоритма задания Б:

(доступ к элементам массива с помощью индексов)

#include <stdio.h>

#include <stdlib.h>

#define m 8

#define n 8

int main()

{ int matrix[n][m]; /* Объявляем матрицу nхm */

int i, j, p; /* Счетчик и признак совпадения */

int p1, iSumm; /* признак нахождение отрицательного элемента и переменная для хранения суммы */

/* генератором случайных чисел заполняем матрицу */

for (i = 0; i < m; i++)

for (j = 0; j < n; j++)

matrix[i][j]=rand()%10-1;

printf("\n Сгенерированная матрица имеет вид:\n ");

/* вывод матрицы */

for (i = 0; i < m; i++)

{ for (j = 0; j < n; j++)

printf(“%d “,matrix[i][j]);

printf("\n ");

}

printf("\n \t\t\tРЕЗУЛЬТАТ ПЕРВОЙ ЧАСТИ ЗАДАНИЯ");

for (i = 0; i < m; i++)

{ p=1;

for (j = 0; j < n; j++)

{ /* Сравниваем элемент i-й строки j-го столбца с элементом j-й строки i-го столбца. В случае их несоответствия присваиваем p значение нуль и прерываем цикл по j конструкцией break */

if (matrix [i][j] != matrix [j][i])

{ p=0;

break;

}

/* В случае p=1 выводим на экран номер соответствующей строки */

if (p==1) printf("\n k = %d ", i+1);

}

if (p==0) printf("\n нет одинаковых строк и столбцов ");

printf("\n \t\t\tРЕЗУЛЬТАТ ВТОРОЙ ЧАСТИ ЗАДАНИЯ");

printf("\n\n");

for (i = 0; i < m; i++)

{

/* Присваиваем переменным исходные значения */

iSumm = 0;

p1=0;

for (j = 0; j < n; j++)

{ /* Суммируем значения элементов i-й строки */

iSumm += matrix [i][j];

/* При нахождение хотя бы одного отрицательного элемента присваиваем p1=1, обозначающее необходимость вывода Суммы на экран */

if (matrix [i][j] < 0) p1=1;

}

/* В случае нахождения в строке хотя бы одного отрицательного элемента выводим на экран сумму элементов i-й строки */

if (p1==1) printf("Сумма элементов строки #%d = %d\n", i+1, iSumm);

}

system("PAUSE");/* задержка экрана*/

return 0;

}

Программное описание алгоритма задания Б:

(доступ к элементам массива с помощью указателя)

#include <stdio.h>

#include <stdlib.h>

#define m 8

#define n 8

void main()

{

int matrix[n][m]; /* Объявляем матрицу nхm */

int i, j, p; /* Счетчик и признак совпадения */

int *mat; /* Объявляем указатель на матрицу matrix[n][m] */

mat=&matrix[0][0]; /* указателю mat присваиваем адрес нулевого элемента матрицы matrix[n][m] */

/* генератором случайных чисел заполняем матрицу */

for (i = 0; i < m; i++)

for (j = 0; j < n; j++)

{

*mat=rand()%10-1;

mat++;

}

mat-= n*m; /* указателю mat присваиваем первоначальный адрес */

printf("\n Сгенерированная матрица имеет вид:\n ");

/* вывод матрицы */

for (i = 0; i < m; i++)

{

for (j = 0; j < n; j++)

{

printf(“%d “,*mat);

mat++;

}

printf("\n ");

}

mat-= n*m;

printf("\n \t\t\tРЕЗУЛЬТАТ ПЕРВОЙ ЧАСТИ ЗАДАНИЯ");

printf("\n Совпавшие строки и столбцы ");

for (i = 0; i < m; i++)

{

p=1;

for (j = 0; j < n; j++)

if (*(mat+i * m + j) != *(mat+j * m + i))

{

p=0;

break;

}

/* В случае p=1 выводим на экран номер соответствующей строки */

if (p==1) printf("\n k = %d ", i);

}

if (p==0) printf("\n нет одинаковых строк и столбцов ");

printf("\n \t\t\tРЕЗУЛЬТАТ ВТОРОЙ ЧАСТИ ЗАДАНИЯ");

mat=&matrix[0][0];

int p1, iSumm; /* признак нахождения отрицательного элемента и переменная для хранения суммы */

printf("\n\n");

for (i = 0; i < m; i++)

{

/* Присваиваем переменным исходные значения */

iSumm = 0;

p1=0;

for (j = 0; j < n; j++)

{ /* Суммируем значения элементов i-й строки */

iSumm += *mat;

/* При нахождении хотя бы одного отрицательного элемента присваиваем p1=1, обозначающее необходимость вывода Суммы на экран */

if (*mat < 0) p1=1; mat++;

}

if (p1==1) printf("Сумма элементов строки #%d = %d\n", i+1, iSumm);

}

system("PAUSE");/* задержка экрана*/

return 0;

}

Результат выполнения программы задания Б:

Сгенерированная матрица имеет вид:

2 7 2 7 1 4 0 3

1 0 7 6 0 -8 3 5

2 7 1 8 1 4 9 3

9 2 8 5 2 0 0 6

7 1 1 3 9 3 9 1

8 2 4 9 1 -6 4 9

0 3 9 0 9 4 8 8

1 8 3 2 8 2 8 0

РЕЗУЛЬТАТ ПЕРВОЙ ЧАСТИ ЗАДАНИЯ

Совпавшие строки и столбцы:

k = 2

k = 6

РЕЗУЛЬТАТ ВТОРОЙ ЧАСТИ ЗАДАНИЯ

Сумма элементов строки #1 = 14

Сумма элементов строки #5 = 31

Контрольные вопросы:

1) Что понимается под сложными структурами данных ?

2) Какие существуют классы задач по обработке массивов?

3) Что предполагают задачи поиска в массивах?

4 Что предполагают задачи замены в массивах?

5) Что предполагают задачи перестановок в массивах?

6) Что предполагают задачи сортировок в массивах?

7) Как поменять местами два элемента массива?

8) Что такое вложенные циклы?

9) Как найти максимальный (минимальный) элемент?

10) Графически описать алгоритм поиска элемента массива.

11) Графически описать алгоритм замены элемента массива.

12) Графически описать алгоритм перестановки элемента массива.

2.3 Расчетно-графическая работа №3. Графическая и программная реализация алгоритмов сортировок данных

Цель: закрепить навыки программирования на языке Си алгоритмов обработки массивов.

Методические рекомендации. При выполнении задания изучить теоретический материал по теме расчетно-графической работы, написать программу решения задачи и оформить отчет в соответствии с требованиями, указанными в настоящих методических указаниях.

Краткая теоретическая часть. Существует традиционное деление алгоритмов на численные (вычислительные) и нечисленные (невычислительные). Численные алгоритмы предназначены для математических расчетов чисел, нечисленные алгоритмы имеют дело с различными структурированными данными. Одними из важных невычислительных алгоритмов являются – сортировка и поиск. Сортировкой называют процесс перегруппировки заданной последовательности объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в отсортированном множестве. Алгоритмы сортировки зависят от выбора структур данных, поэтому методы сортировки делят на два вида: алгоритмы внутренней сортировки (сортировка массивов) и алгоритмы внешней сортировки (сортировка файлов).

Метод сортировки называется устойчивым, если относительный порядок элемента с одинаковыми ключами не меняется при сортировке. Алгоритмы внутренней сортировки - это алгоритмы сортировки с данными во внутренней памяти, удобной структурой в данном случае является массив. Основное требование к методам сортировок массивов – экономное использование памяти. Существуют простые методы сортировки: сортировка простой вставкой, сортировка простой выборкой, сортировка простым обменом (метод пузырька).

Задание А: графически и программно реализовать алгоритмы сортировки элементов одномерного массива. Сортировку осуществить тремя способами:

а) методом простого обмена;

б) методом простой выборки;

в) методом простой вставки.

Варианты задания А: задания соответствуют вариантам задания А, данных в расчетно-графической работе №2.

Задание Б: составить программу сортировки элементов матрицы:

а) элементы побочной диагонали отсортировать методом простого обмена;

б) элементы главной диагонали отсортировать методом простой выборки;

в) элементы первой строки отсортировать методом простой вставки.

Варианты задания Б: задания соответствуют вариантам задания Б, данных в расчетно-графической работе №2.

Словесное описание алгоритма сортировки данных методом простого обмена

1) сравним первый элемент массива со вторым: если 1-ый окажется больше 2-го, то поменяем их местами; выполним эти же действия для 2-го и 3-го, для 3-го и 4-го, … , для (n-1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее n-е место;

2) повторим данный алгоритм сначала, но последний n-й элемент рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n-1)-е место;

3) так повторяем до тех пор, пока не упорядочим весь массив.

Рисунок 2.5 - Графическое описание алгоритма сортировки данных методом простого обмена

Словесное описание алгоритма сортировки данных методом простой выборки:

1) найдем в массиве минимальный (максимальный) элемент;

2) поменяем его местами с первым (последним) элементом;

3) повторим алгоритм поиска минимального (максимального) элемента, уменьшив количество просматриваемых элементов на единицу ;

4) поменяем его местами со вторым (предпоследним элементом);

5) описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве.

Рисунок 2.6 - Графическое описание алгоритма сортировки данных методом простой выборки

Словесное описание алгоритма сортировки данных методом простой вставки:

1) сортируемый массив делим на две части - отсортированную часть и неотсортированную. В начале сортировки первый элемент массива считается отсортированным, все остальные - не отсортированные;

2) берем первый элемент из неотсортированной части и сравниваем его с элементами из отсортированной части;

3) неотсортированный элемент массива вставляем в нужную позицию в отсортированной части массива. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент;

4) описанные выше операции вставки проводим до полного упорядочивания элементов в массиве.

Рисунок 2.7- Графическое описание алгоритма сортировки данных методом простой вставки

Программное описание алгоритма сортировки данных методом простого обмена.

#include <stdio.h>

#include <stdlib.h>

#define N 10

int main()

{

int a[N],min,i,j,buf;

for (i=0;i<N;i++)

a[i]=rand()%10-1;

printf("n\n sgenerirovanni massiv\n" );

for (i=0;i<N;i++)

printf("%d " , a[i]);

printf("\n");

printf ("\n Massiv otsortirovanii metodom prostogo obmena ");

for (i=0;i<N-1;i++)

for (j=0;j<N- i -1;j++)

if (a[j]>a[j+1])

{

buf=a[j];

a[j]=a[j+1];

a[j+1]=buf;

}

printf ("\n");

for (i=0;i<N;i++)

printf (" %d ",a[i]);

system("PAUSE");

return 0;

}

Программное описание алгоритма сортировки данных методом простой выборки.

#include <stdio.h>

#include <stdlib.h>

#define N 10

int main()

{int a[N],min,i,j,buf;

for (i=0;i<N;i++)

a[i]=rand()%10-1;

printf("n\n sgenerirovanni massiv\n" );

for (i=0;i<N;i++)

printf("%d " , a[i]);

printf("\n");

printf ("\n Massiv otsortirovanii metodom prostoi viborki ");

for (i=0 ;i<N;i++)

{

min=a[i];

for (j=i+1;j<N;j++)

if (a[j]<min )

{ min=a[j];a[j]=a[i];

a[i]=min;

}

printf ("\n");

for (i=0;i<N;i++)

printf (" %d ",a[i]);

system("PAUSE");

return 0;

}

Программное описание алгоритма сортировки данных методом простой вставки.

#include <stdio.h>

#include <stdlib.h>

#define N 5

int main()

{int a[N],min,i,j,buf,k;

for (i=0;i<N;i++)

a[i]=rand()%10-1;

printf("n\n sgenerirovanni massiv\n" );

for (i=0;i<N;i++)

printf("%d " , a[i]);

printf("\n");

printf ("\n Massiv otsortirovanii metodom prostoi vstavki");

for (i=1;i<N;i++)

{ buf= a[i];

for ( j= i - 1;j>=0;j--)

if (a[j]>buf)

{ a[j+1]=a[j];

a[j]= buf;

}

printf ("\n");

for (i=0;i<N;i++)

printf (" %d ",a[i]);

getch ();

return 0;

}

Контрольные вопросы:

1) Что понимается под сортировкой массива?

2) Чем отличается сортировка по убыванию от сортировки по невозрастанию?

3) Сформулировать идею сортировки массива методом простого выбора.

4) Сформулировать идею сортировки массива методом простого обмена.

5) Сформулировать идею сортировки массива методом простой вставки.

6) Почему время выполнения одного шага прямо пропорционально размеру неупорядоченной части массива?

7) Как поменять местами два элемента массива?

8) Что такое вложенные циклы?

9) В чем сходство и отличие методов простого выбора и простого обмена?

Заключение

В представленной разработке основной акцент сделан на самостоятельную работу студентов при выполнении ими расчетно-графических работ. Содержащиеся в начале каждой РНР подробные примеры решения задач позволяют самостоятельно изучить материал и успешно выполнить задания по предмету.

Каждая РГР включает в себя два задания А и В по 25 вариантов каждого из заданий, отличающиеся по уровню сложности. При выборе первого задания студент при защите может получить максимальный балл, равный 80%, при защите второго задания – 100%. К защите второго задания студент допускается только при условии защиты первого задания на максимальный балл.

Выполнение заданий РГР способствует выработке у студентов навыков разработки алгоритмов решения задач и их реализации на языке программирования Си.

Список литературы

1. Эпштейн М.С. Программирование на языке С. - М.: «Академия», 2011.

2. Эпштейн М.С. Практикум по программированию на языке С. - М.: «Академия», 2007.

3. Уэйт М и др. Язые Си. Руководство для начинающих. - М.: «Мир», 1988.

4. Керниган Б. Язык программировния Си. - М.: «Финансы и статистика», 1992.

5. Вирт Н. Алгоритмы и структуры данных. - М.: «Мир», 1989.

6. Березин Б.И. Начальный курс С и С++. - М.: «Диалог-Мифи», 2004.

7. Архангельский А.Я. Язык С++ в С++ BUILDER. - М., 2008.

8. Ишкова Э.А. С++ начала программирования. - М.: «Бином», 2011.

9. Коплиен Дж. Программирование на С++. - СПб., 2005.

10 Либерти Дж. Освой самостоятельно С++ за 21 день. - М., 2007.

11. Павловская Т.А. С/С++. Структурное программирование. - СПб.: «Питер», 2010.

12. Подбельский В.В. Программирование на языке Си. – М., 2000.

13. Полубенцева М. С/С++ процедурное программирование. - СПб., 2008.

14. Культин Н. С/С++ в задачах и примервх.-СПб.: «БХВ-Петербург» , 2011.

Приложение А

Образец титульного листа отчета по РГР

Некоммерческое акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Факультет «Информационные технологии»

Кафедра «Информационные системы»

ОТЧЕТ

по расчетно-графической работе №1

по дисциплине «Алгоритмы, структуры данных и программирование»

тема: «Графическая и программная реализация алгоритмов обработки простых структур данных»

вариант № 1

Выполнил ст.гр. БИС-13-2

Петров И.И.

Проверил к.т.н., доцент

_______________Ни А.Г.

“______”__________2013

Алматы 2013

Приложение Б

Образец содержания

Содержание

Введение

1 Теоретическая часть

2 Проектная часть

2.1Содержательная постановка задачи

2.2 Блок-схема алгоритма решения задачи

2.3 Описание входных данных

2.4 Описание пользовательского интерфейса

3 Прикладная часть

3.1 Листинг программы

3.2 Результат решения задачи

3.3 Результат тестирования

Заключение

Список использованных источников

Приложение В

Образец схемы пользовательского интерфейса

На рисунке В.1 приведена схема пользовательского интерфейса

Расчетно-графическая работа №2

вариант № 3

Введите 1, чтобы сместить вправо, 2, чтобы вниз

Ввод ->

Введите число смещения

Ввод ->

Введите 1 для выбора Задания А, 2 для Задания Б

Ввод - >

Начальный массив

Результат:

Рисунок В.1 – Схема пользовательского интерфейса

Приложение Г

Образец результата решения задачи

На рисунках Г.1 и Г.2приведены результаты решения задачи

Рисунок Г.1 – Результат решения по первому методу

Рисунок Г.2 - Результат решения вторым способом

Сводный план 2013г. поз.195