Саровский государственный физико-технический институт

Факультет информационных технологий и электроники

Кафедра вычислительной и информационной техники

Касаткин С.С., Раткевич И.С., Травова Н.Н.

Лабораторный практикум

по курсу “Основы алгоритмизации” в среде Microsoft Visual Studio 2005

г. Саров

2008 г.

Саровский государственный физико-технический институт

Факультет информационных технологий и электроники

Кафедра вычислительной и информационной техники

Касаткин С.С.,Раткевич И.С., Травова Н.Н.

Лабораторный практикум

по курсу “Основы алгоритмизации” в среде Microsoft Visual Studio 2005

Утверждено:

на заседании кафедры ВИТ

Научно методическим Советом СарФТИ

г. Саров

2008 г.

УДК 681.3 Т 65

Одобрено Научно-методическим советом Саровского государственного физико-технического института

Т 65 Касаткин Сергей Сергеевич, Раткевич Ирина Сергеевна, Травова Надежда Николаевна

Лабораторный практикум по курсу “Основы алгоритмизации” в среде Microsoft Visual Studio 2005

Данное пособие предназначено для студентов, изучающих курс “Основы алго­рит­­мизации” и выполняющих практические задания, составляя программы, на­писанные на языке С++. Среда программирования, на которую ориентирован практикум – Microsoft Visual Studio 2005.

Практикум содержит множество примеров программ, решающих клас­си­ческие учебные задачи и иллюстрирующих основные приемы программирова­ния на языке C++, и задания для самостоятельного выполнения. Программы сопровождаются не­об­ходи­мы­ми пояснениями, однако предпо­ла­га­ет­ся, что студенты параллельно слушают курс лекций или изучают самостоятельно по учебнику основы программирования на языке C++.

Рецензент: к.ф.-м.н. доцент Холушкин В.С.

Консультант Лебедев Петр Андреевич

Содержание

Типы данных С++ 7

Лабораторная работа №1 10

Тема: “Программы, использующие команды ветвления. Отладка программы“ 10

Отладка программы 10

Часть 1 11

Ветвление в программе с помощью вложенных конструкций if-else 11

Задание 11

Пример 1 14

Пример 2 15

Организация повторения программы 16

Выполнение программы в пошаговом режиме 17

Задание для самостоятельного выполнения 17

Часть 2 18

Ветвление в программе с помощью оператора switch 18

Задание для самостоятельного выполнения 19

Лабораторная работа №2 20

Тема: “Программы, использующие команды повторения (циклы). Рекур­рент­ные соотношения“ 20

Часть 1 20

Программы, работающие с натуральными числами 20

1. Программа, которая находит наибольший общий делитель двух натуральных чисел m и n 20

2. Программа, которая проверяет, является ли число простым 21

3. Программа, которая проверяет, является ли число палиндромом 22

Часть 2 23

Программы, использующие рекуррентные соотношения 23

4. Программа, которая находит числа Фибоначчи в заданном диапазоне. 23

5. Программа, которая находит значение квадратного корня из за­данного числа, используя рекуррентное соотношение: 24

6. Программа, которая вычисляет сумму ряда с заданной точностью. 25

7. Пример – программа, которая вычисляет сумму ряда для заданного количества слагаемых. 27

Задания для самостоятельного выполнения 27

Лабораторная работа № 3 30

Тема: “Программы, использующие вспомогательные функции”. 30

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

2. Программа, которая находит заданное количество чисел, содержащих цифру 3 31

3. Программа, которая находит на заданном отрезке натуральные числа, которые можно представить в виде суммы квадратов двух натуральных чисел. 32

4. Программа, которая находит первое автоморфное число справа от заданного. 34

5. Программа находит точки пересечения линий y= ax+b и y = c/x +d 35

6. Программа для вычисления биноминальных коэффициентов 37

Задания для самостоятельного выполнения 38

Лабораторная работа № 4 41

Тема: “Программы, использующие строки символов ”. 41

1. Программа, которая считывает строку символов и сортирует ее по возрастанию кодов символов 43

2. Программа перевода числа из десятичной системы счисления в двоичную 44

3. Программа перевода числа из двоичной системы в десятичную 46

