Некоторые приёмы программирования
Наиболее часто используемые приёмы программирования, применяемые студентами на практических занятиях, рассматриваются на примерах обработки числового массива A с количеством элементов N. Ниже представлены фрагменты программ на языке Pascal для каждого из предложенных приемов.
Вычисление суммы и произведения элементов массива:
………
S:=0; / / сумма
P:=1; / / произведение
FOR I:=1 TO N DO
BEGIN
S:= S+A[I];
P:= P*A[I];
END;
……..
Нахождение максимального (минимального) элемента массива (на примере нахождения максимального элемента):
…………
IMAX:=1;
FOR I:=2 TO N DO
IF A[I]>A[IMAX]
THEN
IMAX:=I;
…………
Здесь IMAX – номер максимального элемента;
A[IMAX] – максимальный элемент.
Удаление заданного (К-го) элемента массива:
………..
FOR I:=K TO N-1 DO
A[I]:=A[I+1];
N:=N-1;
………..
Вставка нового элемента (M) на заданное (К-е) место в массив:
…………
N:=N+1;
FOR I:=K+1 TO N DO
A[I]:=A[I-1];
A[K]:=M;
………..
Сортировка массива
1. Метод обмена («метод пузырька»):
Суть данного метода заключается в сравнении соседних элементов массива, начиная с первой и до последней пары. Если предыдущий элемент пары больше последующего (при сортировке по возрастанию), то соседи меняются местами. Для полной сортировки необходимо сделать N-1 таких «проходов» по массиву.
..............
FOR J:= 1 TO N-1 DO
FOR I:= 1 TO N-1 DO
IF A[I] > A[I+1]
THEN
BEGIN
BUF:= A[I];
A[I]:= A[I+1];
A[I+1]:= BUF;
END;
……….
Здесь BUF – буферная переменная для перестановки;
Метод обмена можно ускорить двумя способами:
а) уменьшать на каждом проходе количество сравниваемых пар:
..............
FOR J:= 1 TO N-1 DO // или FOR J:=N-1 DOWNTO 1 DO
FOR I:= 1 TO N-J DO // FOR I:=1 TO J DO
IF A[I] > A[I+1]
THEN
BEGIN
BUF:= A[I];
A[I]:= A[I+1];
A[I+1]:= BUF;
END;
……….
б) прекращать сортировку при окончании перестановок:
……….…
K:=N;
REPEAT
PORYADOK:=TRUE;
K:= K-1;
FOR I:= 1 TO K DO
IF A[I] > A[I+1]
THEN
BEGIN
BUF:= A[I];
A[I]:= A[I+1];
A[I+1]:= BUF;
PORYADOK:=FALSE;
END;
UNTIL PORYADOK;
…………
2.Метод выбора:
Суть метода выбора: при сортировке по возрастанию находится минимальный элемент в диапазоне от первого до последнего и меняется местами с первым. Далее находится минимальный элемент от второго до последнего и меняется со вторым и т.д.
………..
FOR I:= 1 TO N-1 DO
BEGIN
MIN:= A[I];
IMIN:=I;
FOR J:= I+1 TO N DO
IF A[J] < MIN
THEN
BEGIN
MIN:= A[J];
IMIN:= J;
END;
A[IMIN]:= A[I];
A[I]:= MIN;
END;
…………
3.Метод вставки:
Считается, что массив разделён на две части: отсортированную (в начале массива) и неотсортированную (в остальной части массива). В самом начале отсортированная часть состоит из первого элемента. Первый элемент из неотсортированной части (его номер – I) вставляется в отсортированную часть без изменения порядка (в позицию J):
……..
FOR I:= 2 TO N DO
BEGIN
BUF:= A[I];
J:= 1;
WHILE BUF > A[J] DO
J:= J+1;
FOR K:= I DOWNTO J+1 DO
A[K]:= A[K-1];
A[J]:=BUF;
END;
………
Поиск в массиве
1.Метод перебора:
Просматриваются элементы массива, начиная с первого, и сравниваются с искомым значением до тех пор, пока не произойдёт совпадение или не будет просмотрен весь массив.
……..
I:= 0;
NAIDEN:= FALSE;
REPEAT
I:= I+1;
IF A[I] = ISKOMOE
THEN
NAIDEN:=TRUE;
UNTIL NAIDEN OR (I=N);
IF NAIDEN
THEN
WRITELN(‘Элемент найден, его номер - ‘,I)
ELSE
WRITELN(‘Элемент не найден’);
…………
2.Метод бинарного поиска:
Метод бинарного поиска (метод деления пополам) используется только для упорядоченных массивов. Суть его заключается в том, что находится центральный (серединный) элемент массива и сравнивается с искомым. Если они равны, то поиск прекращается. Если они не равны, то, если искомый элемент больше центрального (при сортировке по возрастанию), из рассмотрения исключается половина массива от первого до центрального элемента включительно. Если же искомый элемент меньше центрального, то исключается часть массива, начиная от центрального до последнего элемента. В остальной части находится центральный элемент и сравнивается с искомым и т.д. до тех пор, как произойдёт совпадение или начало области поиска станет больше её конца.
………
NAIDEN:= FALSE;
NA:= 1; // номер первого элемента области поиска
KO:= N; // номер последнего элемента области поиска
REPEAT
SR:=(KO-NA) DIV 2+NA;
IF A[SR] = ISKOMOE
THEN
NAIDEN:=TRUE
ELSE
IF ISKOMOE > A[SR]
THEN
NA:= SR+1
ELSE
KO:= SR-1;
UNTIL NAIDEN OR (NA>KO);
IF NAIDEN
THEN
WRITELN(‘Элемент найден, его номер - ‘,SR)
ELSE
WRITELN(‘Элемент не найден’);
Вопросы для самопроверки
1. Что такое информация?
2. Каковы задачи информатики?
3. Что такое информационные технологии?
4. Сколько было информационных революций? Какова их суть?
5. Что такое информационный кризис и информатизация общества?
6. Чем отличается информация от данных?
7. Какие существуют формы представления информации?
8. Какие бывают системы счисления?
9. Как перевести числа из десятичной в двоичную систему счисления?
10. Сколько этапов развития вычислительной техники?
11. Что такое ЭВМ (компьютер)?
12. Какие существуют типы классификации ЭВМ?
13. Что входит в состав ЭВМ?
14. Какие существуют типы устройств ввода ЭВМ?
15. Какие существуют типы устройств вывода ЭВМ?
16. Какое назначение у основной памяти ЭВМ?
17. Какие существуют типы внешних запоминающих устройства ЭВМ?
18. Что входит в состав центральных устройств ЭВМ?
19. Как обрабатывается машинная команда центральными устройствами?
20. Как взаимодействуют центральные и внешние устройства ЭВМ?
21. Какие существуют типы интерфейса?
22. Что такое шина? Каковы её основные характеристики и типы?
23. Что собой представляет обобщенная структурная схема персонального компьютера?
24. Что такое программное обеспечение ЭВМ? Каковы его основные типы и состав?
25. Что такое операционная система? Каковы её основные функции и виды?
26. Какие существуют типы диалога пользователя с компьютером?
27. Что такое система программирования? Каково её назначение и состав?
28. Каковы основные этапы разработки программных комплексов?
29. В чем заключаются основы структурного программирования?
30. Какие существуют базовые управляющие конструкции?
31. В чем суть «восходящего» и «нисходящего» способов проектирования программ?
32. Что такое алгоритм и схема алгоритма?
33. В чем отличие тестирования и отладки программ?
34. Какие существуют типы ошибок в программах?
35. Какие существуют методы получения дополнительной информации о процессе выполнения программы?
36. Какие существуют типы вычислительных комплексов? Для чего они предназначены?
37. Какие известны типы компьютерных сетей? Из чего они состоят? Каковы их основные характеристики?
38. Какие известны типы топологии компьютерных сетей?
39. Какова структура сети Интернет?
40. Что такое протокол сети?
41. Какие типы адресов компьютера существуют в сети Интернет?
42. Что такое унифицированный указатель ресурса?
43. Какие существуют основные службы сети Интернет?
44. Что такое базы данных, и каково их назначение?
45. Каковы основные требования к базам данных?
46. Что такое предметная область и её объект?
47. Какие типы связей могут быть между объектами предметной области?
48. Что такое отношение и реляционная база данных?
49. В чем суть нормализации отношений?
50. Что такое инфологическая модель предметной области?
51. Какова схема взаимодействия пользователя с базой данных?
52. Что такое система управления базами данных?
53. Как можно оптимизировать сортировку массива методом обмена («пузырька»)?
54. В чём суть сортировки массива методом выбора?
55. В чём суть сортировки массива методом вставки?
56. В чём суть поиска в массиве методом перебора?
57. В чём суть и особенности метода бинарного поиска?
Заключение
Основная задача информатики заключается в определении общих закономерностей процессов обработки информации: создания, передачи, хранения и использования в различных сферах человеческой деятельности. Прикладные задачи связаны с разработкой методов, необходимых для реализации информационных процессов с использованием технических средств.
После освоения дисциплины «Информатика», основу которой наряду с лекциями составляют и практические занятия, студент должен приобрести определенные знания, умения и владения.
Студент должен знать:
§ методы представления информации в ЭВМ и выполнения арифметических и логических операций над двоичными числами;
§ принципы работы технических и программных средств в информационных системах;
§ типовые алгоритмы решения задач;
§ язык программирования;
§ среду программирования.
Студент должен уметь:
§ разрабатывать алгоритмы и кодировать их на языке программирования;
§ проводить оценку функциональных возможностей компьютеров;
§ использовать современные информационные технологии и инструментальные средства для решения различных задач.
Студент должен иметь навыки:
§ самостоятельной работы с учебной и справочной литературой;
§ использования программных комплексов и прикладных программ вычисления на компьютере;
§ разработки алгоритмов и кодирования приложений для решения профессиональных задач;
§ тестирования и отладки приложений;
§ представления результатов в удобном для пользователя виде, создания диалоговых и графических приложений.
Список литературы
- Парфилова Н. И., Пруцков А. В., Пылькин А. Н., Трусов Б. Г. Информатика и программирование. Основы информатики: Учебник для студ. учреждений высш. проф. образования / Под ред. Б.Г. Трусова – М.: Издательский центр «Академия», 2012. – 61 с.
- Исаев А.Л., Чеповский А.М. Введение в теорию баз данных: Учебно-методическое пособие.- М.: МГТУ. – 2000.
- Бройдо В.Л., Ильина О.П. Вычислительные системы, сети и телекоммуникации. – 4-е изд. – СПб.: Питер, 2011. – 560 с.
- Информатика. Общий курс: учеб. / А.Н. Гуда, М.А. Бутакова, Н.М. Нечитайло, А.В. Чернов; под ред. академика РАН В.И. Колосникова. – 4-е изд. – М.: Издательско-торговая корпорация «Дашков и К»; Ростов н/Д: Наука-Спектр, 2011. – 400 с.
- Информатика: учеб. / Б.В. Соболь, А.Б. Галин, Ю.В. Панов и др. – 3-е изд., доп. и перераб. – Ростов н/Д: Феникс, 2007. – 446 с.
- Информатика: учеб. пособие / Н.И. Иопа; Рязан. гос. радиотехн. акад. – Рязань, 2005. – 216 с.
- Максимов Н.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем: учеб. – 3-е изд., перераб и доп. – М.: Форум, 2010. – 512 с.
- Мельников В.П. Информационные технологии: учеб. для студ. вузов. – М.: Издательский центр «Академия», 2008. – 432 с.
- Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: учеб. пособие для студ. пед. вузов / под ред. Е.К. Хеннера. – 3-е изд., перераб. и доп. – М.: Издательский центр «Академия», 2004. – 848 с.
- Новые информационные технологии. учеб. пособие / под ред. проф. В.П. Дьяконова. – М.: СОЛОН-Пресс, 2005. – 640 с.
- Острейковский В.А. Информатика: учеб. для вузов. – 5-е изд., стер. – М.: Высш. шк., 2009. – 511 с.
Дата добавления: 2018-09-24; просмотров: 397;