Учебно-методический комплекс учебной дисциплины сдм. 02 «программирование» подготовки магистров по направлению 050200 «Физико-математическое образование» магистерская программа «Информатика в образовании»

Вид материала

Учебно-методический комплекс

Содержание Определение массива в Си++ Сортировка массивов Поиск в отсортированном массиве. Одномерные массивы и указатели. Многомерные массивы и указатели. Динамические массивы. Правила работы со ссылками Строковая переменная Функции работы со строками из библиотеки обработки строк Практическая работа №2 Практическая работа №3

Подобный материал:

• Учебно-методический комплекс учебной дисциплины ен. В. 01 по выбору (информатика) «Программирование, 553.96kb.
• Учебно- методический комплекс учебной дисциплины дпп. 04"Теоретические основы информатики", 530.12kb.
• Программа вступительных испытаний для лиц, поступающих в магистратуру на направление, 220.49kb.
• Программа вступительного экзамена в магистратуру по направлению 050200 «Физико-математическое, 500.22kb.
• Магистерская программа 540204м информатика в образовании Разработчики программы, 115.3kb.
• Магистерская программа «Языковое образование (русский язык)» умк принят в фонд учебно-методического, 541.81kb.
• Рабочая программа учебной дисциплины сдм. 01. 02 Виды обеспечений сапр для подготовки, 191.35kb.
• Учебно-методический комплекс учебной дисциплины сдм. 02 Валютная политика государства, 3226.07kb.
• Учебно-методический комплекс учебной дисциплины сдм. 03 Анализ финансовой отчетности, 3496.13kb.
• Учебно-методический комплекс по специальностям 050202. 65 и 050200. 62 «Информатика», 457.74kb.

Лекция №2. Массивы и указатели

Массив – это упорядоченная последовательность переменных одного типа. Каждому элементу массива отводится одна ячейка памяти. Элементы одного массива занимают последовательно расположенные ячейки памяти. Все элементы имеют одно имя – имя массива и отличаются индексами – порядковыми номерами в массиве.

Количество элементов в массиве называется его размером. Чтобы отвести в памяти нужное количество ячеек для размещения массива, надо заранее знать его размер. Резервирование памяти для массива выполняется на этапе компиляции программы.

Определение массива в Си++

int a[100]; //массив из 100 элементов целого типа

Операция sizeof(a) даст результат 400, т. е.100 элементов по 4 байта.

Элементы массива всегда нумеруются с 0, (т.е. 0 1 2 ….)

Массивы бывают одномерные (mass_1[n]) и многомерные (mass_2[m][n]), где mass_1 и mass_2 – имена массива, а m и n – номера элементов в массиве (индексы):

a[0] – индекс задается как константа,

a[55] – индекс задается как константа,

a[I] – индекс задается как переменная,

a[2*I] – индекс задается как выражение.

Элементы массива можно задавать при его определении:

int a[10]={1,2,3,4,5,6,7,8,9,10} ;

Сортировка массивов – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.

Сортировки массивов подразделяются по быстродействию. Существуют простые методы сортировок, которые требуют n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы.

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

Простые методы подразделяются на три основные категории: сортировка методом простого включения, простого выделения, простого обмена;

Поиск в отсортированном массиве. В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если (n- m)-ая степень 2, если n не является степенью 2, то n
Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то если a[S]
Указатели являются специальными объектами в программах на Си++. Указатели предназначены для хранения адресов памяти.

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

Указатели делятся на две категории: указатели на объекты и указатели на функции. Размер указателя зависит от модели памяти. Можно определить указатель на указатель: int**a;

Указатель может быть константой или переменной, а также указывать на константу или переменную. Для инициализации указателя существуют следующие способы:

Присваивание адреса существующего объекта:

1. с помощью операции получения адреса;
   
2. с помощью проинициализированного указателя;
   
3. адрес присваивается в явном виде;
   
4. присваивание пустого значения.
   

Динамические переменные

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

Для создания динамических переменных используют операцию new, определенную в СИ++: указатель = new имя_типа[инициализатор];