4. Программа перевода числа из 16-ой системы счисления в 2-ую. 47

5. Программа перевода числа из 2-ой системы счисления в 16-ую. 48

6. Программа, которая выводит на экран треугольник Паскаля (треугольник биноминальных коэффициентов) 50

Задания для самостоятельного выполнения 52

Лабораторная работа № 5 55

Тема: “Программы, использующие файлы ”. 55

1. Программа, которая считывает имя файла, открывает его и подсчитывает количество скобок каждого вида, содержащихся в файле. 55

2. Программа, инвертирующая файл (переставляющая символы в обратном порядке) 56

3. Программа выводит на экран n-ую строку файла 58

4. Программа, которая переписывает текст из одного файла в другой, удаляя лиш­ние пробелы между словами и делая ширину текста максимум 70 символов 59

5. Программа, которая считывает текст файла и создает новый файл, заменив во всем тексте заданное слово на новое (не изменяя деление на строки и коли­чес­т­во пробелов между словами) 61

6. Программа, которая считывает данные для структуры Man из файла. 62

7. Программа создающая новый текстовый файл из двух данных, в котором 1-я строка –строка из первого файла, 2-я строка – строка из 2-го файла, 3-я строка – содержит общие символы первых 2-х строк. 65

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

Задания для самостоятельного выполнения 70

Лабораторная работа № 6 73

Тема: “Программы, использующие массивы ”. 73

1. Программа заполняет массив A(50) случайными целыми числами из диапазона [-20, 30] и упорядочивает его по возрастанию. Исходный и упорядоченный массивы выводятся на экран дисплея. 73

2. Программа, которая по заданным корням многочлена степени n восста­нав­ливает все коэффициенты многочлена. 74

3. Программа считывает линейный массив из файла, выводит его на экран, и подсчитывает количество элементов массива, находит min и max элементы и их ин­дексы. 76

4. Программа заполняет массив A[5][5] случайными целыми числами из диапазона [-3, 3] и находит произведение элементов, стоящих на побочной диагонали. 78

5. Программа считывает матрицу из файла, выводит ee на экран, сортирует элементы в каждом столбце и отсортированную матрицу записывает в файл. 79

6. Программа, сортирующая файл по длине строки методом быстрой сортиров­ки. 81

Задания для самостоятельного выполнения 84

Лабораторная работа № 7 87

Тема: “Программы, использующие динамические структуры”. 87

1. Программа, которая создает очередь символов. 87

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

3. Программа, которая работает со стеком. 90

4. Программа, которая работает с деревом. 91

Задания для самостоятельного выполнения 93

Типы данных С++

Концепция типа данных

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

Тип данных определяет:

• внутреннее представление данных в памяти компьютера;

• множество значений, которые могут принимать величины этого типа;

• операции и функции, которые можно применять к величинам этого типа.

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

Все типы языка С++ можно разделить основные и составные. В языке С++ определенно шесть основных типов данных для представления целых (int, long), вещественных (float, double), символьных (char, wchar_t) и логических величин (bool). На основе этих типов программист может вводить описание составных типов. К ним относятся массивы, перечисления, функции, структуры, ссылки, указатели, объединения и классы. Существуют также четыре спецификатора типов: signed - знаковый, unsigned – без знаковый, short - короткий, long - длинный.

Ниже приведена таблица основных типов данных (Fundamental Types – по спецификации Microsoft).

Имя типа	Размер в байтах	Другое имя	Диапазон значений
int	4	signed	–2,147,483,648 ; 2,147,483,647
unsigned int	4	unsigned	0 ; 4,294,967,295
__int8	1	char	–128 ; 127
unsigned __int8	1	unsigned char	0 ; 255
__int16	2	short, short int, signed short int	–32,768; 32,767
unsigned __int16	2	unsigned short, unsigned short int	0 ; 65,535
__int32	4	signed, signed int, int	–2,147,483,648 ; 2,147,483,647
unsigned __int32	4	unsigned, unsigned int	0 ; 4,294,967,295
__int64	8	long long, signed long long	–9,223,372,036,854,775,808 ; 9,223,372,036,854,775,807
unsigned __int64	8	unsigned long long	0 ; 18,446,744,073,709,551,615
bool	1	нет	false или true
char	1	нет	–128 ; 127 по умолчанию 0 to 255 при компиляции с ключём /J
signed char	1	нет	–128 ; 127
unsigned char	1	нет	0 ; 255
short	2	short int, signed short int	–32,768 ; 32,767
unsigned short	2	unsigned short int	0 ; 65,535
long	4	long int, signed long int	–2,147,483,648 ; 2,147,483,647
unsigned long	4	unsigned long int	0 ; 4,294,967,295
long long	8	нет (но эквивалентно __int64)	–9,223,372,036,854,775,808 ; 9,223,372,036,854,775,807
unsigned long long	8	нет (но эквивалентно unsigned __int64)	0 ; 18,446,744,073,709,551,615
float	4	нет	3.4E +/- 38 (7 знаков)
double	8	нет	1.7E +/- 308 (15 знаков)
long double	также как и double	нет	также как и double
wchar_t	2	__wchar_t	0 ; 65,535

Лабораторная работа №1 Тема: “Программы, использующие команды ветвления. Отладка программы“ Отладка программы

Отладку программы выполняют для поиска логических ошибок в программе.

Перед отладкой необходимо откомпилировать программу (F7).

Отладка осуществляется с помощью пошагового выполнения программы и просмотра текущих значений переменных. Для просмотра текущего значения переменной нужно поставить курсор на строку, следующую за строкой с интересующей нас переменной, и поставить точку останова программы <F9>. Далее нажать кнопку <F5> для выполнения программы до данной строки. Значение переменной будет отображено на вкладке Locals в нижней части экрана. Можно также просто перетащить переменную на вкладку Watch.

Вкладки Locals и Watch

Команды отладчика:

<Ctrl> + <F10> - выполняет программу до строки, в которой находится курсор.

<F10> - выполняет один шаг программы (одну строку); подпрограммы выпол­ня­ют­ся как один шаг.

<F11> - если курсор стоит на строке, в которой выполняется вызов подпрограммы, то выполняется заход в подпрограмму.

<F5> - выполняет программу до той строки, где стоит точка останова программы, в случае если таких точек нет, программа выполняется полностью.

<F9> - поставить/снять точку останова программы

<Shift> + <F5> - останавливает отладку программы.

Эти клавиши необходимо нажимать, когда активно окно с текстом программы. Сделать нужное окно активным можно щелчком мыши в этом окне, или с помощью панели задач, или с помощью комбинации клавиш <Alt> + <Tab>.

Часть 1 Ветвление в программе с помощью вложенных конструкций if-else Задание

Запустите среду программирования Microsoft Visual Studio 2005.

Вы увидите стартовую страницу данной среды разработки. Далее создайте проект консольного приложения. Для этого выполните команду меню File|New|Project (или нажмите <Ctrl>+<Shift>+<N>). Затем выберите тип проекта (Project types:) Visual C++, если дерево доступных проектов еще не открылось нажмите левой клавишей мыши по значку «+» с лева от названия типа проекта. Теперь нажмите Win32, выберите из предоставленных шаблонов (Templates:) Win32 Console Application введите в поле Name: свою фамилию латинскими буквами. В поле Location: C:\Work (см. рисунок).

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

Перед вами появится окно мастера создания проектов (см. рисунок на следующей странице).

Нажмите кнопку Next>.

В следующем окне в поле Additional Options: установите флажок Empty project (см. рисунок).

Нажмите кнопку Finish.

В следующем окне щелкните правой клавишей мыши по папке Source Files на вкладке Solution Explorer, выберите пункт выпадающего меню Add|New Item…

Перед вами появится окно мастера Add New Item. В появившемся окне в разделе Categories: (находится слева) выберите Code (см. рисунок). Затем в разделе Templates: выберите C++ File (.cpp) и в поле Name введите имя файла: свою фамилию латинскими буквами.

Затем нажмите кнопку Add.

Набирая далее текст программы, периодически нажимайте <Ctrl>+<S>, при этом выполняет­ся команда Save и сохраняется текущее состояние программы. Делать это необ­хо­ди­мо во избежание потери результатов своей работы.