где инициализатор – выражение в круглых скобках.

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

int*x=new int(5);

Для удаления динамических переменных используется операция delete, определенная в СИ++: delete указатель;

где указатель содержит адрес участка памяти, ранее выделенный с помощью операции new. delete x;

Одномерные массивы и указатели. При определении массива ему выделяется память. После этого имя массива воспринимается как константный указатель того типа, к которому относятся элементы массива. Исключением является использование операции sizeof (имя_массива) и операции &имя_массива. Имя массива является указателем-константой, значением которой служит адрес первого элемента массива, следовательно, к нему применимы все правила адресной арифметики, связанной с указателями. Запись имя_массива[индекс] это выражение с двумя операндами: имя массива и индекс. Имя_массива - это указатель константа, а индекс определяет смещение от начала массива. Используя указатели, обращение по индексу можно записать следующим образом: *(имя_массива+индекс).

Многомерные массивы и указатели. Многомерный массив это массив, элементами которого служат массивы. Например, массив с описанием int a[4][5] – это массив из 4 указателей типа int*, которые содержат адреса одномерных массивов из 5 целых элементов. Инициализация многомерных массивов выполняется аналогично одномерным массивам. Доступ к элементам многомерных массивов возможен и с помощью индексированных переменных и с помощью указателей.

Динамические массивы. Операция new при использовании с массивами имеет следующий формат: new тип_массива

Такая операция выделяет для размещения массива участок динамической памяти соответствующего размера, но не позволяет инициализировать элементы массива. Операция new возвращает указатель, значением которого служит адрес первого элемента массива. При выделении динамической памяти размеры массива должны быть полностью определены.

Указатель на динамический массив затем используется при освобождении памяти с помощью операции delete.

Вопросы.

1. Что такое массив?
   
2. Виды массивов и их инициализация.
   
3. Что такое сортировка? Какие методы сортировок существуют?
   
4. Назовите три основные категории сортировок.
   
5. Что такое указатель и для чего он предназначен?
   
6. Назовите категории указателей.
   
7. Что такое динамические переменные?
   
8. Для чего используют операции new и delete?
   

Лекция №3. Ссылки и строки

Ссылки – это синоним имени объекта, указанного при инициализации ссылки. Формат объявления ссылки: тип & имя =имя_объекта;

Примеры:

int x; // определение переменной

int & sx=x; // определение ссылки на переменную х

const char & CR=’\n’; //определение ссылки на константу

Правила работы со ссылками:

1. Переменная ссылка должна явно инициализироваться при ее описании, если она не является параметром функции, не описана как extern или не ссылается на поле класса.
   
2. После инициализации ссылки не может быть присвоено другое значение.
   
3. Не существует указателей на ссылки, массивов ссылок и ссылок на ссылки.
   
4. Операция над ссылкой приводит к изменению величины на которую она ссылается.
   

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

Строки – это последовательность символов, заключенная в двойные кавычки: "это строка". Строка может включать буквы, цифры и разнообразные специальные символы, такие как +, – , *, /, $ и другие.

Одним из способов представления строк является использование массива базового типа char. Например, строку "Hello" удобно представить как массив из шести индексированных переменных: пяти букв слова "Hello" и одного нулевого символа '\0', служащего маркером конца строки. Символ '\0' называется нуль-символом или нулевым символом, а когда он используется в качестве маркера конца строки – нуль-терминатором. При использовании таких маркеров программа может считывать массивы посимвольно и знать, когда следует остановиться.

Строковая переменная – это обычный массив символов, используемый особым образом. Она объявляется так же, как любой массив символов.

Синтаксис: char имя_массива[максимальный_размер_строки+1];

Единица прибавляется для того, чтобы вмещал нуль-символ '\0', отмечающий конец хранящейся в массиве строки. В частности, строковая переменная string вмещает строку длиной в десять или менее символов.

Например: char string[11];

Строка может быть объявлена либо как массив символов, либо как переменная типа char*. Каждое из объявлений

char color[]="синий";

сhar *colorPtr[]="синий";

присваивает переменной строке начальное значение "синий".

Первое объявление создает массив из 6 элементов color содержащий символы 'с', 'и', 'н', 'и', 'й' и '\0'.

Второе объявление создает переменную указатель *colorPtr, который указывает на строку «синий» где то в памяти.

Функции работы со строками из библиотеки обработки строк

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

Вопросы.

1. Что такое ссылка? Назовите основные правила работы со ссылками.
   
2. Что такое символ? Что такое строка?
   
3. Что такое строковая переменная?
   
4. Назовите функции обрабатывающие строки и их назначение.
   
5. Что такое нулевой символ и для чего он используется?
   

Практическая работа №1

Цель: Получение навыков в выборе и использовании операторов С++; знакомство с итерационными процессами.

Задачи:

1. Написать программу, которая сообщает, является ли введенное с клавиатуры число четным или нечетным.

2. Напишите программу, которая выводит числа от 1 до N.

3. Проверка возраста человека (подросток или нет).

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

5. Печать чисел от 1 до N с использованием инструкции for.

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

7. Бросание шестигранной игральной кости 6000 раз.

Дополнительные задачи:

1. Напишите программу, которая сообщает, делится ли введенное число без остатка на 7.

2. Напишите программу, которая печатает все числа от n1 до n2, где n1 и n2 – это два числа, введенные пользователем.

3. Напишите программу, которая выводила числа от 1 до N в обратном порядке.

4. Напишите программу, которая проверяет принадлежность числа диапазону от 0 до 100 включительно.

5. Напишите программу с использованием инструкции for, которая печатает все числа от n1 до n2, где n1 и n2 – это два числа, введенные пользователем.

6. Напишите программу с использованием инструкции for, которая выводила числа от 1 до N в обратном порядке (Подсказка: в цикле, образованном при помощи инструкции for, проинициализируйте переменную i значением n, используйте в условии i >=1 и вычитайте 1 из значения переменной i на шаге инкремента).


Практическая работа №2

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

Задачи:

Массивы:

1. Написать программу, выводящую список элементов массива.

2. (вывод постоянно случайных чисел) генерация 10 различных значений.

3. Напишите программу, которая имитирует раздачу карт из стандартной колоды, состоящей из 52 игральных карт (использование двух массивов строк: ранги и масти).

Указатели:

4. Пример программы, использующей функцию с именем double_it, которая умножает значение переменной, переданной в нее, на 2.

5. Написать программу сортировки массива по возрастанию методом выбора (использование функции swap).

6. Обнуление целочисленного массива.

Дополнительные задачи:

1. Напишите программу, инициализирующую массив, состоящий из восьми целочисленных элементов, значениями 5, 15, 25, 35, 45, 55, 65 и 75, а затем печатающую значение каждого из элементов.
   
2. Напишите программу, которая выводит пользователю подсказку для ввода каждого из семи значений, сохраняет введенные значения в массиве, а затем печатает значение каждого из элементов и их общую сумму. Для этой программы вам потребуется написать два цикла for: один для сбора данных, а второй для подсчета суммы и для вывода значений.
   
3. Напишите программу, которая генерировала 5 различных значений (используйте функцию rand_0toN1 для получения значений 0, 1, 2, 3 или 4). Затем выполните запрошенное количество попыток, в котором, по вашему мнению, каждое значение из пяти возможных будет сгенерировано один раз из пяти.
   
4. Напишите программу, которая случайным образом выбирает объект из сумки, в которой находится восемь предметов. Каждый предмет может быть красным, синим, оранжевым или зеленым, а также он может быть шаром или кубом. Предположите, что в сумке находится по одному предмету для каждой комбинации (один красный шар, один красный куб, один оранжевый шар, один оранжевый шар, и так далее). Напишите код, использующий два массива строк – один для идентификации цветов, а второй – для идентификации форм.
   

Практическая работа №3

Цель: получение навыков работы со строками.

Задачи:

1. Написать программу построения строки из более мелких строк. (Программа получает пару строк от пользователя, строит большую строку из этих меньших строк, после чего печатает результаты).

2. Написать программу, которая получает числа и печатает их квадратные корни до тех пор, пока пользователь не напечатает «0» или не нажмет клавишу «Enter» сразу после подсказки.

3. Написать программу, которая получает введенную пользователем строку и распознает новое «поле» везде, где встречает запятую.

Дополнительные задачи:

1. Написать программу, которая получает введенную пользователем строку и распознает новое «поле» везде, где встречает пробел.
   
2. Получите от пользователя три порции информации: имя собаки, ее породу и возраст. Затем напечатайте предложение, использующее эту информацию.
   

Самостоятельная работа. На самостоятельное изучение выносятся следующие темы (или вопросы):

1) Теоретические:

1. Обработка одномерных массивов.
   
2. Перебор массива по одному и по двум элементам.
   
3. Формирование псевдодинамических массивов.
   
4. Использование датчика случайных чисел для формирования массива.
   
5. Классы задач по обработке массивов.
   
6. Динамические массивы.
   
7. Строки.
   

2) Задачи:

К лекции №1

Используя оператор цикла, найти сумму элементов, указанных в конкретном варианте.

Варианты:

1. Найти сумму целых положительных чисел, кратных 3 и меньших 200.
   
2. Найти сумму ряда с точностью , общий член которого .
   
3. Найти сумму целых положительных четных чисел, меньших 100.
   
4. Найти сумму ряда с точностью , общий член которого .
   
5. Найти сумму целых положительных нечетных чисел, меньших 200.
   
6. Найти сумму ряда с точностью , общий член которого .
   
7. Найти сумму целых положительных чисел, больших 20, меньших 100 и кратных 3.
   
8. Найти сумму ряда с точностью , общий член которого .
   

К лекции №2

Варианты:

1.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Удалить элемент с номером К.
   
4. Добавить после каждого четного элемента массива элемент со значением 0.
   
5. Распечатать полученный массив.
   

2.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Удалить первый элемент равный 0.
   
4. Добавить после каждого четного элемента массива элемент со значением M[I-1]+2.
   
5. Распечатать полученный массив.
   

3.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Удалить элементы кратные 7.
   
4. Добавить после каждого нечетного элемента массива элемент со значением 0.
   
5. Распечатать полученный массив.
   

4.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Удалить все элементы с заданным значением.
   
4. Добавить перед каждым четным элементом массива элемент со значением 0.
   
5. Распечатать полученный массив.
   

5.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Удалить 5 первых элементы массива.
   
4. Добавить в конец массива 3 новых элемента.
   
5. Распечатать полученный массив.
   

6.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Удалить 5 последних элементов массива.
   
4. Добавить в начало массива 3 элемента со значением M[I+1]+2.
   
5. Распечатать полученный массив.
   

7.

1. Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
   
2. Распечатать полученный массив.
   
3. Поменять местами минимальный и максимальный элементы массива.
   
4. Удалить из массива все элементы, превышающие его среднее значение более чем на 10%.
   
5. Распечатать полученный массив.
   

8.

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

9.

1. Реализовать с использованием массива двунаправленное кольцо (просмотр возможен в обе стороны, от последнего элемента можно перейти к первому).
   
2. Распечатать полученный массив, начиная с К-ого элемента и до К-1 ( по кольцу влево).
   
3. Добавить в кольцо первый и последний элементы.
   
4. Распечатать полученный массив, начиная с К-ого элемента (и до К+1 по кольцу вправо).
   

10.

1. Реализовать с использованием массива двунаправленное кольцо (просмотр возможен в обе стороны, от последнего элемента можно перейти к первому).
   
2. Распечатать полученный массив, начиная с К-ого элемента и до К-1 ( по кольцу влево).
   
3. Добавить в кольцо после элементов с индексами кратными 5 элементы равные 0.
   
4. Распечатать полученный массив, начиная с К-ого элемента(и до К+1 по кольцу вправо).
   

К лекции №3

Варианты:

1. Проверить является ли строка палиндромом. (Палиндром – это выражение, которое читается одинакова слева направо и справа налево).
   
2. Напечатать самое длинное и самое короткое слово в этой строке.
   
3. Напечатать все слова, которые содержат по одной цифре.
   
4. Напечатать все слова, которые совпадают с ее первым словом.
   
5. Преобразовать строку таким образом, чтобы сначала в ней были напечатаны только буквы, а потом только цифры, не меняя порядка следования символов в строке.
   
6. Преобразовать строку так, чтобы все слова в ней стали идентификаторами, слова, состоящие только из цифр – удалить.
   
7. Преобразовать строку таким образом, чтобы цифры каждого слова в ней были отсортированы по убыванию.
   
8. Преобразовать строку таким образом, чтобы в ней остались только слова, содержащие буквы и цифры, остальные слова удалить.
   
9. Определить какое слово встречается в строке чаще всего.
   
10. Удалить из строки все слова, которые не являются идентификаторами.
    

Контрольные вопросы к модулю 2.

1. 
   Перечислите базовые конструкции структурного программирования и основные управляющие конструкции программы.
   
2. В каких циклах известно условие выполнение цикла? Перечислите их. Приведите примеры.
   
3. Что такое метка? Что такое ссылка?
   
4. Что такое символ?
   
5. Что такое строка? Что такое строковая переменная?
   
6. Что такое массив?
   
7. Что такое сортировка? Какие методы сортировок существуют?
   
8. Что такое указатель и для чего он предназначен? Назовите категории указателей.
   
9. Что такое динамические переменные?
   
10. Для чего используют операции new и delete?
    

Рубежный тест

1. Чем линейные вычислительные процессы отличаются от циклических?

1. тем, что они более громоздки;
   
2. тем, что они гораздо быстрее;
   
3. тем, что они выполняются по порядку следования в программе;
   
4. тем, что они выполняются только один раз.
   

2. Каковы основные свойства алгоритма?

1. завершенность, результативность, предметность, определенность;
   
2. точность, дискретность, определенность, определяемость;
   
3. всеобщность, дискретность, результативность, определенность;
   
4. программируемость, устойчивость, дискретность, массовость.
   

3. Какие операторы в С++ применяются для организации разветвляющихся вычислительных процессов?

1. go to, for, do while;
   
2. continue, go to, switch;
   
3. go to, break, continue, switch;
   
4. go to, for, break; do while, switch.
   

4. Какие операторы в С++ применяются для организации циклических вычислительных процессов?

1. go to, break, continue, switch;
   
2. go to, for, break; do while, switch;
   
3. for, while, do while;
   
4. for, go to, while, switch.
   

5. В каком случае оправдано применение оператора GOTO?

1. в случае выхода из тела цикла наружу;
   
2. в случае входа внутрь вложенных циклов;
   
3. в случае выхода из вложенных циклов;
   
4. там, где требуется перейти к другой функции.
   

6. Какие значения будут присвоены a[i] и i после выполнения выражения: ; (до выполнения операции i=2)?

1. ;
   
2. ;
   
3. ;
   
4. это зависит от модели используемого компилятора.
   

7. Как в языке С++ объявить массив целого типа из 10 элементов?

1. int a(10);
   
2. int a[10];
   
3. char b[10];
   
4. float b(10).
   

8. Как в языке С++ представляются многомерные массивы?

1. в виде двумерного массива;
   
2. в виде линейной комбинации независимых переменных;
   
3. в виде особого одномерного массива;
   
4. в виде последовательности символов в памяти.
   

9. Чем характеризуется любой одномерный массив?

1. именем массива и константами;
   
2. числом элементов массива и параметрами;
   
3. именем массива и числом элементов;
   
4. именем массива и числом параметров.
   

10. Почему в языке С++ выгодно динамическое представление массивов?

1. так как увеличивается объем полезной памяти;
   
2. так как уменьшается размер исполняемого файла;
   
3. так как остается больше места для других данных;
   
4. все приведенные ответы.