Основы алгоритмизации и программирования

Учреждение образования

«Белорусский государственный
технологический университет»

Кафедра информационных систем и технологий

Основы алгоритмизации

и программирования

Методические указания и контрольные задания

для студентов специальности 1-40 01 02-03

«Информационные системы и технологии (издательско-полиграфический комплекс)»

заочной формы обучения

Минск 2012


Аннотация

УДК | 004.4(076.5)
ББК | 22.18я73
 | О-75

Рассмотрены и рекомендованы к изданию редакционно-издательским советом университета

Составитель

Н. В. Пацей

Рецензент

кандидат технических наук, доцент кафедры автоматизации производственных процессов и электротехники БГТУ

Д. А. Гринюк

По тематическому плану изданий учебно-методической литературы университета на 2012 год. Поз. 167.

Для студентов специальности1-40 01 02-03 «Информационные системы и технологии (издательско-полиграфический комплекс)» заочной формы обучения.

Ó | УО «Белорусский государственный технологический университет», 2012


ВВЕДЕНИЕ

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

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

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

Цель курса, разработанного в соответствии с образовательными стандартами Республики Беларусь для специальности 1-40 01 02-03 «Информационные системы и технологии (издательско-полиграфический комплекс)», – дать студенту знания и практические навыки по основам теории алгоритмов и их применению, разработке, использованию и реализации различных структур данных в прикладных программах, отладке и тестированию программ.

Основные задачи курса – изучение основ алгоритмизации, освоение технологии программирования на языке С++ и подготовка студентов к объектно-ориентированному программированию.

ОФОРМЛЕНИЕ ЗАДАЧ

Задачи должны быть оформлены следующим образом. Распечатка на листах формата A4 включает: условие задачи, блок-схему ее решения (если требуется по условию), листинг программы с комментариями, результат выполнения задачи. Проекты решения задач в используемой среде разработки необходимо записать на CD или DVD и приложить к распечаткам.

УСТАНОВКА MICROSOFT VISUAL STUDIO 2010

Для разработки программ требуется интегрированная среда разработки программного обеспечения MS Visual Studio 2010, включающая в себя редактор исходного кода с поддержкой технологии IntelliSense и возможностью простейшего рефакторинга кода, встроенный отладчик и множество других компонентов, которые пока не будут использоваться.

Необходимо скачать данный продукт с официального сайта http://www.microsoft.com/ru/ru/softmicrosoft/vs2010.aspx и выполнить установку.

Возможно использование другого компилятора С/C++ (C++ Builder, GNU GCC, Code::Blocks IDE и т. д.).


I семестр

ТЕМА 1. СИСТЕМЫ СЧИСЛЕНИЯ

Изучите теоретический материал главы 1 «Системы счисления и коды чисел» [1]. Ответьте на вопросы. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое система счисления?

2. Десятичное целое 10 в 16 с/c равно …

3. Десятичное целое 10 в 8 с/c равно …

4. Десятичное целое 10 в 2 с/c равно …

5. Перевести число 5028 в 2 с/с.

6. Десятичное целое 31 в 8 с/c равно …

7. Десятичное целое 16 в 16 с/c равно …

8. Записать число 010100102 в 16 с/с.

9. Что такое прямой код? Приведите пример положительного и отрицательного числа в прямом коде.

10. Что такое дополнительный код? Приведите пример положительного и отрицательного числа в дополнительном коде.


Задачи для самостоятельного решения

1 | Выполнить перевод чисел 122(8 c/c) → ? (2 c/c) → ? (16 c/c) 110101(2 c/c) → ? (10 c/c) 65(10 c/c) → ? (2 c/c) 0.25(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 140.2(8 c/c) – 130.54(8 c/c)
2 | Выполнить перевод чисел 212(8 c/c) → ? (2 c/c) → ? (16 c/c) 110011(2 c/c) → ? (10 c/c) 322(10 c/c) → ? (2 c/c) 0.21(10 c/c) → ? (8 c/c) (получить четыре знака после точки в восьмеричном представлении) Выполнить арифметические операции 1111(2 c/c) – 101(2 c/c)
3 | Выполнить перевод чисел 25(8 c/c) → ? (2 c/c) → ? (16 c/c) 111111(2 c/c) → ? (10 c/c) 122(10 c/c) → ? (2 c/c) 0.35(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 12310.35(8 c/c) – 1230.34(8 c/c)
4 | Выполнить перевод чисел 332(8 c/c) → ? (2 c/c) → ? (16 c/c) 1011(2 c/c) → ? (10 c/c) 11111(10 c/c) → ? (2 c/c) 0.115(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 11111(2 c/c) + 11111(2 c/c)
5 | Выполнить перевод чисел 11(8 c/c) → ? (2 c/c) → ? (16 c/c) 1111(2 c/c) → ? (10 c/c) 168(10 c/c) → ? (2 c/c) 0.347(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 10.232(8 c/c) – 5.54(8 c/c)
6 | Выполнить перевод чисел 1005(8 c/c) → ? (2 c/c) → ? (16 c/c) 10101(2 c/c) → ? (10c/c) 152(10 c/c) → ? (2 c/c) 0.98(10 c/c) → ? (8 c/c) (получить четыре знака после точки в восьмеричном представлении) Выполнить арифметические операции BB3.6(16 c/c) + 3AB.E(16 c/c)
7 | Выполнить перевод чисел 45(8 c/c) → ? (2 c/c) → ? (16 c/c) 11101(2 c/c) → ? (10 c/c) 43(10 c/c) → ? (2 c/c) 0.23(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 4510.23(8 c/c) – 330.14(8 c/c)
8 | Выполнить перевод чисел 106(8 c/c) → ? (2 c/c) → ? (16 c/c) 10011001(2 c/c) → ? (10 c/c) 24(10 c/c) → ? (2 c/c) 0.11(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 33.8(16 c/c) + AAA.4(16 c/c)
9 | Выполнить перевод чисел 31(8 c/c) → ? (2 c/c) → ? (16 c/c) 1001(2 c/c) → ? (10 c/c) 76(10 c/c) → ? (2 c/c) 0.222(10 c/c) → ? (8 c/c) (получить четыре знака после точки в восьмеричном представлении) Выполнить арифметические операции 100111(2 c/c) – 10011(2 c/c)
10 | Выполнить перевод чисел 54(8 c/c) → ? (2 c/c) → ? (16 c/c) 10111011(2 c/c) → ? (10c/c) 40(10 c/c) → ? (2 c/c) 0.897(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 155.5(8 c/c) + 10.14(8 c/c)
11 | Выполнить перевод чисел 131(8 c/c) → ? (2 c/c) → ? (16 c/c) 10000001(2 c/c) → ? (10 c/c) 98(10 c/c) → ? (2 c/c) 0.48(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 10111(2 c/c) + 10011(2 c/c)
12 | Выполнить перевод чисел 11(8 c/c) → ? (2 c/c) → ? (16 c/c) 11111001(2 c/c) → ? (10 c/c) 77(10 c/c) → ? (2 c/c) 0.19(10 c/c) → ? (2 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 3B.C(16 c/c) – 21.4(16 c/c)
13 | Выполнить перевод чисел 1003(8 c/c) → ? (2 c/c) → ? (16 c/c) 1010111(2 c/c) → ? (10 c/c) 29(10 c/c) → ? (2 c/c) 0.95(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 111111(2 c/c) + 1000111(2 c/c)
14 | Выполнить перевод чисел 316(8 c/c) → ? (2 c/c) → ? (16 c/c) 11100001(2 c/c) → ? (10 c/c) 764(10 c/c) → ? (2 c/c) 0.12(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 110.2(8 c/c) + 1126630.44(8 c/c)
15 | Выполнить перевод чисел 653(8 c/c) → ? (2 c/c) → ? (16 c/c) 111001(2 c/c) → ? (10 c/c) 100(10 c/c) → ? (2 c/c) 0.33(10 c/c) → ? (8 c/c) (получить три знака после точки в восьмеричном представлении) Выполнить арифметические операции 100111(2 c/c) – 1011(2 c/c)


ТЕМА 2. ВВЕДЕНИЕ В ЯЗЫК

Изучите теоретический материал глав 2–4 [1]. Создайте решение в VS2010, выполните и получите результат. Ответьте на вопросы.

Вопросы для подготовки к тесту

1. Что такое идентификатор? Приведите пример.

2. Пусть есть два идентификатора az и AZ. Будут ли они в языке программирования С идентичными?

3. С какого символа начиняется управляющая последовательность?

4. Что такое ключевые слова? Приведите пример.

5. Что такое константа? Приведите пример.

6. Какой тип данных будет у константы 1L?

7. Когда используется ключевое слово const?

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

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

10. Укажите допустимые типы данных в языке программирования С++.

11. Как в языке программирования С обозначается комментарий?

12. Какой тип данных в языке программирования С используется для представления целых со знаком?

13. Какой тип данных в языке программирования С используется для представления целых без знака?

14. Какой тип данных в языке программирования С используется для представления символов?

15. Какой тип данных в языке программирования С используется для представления вещественных чисел?

16. Можно ли в процессе выполнения программы изменить тип переменной?

17. Для чего используется тип данных bool?

18. В чем разница между типами данных float и double?

19. Найдите ошибку.

char as;

as = "333";

20. Найдите ошибку.

unsigned char  D = 266;

21. С какой функции начинается выполнение программы в С?

22. Приведите пример общей структуры программы на C.

23. Что такое директивы препроцессора? Приведите пример.

24. Что такое пространство имен? Приведите пример.

25. В каком случае используется ключевое слово typedef?

26. Дайте определение времени жизни переменной.

27. Какую область действия имеет переменная класса auto?

28. Какую область действия имеет переменная класса register?

29. Какую область действия имеет переменная класса extern?

30. Какую область действия имеет переменная класса static?

31. Истинно ли следующее высказывание? Переменные можно распределять по декларациям произвольным образом.

32. Что означает последний оператор?

char p;  …

long ll = long(p);

33. Пусть

int i1 = 256 + 255;

char ch = i1;

int i2 = ch;

Что будет содержаться в i2?

34. Установите правильную последовательность решения задачи:

выбор метода решения поставленной задачи;

запись алгоритма, т. е. текста программы;

отладка программ, т. е. обнаружение и устранение возможных ошибок;

построение алгоритма решения поставленной задачи;

математическая или информационная формулировка задачи;

выполнение программы.

35. Установите соответствие между элементами блок-схемы и их назначением.

36. Запишите синтаксис оператора присваивания.

37. Запишите синтаксис составного оператора.

38. Определите роль символа ";".

39. Определите смысл операций "%" и "/".


ТЕМА 3. ОПЕРАТОРЫ ВВОДА-ВЫВОДА

Изучите теоретический материал глав 4–5 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Листинги решений задач можно скопировать в свой проект. Если предложенное решение непонятно, запустите его в отладчике. Сравните полученный результат с результатом в тексте пособия.

Вопросы для подготовки к тесту

1. Как определен стандартный поток ввода в библиотеке потоков?

2. Как определен стандартный поток вывода в библиотеке потоков?

3. Что такое манипуляторы? Как они используются при выводе?

4. Зачем надо подключать #include <iostream>?

5. Что делает функция printf? Приведите пример.

6. Что делает функция scanf? Приведите пример.

7. Какая функция используется для строкового ввода? Приведите пример.

8. Какая функция используется для строкового вывода? Приведите пример.

9. Какая функция используется для символьного ввода? Приведите пример.

10. Какая функция используется для символьного вывода? Приведите пример.

11. Исправьте ошибки.

int x;

float y;

scanf("%d%f", x, y);

12. Исправьте ошибки.

int x;

getchar() = x;

13. Исправьте ошибки.

char x = "hello";

putchar(x);


Примеры решения задач

Задача 3.1

Вывести на экран размеры всех базовых типов данных С в байтах.

Листинг задачи 3.1

#include "stdafx.h"

#include <iostream>

#include <locale>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

using std::cout;

using std::endl;

//определение размерности, размерность базовых типов данных

cout << " Тип объекта Его размер в байтах" << endl;

cout << " Размерность int: " << sizeof(int) << "\n";

cout << " Размерность char: " << sizeof(char) << "\n";

cout << " Размерность unsignid: " << sizeof(unsigned) << "\n";

cout << " Размерность long: " << sizeof(long) << "\n";

cout << " Размерность float: " << sizeof(float) << "\n";

cout << " Размерность double: " << sizeof(double) << "\n";

cout << "\n";

return 0;

}

Результат выполнения задачи 3.1


Задача 3.2

Выполнить ввод на консоль переменных следующих типов данных: char, int, float, unsigned int, unsigned short int, long long, double, long double, bool. Выполнить вывод введенных переменных, используя потоковый вывод с манипуляторами, форматированный вывод и символьный вывод.

Листинг задачи 3.2

#include "stdafx.h"

#include <iostream>

#include <locale>

#include <stdio.h>

#include <iomanip>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

using namespace std;

char c, probel;

probel = ' ';

int i;

float f;

unsigned int ui;

unsigned short int usi;

long long ll;

double d;

long double ld;

bool b;

cout << "Введите char: ";

cin >> c;

cout << "Введите int: ";

cin >> i;

cout << "Введите float: ";

cin >> f;

cout << "Введите unsigned int: ";

cin >> ui;

cout << "Введите unsigned short int: ";

cin >> usi;

cout << "Введите long long: ";

cin >> ll;

cout << "Введите double: ";

cin >> d;

cout << "Введите long double: ";

cin >> ld;

cout << "Введите bool: ";

cin >> b;

cout << "Число unsigned int: " << ui << endl;

cout << "Число в восьмеричной системе " << oct << ui << endl;

printf("Значение числа double равно: %f", d);

cout << "\n";;

puts("Это символьный вывод "); putchar(c);

cout << "\n";;

cout << " Тип объекта  Его размер в байтах" << endl;

cout << " Размерность  int: " << sizeof(int) << "\n";

cout << " Размерность  char: " << sizeof(char) << "\n";

cout << " Размерность  unsigned: " << sizeof(unsigned) << "\n";

cout << " Размерность  long: " << sizeof(long) << "\n";

cout << " Размерность  float: " << sizeof(float) << "\n";

cout << " Размерность  double: " << sizeof(double) << "\n";

cout << "\n";

cout << setw(35) << setfill(probel) << probel;

cout << setw(10) << setfill(c) << c << endl;

cout << setw(34) << setfill(probel) << probel;

cout << setw(12) << setfill(c) << c << endl;

cout << setw(33) << setfill(probel) << probel;

cout << setw(14) << setfill(c) << c << endl;

cout << setw(32) << setfill(probel) << probel;

cout << setw(16) << setfill(c) << c << endl;

cout << setw(31) << setfill(probel) << probel;

cout << setw(18) << setfill(c) << c << endl;

cout << setw(32) << setfill(probel) << probel;

cout << setw(16) << setfill(c) << c << endl;

cout << setw(33) << setfill(probel) << probel;

cout << setw(14) << setfill(c) << c << endl;

cout << setw(34) << setfill(probel) << probel;

cout << setw(12) << setfill(c) << c << endl;

cout << setw(35) << setfill(probel) << probel;

cout << setw(10) << setfill(c) << c << endl;

return 0;

}

Результат выполнения задачи 3.2


ТЕМА 4. ЛИНЕЙНЫЕ АЛГОРИТМЫ

Изучите теоретический материал главы 5 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое унарные операции? Приведите пример.

2. Что такое бинарные операции? Приведите пример.

3. Запишите унарную операцию инкремента в префиксной и постфиксной форме?

4. Запишите унарную операцию декремента в префиксной и постфиксной форме?

5. Выберите оператор C++, который прибавляет 1 к целой переменной х.

х = х + 1;

х += 1;

++x;

x++;

Для чего используется sizeof?

6. Пусть int x = 0 , чему будет равно !x?

7. Чему равно 31 % 5?

8. Чему равно 31 / 5?

9. Какие варианты операций сравнения вы знаете?

10. Что такое операция составного присваивания?

11. Чему равно d, если

float a, b;

int c, d;

c = 5;

a = 15.1;

b = 1.9;

d = (a + b) * c;

12. Объясните, как работает тернарная условная операция? Приведите пример.

13. Верно ли следующее утверждение: нет никаких препятствий к использованию переменных разного типа в одном арифметическом выражении?

14. Какое значение выведет на экран указанный оператор, если начальное значение переменной varl равно 2?

cout << ++varl;

cout << varl++;

15. Что такое выражение? Как оно связано с операциями?

16. Напишите оператор C++, выполняющий следующие действия: присваивание суммы х и у переменной z и увеличение значения х на 1 после этого вычисления.

17. Напишите оператор C++, выполняющий следующие действия: уменьшение переменной х на 1 и затем ее вычитание из переменной z.

18. В какой последовательности будет выполняться присваивание a = b = d;?

19. Поясните значение операции с *= с;

20. Можно ли выполнить операцию ++(a + b);? Если нет, то почему?

21. Приведите пример битовых операций?

22. Если a = 0; b = 1;, чему будет равно a & b, a | b, a && b, a || b?

23. Если a = 56(10 c/c), чему равно x = a % 10;?

24. Если a = 1, чему равно a << 1 и a >> 1?

25. Чему равны значения переменных?

int a, q = 2, s = 3, c = 8;

a = (q++, --s, c = 9, s = ++c);

26. Что такое неявное преобразование типов переменных?

27. Как выполнить явное преобразование типов переменных в С и С++? Приведите пример.

28. В каких заголовочных файлах содержатся описания математических функций?

29. Что выполняет функция pow(2.5, 3)?

30. Что возвращает функция rand?

31. Что возвращает функция fabs?

32. Что возвращает функция srand?

33. Что возвращает функция sqrt?

34. Для чего используется директива #include?

35. Для чего используется директива #define? Приведите пример.

36. Для чего используется директива #ifndef и #endif? Приведите пример.

37. Для чего используется макрос assert?


Примеры решения задач

Задача 4.1

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

если

Листинг задачи 4.1

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <cmath>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

                                 //объявление переменных

float x;

int m;

double z, y, s;

                                 //ввод переменных

cout << "Введите Х" << endl;

cin >> x;

cout << "Введите M" << endl;

cin >> m;

cout << "Введите Z" << endl;

cin >> z;

                                 //вычисление выражений

s = log((2 * x / 3) + ((pow(2.78, ((int) - x)))) / (1.05 + x));

y = (sqrt(1 + pow(x, -2))) - (cos((float)m) / sin(0.9 * m)) - 18 * z;

cout << endl;

                                 //вывод результатов

cout << "s = " << s << endl;

cout << "y = " << y << endl;

return 0;

}

Результат выполнения задачи 4.1


Задача 4.2

Дано действительное число а. Не пользуясь никакими операциями, кроме *, получить заданные значения. Составить блок-схему алгоритма. Вывести на экран результат в виде:

число а

результаты 1-й 2-й

3-й 4-й

5-й 6-й и т. д. операций

Выполнить задание, используя математические функции для возведения числа в степень, и сравнить результаты.

Для а 4 и а20 за 5 операций.

Листинг задачи 4.2

#include "stdafx.h"

#include <cmath>

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

float a;

float b, c, d, e, f;

cout << "Введите число" << endl;

cin >> a;

b = a * a;

c = b * b;

d = c * c;

e = d * d;

f = e * с;

cout << endl;

cout << "Число" << a << endl;

cout << "Результаты" << endl;

cout << "1-й = " << b << endl;

cout << "2-й = " << c << endl;

cout << "3-й = " << d << endl;

cout << "4-й = " << e << endl;

cout << "5-й = " << f << endl;

cout << "Второй вариант задачи" << endl;

cout << "Число в 4-й степени = " << pow(a, 4) << endl;

cout << "Число в 20-й степени = " << pow(a, 20) << endl;

return 0;

}

Результат выполнения задачи 4.2


Задача 4.3

«Косой» квадрат. У квадрата ABCD на плоскости известны координаты двух противоположных вершин – точек A и С. Найти координаты точек В и D.

Примечание. Расположение квадрата произвольно; его стороны не обязательно параллельны координатным осям.

Листинг задачи 4.3

#include "stdafx.h"

#include <iostream>

#include <locale>

#include <stdio.h>

using namespace std;

int main()

{

setlocale(LC_CTYPE, "Russian");

cout << "Введите координаты точек А и С" << std::endl;

float x1, x2, y1, y2, vectx, vecty, X, Y;

cout << "Введите координаты точки А: " << endl;

cin >> x1 >> y1;

cout << "Введите координаты точки C: " << endl;

cin >> x2 >> y2;

X = (x1 + x2) / 2;

Y = (y1 + y2) / 2;

vectx = x2 - x1;

vecty = y2 - y1;

cout << "Координаты двух других вершин квадрата" << endl;

printf("B ""%0.2f %0.2f\n", X - vecty / 2, Y + vectx / 2);

printf("D ""%0.2f %0.2f\n", X + vecty / 2, Y - vectx / 2);

return 0;

}

Результат выполнения задачи 4.3


Задача 4.4

Треугольник задается координатами своих вершин на плоскости A(x1, y1), B(x2, y2), C(x3, y3). Найти площадь треугольника.

Листинг задачи 4.4

#include "stdafx.h"

#include <stdio.h>

#include <math.h>

#include <locale>

inline float dist(float x1, float y1, float x2, float y2)

{

return (float) sqrt((float) pow(x2 - x1, 2) + (float) pow(y2 - y1, 2));

}

int _tmain(int argc, _TCHAR* argv[])

{

float xa, ya, xb, yb, xc, yc;

setlocale(LC_CTYPE, "Russian");

printf("Введите координаты вершин треугольника\n");

scanf("%f%f%f%f%f%f", &xa, &ya, &xb, &yb, &xc, &yc);

float a = dist(xa, ya, xb, yb),
b = dist(xa, ya, xc, yc), c = dist(xb, yb, xc,
yc);

float p = (a + b + c) / 2.0;

float s = (float) sqrt(p * (p - a) * (p  - b) * (p - c));

printf("Площадь треугольника равна - %0.5f\n", s);

return 0;

}

Результат выполнения задачи 4.4


Задачи для самостоятельного решения

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

Вариант

Формула для вычислений

Исходные данные

1

2

3

4

5

6

7

Дано действительное число а. Не пользуясь никакими операциями, кроме *, получить заданные значения. Вывести на экран результат в виде:

число а

результаты 1-й 2-й

3-й 4-й

5-й 6-й операций

Выполнить задание, используя математические функции для возведения числа в степень и сравнить результаты.

8

а3 и а10 за 4 операции

9

а5, и а13, за 5 операций

10

а2, и а5, и а17 за 6 операций

11

а4, и а12, и а28 за 6 операций

12

а21 за 6 операций

13

а15 за 5 операций

14

а64 за 6 операций

15

а13 за 5 операций

16

а5 и а19 за 6 операций

17

а21 за 6 операций

18

а3 и а10 за 4 операции

Составить программу по условию.

19

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

20

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

21

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

22

Движение без топлива. Владелец автомобиля приобрел новый карбюратор, который экономит 50% топлива, новую систему зажигания, которая экономит 30% топлива, и поршневые кольца, экономящие 20% топлива. Верно ли, что его автомобиль теперь сможет обходиться совсем без топлива? Найти фактическую экономию для произвольно заданных сэкономленных процентов.

23

Такси. В такси одновременно сели три пассажира. Когда вышел первый пассажир, на счетчике было р1 руб.; когда вышел второй – р2 руб. Сколько должен был заплатить каждый пассажир, если по окончании поездки счетчик показал р3 руб.? Плата за посадку составляет р0 руб. Тестирование: общая сумма оплаты пассажирами должна совпадать с показанием счетчика по окончании поездки. Рассмотрим крайние ситуации. По справедливости, если все три пассажира вышли одновременно, они должны заплатить по (р0 + р3) / 3 руб. Если же первый и второй пассажиры «передумали ехать», они платят по р0 / 3 руб., а оставшаяся сумма ложится на счет третьего пассажира.

24

Приближение sin(x). Функция у = sin(x) на отрезке [0, π / 2] хорошо аппроксимируется разложением y = x – 3x / 6 + 5x / 120. Для заданного значения аргумента х вычислить у по этой формуле и сравнить с точным значением, вычисленным с помощью стандартной функции sin.

25

Русские неметрические единицы длины: 1 верста = 500 саженей; 1 сажень = 3 аршина; 1 аршин = 16 вершков; 1 вершок = 44.45 мм. Длина некоторого отрезка составляет р м. Перевести ее в русскую неметрическую систему.

26

Коммерция. Коммерсант, имея стартовый капитал k руб., занялся торговлей, которая ежемесячно увеличивает капитал на р %. Через сколько лет он накопит сумму s, достаточную для покупки собственного магазина?

27

Из дюймов в метры. Длина отрезка задана в дюймах (1 дюйм = 2.54 см). Перевести значение длины в метрическую систему, т. е. выразить ее в метрах, сантиметрах и миллиметрах. Так, например, 21 дюйм = 0 м 53 см 3.4 мм.

28

Цена на молоко. Животновод в начале каждой зимы повышает отпускную цену на молоко на р %, а каждым летом – снижает на столько же процентов. Изменится ли цена на молоко, и если да, то в какую сторону и на сколько через n лет?

29

Длина высоты. Треугольник ABC задан длинами своих сторон. Найти длину высоты, опущенной из вершины А. Экстремальные тесты: сумма двух сторон равна третьей; одна из сторон равна нулю.

30

Вершина параболы. Найти координаты вершины параболы y = ax2 + bx + c.


ТЕМА 5. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ

Изучите теоретический материал главы 6 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Запишите формат условного оператора if.

2. Приведите пример вложенных конструкций if – else.

3. Запишите формат switch. Поясните его работу.

4. Истинно ли следующее высказывание? В структуре выбора switch обязательно должна быть метка default.

5. Истинно ли следующее высказывание? В структуре выбора switch в разделе default требуется оператор goto.

6. Истинно ли следующее высказывание? Выражение (х > у && а < c) истинно, если х > у или а < c.

7. Что делает выражение c = x < 0? –x : x;?

8. Чему равно r после выполнения?

int main( )

{

int t = 2, b = 7, r = 3;

if (t > b)

{

if (b < r)  r = b;

}

else r = t;

return 0;

}

9. Чему равно r после выполнения?

int main ( )

{

int t = 2, r = 9, c = 2, b = 7, a =3 ;

if (a > b)

if (b < c) t = b;

else      r = t;

return 0;

}

10. Написать численные значения переменных после окончания if.

i = 5; if (i) i++;

11. Чему равно r?

int main( )

{

int t = 2, b = 7, r = 3;

if (t > b)

{

if (b < r)  r = b;

}

else r = t;

return 0;

}

12. Чему равно r?

int main( )

{

int t = 2, r = 45, c = 2, b = 7, a = 3;

if (a > b)

if (b < c) t = b;

else       r = t;

return 0;

}


Примеры решения задач

Задача 5.1

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

Только одна из логических переменных a, b и с имеет значение true. Указанные переменные ввести с клавиатуры.

Листинг задачи 5.1

#include "stdafx.h"

#include <iostream>

#include <locale>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

std::cout << "Введите a, b и c" << std::endl;

int a, b, c;

std::cin >> a >> b >> c;

(a && !b && !c) || (!a && b && !c) || (!a && !b && c) ? std::cout << "Истина" << std::endl : std::cout << "Ложь" << std::endl;

return 0;

}

Результат выполнения задачи 5.1


Задача 5.2

Ввести с клавиатуры действительные числа x, y, z, используя функции форматированного ввода. Вычислить max(x + y + z, xyz) * min(x, y, z). Составить блок-схему решения задачи.

Листинг задачи 5.2

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])   //главная функция

{

float x, y, z, min, max;           //описание переменных

printf("Enter x: ");               //ввод 3-х чисел

scanf("%f", &x);

printf("Enter y: ");

scanf("%f", &y);

printf("Enter z: ");

scanf("%f", &z);

if ((x + y + z) < (x * y * z))     //операции сравнения

max = (x * y * z);

else

max = (x + y + z);

if (z < y)

min = z;

else

min = y;

if (x < min)

min = x;

printf("max(x + y + z, xyz) * min(x, y, z) = %f \n", min * max);

//вывод результата

}

Результат выполнения задачи 5.2


Задача 5.3

Определить, равна ли сумма двух первых цифр заданного четырехзначного числа сумме двух его последних цифр.

Листинг задачи 5.3

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

unsigned int ch, a, b, c, d;

cout << "Задайте четырехзначное число: ";

cin >> ch;

if (ch >= 1000 && ch <= 9999)

{

d = ch % 10;              //единицы

ch /= 10;

c = ch % 10;              //десятки

ch /= 10;

b = ch % 10;              //сотни

ch /= 10;

a = ch % 10;              //тысячи

if (a + b == c + d)

cout << "Сумма двух первых цифр заданного четырехзначного числа РАВНА сумме  двух его последних цифр" << endl;

else cout << "Сумма двух первых цифр заданного четырехзначного числа HE РАВНА сумме  двух его последних цифр" << endl;

}

else

cout << "Вы ввели НЕ четырёхзначное число. Попробуйте ещё раз!" << endl;

system ("Pause");

return 0;

}

Результат выполнения задачи 5.3


Задача 5.4

Выполнить задание с использованием условных операторов. Даны числа a, b, c, d. Если a <= b <= c <= d, то каждое число заменить наибольшим, если a > b > c > d, то числа – без изменений, в противном случае все числа заменить их квадратами.

Листинг задачи 5.4

#include "stdafx.h"

#include <iostream>

#include <cmath>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int a, b, c, d;

cin >> a >> b >> c >> d;

if (a <= b && b <= c && c <= d)

{

a = d;

b = d;

c = d;

}

else

if (a > b && b > c && c > d);

else

{

a = a * a;

b = b * b;

c = c * c;

d = d * d;

}

cout << a << endl << b << endl << c << endl << d << endl;

return 0;

}

Результат выполнения задачи 5.4


Задача 5.5

Определить, есть ли среди заданных целых чисел A, B, C, D хотя бы два четных.

Листинг задачи 5.5

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

int A, B, C, D;

cout << "Задайте числа A, B, C, D:" << endl;

cin >> A >> B >> C >> D;

if (A % 2 == 0 && B % 2 == 0 || A % 2 == 0 && C % 2 == 0 || A % 2 == 0 && D % 2 == 0 || B % 2 == 0 && C % 2 == 0 || B % 2 == 0 && D % 2 == 0 || C % 2 == 0 && D % 2 == 0)

cout << "Среди заданных значений ЕСТЬ хотя бы два четных числа" << endl;

else

cout << "Среди заданных значений НЕТ хотя бы двух четных" << endl;

system ("Pause");

return 0;

}

Результат выполнения задачи 5.5


Задача 5.6

Даны x, y, z – вещественные числа. Существует ли треугольник с длинами сторон x, y, z? Если существует, то ответить, является ли он разносторонним, равнобедренным или равносторонним?

Листинг задачи 5.6

#include "stdafx.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

float a, b, c;

cout << "Задайте стороны треугольника:" << endl;

cin >> a >> b >> c;

if (a > 0 || b > 0 || c > 0)

{

if (a <= b + c && b <= a + c && c <= a + b)

{

cout << "Заданные числа МОГУТ быть сторонами треугольника.";

if (a == b && b == c)

cout << "Треугольник равносторонний." << endl;

else

{

if(a == b || b == c || a == c)

cout << "Треугольник равнобедренный." << endl;

else

cout << "Треугольник разносторонний." << endl;

}

}

else

cout << "Заданные числа НЕ МОГУТ быть сторонами треугольника." << endl;

}

else

cout << "Вы ввели числа меньше нуля. Стороны треугольника не могут быть отрицательными числами. Попробуйте еще раз!";

system ("Pause");

return 0;

}

Результат выполнения задачи 5.6


Задача 5.7

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

Замечание: поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит 8: первое – номер вертикали, второе – номер горизонтали. Позиции фигур заданы натуральными числами.

Листинг задачи 5.7

#include "stdafx.h"

#include <iostream>

#include <cmath>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

int x, c, v, b, n, m, a, s;

cout << "Введите координаты короля" << endl;

cin >> x >> c;

cout << "Введите координаты ладьи № 1" << endl;

cin >> v >> b;

cout << "Введите координаты ладьи № 2" << endl;

cin >> n >> m;

cout << "Введите координаты ладьи № 3" << endl;

cin >> a >> s;

if ((x == v) || (c == b))

cout << "Король под боем ладьи № 1" << endl;

else if ((x == n) || (c == m))

cout << "Король под боем ладьи № 2" << endl;

else if ((x == a) || (c == s))

cout << "Король под боем ладьи № 3" << endl;

else

cout << "НЕ ПОД БОЕМ" << endl;

return 0;

}

Результат выполнения задачи 5.7


Задача 5.8

Голодная зима. Суточный рацион коровы составляет n кг сена, v кг силоса и w кг комбикорма. В хозяйстве, содержащем стадо из k голов, осталось s цт сена, t т силоса и f мешков комбикорма по 50 кг. Сколько еще дней хозяйство сможет кормить коров по полному рациону? Какой из кормов закончится раньше других?

Листинг задачи 5.8

#include "stdafx.h"

#include <locale>

#include <iostream>

#include <cmath>

#include <stdlib.h>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

using namespace std;

int n, v, w, k, s, t, f, ceno, cilos, kombik;

cout << "Введите суточный рацион коровы сена кг:" << endl;

cin >> n;

cout << "Введите суточный рацион коровы силоса кг:" << endl;

cin >> v;

cout << "Введите суточный рацион коровы комбикорма кг:" << endl;

cin >> w;

cout << "Введите кол-во оставшегося сена ц:" << endl;

cin >> s;

cout << "Введите кол-во оставшегося силоса т:" << endl;

cin >> t;

cout << "Введите кол-во мешков оставшегося комбикорма:" << endl;

cin >> f;

cout << "Введите кол-во коров:" << endl;

cin >> k;

ceno = (100 * s) / (k * n);

cilos = (1000 * t) / (k * v);

kombik = (50 * f) / (k * w);

if (ceno == 0 || cilos == 0 || kombik == 0)

cout << "Корма не хватит ни на один день" << endl;

else

{

if (ceno <= cilos && ceno <= kombik)

cout << "Прокормят еще " << ceno << " дней. Первым закончится сено" << endl;

if (cilos <= ceno && cilos <= kombik)

cout << "Прокормят еще " << cilos << " дней. Первым закончится силос" << endl;

if (kombik <= cilos && kombik <= ceno)

cout << "Прокормят еще " << kombik << " дней. Первым закончится комбикорм" << endl;

}

return 0;

}

Результат выполнения задачи 5.8


Задачи для самостоятельного решения

Выполнить задания, используя оператор ветвления (if/ if-else/ case). Составить блок-схему алгоритма.
1 | Дано натуральное n. Верно ли, что среди цифр трехзначного числа есть 1 или 2?
2 | Ввести с клавиатуры действительные x, y, z. Вычислить . Использовать потоковый ввод/вывод и функции форматированного ввода.
3 | Ввести с клавиатуры действительные числа x, y, z. Вычислить max(x – y, y – x, z – x), используя минимальное количество условных операторов.
4 | Ввести с клавиатуры действительные числа x, y, z, используя потоковый ввод. Вычислить max(x, y, z) × min(x, y, z).
5 | Определить, есть ли среди первых трех цифр дробной части заданного положительного вещественного числа цифра 5.
6 | Ввести с клавиатуры действительные числа x, y, z. Вычислить
7 | Ввести с клавиатуры действительные числа x, y, z. Поменять значения переменных так, чтобы x < y < z.
8 | Ввести с клавиатуры действительные числа x, y, z, используя функции форматированного ввода. Поменять значения переменных так, чтобы x >= y >= z.
9 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить max(x1, y1, x2, y2), используя минимальное количество условных операторов.
10 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить max(x1, y1, x2, y2) × min(x1, y1, x2, y2).
11 | Ввести с клавиатуры действительные числа x, y, z, используя потоковый ввод. Вычислить avrg(x, y, z) × min(x, y, z).
12 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить min(x1 + y1, x2 × y2) + max(x1, y1, x2, y2), используя минимальное количество условных операторов.
13 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить max(x1 + y1, x1 × y1, x2 + y2, x2 × y2) + min(x1, y1, x2, y2), используя минимальное количество условных операторов.
14 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить min2(x1 + y1 + x2 × y2, x1 × y1 + x2 + y2, x1 × y1 + x2 × y2) + min(x1 × y1, x2, y2), используя минимальное количество условных операторов.
15 | Кирпич. Пройдет ли кирпич со сторонами а, b и с сквозь прямоугольное отверстие со сторонами r и s? Стороны отверстия должны быть параллельны граням кирпича.
16 | Дано натуральное n. Верно ли, что среди цифр трехзначного числа есть 0 или 9?
17 | Дано четырехзначное натуральное n. Верно ли, что это число содержит все одинаковые цифры?
18 | Проверить, является ли дробь А/В правильной.
19 | Ввести с клавиатуры действительные x, y, z. Вычислить . Использовать потоковый ввод/вывод и функции форматированного ввода.
20 | Ввести с клавиатуры действительные числа x, y, z, используя потоковый ввод. Вычислить avrg(x, y, z) × min(x, y, z).
21 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить min(x1 + y1, x2 × y2) + max(x1, y1, x2, y2), используя минимальное количество условных операторов.
22 | Дано натуральное n. Верно ли, что три цифры четырехзначного числа одинаковы?
23 | Определить, есть ли среди заданных целых чисел A, B, C, D хотя бы два больше десяти и меньше ста.
24 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить max(x1 – y1, x2 – y2, x1 – y2, x2 – y1) × avrg(x1, y1, x2, y2).
25 | Планировка. Можно ли на прямоугольном участке застройки размером а на b м разместить два дома размером в плане р на q и r на s м? Дома можно располагать только параллельно сторонам участка.
26 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить max(x1 + y1 + x2 × y2, x1 × y1 + x2 + y2, x1 × y1 + x2 × y2) + max(x1, y1, x2, y2), используя минимальное количество условных операторов.
27 | Даны x, y, z – вещественные числа. Проверить, существует ли треугольник с длинами сторон x, y, z?
28 | Ввести с клавиатуры целые числа x, y, z. Вычислить max(x + y, y + z, z + x) – min(x, y, z), используя минимальное количество условных операторов.
29 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить max(x1 + y1, x1 × y1, x2 + y2, x2 × y2) + min(x1, y1, x2, y2), используя минимальное количество условных операторов.
30 | Ввести с клавиатуры действительные числа x1, y1, x2, y2. Вычислить min2(x1 + y1 + x2 × y2, x1 × y1 + x2 + y2, x1 × y1 + x2 × y2) + min(x1, y1, x2, y2), используя минимальное количество условных операторов.


ТЕМА 6. ЦИКЛИЧЕСКИЕ КОНСТРУКЦИИ И ИТЕРАЦИОННЫЕ АЛГОРИТМЫ

Изучите теоретический материал главы 7 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Записать синтаксис оператора цикла for.

2. Записать синтаксис оператора цикла while.

3. Записать синтаксис оператора цикла do - while.

4. Показать на примерах универсальность цикла for в С++.

5. Сколько раз выполнится цикл for (;  {   ...   } ?

6. Какое минимальное число раз исполняется тело цикла do - while?

7. В цикле for, тело которого состоит более чем из одного оператора, точка с запятой ставится после…

8. Истинно ли следующее утверждение? Инкрементирующее выражение цикла может декрементировать счетчик цикла.

9. Сколько раз выполнится цикл?

х = 1;

while ( х <- 10 );

10. Какой оператор надо записать в строке 2, чтобы множественный выбор работал корректно?

switch (n)

{                                                                    //1

case 1 : cout << "Число равно 1" << endl;                        //2

case 2 : cout << "Число равно 2" << endl; break;                 //3

default: cout << "Число не равно ни 1, ни 2" << endl; break;     //4

}

11. Чему равно значение последнего n, выведенного на экран?

while (n < 10)

cout << n++ << endl;

12. Что такое итерация?

13. Установите правильную последовательность выполнения оператора do {тело цикла} while (выражение).

14. Установите правильную последовательность выполнения оператора for (выражение1; выражение 2; выражение 3).

15. Перепишите фрагмент с циклом for .

int i = 0;

while (i < 10)

{

q[i] = p[i];

i++;

}

16. Перепишите с оператором switch.

if (n == 1) goto m1;

if (n == 2) goto m2;

if (n == 4) goto m3;

goto md;

m1: n = n + 2; goto mend;

m2: n = 0;     goto mend;

m3: n++;       goto mend;

md: n = -1;

mend: ...

17. Перепишите без break.

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

{

if (...a[i]...) break; ...

}

if (i == n) A

else B

18. Перепишите без goto.

m1:

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

{

...if () goto m1;

...

}

19. Что вычисляется в цикле?

for (s = 0, i = 1; i <1 00; i++)

{

cin >> x;

if (x == 0) break;

s += x;

}

20. Написать численные значения переменных после окончания цикла.

for (i = 0; i >= 0; i++);

21. Написать численные значения всех переменных после окончания цикла.

for (i = 0, d = 0; i < 10; i++, d = !d);

22. Написать численные значения всех переменных после окончания цикла.

for (n = 16, i = 0; n != 1; i++, n /= 2);


Примеры решения задач

Задача 6.1

Описание алгоритма. Очевидно, что процесс подсчета суммы членов ряда должен быть итерационным: следует повторять вычисления по одной и той же формуле при значениях k = 0, 1, 2, ... . В каждой итерации цикла необходимо выполнять вычисления по заданной формуле для текущего значения k, т. е. подсчитывать очередной член ряда. Полученное значение следует прибавлять к переменной, которая представляет сумму. Эта переменная в каждой итерации будет содержать в себе сумму всех уже обработанных членов ряда, следовательно, ее начальное значение (когда ни один член еще не обработан) должно быть 0. После вычисления суммы следует вывести ее значение. После вычисления каждого члена ряда (но до прибавления его значения к сумме) надо сравнить полученное значение с заданным пределом точности. Из-за того что значение члена ряда может быть как положительным, так и отрицательным, при сравнении необходимо использовать абсолютное значение. Если оно не превышает предела точности, следует закончить вычисления: выйти из цикла, напечатать значение суммы и завершить программу.

Алгоритм вычисления zk. Для выполнения возведения в степень можно применить библиотечную функцию pow(x, y). Но есть возможность получения этого значения более эффективным способом. В каждой следующей итерации цикла значение данного выражения вдвое больше, чем в предыдущей. Так что будет целесообразно выделить отдельную переменную для сохранения значения zk. Ее начальное значение должно быть z0 = 1, а в конце каждой итерации оно должно увеличиваться в z раз.

Алгоритм вычисления (-1)k. В этом случае также нецелесообразно применять функцию возведения в степень. Значение этого выражения будет 1 при четных значениях k и -1 – при нечетных. Так что можно выделить переменную для сохранения значения этого выражения. Ее начальное значение должно быть (-1)0 = 1, а в конце каждой итерации оно должно менять знак на противоположный.

Листинг задачи 6.1

#include "stdafx.h"

#include <stdio.h>

#include <cmath>

int _tmain(int argc, _TCHAR* argv[])

{

float S = 0, a, s, p;

int n;

for (n = 2; n < 17; n++)                 //цикл

{

s = pow((float)n, log((float)n));    //вычисление числителя

p = pow(log((float)n), (float)n);    //вычисления знаменателя

a = s / p;

S += a;                              //вычисления суммы

}

printf("S = %1.6f\n", S);                   //вывод результата на консоль

return 0;

}

Результат выполнения задачи 6.1


Задача 6.2

Сравнить cos(x), полученный расчетным путем (с заданной точностью) и с помощью функции.

Листинг задачи 6.2

#include "stdafx.h"

#include <stdio.h>

#include <cmath>

int _tmain(int argc, _TCHAR* argv[])

{

int i, j, n, F;

float x, e, s, k, d;

printf("x = "); scanf("%f", &x);      //вводим х

printf("e = "); scanf("%f", &e);      //вводим точность

i = 0;

n = 1;

s = 1;

do                                    //цикл

{

F = 1;

for (j = 1; j <= 2 * n; j++)

F = F * j;                        //считаем факториал

k = pow((float) - 1, (float)n) * pow((float)x, (float)2 * n) / F;

s = s + k;

n = n + 1;

}

while (fabs((float)k) > e);

//пока не достигнута заданная точность

d = cos(x);

printf("cos(x) = %1.12f\n", d);      //вывод результатов

printf("s = %1.12f\n", s);

return 0;

}

Результат выполнения задачи 6.2


Задача 6.3

Проверить численно первый замечательный предел, задавая x значения 1, 1/2, 1/4, 1/8,... до тех пор, пока левая часть равенства не будет отличаться от правой менее, чем на заданную погрешность е.

Листинг задачи 6.3

#include "stdafx.h"

#include <stdio.h>

#include <cmath>

#define p       1                       //левая часть

int _tmain(int argc, _TCHAR* argv[])

{

                                       //объявление переменных

double s;                          //правая часть

float n = 1, eps;

int i = 0;                         //число шагов

                                   //инициализация переменных

printf("eps = "); scanf("%f", &eps);

                                   //вычисления

do

{

s = sin(n) / n;

n = n * 1 / 2;

i++;

}

while(p – s >= eps);

                                      //вывод результатов

printf("Right part %1.20f\n", s);

printf("Number of steps %d\n", i);

return 0;

}

Результат выполнения задачи 6.3


Задача 6.4

Составить алгоритм решения ребуса РАДАР = (Р + А + Д) ^ 4 (различные буквы означают различные цифры, старшая – не 0).

Листинг задачи 6.4

#include "stdafx.h"

#include <stdio.h>

#include <locale>

#include <math.h>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

printf("Программа решения ребуса РАДАР = (Р + А + Д) ^ 4\n\n");

for (int i = 1; i < 10; i++)                //перебор значений Р

for (int j = 0; j < 10; j++)                //перебор значений А

for (int k = 0; k < 10; k++)                //перебор значений Д

{

if (i == j || j == k || i == k) continue;

if (i * 10000 + j * 1000 + k * 100 + j * 10 + i == (int) pow((double) i + j + k, 4.0))

printf ("%d%d%d%d%d = (%d + %d + %d) ^ 4\n", i, j, k, j, i, i, j, k);

}

return 0;

}

Результат выполнения задачи 6.4


Задача 6.5

Используя перебор значений, найти все числа из диапазона от n до m, которые при возведении в квадрат дают палиндром.

Листинг задачи 6.5

#include "stdafx.h"

#include <stdio.h>

#include <locale>

#include <algorithm>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

printf("Введите N и M!\n");

unsigned n, m;

scanf("%u %u", &n, &m);

if (n > m) std::swap(n, m);            //выбрать большее из чисел

bool ans = false;                      //установить флаг

for (unsigned i = n; i <= m; i++)      //цикл от n до m

{

unsigned sqr = i * i, sqr2 = 0, tmp = sqr;

while (tmp)

{

sqr2 = sqr2 * 10 + tmp % 10;

tmp /= 10;

}

if (sqr == sqr2)

{

ans = true;

printf("%u\n", i);

}

}

if (!ans) printf("Палиндромов на данном промежутке нет");

putchar('\n');

return 0;

}

Результат выполнения задачи 6.5


Задача 6.6

Записать программу табулирования на отрезке условной функции в двух вариантах (с циклами while, for). Вывод результатов на экран обеспечить в виде таблицы

а = 1.65, х[0; 3], Δх = 0.15

Листинг задачи 6.6

#include "stdafx.h"

#include <iostream>

#include <math.h>

#define pi 3.14                                //определение пи

int _tmain(int argc, _TCHAR* argv[])

{

using namespace std;

float a, x;

int N, n;

a = 1.65;

cout << "enter N" << endl;

cin >> N;

printf("|   x    |   y    |\n");

for (x = 0; x <= 3; x += 0.15)            //цикл - для всех x

{

float y = 0;

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

y = pi * (float)pow(x, 2) – 7 / (float)pow(x, 2);

else

if (x == 1.4)

y = a * (float)pow(x, 3) + 7 * (float)sqrt(x);

else

y = (float)log(x + 7 * (float)sqrt(abs(x + a)));

printf("| %5.2f | %5.2f |\n", x, y);

}

x = 0;

                                             //оператор while

cout << "______________________" << endl;

cout << "    x      |       y  " << endl;

cout << "______________________" << endl;

while (x <= 3)                           //цикл

{

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

cout << pi * pow(x, 2) – 7 / pow(x, 2) << endl;

else

if (x == 1.4)

cout << a * pow(x, 3) + 7 * sqrt(x) << endl;

else

cout << log(x + 7 * sqrt(abs(x + a))) << endl;

x += 0.15;

printf("%f", x);

cout << "     ";

cout << "|";

cout << x;

}

return 0;

}

Результат выполнения задачи 6.6


Задача 6.7

Пусть задана последовательность 1 2 3 4 5 ... 99. Вывести k-ю цифру последовательности.

Листинг задачи 6.7

#include "stdafx.h"

#include <iostream>

#include <locale>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

using namespace std;

int k, cifra;

cout << "---------------------------------------------" << endl;

cout << "Последовательность 1 2 3 4 5 ... 99" << endl;

cout << "Введите k (k – номер числа последовательности)" << endl;

cin >> k;

if (k >= 1 && k <= 9) cifra = k;

else if (k % 2 == 0) cifra = (k - (k - 10) / 2) / 10;

else cifra = (k - (k - 9) / 2) % 10;

cout << "k-я цифра последовательности " << cifra << endl;

return 0;

}

Результат выполнения задачи 6.7


Задачи для самостоятельного решения

Найти сумму ряда с точностью e = 10–4, общий член которого (при определении суммы членов ряда следует использовать рекуррентную формулу для получения следующего члена ряда, выводимую из отношения an+1/an; считать, что точность достигнута, если аn < e); n = 0, 1, 2… Составить блок-схему алгоритма.
1 |  | 2 |  |
3 |  | 4 |  |
5 |  | 6 |  |
7 |  | 8 |  |
9 |  | 10 |  |
Найти сумму 13 членов ряда, в котором (привести варианты решения этой задачи с использованием итерационных циклов for, while) член an равен
11 |  | 12 |  |
13 |  | 14 |  |
Записать программу табулирования на отрезке условной функции в двух вариантах (с циклами for, while). Вывод результатов на экран обеспечить в виде таблицы с «шапкой».
15 | а = –0.5, b = 2, t Î [0; 3], Dt = 0.15 |  | 16 | а = 1.5, x Î [0.8; 2], Dx = 0.15
17 | а = 2.8, b = –0.3, c = 4 , хÎ [1; 2], Dх = 0.05 |  | 18 | а = 1.65, х Î [0; 3], Dх = 0.15
Составить программу табулирования на отрезке с шагом 0.01 функции, имеющей вид многочлена. Вывод результатов обеспечить в виде таблицы.
19 | y = 2x9 + 3x7 + x5 + x3 – 2x + 1, х Î [0; 1] |  | 20 | z = x10 + 3.7x8 + x7 – x6 – 0.5x4 – x2, х Î [1; 1.5]
21 | y = 12x9 + 3x7 + x5 + x3 – 20x, х Î [0; 1] |  | 22 | х Î [1; 2]
Ввести натуральное n. Вычислить сумму ряда двумя способами: организовав вычисления суммы слева направо и справа налево. Вывести, сравнить и объяснить полученные результаты.
23 |  | 24 |  |
25 |  | 26 |  |
27 |  | 28 |  |
29 |  | 30 |  |


ТЕМА 7. ОДНОМЕРНЫЕ МАССИВЫ

Изучите теоретический материал главы 8 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Дайте определение массива.

2. Как располагаются элементы массива в памяти компьютера?

3. Что такое индекс элемента массива?

4. Как проинициализировать массив? Приведите пример.

5. Как определить длину массива?

6. Как сгенерировать случайное число в заданном диапазоне?

7. C какого числа начинается нумерация элементов массива?

8. Если в программе отсутствует инициализация массива, что содержат его элементы?

9. Сформируйте одномерный статический массив целых чисел.

10. Запишите цикл подсчета среднего арифметического элементов массива.

11. Запишите цикл подсчета максимального элемента массива.

12. Запишите цикл подсчета минимального элемента массива.

13. Существует ли в С++ проверка границ массивов?

14. Какой по счету будет элемент массива doubleArray [7]?

15. Определите общее количество памяти, выделяемой под массив int A [20].

16. Дополните предложение. Все элементы массива должны быть … типа.

17. Напишите выражение, которое определяет одномерный массив, именованный как doubleArray типа double, содержащий 100 элементов.

18. Объявите массив с числом элементов arraySize типа double, имеющих нулевые начальные значения.

19. Верно ли утверждение? Массив может хранить много различных типов данных.

20. Верно ли утверждение? Индексы массива обычно должны иметь тип float.

21. Верно ли утверждение? Если количество начальных значений в списке инициализации меньше, чем количество элементов массива, оставшиеся элементы автоматически получают в качестве начальных значений последние значения из списка инициализации.

22. Верно ли утверждение? Если список инициализации содержит начальных значений больше, чем элементов массива, то это – ошибка.

23. Дополните предложение. Элементы массива связаны тем, что они имеют одно и то же … .

24. Обратитесь к четвертому элементу от начала массива.

float fractions[ 10 ];

25. Выберите правильное объявление массива:

a) int temps[31];

b) int [31];

c) char name[5];

26. Что выполняет фрагмент программы?

int rmin = 0;

int rmax = 100;

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

{

m[i] = (int)(((double)rand() / (double)RAND_MAX) * (rmax - rmin) + rmin);

cout << m[i] << "\n";

}

27. По фрагменту программы определите назначение переменной s.

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

if  (A[i] > 0) s += A[i];

28. По фрагменту программы определите назначение переменной m.

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

if  (A[i] > 0)

m++;

29. По фрагменту программы определите назначение переменной s.

for (s = A[0], i = 1; i <10; i++)

if  (A[i] > s) s = A[i];

30. По фрагменту программы определите назначение переменной s.

for (s = A[0],i = 1; i < 10; i++)

if  (A[i] < s) s = A[i];

31. По фрагменту программы определите назначение переменной s.

for (s = 1, i = 0; i < 10; i++) s = s * A[i];

32. Какие действия выполняет фрагмент программы?

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

{

if  (mas[i] < 0)

{

for (int j = i; j < n; j++)

mas[j] = mas[j+1];

n--; i--;

}

}


Задача 7.1

Размерность массива – 100. Диапазон значений –50¸50. Во всех последовательностях отрицательных чисел ограничить значения тех элементов, абсолютное значение которых превышает абсолютное среднее для этой последовательности.

Замечание: 0 считается положительным числом, если в задании не оговорен другой его статус; когда речь идет о какой-то последовательности чисел, имеется в виду последовательность с длиной больше 1.

Методические указания к задаче 7.1.

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

Необходимо также вычислять среднее значение последовательности, т. е. подсчитывать количество элементов в ней. Для этого вводим переменную nn – счетчик элементов, нулевое значение которой говорит об отсутствии последовательности для обработки. В начале обработки устанавливаем nn = 0.

Далее организуем цикл со счетчиком, в котором перебираем элементы массива. Для каждого элемента в первую очередь проверяется его знак. Если он отрицательный, то это может быть первый или не первый элемент последовательности, это можно определить, проверяя значение переменной nn: если 0 – первый элемент. Для первого элемента запоминаем в переменной ib индекс начала последовательности, устанавливаем счетчик элементов nn в 1, а в переменную av записываем значение этого элемента. Для не первого элемента увеличиваем счетчик на 1, а значение элемента суммируем со значением переменной av. Таким образом, переменная av играет роль накопителя суммы элементов последовательности.

Если же очередной элемент последовательности положительный, то возникает вопрос – не является ли этот элемент первым положительным элементом после отрицательной последовательности? Это можно проверить по счетчику nn. Если элемент первый, то значение nn должно быть больше 0. Если нет, то необходимо обработать ту отрицательную последовательность, которая только что закончилась. Для обработки в первую очередь получаем среднее значение. Потом организуем цикл со счетчиком j, который изменяется от ib (индекс начала отрицательной последовательности, который был сохранен раньше) до i-1 (i – индекс первого положительного элемента после отрицательной последовательности, значит i-1 – индекс последнего элемента отрицательной последовательности). В каждой итерации этого цикла сравниваем j-й элемент массива со средним значением av. Если значение элемента меньше среднего (т. е. больше по абсолютному значению), то среднее значение записывается в j-й элемент, если же нет – ничего не происходит. По выходу из цикла устанавливаем счетчик nn в 0 как признак того, что необработанной последовательности нет. Для не первого положительного элемента нет необходимости что-либо делать.

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

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

Определение переменных программы. Для реализации алгоритма необходимы следующие переменные:

a) массив целых чисел, который будет обрабатываться: int Ar[100]; (массив должен располагаться в статической памяти);

b) индексы элементов массива для внешнего и внутреннего циклов: int i, j;

с) переменные, в которых будут храниться параметры очередной последовательности: сумма элементов, а потом среднее значение av, количество элементов в последовательности nn, индекс начала последовательности ib:

int av;  //среднее значение

int nn;  //количество эл-тов в последовательности

int ib;  //индекс начала последовательности

Отметим, что для большинства данных, которые представляются переменными программы, достаточно было бы и типа short или char, так как их значения укладываются в диапазон –128¸128. Тип int выбираем согласно общему стилю программирования на языке C. Отдельного рассмотрения требует переменная av, так как в ней накапливается сумма, а значит ее значение может значительно превысить значения остальных переменных. Но в наихудшем случае (когда все элементы массива будут иметь максимальные значения) ее величина не превысит 100 × 50 = 5000, следовательно типа int достаточно и для нее.

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

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <iomanip>

#include <stdlib.h>

#include <time.h>

#include <locale>

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

int Ar[100];

Далее ставим заголовок главной функции main и открываем ее тело:

int _tmain(int argc, _TCHAR* argv[])

Главная функция начинается с объявления остальных переменных программы.

Далее организуем простой цикл со счетчиком, в каждой итерации которого в следующий элемент массива записывается случайное число. Обращение к функции rand() возвращает нам число в пределах 0–100; вычитая из него 50, приводим его к диапазону –50¸50.

for (i
= 0; i < 1 00; Ar[i++] = (int)(((double)rand() /( double)RAND_MAX)
* (rmax - rmin) + rmin));

Заполненный таким образом массив в цикле выводим на экран. Каждый элемент занимает 5 позиций, а в одной строке экрана разместится целое число (16) элементов, что обеспечит удобное представление массива.

cout << "Начальный массив:\n";

for (i = 0; i < 100; cout << setw(5) << Ar[i++]);

putchar('\n');

putchar('\n');

Далее идет заголовок цикла перебора массива, в котором также присваиваем начальное значение счетчику nn:

for (nn = i = 0; i < 100; i++) {

Все тело цикла состоит из одного условного оператора. В этом операторе проверяем знак i-го элемента массива:

if (Ar[i] < 0)

Если это условие – истина, то проверяем, не равен ли 0 счетчик элементов последовательности nn:

if (!nn) {

При выполнении этого условия происходит ряд действий, которые берутся в операторные скобки:

ib = i; av = Ar[i]; nn = 1;

Если же условие ложно, то выполняется сложный оператор:

else

{

av += Ar[i];

nn++;

Если же элемент положительный, то выполняется часть else первого условного оператора, в которой анализируется nn – нет ли необработанной отрицательной последовательности:

else  if (nn) {

Если есть необработанная последовательность, выполняем усреднение значения av:

av /= nn;

и организуем цикл с параметром j, который изменяется от ib до i-1:

for (j = ib; j < i; j++)

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

if (Ar[j] > av) Ar[j] = av;

При выходе из цикла записываем 0 в счетчик nn:

nn = 0;

На этом заканчивается и внешний цикл.

Несколько операторов, которые следуют после выхода из цикла, обеспечивают обработку окончательной последовательности и в основном являются копией. Разница состоит в том, что тут внесли усреднение в начальное действие цикла и убрали присваивание nn = 0, так как значение nn больше не понадобится.

Операторы вывода массива-результата – копия вывода начального массива.

Листинг задачи 7.1

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <iomanip>

#include <stdlib.h>

#include <time.h>

#include <locale>

#include <conio.h>

using namespace std;

int Ar[100];                              //массив, который обрабатывается

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

int i, j;                             //индексы в массиве

int av;                               //среднее значение

int nn;                               //количество элементов в последовательности

int ib;                               //индекс начала последовательности

int rmin = -50;                       //диапазоны элементов

int rmax = 50;

srand((unsigned)time(NULL));

                                      //заполнение массива случайными числами

for (i = 0; i
<1 00; Ar[i++] = (int)(((double)rand() / (double)RAND_MAX)
* (rmax - rmin) + rmin));

                                      //вывод начального массива

cout << "Начальный массив:\n";

for (i = 0; i
< 100; cout << setw(5)
<< Ar[i++]);

putchar('\n');

putchar('\n');

for (nn = i = 0; i < 100; i++)

{                                    //перебор массива

if (Ar[i] < 0)

                                 //обработка отрицательного элемента

if (!nn)

{

                                        //начало последовательности

                                        //запомнить индекс начала,

      //начальное значение

      //накопителя суммы

                                        //и счетчика элементов

ib = i;

av = Ar[i];

nn = 1;

}

else

{

                                       //накопление суммы

     //подсчет количества

av += Ar[i];

nn++;

}

                                      //конец обработки

    //отрицательного элемента

else                          //обработка положительного

    //элемента

if (nn)

{

                                     //если есть необработанная

   //отрицательная

   //последовательность

av /= nn;            //усреднение

                                    //перебор всей последовательности

  //с ограничением

for (j = ib; j < i; j++)

if (Ar[j] > av) Ar[j] = av;

nn = 0;             //последовательность обработана

}                       //конец, если есть необработанная

}                              //конец перебора массива

if (nn)                        //если не обработана

 //последняя отрицательная

 //последовательность

for (av /= nn, j = ib; j < i; j++)

if (Ar[j] > av)

Ar[j] = av;

                                  //вывод результатов

printf("Массив-результат:\n");

for (i = 0; i
< 100; cout << setw(5)
<< Ar[i++]);

putchar('\n');

getchar();

return 0;

}

Результат выполнения задачи 7.1


Задача 7.2

Даны два массива A и B размера 5, элементы которых упорядочены по возрастанию. Объединить эти массивы так, чтобы результирующий массив остался упорядоченным.

Листинг задачи 7.2

#include "stdafx.h"

#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])

{

                                     //объявление переменных

int a[5], b[5], c[10];

int k, l, i;

                                     //инициализация переменных

printf("A:\n");

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

scanf("%d", &a[i]);

printf("B:\n");

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

scanf("%d", &b[i]);

i = 0; k = 0; l = 0;

do

{

if (a[k] <= b[l])

{

c[i] = a[k];

k++;

}

else

{

c[i] = b[l];

l++;

}

i++;

if (k == 5)

for (; l < 5; l++)

{

c[i] = b[l];

i++;

}

if (l == 5)

for(; k < 5; k++)

{

c[i] = a[k];

i++;

}

}

while (i < 10);

                                     //выводим результат

printf("\n");

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

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

printf("\n");

return 0;

}

Результат выполнения задачи 7.2


Задача 7.3

Сформировать одномерный массив целых чисел, используя датчик случайных чисел, и выполнить задание c использованием индексов. Удалить последний элемент, равный 0. Добавить после элемента массива с заданным индексом элемент со значением 100.

Листинг задачи 7.3

#include "stdafx.h"

#include <stdio.h>

#include <algorithm>

#include <locale>

#include <time.h>

#define MaxN 100

int a[MaxN];

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

int n;

printf("Введите размерность массива\n");

scanf("%d", &n);

srand((unsigned)time(NULL));

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

{

a[i] = rand () % 10;

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

}

putchar('\n');

int pos;

for (pos = n - 1; pos >= 0 && a[pos] != 0; pos--);

pos == -1 ? printf("Нет нулевого элемента\n") :

printf("Позиция последнего нулевого элемента: %d\n", pos);

for (int i = pos; i < n - 1; i++)

std::swap(a[i], a[i + 1]);

printf("Введите позицию элемента, после которого вставить 100\n");

scanf("%d", &pos);

for (int i = n - 1; i > pos + 1; i--)

std::swap(a[i], a[i - 1]);

a[++pos] = 100;

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

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

putchar('\n');

return 0;

}

Результат выполнения задачи 7.3


Задача 7.4

В массиве M(k) много совпадающих элементов. Найти количество различных элементов в нем, не упорядочивая массив.

Листинг задачи 7.4

#include "stdafx.h"

#include <stdio.h>

#include <locale>

#include <math.h>

#include <time.h>

#define  MaxN 100

int m[MaxN];

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

int n;

printf("Введите размерность массива\n");

scanf("%d", &n);

srand((unsigned)time(NULL));

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

{

m[i] = rand() % 10;

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

}

printf("\nНеповторяющиеся элементы\n");

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

{

bool ans = true;

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

{

if (i == j) continue;

if (m[i] == m[j])

{

ans = false;

break;

}

}

if (ans) printf("%d ", m[i]);

}

return 0;

}

Результат выполнения задачи 7.4


Задача 7.5

Найти в массиве наибольшее число идущих подряд одинаковых элементов (например, {1, 5, 3, 6, 6, 6, 6, 6, 3, 4, 4, 5, 5, 5} = 5). Посчитать процент их встречаемости.

Листинг задачи 7.5

#include "stdafx.h"

#include <iostream>

#include <locale>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

using namespace std;

int mass[20], rmin = 0, rmax = 10, n, i, k = 1, s = 0;

cout << "Введите число элементов (максимум 20): ";

cin >> n;

                            //случайное заполнение

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

{

mass[i] = (int)(((double)rand() /

(double)RAND_MAX) * (rmax - rmin) + rmin);

cout << mass[i] << " ";

}

                               //наибольшее число идущих подряд

                               //одинаковых элементов

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

{

if (mass[i] == mass[i-1])

{

if(s == 1)

k = k+1;

else

{

k = 1;

s = 1;

k += 1;

}

}

else

s = 0;

}

cout << " " << k << endl;

                              //задание 2

cout << "\n\n---------------------------------------------\n\n";

int K[100], pr[10], pry[10], j, m, max;

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

K[i] = (int)(((double)rand() / (double)RAND_MAX) * (rmax - rmin) + rmin);

cout << "Введите m (кол-во наиболее частых) ";

cin >> m;

                               //находим кол-во каждой цифры

for (i = 0, s = 0; i < rmax; i++, s=0)

{

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

if (K[j] == i)

s += 1;

pr[i] = s;

}

                               //упорядочиваем массив

for (i = 0, max = 0; i < 10; i++)

{

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

if (pr[j] > pr[max])

max = j;

pry[i] = pr[max];

K[i] = max;

pr[max] = 0;

}

                               //выводим на экран m

//часто встречающихся

cout << "Массив K[100] содержит \n";

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

cout << K[i] << " - " << pry[i] << "%" << endl;

return 0;

}

Результат выполнения задачи 7.5


Задача 7.6

Найти в массиве наибольший и наименьший элементы.

Листинг задачи 7.6

#include "stdafx.h"

#include <locale>

#include <iostream>

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "rus");

using namespace std;

int n, i, a[300];

cout << "Введите размерность массива" << endl;

cin >> n;

srand((unsigned)time(NULL));

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

{

a[i] = rand() % 30;

cout << a[i] << " ";

}

cout << endl;

cout << "*************************" << endl;

    int kmin = 0, kmax = 0;

for (int i = 1; i < n; i++)

//поиск наименьшего и

//наибольшего элемента в

//массиве

{

if (a[i] < a[kmin]) kmin = i;

if (a[i] > a[kmax]) kmax = i;

}

cout << "Минимальный элемент" << a[kmin] << endl;

cout << "Максимальный элемент" << a[kmax] << endl;

return 0;

}

Результат выполнения задачи 7.6


Задачи для самостоятельного решения

При выполнении работы используются статические массивы. Для организации статических массивов с псевдопеременными границами необходимо объявить массив достаточно большой длины. Затем пользователь вводит реальную длину массива (не больше N) и работает с массивом той длины, которую он сам указал. Остальные элементы (хотя память под них и будет выделена) не рассматриваются. При уменьшении или увеличении длины массива необходимо изменять его реальную длину.

Составить блок-схему алгоритма.

Сформировать одномерный массив целых чисел, используя датчик случайных чисел (диапазон от 0 до 99), и выполнить задание двумя вариантами (c использованием индексов и указателей). Размер массива ввести с клавиатуры.
1 | Удалить элемент с номером k. Добавить после каждого четного элемента массива элемент со значением 0.
2 | Удалить первый элемент, равный 0. Добавить после каждого четного элемента массива элемент со значением m[i - 1] + 2.
3 | Удалить все элементы, равные 0. Добавить после первого четного элемента массива элемент со значением m[i - 1] + 2.
4 | Удалить элементы, индексы которых кратны 3. Добавить после каждого отрицательного элемента массива элемент со значением | m[i - 1] + 1|.
5 | Удалить элементы, кратные 7. Добавить после каждого нечетного элемента массива элемент со значением 4.
6 | Удалить последний элемент, равный 6. Добавить после элемента массива с заданным индексом элемент со значением 99.
7 | Удалить все элементы с заданным значением. Добавить перед каждым четным элементом массива элемент со значением 1.
8 | Удалить первый элемент с заданным значением. Сдвинуть массив циклически на k элементов вправо.
9 | Удалить пять первых нечетных элементов массива. Добавить в конец массива три новых нулевых элемента.
10 | Поменять местами минимальный и максимальный элементы массива. Удалить из массива все элементы, превышающие его среднее значение более чем на 10%.
11 | Удалить из массива все элементы, совпадающие с его минимальным значением. Добавить в начало массива три элемента со значением, равным среднему арифметическому массива.
12 | Перевернуть массив и, если число его элементов нечетное, удалить средний элемент. Добавить в начало массива три элемента со значением m[i + 10] - 2.
13 | Найти в массиве и вывести значение наиболее часто встречающегося элемента.
14 | Найти в массиве элемент, наиболее близкий к среднему арифметическому суммы его элементов.
15 | Разделить массив на две части, поместив в первую элементы, большие среднего арифметического их суммы, а во вторую – меньшие (части не сортировать).
16 | Найти наименьшее общее кратное всех элементов массива (т. е. число, которое делится на все элементы).
17 | Найти в массиве элемент, если он существует, равный среднему арифметическому суммы трех его последних элементов.
Ввести одномерный массив целых чисел. Размер массива вводится пользователем.
18 | По заданному массиву А размера n построить массив В такой, что B(i) – это количество элементов из А, не превосходящих A(i) в конечном отрезке А длиной i - 1.
19 | Найти максимальную по длине монотонную неубывающую подпоследовательность заданного массива целых чисел.
20 | Найти наибольший общий делитель всех элементов массива.
21 | В массиве С(m) каждый третий элемент заменить полусуммой двух предыдущих, а стоящий перед ним – полусуммой соседних с ним элементов. Дополнительный (рабочий) массив не использовать.
22 | Каждый из элементов ti массива Т(n) заменить минимальным среди первых i элементов этого массива.
23 | В массиве А(n) каждый элемент, кроме первого, заменить суммой всех предыдущих.
24 | Дан массив целых чисел К(n). Найти в нем минимальный kmin и максимальный kmax элементы. Вывести в порядке возрастания все целые числа из интервала (kmin, kmax), не встречающиеся в исходном массиве.
25 | Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами.
26 | Найти все числа, встречающиеся в массиве Р(m) строго два раза (не упорядочивая сам массив).
27 | В массиве найти первый и последний нулевые элементы. Вывести их индексы.
28 | Все четные элементы целочисленного массива K(n) поместить в массив L(n), а нечетные – в массив М(n). Подсчитать количество тех и других.
29 | Каждый из элементов ti массива Т(n) заменить средним арифметическим среди первых i элементов этого массива.
30 | В массиве найти первый и последний минимальные элементы. Вывести их индексы.


ТЕМА 8. МАССИВЫ И УКАЗАТЕЛИ

Изучите теоретический материал главы 8 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое указатель?

2. Приведите формат объявления указателя.

3. Что такое ссылочный тип?

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

5. Что такое разыменование указателя?

6. Какие операции возможны над указателями?

7. Как связаны указатели и массивы?

8. Как обратиться к элементу массива с индексом 5, используя указатели?

9. Что такое многомерный массив? Приведите пример.

10. Как обратиться к элементу массива A[m][n], используя указатели?

11. Правильно ли написано увеличение величины, на которую указывает указатель a, на единицу *a++?

12. Пусть есть mas[30][100]. Выразите адрес mas[22][0] двумя способами.

13. Что будет записано в y = *px + 1 ?

14. Что будет записано в y = *(px + 1)?

15. Если px указывает на x, то что означает *px = 0 ?

16. Как увеличить значение х на единицу через указатель (*px += 1) или (*px)++?

17. Напишите вариант функции strlen, вычисляющей длину строки через указатель.

18. Если p и q – указатели, когда выражение вида p < q будет истинным?

19. Если p и q – указатели, что подразумевает выражение p + q?

20. Если p и q указывают на элементы одного и того же массива, то что означает p - q ?

21. Что означает *++p?

22. Что делает while (*q++ = *p++);?

23. Что означает char** cpp;?

24. Что означает int (*vp)[10];?

25. Если

char c1 = 'a';

char* p = &c1;

char c2 = *p;

что хранится в p и с2 ?

26. Что выполняется?

int ii = 0;

int& rr = ii;

rr++;

27. Является ли допустимой операция &3 и &(x – 3)?

28. Могут ли указатели входить в выражения y = *ip + 1?

29. Если data[3] – массив, будут ли правильны следующие операции: data = pdata, или data++, или pdata = &data?

30. Что означает равенство указателей?

31. Какому типу указателя можно присвоить NULL?

32. Как можно интерпретировать указатель на char?

33. Можно ли присваивать указатели разных типов друг другу?

34. Продолжите

int     *q;

long *l;

q =

35. Сколько места будет выделено под масcив int a[2][2][3];?

36. Допускается ли суммирование двух указателей?

37. Что выполняет фрагмент программы?

int data[7];

int *pdata ;

pdata = &data[0];

38. Выберите верные объявления многомерного массива:

a) int a[3][4];

b) int a{3.4};

c) int a[3,4];

39. Для присвоения указателю начального значения можно использовать три значения… . Перечислите их.


Методические указания

Условие задачи. Размерность массива – 100. Диапазон значений –50–50. Во всех последовательностях отрицательных чисел ограничить значения тех элементов, абсолютное значение которых превышает абсолютное среднее для этой последовательности.

Замечание: 0 считается положительным числом, если в задании не оговорен какой-то другой его статус; когда речь идет о некой последовательности чисел, имеется в виду последовательность с длиной больше 1.

Разработка алгоритма. Алгоритм решения задачи в основном тот же, что и в теме № 7, поэтому его схема не приводится.

Существенные отличия возникают в реализации алгоритма. Проще всего задание могло быть выполнено простой заменой во всех местах операции индексации на операцию адресации, имея в виду тождественность Ar[i] = *(Ar + i).

Это соответствовало бы заданию, но не стилю языка C++. При переходе от индексации к адресации пропадает необходимость в индексах и даже переменных, которые их представляют. Это приводит к другому способу реализации всех циклов. Если имя массива Ar является указателем на его начало, то вместо цикла, в котором индекс i меняется от 0 до size, можно организовать цикл, где некоторый текущий указатель Cr меняется от Ar до Ar + size. Также, когда нужно запомнить начало отрицательной последовательности, можно запоминать не индекс соответствующего элемента, а его адрес – указатель на него.

Определение переменных программы. Переменные программы описываем так же, как в работе № 7. Память для массива целых чисел не выделяется на этапе компиляции, значит достаточно объявить в программе только переменную – указатель на начало массива:

int *Ar;

Размерность массива определяется при выполнении программы, т. е. для ее сохранения нужна отдельная переменная:

int size;

Вместо переменных, которые в работе № 7 являются индексами элементов массива, будем применять указатели:

int *Cr; – это будет указатель на текущий элемент массива при его полном переборе, и:

int *Ir; – в этом указателе будет сохраняться адрес начала отрицательной последовательности, а потом – при обработке последовательности – адрес текущего ее элемента.

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

int av;

int nn;

Разработка текста программы. Полученный размер массива сразу выводим на экран.

Выделяем с помощью операции new память под массив:

Ar = new int[size];

Далее организуем цикл перебора массива. В отличие от работы № 7, тут в одном цикле можно получить и случайные числа, и вывести начальный массив на экран. Заголовок этого цикла существенно отличается от заголовка в теме № 7:

for (Cr = Ar; Cr < Ar + size; Cr++) {

В начальных установках цикла записываем в переменную Cr адрес начала массива, т.е. Cr показывает на элемент с индексом 0. В конце каждой итерации Cr увеличивается на 1, т. е. показывает на следующий элемент массива. Последняя итерация происходит при значении Cr = Ar + size - 1, т. е. Cr будет показывать на последний элемент. В каждой итерации обращаемся к текущему элементу массива как *Cr, т. е. к тому, на что показывает указатель Cr.

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

Тело цикла в основном подобно тому, что приведено в лабораторной работе № 7 за исключением того, что к текущему элементу массива следует обращаться через указатель на него: *Cr. Там, где требуется запомнить начало отрицательной последовательности, просто сохраняется текущее значение указателя Cr в переменной-указателе Ir.

Внутренний цикл, в котором обрабатывается отрицательная последовательность, существенно отличается от приведенного в работе № 7:

for (av /= nn; Ir < Cr; Ir++)

if (*Ir < av) *Ir = av;

Начальные установки этого цикла – только усреднение значения в av, переменная Ir уже содержит в себе указатель на первый элемент отрицательной последовательности. В конце каждой итерации Ir увеличивается на 1, т. е. показывает на следующий элемент последовательности (обращение к этому элементу – *Ir). Последняя итерация происходит при значении Ir = Cr - 1, поскольку Cr показывает на первый положительный элемент за отрицательной последовательностью.

Остаток программы повторяет предыдущие фрагменты.

Предпоследний оператор – для освобождения памяти, которая была выделена под массив.


Задача 8.1

В массиве M(k) много совпадающих элементов. Найти количество различных элементов в нем (не упорядочивая массива).

Листинг задачи 8.1

#include "stdafx.h"

#include <stdio.h>

#include <locale>

#include <math.h>

#include <time.h>

#define MaxN 100

int m[MaxN];

int main(void)

{

setlocale(LC_CTYPE, "Russian");

int n;

printf("Введите размерность массива\n");

scanf("%d", &n);

srand((unsigned)time(NULL));

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

{

*(m + i) = rand() % 10;

printf("%d ", *(m + i));

}

printf("\nНеповторяющиеся элементы\n");

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

{

bool ans = true;

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

{

if (i == j) continue;

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

{

ans = false;

break;

}

}

if (ans) printf ("%d ", *(m + i));

}

    return 0;

}

Результат выполнения задачи 8.1


Задача 8.2

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

Листинг задачи 8.2

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <cmath>

#include <ctime>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

srand((unsigned)time(NULL));

int n, i, j, m, a[100];

cin >> n >> m;

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

*(a + i) = rand() % 6;

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

cout << *(a + i) << " ";

cout << endl;

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

{

if (*(a + i) == m)

{

for (j = i; j <= n - 1; j++)

*(a + j) = *(a + j + 1);

n--;

}

}

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

{

if (*(a + i) % 2 == 0)

{

for (j = n; j >= i; j--)

*(a + j + 1) = *(a + j);

n++;

*(a + i) = 0;

i++;

}

}

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

cout << *(a + i) << " ";

cout << endl;

return 0;

}

Результат выполнения задачи 8.2


Задача 8.3

Сформировать одномерный массив целых чисел, используя ввод данных с клавиатуры, и выполнить задание c использованием указателей. Найти непрерывные участки, на которых сумма элементов равна 100.

Листинг задачи 8.3

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <cmath>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n, i, j, a[1000], s, k;

s = 0;

cout << "Enter size" << endl;

cin >> n;

cout << "Array" << endl;

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

{

*(a + i) = rand() % 10;

cout << *(a + i) << " ";

}

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

{

s = *(a + i);

if (*(a + i) == 100)

cout << *(a + i) << endl;

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

{

s += *(a + j);

if (s == 100)

{

for (k = i,

cout << "Find a part of array:" << endl;

k <= j; k++)

cout << *(a+k) << " ";

cout << endl;

}

}

}

return 0;

}

Результат выполнения задачи 8.3


Задача 8.4

Даны два целочисленных массива K(m) и L(n). Найти наибольший элемент массива K, не имеющий себе равных в массиве L.

Листинг задачи 8.4

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <cmath>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int m, n, k[30], l[20], i, j, max, q, w, e;

cout << "Vvedite m" << endl;

cin >> m;

cin >> n;

for (i = 1; i <= m; i++) cin >> *(k + i);

for (j = 1; j <= n; j++) cin >> *(l + j);

for (q = 1; q <= m * 2; q++)

{

max = - 2147000000;

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

{

if (*(k + i) > max)

{

max = *(k + i);

w = i;

}

}

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

{

if (max == *(l + j))

{

for (e = w; e <= m - 1; e++)

*(k + e) = *(k + e + 1);

m--;

break;

}

}

if (j == n + 1)

{

cout << max;

return 0;

}

}

cout << "No";

return 0;

}

Результат выполнения задачи 8.4


Задачи для самостоятельного решения

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


ТЕМА 9. СТРОКИ И УКАЗАТЕЛИ

Изучите теоретический материал главы 9 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое строка?

2. Строковые данные можно задать на основе типа данных ... .

3. Описание функций работы со строками содержится в заголовочном файле … .

4. Определите назначение функций

strlen(char*);

strcpy(char*, char*);

strcat(char*, char*);

5. Что выполняет фрагмент программы?

char *s, *t;

while (*s++ = *t++);

6. Запишите пример поиска конца строки.

7. Запишите пример просмотра строки.

8. Запишите пример копирования строки.

9. Запишите пример добавления символа к строке.

10. Запишите строку через массив символов.

char s[] = "ABCDEF";

11. Являются ли описания char s[]; и char *s; эквивалентными?

12. Если char *message;, можно ли выполнить message = "now is the time";?

13. Чему равно sizeof("asdf")?

14. Является ли выражение тождеством strlen(s) == sizeof(s)?

15. Что означает следующий фрагмент?

char c;

int n;

n = c - '0';

c = n + '0';

16. Запишите версию стандартной функции strcmp.

17. Запишите версию стандартной функции strcpy.

18. Напишите выражение, которое определяет строковую переменную cit, содержащую строку длиной до 20 символов.

19. Первый элемент строки – это … .

20. Строковые данные можно задать на основе типа данных … .

21. Описание функций работы со строками содержится в заголовочном файле … .


Примеры решения задач

Задача 9.1

Преобразовать строку следующим образом: удалить все символы "*" и повторить каждый символ, отличный от "*".

Листинг задачи 9.1

#include "stdafx.h"

#include <stdio.h>

#include <locale>

#define MaxLen 256

int main(void)

{

setlocale(LC_CTYPE, "Russian");

puts("Введите строку");

char s[MaxLen], ans[MaxLen * 2];

gets (s);

int len = -1;

for (int i = 0; s[i]; i++)

if (s[i] != '*')

{

ans[++len] = s[i];

ans[++len] = s[i];

}

ans[++len] = '\0';

puts(ans);

putchar('\n');

return 0;

}

Результат выполнения задачи 9.1


Задача 9.2

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

Листинг задачи 9.2

#include "stdafx.h"

#include <stdio.h>

void main()

{

char s[256];

int i, c;

printf("Enter string: ");

gets(s);

for (c = i = 0; s[i] != 0; i++)

{

if (s[i] == '(')

c++;

if (s[i] == ')')

c--;

}

if (c)

printf("Error\n");

else

printf("It's right\n");

}

Результат выполнения задачи 9.2


Задача 9.3

Функция создает копию строки и «переворачивает» ее. (Дополнительно: программа проверяет, не является ли исходная строка перевертышем.)

Листинг задачи 9.3

#include  "stdafx.h"

#include  <stdio.h>

#include  <iostream>

#include  <locale>

#include  <string.h>

#include  <windows.h>

using namespace std;

void perest(char *c, int *n)

{

int i, j, k, f = 0;

char buff; *n = 0;

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

if (c[0] ==' ')

for (i = 0; c[i] ==' '; i++);

else i = 0;

for (; c[i] != '\0'; i++)

if (c[i] == ' ' && c[i+1] != ' ' && c[i+1] != '\0')

                    *n = *n + 1;

{

f = i;

for (j = i - 1, k = i - f; j > k; j--, k++)

{

buff = c[j];

c[j] = c[k];

c[k] = buff;

}

}

if (*n != 0) *n = *n + 1;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

char c[100];

int N, n, i, k, x;

gets(c);

perest(c, &N);

printf("%s\n", c);

n = strlen(c);

if (n % 2 == 0) x = n / 2;

else x = (n + 1) / 2;

k = 0;

for (i = 0, n = n - 1; i <= n; i++, n--)

if (c[i] == c[n]) k++;

if (k == x)

cout <<" Это строка перевертыш ";

else

cout <<" Это строка не перевертыш ";

cout << "Коли4ество слов равно: ";

cout << N << endl;

}

Результат выполнения задачи 9.3


Задача 9.4

Написать программу, реализующую удаление k символов с позиции номер n из строки S. Не использовать стандартные операции и процедуры для строк символов.

Листинг задачи 9.4

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE,"Russian");

char S[100];

int k, n;

cout << "Задайте строку " << endl;

cin.getline(S, '/0');

cout << "Задайте позицию n " << endl;

cin >> n;

cout << "Задайте количество элементов, которые нужно удалить" << endl;

cin >> k;

for (int i = 0; i < k; i++)

{

int j = n;

while (S[j] != '\0')

{

S[j] = S[j+1];

j++;

}

}

cout << "Новая строка: " << endl;

for (int i = 0; S[i] != '\0'; i++)

cout << S[i];

system("Pause");

return 0;

}

Результат выполнения задачи 9.4


Задача 9.5

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

Листинг задачи 9.5

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE,"Russian");

char mas[100];

int sum = 0;

cout << "Задайте строку" << endl;

cin.getline(mas, '/0');

int i = 0;

while (mas[i] != '\0')

{

if ((mas[i] == '.') || (mas[i] == '!') || (mas[i] == '?'))

sum++;

i++;

}

cout << "Количество предложений в заданном тексте " << sum << endl;

system("Pause");

return 0;

}

Результат выполнения задачи 9.5


ТЕМА 10. ФУНКЦИИ

Изучите теоретический материал главы 11 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое функция?

2. В чем преимущества использования функций?

3. Приведите пример формы определения функции.

4. При объявлении функций компилятору важно знать … .

5. Какой оператор используется для возврата значения функции?

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

7. Перечислите существующие способы передачи аргументов функции.

8. Как выполняется передача результата из функции в функцию main?

9. Как выполнить передачу параметра в функцию по адресу?

10. Как передать массив в функцию?

11. Допустимы ли в С функции, у которых при компиляции не фиксируется число параметров и может быть неизвестен тип параметров?

12. Как описать функцию, не возвращая значения?

13. Что такое формальные и фактические параметры?

14. Замените функцию double     FF()   { int nn;     return (nn+1);} эквивалентным выражением.

15. В чем разница между объявлением и определением функции? Приведите примеры.

16. Приведите пример обычного объявления функции и по прототипу.

17. Область действия статической функции.

18. Приведите пример вызова функции.

19. Функция активируется с помощью … .

20. Переменная, известная только внутри функции, в которой она определена, называется … .

21. Функция, которая прямо или косвенно вызывает сама себя, называется … .

22. В C++ можно иметь разные функции с одинаковым именем, каждая из которых оперирует различными типами и (или) количеством аргументов. Такая функция называется … .

23. … предоставляет возможность доступа к глобальной переменной с тем же именем, что и переменная в текущей области действия. Унарная операция разрешения области действия … .

24. … позволяет компилятору проверить количество, типы и порядок следования аргументов, передаваемых функции.

25. Функция … используется для получения случайных чисел.

26. Переменная, объявленная вне любого блока или функции, является … .

27. Найдите ошибку во фрагменте программы и объясните, как ее можно исправить.

int g(void)

{

cout <<  "Внутри функции g" << endl;

int h(void)

{

cout << "Внутри функции h" << endl;

}

}

28. Найдите ошибку во фрагменте программы и объясните, как ее можно исправить.

int sum(int x, int у)

 {

int result;

result = x + y;

 }

29. Найдите ошибку во фрагменте программы и объясните, как ее можно исправить.

int sum(int n)

{

if ( n == 0 ) return 0;

else  n + sum(n - 1) ;

}

30. Верно или нет, что все вызовы функций в C++ выполняются вызовом по значению?

31. Приведите пример функции с переменным числом аргументов.

32. Что значат параметры функции по умолчанию? Приведите пример.

33. Что значит перегрузка имен функций? Приведите пример.


Примеры решения задач

Задача 10.1

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

Листинг задачи 10.1

#include "stdafx.h"

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <windows.h>

using namespace std;

int find(char *p)

{

int i, n, k, u, m;

n = 0; k = 0;

if (p[0] == ' ')

for (i = 0; p[i] == ' '; i++)

n = 0;

else

i = 0;

for (u = i; p[i] != 0; i++)

{

if (p[i] != ' ')

n++;

else break;

}

while (p[i] != 0)

{

for (m = i; p[i] != 0 && p[i] == ' '; i++)

{

k = 0;

m++;

}

for (; p[i] != 0 && p[i] != ' '; i++)

k++;

if (k > n)

{

n = k;

u = m;

}

k = 0;

}

return u;

}

int _tmain(int argc, _TCHAR* argv[])

{

char p[100], p1[100], p2[100];

int i = 0, u, j = 0, k, l;

cout << "Input string: " << endl;

gets(p);

l = strlen(p);

cout << endl;

while (j < l)

{

u = find(p);

for (i = u; p[i] != 0; i++, j++)

{

if(p[i] != ' ')

p1[j] = p[i];

else break;

}

p1[j] = ' ';

k = 0;

if (u ! =0)

{

for (i = 0; i < u; i++, k++)

p2[k] = p[i];

}

if ((i + j) != l)

{

for (i = i + j; p[i] != 0; i++, k++)

p2[k] = p[i];

p2[k] = '\0';

}

else p2[k] = '\0';

for (i = 0; p2[i] != 0; i++)

p[i] = p2[i];

p[i] = '\0';

j++;

}

p[j--] = '\0';

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

cout << p1[i];

cout << endl;

}

Результат выполнения задачи 10.1


Задача 10.2

Написать функцию, проверяющую, есть ли отрицательные элементы в указанной строке двумерного массива. Удалить из массива все строки с отрицательными элементами, удаленная строка заполняется 0 и переносится в конец массива.

Листинг задачи 10.2

#include "stdafx.h"

#include <iostream>

#include <math.h>

#include <time.h>

bool check(int *p, int m)

{

int i;

for (i
= 0; i < m && p[i];
i++);

return i != m;

}

#define MaxN 100

int a[MaxN][MaxN];

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

int n, m;

std::cout << "Введите размерность матрицы" << std::endl;

std::cin >> n >> m;

srand((unsigned)time(NULL));

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

{

for (int j = 0; j < m; j++)

{

a[i][j] = rand() % 10;

std::cout << a[i][j] << ' ';

}

std::cout << std::endl;

}

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

if (check((int*) a[i], m))

{

for (int k = i + 1; k < n; k++)

for (int j = 0; j < m; j++)

std::swap(a[k][j], a[k - 1][j]);

for (int j = 0; j < m; j++) a[n - 1][j] = 0;

}

std::cout << std::endl;

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

{

for (int j = 0; j < m; j++) std::cout << a[i][j] << ' ';

std::cout << std::endl;

}

return 0;

}

Результат выполнения задачи 10.2


Задачи для самостоятельного решения

Выполнить задание двумя способами – используя индексы и указатели при работе со строками и не используя стандартные операции и функции для строк символов.

Вариант задания реализовать в виде функции. Если функция возвращает строку или ее фрагмент, то это необходимо сделать через указатель. Строки динамические, размер вводится с клавиатуры. Строки вводить с клавиатуры. Составить блок-схему алгоритма.

1

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

2

Написать функцию, реализующую добавление k символов с позиции номер n в строку S. Не использовать стандартные операции и процедуры для строк символов.

3

Написать функцию, реализующую выделение подстроки S1 длиной k с позиции номер n из строки S. Не использовать стандартные операции и процедуры для строк символов.

4

Написать функцию удаления в строке всех букв «b», непосредственно за которыми идет цифра.

5

Написать функцию удаления всех символов «FF» и повторить каждый символ, отличный от цифры.

6

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

7

Написать функцию определения числа вхождений в строку подстроки «abа».

8

Написать функцию для вывода слова строки, начинающегося и заканчивающегося одной и той же буквой, содержащего ровно три буквы «k».

9

Написать функцию, удаляющую в строке все буквы «b», непосредственно за которыми идет цифра.

10

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

11

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

12

Написать функцию преобразования строки, после каждой буквы «a» добавить символ «!».

13

Написать функцию, которая удаляет все «лишние» пробелы, т. е. из нескольких подряд идущих пробелов оставить только один.

14

Написать функцию, которая осуществляет сравнение двух строк.

15

Написать функцию замены k символов с позиции номер n в строке S.

16

Написать функцию конкатенации k строк.

17

Написать функцию вставки подстроки S1 длиной k в строку S с позиции номер n.

18

Написать функцию определения номера позиции, с которой подстрока S1 длиной k входит в строку S. Удалить в строке x все вхождения подстроки y.

19

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

20

Написать функцию, которая преобразует строку символов в число – целое или вещественное, если это возможно, или сообщает об ошибке в противном случае.

21

Написать функцию, реализующую вставку подстроки S1 длиной k в строку S с позиции номер n. С ее помощью вставить в каждую пятую позицию cтроки X подстроку Y.

22

Написать функцию, реализующую удаление k символов с позиции номер n из строки S. С ее помощью удалить из каждой пятой позиции cтроки X подстроку Y.

23

В строке есть символ «*». Написать функцию, реализующую вывод всех символов между первым и вторым символом «*». Если второго символа «*» нет, то получить все символы после единственного символа «*».

24

Написать функцию, определяющую число вхождений в строку подстроки «abа».

25

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

26

Написать функцию, реализующую удаление в строке всех вхождений «abc».

27

Написать функцию, которая реализует преобразущую строку следующим образом: удалить все символы «Е» и повторить каждый символ, отличный от «L».

28

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

29

Написать функцию подсчета количества слов в строке.

30

Написать функцию подсчета определенной буквы в строке.


ТЕМА 11. ДИНАМИЧЕСКИЕ МНОГОМЕРНЫЕ МАССИВЫ

Изучите теоретический материал главы 10, 12 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Динамические объекты создаются при трансляции программы или при ее выполнении?

2. Какие существуют функции работы с динамической памятью?

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

4. Как можно организовать формирование массивов с переменными размерами? Приведите пример.

5. Что возвращает функция void *malloc(unsigned s)?

6. Что возвращает void *calloc(unsigned n, unsigned m)?

7. Что возвращает void *free(void p)?

8. Сформируйте двумерный динамический массив и освободите память.

9. В чем разница между статическим и динамическим объектами в языке программирования?

10. Как получить доступ к динамической переменной? Может ли она иметь имя?

11. Чем определяется количество и размерность динамических переменных?

12. Может ли содержать динамическая переменная указатели на другие динамические переменные?

13. Приведите пример создания простой динамической переменной типа int и ее инициализации?

14. Как использовать оператор new?

15. Как использовать оператор delete?


Задача 11.1

Дана целочисленная матрица A(N, M). Вычислите сумму и произведение тех ее элементов, которые при делении на два дают нечетное число. Использовать для работы с матрицами указатели и операции вида *p++, p++ и т. д. Матрицы динамические, размер вводится с клавиатуры. Числовые значения считать целыми. Инициализацию матриц реализовать через датчик случайных чисел или ввод с клавиатуры. Результат программы записать в файл.

Составить блок-схему алгоритма.

Листинг задачи 11.1

#include "stdafx.h"

#include "time.h"

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <math.h>

#include <conio.h>

using namespace std;

void make_matr(int** matrix, int m, int n)

           //формирование матрицы

{

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

{

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

cout << matrix[i][j]  <<  " ";

cout << endl;

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int M, N;

int** matrix;

          //адрес адресов - массив

          //указателей

cout << "Enter size rows: ";

cin >> M;

cout << "Enter size columns: ";

cin >> N;

srand(time(0));                           //датчик случайных чисел

matrix = new int*[M];                     //выделение памяти для массива

                                              //указателей

for (int i = 0; i < M; i++)

{

matrix[i] = new int[M];           //выделить память M раз

        //под массив из N

for (int j = 0; j < N; j++)

matrix[i][j] = 1 + rand() % 10;   //инициализация

}

int muls = 1;

int sum = 0;

for (int** ptr = matrix; ptr != matrix + M; ++ptr)

{

for (int* iter = *ptr; iter != *ptr + N; ++iter)

{

printf("%d\t", *iter);

if (*iter % 2 == 0 && (*iter / 2) % 2 != 0 && *iter != 0)

                        //вычисления

{

muls* = *iter;

sum += *iter;

}

}

putchar('\n');

}

FILE* fp = fopen("D:\\result.txt", "w");

        //записать результат в файл

fprintf(fp, "sum: %d\n", sum);

fprintf(fp, "mul: %d", muls);

fclose(fp);

for (int k = 0; k < M; k++)

        //освобождение памяти

delete[] matrix[k];

delete[] matrix;

matrix = NULL;

return 0;

}

Результат выполнения задачи 11.1


Задача 11.2

Дана действительная квадратная матрица порядка 2n. Матрица задается динамически. Получить новую матрицу, переставляя ее блоки размера n×n:

Листинг задачи 11.2

#include "stdafx.h"

#include <iostream>

#include <stdlib.h>

#include <time.h>

#include <iomanip>

using namespace std;

int ** make_matr(int n)

{

int **matr;                                    //адрес адресов – массив

                 //указателей

int i, j, min = -10, max = 10;

matr = new
int*[n];
                        //выделить память под массив

                 //из n элементов

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

{

cout << "\n\n";

matr[i] = new int[n];                      //выделить память n раз под

                 //массив из m

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

{

matr[i][j] = (int)(((double)rand() / (double)RAND_MAX) * (max - min) + min);//инициализация

cout << setw(4) << matr[i][j];         //<<"  ";

                                                  //cout << " [" << i << "] [" << j << "] " << matr[i][j] << "  ";

}

}

return matr;

}

int _tmain(int argc, _TCHAR* argv[])

{

int n, nn, **mas, **masn, i = 0, j = 0, k = 0;

cout << "Razmernost massiva 2n. Vvedite n:" << endl;

cin >> n;

nn = n * 2;

mas = (make_matr(nn));

masn = new int*[n];                          //выделить память под массив

               //из n элементов

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

masn[i] = new int[n];

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

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

(*(*(masn + i) + j)) = 0;

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

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

{

masn[i][j] = mas[i][j];

mas[i][j] = mas[i + n][j + n];

mas[i + n][j + n] = masn[i][j];

}

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

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

{

masn[i][j - n] = mas[i][j];

mas[i][j] = mas[i + n][j - n];

mas[i + n][j - n] = masn[i][j - n];

}

cout << "\n\n\nPreobrazovannyy massiv:" << endl;

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

{

cout << "\n\n";

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

cout << setw(4) << mas[i][j];            //<<"  ";

}

cout << "\n" << endl;

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

delete mas[i];

delete []mas;

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

delete masn[i];

delete []masn;

return 0;

}

Результат выполнения задачи 11.2


Задача 11.3

В каждой строке заданной матрицы A(N, M) вычислить сумму, количество и среднее арифметическое положительных элементов. Матрица задается динамически.

Листинг задачи 11.3

#include "stdafx.h"

#include <iostream>

#include <time.h>

using namespace std;

int ** make_matr(int n,int m)

{

int **matr;                               //адрес адресов – массив указателей

int i, j ,min = -10, max = 10;

matr = new
int*[n];
                      //выделить
память под массив из n

                                          //элементов

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

{

cout << "\n";

matr[i] = new int[m];                 //выделить память n раз под массив из m

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

{

matr[i][j] = (int)(((double)rand() / (double)RAND_MAX) * (max - min) + min);

                 //инициализация

cout << "[" << i << "][" << j << "] " << matr[i][j] < <"\n";

}

}

return matr;

}

int _tmain(int argc, _TCHAR* argv[])

{

int n, m, **mas, k = 0, s = 0;

float srd = 0;

cout << "Vvedite razmernost massiva: " << endl;

cin >> n >> m;

mas = (make_matr(n, m));

//cout << "mas= " << **mas;

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

{

cout << "\n stroka " << i << endl;

for (int j = 0; j < m; j++)

{

if (*(*(mas + i) + j) > 0)

{

k++;

s = s + (*(*(mas + i) + j));

srd = (float)s / (float)k;

}

}

cout << "k = " << k << "summa = " << s << "srednee = " << srd << endl;

k = 0;

s = 0;

}

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

delete []mas[i];

delete []mas;

return 0;

}

Результат выполнения задачи 11.3


Задача 11.4

Дана динамическая матрица A(N, M). Поменять местами ее наибольший и наименьший элементы.

Листинг задачи 11.4

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <iomanip>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n, m, i, j, max, min, temp, x1, y1, x2, y2;

int **mas;

cout << "Razmer massiva n i m" << endl;

cin >> n >> m;

mas = new int*[n];

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

{

mas[i] = new int[m];

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

{

mas[i][j] = rand() % 99;

}

}

max = 0;

min = 100;

cout << "Isxodniy massiv" << endl;

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

{

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

cout << setw(4) << mas[i][j];

cout << endl;

}

cout << endl;

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

{

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

{

if (max < mas[i][j])

{

max = mas[i][j];

x1 = i;

y1 = j;

}

if (min > mas[i][j])

{

min = mas[i][j];

x2 = i;

y2 = j;

}

}

}

temp = mas[x1][y1];

mas[x1][y1] = mas[x2][y2];

mas[x2][y2] = temp;

cout << "Polucheniy massiv" << endl;

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

{

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

cout << setw(4) << mas[i][j];

cout << endl;

}

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

delete []mas[i];

delete []mas;

return 0;

}

Результат выполнения задачи 11.4


Задача 11.5

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

Листинг задачи 11.5

#include "stdafx.h"

#include <iostream>

#include <time.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n, i, j;

int **mas;

cout << "Razmer massiva n" << endl;

cin >> n;

mas = new int*[n];

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

{

mas[i] = new int[n];

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

{

mas[i][j] = 1;

}

}

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

for (i = j + 1; i < n - j - 1; i++)

mas[i][j] = 0;

for (j = n - 1; j > n / 2; j--)

for (i = n - j; i < j; i++)

mas[i][j] = 0;

cout << "Polucheniy massiv" << endl;

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

{

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

{

cout << mas[i][j] << ' ';

}

cout << endl;

}

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

delete []mas[i];

delete []mas;

return 0;

}

Результат выполнения задачи 11.5


Задача 11.6

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

Листинг задачи 11.6

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <iomanip>

#include <fstream>

using namespace std;

//разработать функции создания,

//транспонирования, суммирования

//матриц, вывода на экран и в файл

int **create_matrix(int m)

{

srand(time(NULL));

int **matrix;

matrix = new int*[m];

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

matrix[i] = new int[m];

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

{

for (int j = 0; j < m; j++)

{

matrix[i][j] = rand() % 100;

}

}

return matrix;

}

int **transponate_matrix(int **matrix, int m)

{

int **transpose_matrix = new int *[m];

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

transpose_matrix[i] = new int[m];

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

{

for (int j = 0; j < m; j++)

{

transpose_matrix[i][j] = matrix[j][i];

}

}

return transpose_matrix;

}

int **sum_matrix(int **matrix1, int **matrix2, int m)

{

int **result_matrix;

result_matrix = new int *[m];

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

result_matrix[i] = new int[m];

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

for (int j = 0; j < m; j++)

result_matrix[i][j] = matrix1[i][j] + matrix2[i][j];

return result_matrix;

}

void print_matrix_to_Screen(int **matrix, int m)

{

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

{

for (int j = 0; j < m; j++)

{

cout << setw(4) << matrix[i][j];

}

cout << "\n";

}

cout << "\n";

}

void print_matrix_to_file( int **matrix, int m)

{

fstream file("result.txt", ios::app );

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

{

for (int j = 0; j < m; j++ )

file << setw(4) << matrix[i][j];

file << "\n";

}

file << "\n";

file.close();

}

int _tmain(int argc, _TCHAR* argv[])

{

int m;

srand(time(NULL));

fstream file("result.txt", ios::out);

     file << "";

file.close();

cout << "Enter the size of square matrix: ";

cin >> m;

int **matrix = create_matrix(m);

print_matrix_to_Screen(matrix, m);

print_matrix_to_file(matrix, m);

int **transpose_matrix = transponate_matrix(matrix, m);

print_matrix_to_Screen(transpose_matrix, m);

print_matrix_to_file(transpose_matrix, m);

int **summate_matrix = sum_matrix(matrix, transpose_matrix, m);

print_matrix_to_Screen(summate_matrix, m);

print_matrix_to_file(summate_matrix, m);

cin.get();

cin.get();

return 0;

}

Результат выполнения задачи 11.6


Задачи для самостоятельного решения

Использовать для работы с матрицами указатели и операции вида *p++, p++ и т. д. Матрицы динамические, размер вводится с клавиатуры. Числовые значения считать целыми. Инициализацию матриц реализовать через датчик случайных чисел или ввод с клавиатуры. Результат программы записать в файл. Составить блок-схему алгоритма.
1 | Ввести динамическую матрицу A(N, M). Найти ее наибольший элемент и номера строки и столбца, на пересечении которых он находится.
2 | Найти минимальный из повторяющихся элементов матрицы А(M, N).
3 | Для заданной целочисленной матрицы A(N, M) определить, является ли сумма ее элементов четным числом, и вывести на печать соответствующий текст.
4 | Дана матрица A(N, M). Найти количество элементов этой матрицы, больших среднего арифметического всех ее элементов.
5 | По трем заданным матрицам А(N, N), В(N, N) и С(N, N) построить матрицу Х того же размера, каждый элемент которой вычисляется по формуле xij = min { aij , bij , cij } .
6 | В заданной матрице A(N, M) поменять местами столбцы с номерами P и Q.
7 | Элементы заданной матрицы A(N, N) переписывать построчно в одномерный массив до тех пор, пока не встретится отрицательный элемент.
8 | Даны две целочисленные матрицы A(N, M) и B(N, M). Подсчитать (в отдельности) количество тех пар (aij , bij ) , для которых: а) aij < bij; b) aij = bij; c) aij > bij.
9 | Дана матрица A(N, N). Переписать элеменаты ее главной диагонали в одномерный массив Y(N) и разделить их на максимальный элемент главной диагонали.
10 | Дана матрица A(N, M). Получите Y = X1 * XN + X2 * XN-1 + ... + XN * X1 , где Xi – наибольший элемент в строке с номером i матрицы A.
11 | Найти наибольший элемент побочной диагонали заданной матрицы A(N, N) и вывести на печать всю строку, в которой он находится.
12 | Дана целочисленная матрица A(N, M). Вычислить сумму и произведение нечетных отрицательных элементов матрицы, удовлетворяющих условию | aij | < i.
13 | По трем заданным матрицам А(N, N), В(N, N) и С(N, N) построить матрицу Х того же размера, каждый элемент которой вычисляется по формуле xij = max {aij , bij , cij }.
14 | Дана матрица А(N, N) и целое P. Преобразовать матрицу по правилу: строку с номером P сделать столбцом с номером P, а столбец с номером P – строкой с номером P.
15 | В заданном массиве A(N, N) вычислить две суммы элементов, расположенных выше и ниже главной диагонали.
16 | Если в заданной матрице A(N, N) есть хотя бы один элемент, больший ста, то элементы обеих диагоналей заменить нулями.
17 | Из заданной матрицы A(N, N) удалить строку и столбец, в которых находится первый элемент, равный нулю. Полученную матрицу уплотнить. Элементы матриц просматривать слева направо и сверху вниз.
18 | В заданной целочисленной матрице A(N, M) заменить первый отрицательный элемент максимальным элементом матрицы. Если отрицательных элементов нет, то вывести соответствующий текст. Элементы матриц просматривать слева направо и сверху вниз.
19 | Дана квадpатная таблица А(N, N), элементами котоpой являются нули и единицы. Установить наличие в ней квадpата, стороны которого состоят из М единиц (M <= N) и параллельны строкам или столбцам таблицы. Если такой квадpат найдется, то нужно вывести кооpдинаты его веpхнего левого угла.
20 | Из заданной матрицы A(N, N) удалить строку, в которой находится первый отрицательный элемент. Элементы матриц просматривать слева направо и сверху вниз.
21 | Элементы заданной матрицы A(N, N) переписывать построчно в одномерный массив до тех пор, пока не встретится нулевой элемент.
22 | Проверить, удовлетворяет ли заданная матрица A(N, N) следующему условию: для всех i > 1 и для всех j > 1 верно неравенство aij >= ai-1,j + ai,j-1.
23 | Для заданной матрицы A(N, N) найти хотя бы одно k такое, что k-я строка матрицы совпадает с k-м столбцом.
24 | Задана матрица A(K, M). Найти вектор В(M), каждый элемент которого равен среднему арифметическому элементов соответствующего столбца матрицы А.
25 | Седловой точкой в матрице называется элемент, являющийся одновременно наибольшим в столбце и наименьшим в строке. Седловых точек может быть несколько (в этом случае они имеют равные значения). В матрице А(M, N) найти седловую точку и ее координаты p, q либо установить, что такой точки нет.
26 | В массиве Х(M, N) каждый элемент (кроме граничных) заменить суммой непосредственно примыкающих к нему элементов по вертикали, горизонтали и диагоналям.
27 | В каждом столбце и каждой строке матрицы Р(N, N) содержится строго по одному нулевому элементу. Перестановкой строк добиться расположения всех нулей по главной диагонали матрицы.
28 | Найти среднее арифметическое элементов каждой строки матрицы Q(N, M) и вычесть его из элементов этой строки.
29 | Найти максимальный из повторяющихся элементов матрицы А(M, N).
30 | В двумерном массиве А(M, N) найти среднее арифметическое первого столбца и количество элементов в каждом из следующих столбцов, превышающих среднее арифметическое предыдущего.


ТЕМА 12. СТРУКТУРЫ, ОБЪЕДИНЕНИЯ, БИТОВЫЕ ПОЛЯ, ПЕРЕЧИСЛЕНИЯ

Изучите теоретический материал главы 13 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое структура? Приведите пример.

2. Что означает описание struct date d;?

3. Дана структура, инициализируйте ее.

4. Перечислите способы доступа к элементам структур.

5. Что такое вложенные структуры?

6. Что такое перечисления? Приведите пример.

7. Что такое битовые поля? Приведите пример.

8. Что такое объединения? Приведите пример.

9. Перечислите свойства структур.

10. Перечислите свойства объединений.

11. Перечислите свойства битовых полей.

12. Как обратиться к элементу структуры struct date *pd;?

13. Если struct date *pd;, как по другому можно обратиться к (*pd).year ?

14. Что может быть за конструкция, если мы обращаемся p -> q -> memb?

15. Если

struct

{

int x;

int *y;

} *p;

что делает выражение ++p -> x?

16. Определите массив структур.

17. Инициализируйте массив структур.

struct key

{

char *keyword;

int  keycount;

}

keytab[] =

18. Что означает следующее определение:

struct

{

unsigned is_keyword : 1;

unsigned is_extern : 1;

unsigned is_static : 1;

} flags;


Задача 12.1

Определить структурированный тип, набор функций (в виде меню) для работы с массивом структур.

1. В структурированной переменной предусмотреть способ отметки ее как не содержащей данных (т. е. «пустой»).

2. Функции должны работать с массивом структур или с отдельной структурой через указатели, а также при необходимости возвращать указатель на структуру. В перечень обязательных функций входят:

– «очистка» структурированных переменных;

– поиск свободной структурированной переменной;

– ввод элементов (полей) структуры с клавиатуры;

– вывод элементов (полей) структуры с клавиатуры;

– поиск в массиве структуры c минимальным значением заданного поля.

3. Дополнительные функции:

– сортировка массива структур в порядке возрастания заданного поля (при сортировке разрешается присваивание структурированных переменных);

– удаление заданного элемента;

– изменение (редактирование) заданного элемента.

4. Интерфейс пользователя осуществить в виде командного процессора:

1 – загрузить данные;

2 – вывести на экран ... .

База данных «студент». Ф. И. О., дата поступления, дата отчисления. Выбор по произвольному шаблону.

Листинг задачи 12.1

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <windows.h>

#include  <locale>

#define nam 30                        //название пункта

#define zap 30                        //кол-во структур

int er;                               //переключатель

using namespace std;

struct student

{

char name[nam];                   //продолжительность

int date;                         //время

int dat;                          //время

};

struct student mas_student[zap];

struct student bad;

int sch = 0;                          //счетчик полных записей

void enter_new()                      //функция ввода новой

//структуры

{

if (sch < zap)

{

cout << "Запись номер";

cout << sch + 1;

cout << endl << "Введите имя" << endl;

cin >> mas_student[sch].name;

cout << "Введите дату поступления" << endl;

cin >> mas_student[sch].date;

cout << "Введите дату отчисления " << endl;

cin >> mas_student[sch].dat;

sch++;

}

else cout << "Введено максимальное кол-во записей";

cout << "Что делать дальше?" << endl;

cin >> er;

}

void del()                            //функция удаления записи

{

int d;                            //номер записи, которую

//нужно удалить

cout << "\nВведите номер записи, которую необходимо удалить"

<< endl;

cout << "Если необходимо удалить все записи, нажмите '99'"

<< endl;

cin >> d;

if (d != 99)

{

for (int de_1 = (d - 1); de_1 < sch;de_1++)

mas_student[de_1] = mas_student[de_1 + 1];

sch = sch - 1;

}

if (d == 99)

for (int i = 0; i < zap; i++)

mas_student[i] = bad;

cout << "Что делать дальше?" << endl;

cin >> er;

}

void change()

{

int c;                             //номер записи, которую

//нужно изменить

int per;

cout << "\nВведите номер записи" << endl;

cin >> c;

do

{

cout << "Введите: " << endl;

cout << "1 - для изменения имени" << endl;

cout << "2 - для изменения даты поступления" << endl;

cout << "3 - для изменения даты отчисления" << endl;

cout << "4 - для прекращения\n";

cin >> per;

switch (per)

{

case 1: cout << "Введите новое имя ";

cin >> mas_student[c - 1].name;

break;

case 2: cout << "Введите новую дату поступления ";

cin >> mas_student[c - 1].date;

break;

case 3: cout << "Введите новое дату отчисления ";

cin >> mas_student[c - 1].dat;

break;

cin >> per;

}

} while (per != 4);

cout << "Что делать дальше?" << endl;

cin >> er;

}

void out()                            //функция вывода записей

{

int sw;                           //переключатель

int o;                            //номер структуры,

//которую надо вывести

cout << endl << "Введите: " << endl;

cout << "1 - если хотите вывести какую-либо запись" << endl;

cout << "2 - если хотите вывести все записи" << endl;

cin >> sw;

if (sw == 1)

{

cout << "Введите номер записи, которую нужно вывести" << endl;

cin >> o;

cout << endl;

cout << "Имя";

cout << mas_student[o - 1].name << endl;

cout << "Дату поступления";

cout << mas_student[o - 1].date << endl;

cout << "Дату отчисления";

cout << mas_student[o - 1].dat << endl;

}

if (sw == 2)

{   for (int i = 0; i < sw; i++)

{

cout << "Имя";

cout << mas_student[i].name << endl;

cout << "Дату поступления";

cout << mas_student[i].date << endl;

cout << "Дату отчисления";

cout << mas_student[i].dat << endl;

}

}

cout << "Что делать дальше?" << endl;

cin >> er;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_CTYPE, "Russian");

cout << "Записей пока нет" << endl;

cout << "Введите:" << endl;

cout << "1 - для удаления записи" << endl;

cout << "2 - для ввода новой записи" << endl;

cout << "3 - для изменения записи" << endl;

cout << "4 - для вывода записи(ей)" << endl;

cout << "5 - для выхода" << endl;

cin >> er;

do

{

switch(er)

{

case 1: del();       break;

case 2: enter_new(); break;

case 3: change();    break;

case 4: out();       break;

}

}  while (er != 5);

}

Результат выполнения задачи 12.1


Задача 12.2

Определить структурированный тип, набор функций (в виде меню) для работы с массивом структур. Создать разделы «Читатели», «Ф. И. О», «Номер читательского билета», «Название книги», «Срок возврата книги». В структурированной переменной предусмотреть способ отметки ее как не содержащей данных (т. е. «пустой»). Функции должны работать с массивом структур или с отдельной структурой через указатели, а также при необходимости возвращать указатель на структуру.

Листинг задачи 12.2

#include "stdafx.h"

#include <iostream>

#include "locale"

#include <stdio.h>

#include <algorithm>

#define Max 200

using namespace std;

//описание структуры

struct LIBRARY

{

bool work;

char familia[Max], name[Max], Surname[Max], book[Max];

int number, cost;

LIBRARY()

{

work = false;

};

}

library[Max];

//глобальные переменные:

int Size = -1;

//функция удаления

//элементов

void clear (int n)

{

if (n < Max)

{

library[n].work = false;

printf("Элемент %d был удален\n", n);

}

else printf("Число слишком большое\n");

}

//функция поиска свободного

//элемента

void find ()

{

int i;

for (i = 0; i < Max && library[i].work; i++);

i == Max ? printf("Не найдено свободных ячеек\n") : printf("Свободная ячейка: %d\n", i);

}

//функция ввода данных

void input()

{

int pos;

for (pos = 0; pos < Max && library[pos].work; pos++);

if (pos == Max)

{

printf("Не найдено свободных ячеек\n");

return;

}

library[pos].work = true;

cout << "Введите данные нового абонента:" << endl;

cout << "Введите фамилию абонента" << endl;

cin >> library[pos].familia;

cout << "Введите имя абонента" << endl;

cin >> library[pos].name;

cout << "Введите отчество абонента" << endl;

cin >> library[pos].Surname;

cout << "Введите номер читательского билета" << endl;

scanf_s("%d", &library[pos].number);

cout << "Введите название книги (без пробелов)" << endl;

cin >> library[pos].book;

cout << "Срок возврата (дней) " << endl;

scanf_s("%d", &library[pos].cost);

Size++;

}

//функция вывода

void output()

{

for (int i = 0; i < Max; i++)

if (library[i].work)

{

cout << '\n'<< "Фамилия                     : "

<< library[i].familia;

cout << '\n' << "Имя                         : "

<< library[i].name;

cout << '\n' << "Отчество                    : "

<< library[i].Surname;

cout << '\n' << "Номер билета                : "

<< library[i].number;

cout << '\n' << "Название книги              : "

<< library[i].book;

cout << '\n' << "Срок возврата книги         : "

<< library[i].cost << '\n';

}

//printf("%s %s %s %d %s %d\n", library[i].familia, library[i].name, library[i].Surname, library[i].number, library[i].book, library[i].cost);

}

//функция сортировки

void sort ()

{

int f;

int date = library[0].number;

int buf;

cout << "Введите:" << endl;

cout << "1 - для поиска по минимальному номеру читательского билета" << endl;

cout << "0 - для поиска по минимальному количеству дней возврата книги" << endl;

cin >> f;

if (f == 1)

{

for (int i = 0; i < Max; i++)

{

if (library[i].work)

if (library[i].number <= date)

{

date = library[i].number;

buf = i;

}

}

cout << "Минимальный номер читательского билета:" << "   " << library[buf].number << endl;

}

if (f == 0)

{

int namef = library[0].cost;

for (int i = 0; i < Max; i++)

{

if (library[i].work)

if (library[i].cost <= namef)

{

namef = library[i].cost;

buf = i;

}

}

cout << "Минимальное количество дней до возврата книги:" << "   " << library[buf].cost << endl;

}

}

//функция удаления элементов

void del(int n)

{

if (n >= 0 && n < Max)

if (library[n].work)

library[n].work = false;

for (int i = n; i < Max - 1; i++)

swap(library[i], library[i + 1]);

Size--;

cout << "Элемент успешно удален" << endl;

}

//функция изменения данных

void edit(int n)

{

if (n >= 0 && n < Max)

if (!library[n].work)

cout << "Данный элемент не существует" << endl;

else

{

cout << "Введите фамилию абонента" << endl;

cin >> library[n].familia;

cout << "Введите имя абонента" << endl;

cin >> library[n].name;

cout << "Введите отчество абонента" << endl;

cin >> library[n].Surname;

cout << "Введите номер читательского билета" << endl;

scanf_s("%d", &library[n].number);

cout << "Введите название книг (без пробелов)" << endl;

cin >> library[n].book;

cout << "Срок возврата (дней) " << endl;

scanf_s("%d", &library[n].cost);

}

else cout << "Данного элемента не существует" << endl;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "rus");

locale loc("Russian_Russia");

cout << "Вас приветствует электронная библиотека ОАО 'ИСиТ'" << endl;

char er;

do

{

cout << "Выберите один из пунктов меню и введите соответствующую цифру:" << endl;

cout << "________________________________________" << endl;

cout << "1.  Очистка переменной." << endl;

cout << "2.  Поиск свободной переменной." << endl;

cout << "3.  Ввод элементов в базу данных." << endl;

cout << "4.  Вывод элементов." << endl;

cout << "5.  Сортировка элементов." << endl;

cout << "6.  Удаление заданного элемента." << endl;

cout << "7.  Изменение выбранного элемента." << endl;

cout << "0.  Выход из программы." << endl;

er = getchar();

if (er == '0') break;

int n;

switch(er)

{

case '1':

cout << "Введите номер элемента" << endl;

scanf_s("%d", &n);

clear(n);

break;

case '2':

find();

break;

case '3':

input();

break;

case '4':

output();

break;

case '5':

sort();

break;

case '6':

cout << "Введите номер элемента" << endl;

scanf_s("%d", &n);

del(n);

break;

case '7':

cout << "Введите номер элемента" << endl;

scanf_s("%d", &n);

edit(n);

break;

}

} while (true);

return 0;

}

Результат выполнения задачи 12.2


Задачи для самостоятельного решения

Определить структурированный тип, набор функций (в виде меню) для работы с массивом структур. В структурированной переменной предусмотреть способ отметки ее как не содержащей данных (т. е. «пустой»). Функции должны работать с массивом структур или с отдельной структурой через указатели, а также при необходимости возвращать указатель на структуру.

1. В перечень обязательных функций входят:

– «очистка» структурированных переменных;

– поиск свободной структурированной переменной;

– ввод элементов (полей) структуры с клавиатуры;

– вывод элементов (полей) структуры с клавиатуры;

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

2. Дополнительные функции:

– сортировка массива структур в порядке возрастания заданного поля (при сортировке разрешается присваивание структурированных переменных);

– удаление заданного элемента;

– изменение (редактирование) заданного элемента.

3. Интерфейс пользователя осуществить в виде командного процессора:

1 – загрузить данные;

2 – вывести на экран ... .

int menu_code;

[Вызов процедуры вывода меню]

do

{

printf("command: ");

scanf("%d", &menu_code);

switch (menu_code)

{

case 1:

[Вызов функции в случае выбора меню 1]

break;

case 2:

[Вызов функции в случае выбора меню 2]

break;

..............................

case 5:

[Вызов функции в случае выбора меню 5]

break;

}

[Вызов процедуры вывода меню]

} while (menu_code != 5);

1

Горожанин. Ф. И. О., дата рождения, адрес, пол (м, ж). Выборка по полу и году рождения.

Дату рождения реализовать с помощью битового поля.

Пол реализовать с помощью перечисления.

2

База данных «Гостиница». Список гостей: паспортные данные, даты приезда и отъезда, номер, тип размещения (люкс, одноместный, двухместный, трехместный, апартаменты). Поиск гостя по дате приезда или по фамилии.

Даты приезда и отъезда реализовать с помощью битового поля.

Тип размещения реализовать с помощью перечисления.

3

Клиенты банка. Ф. И. О., тип счета (долгосрочный, льготный и т. д.), номер счета, сумма на счете, дата последнего изменения. Выбор по номеру счета, по диапазону суммы (<100, >100).

Дату реализовать с помощью битового поля.

Тип счета реализовать с помощью перечисления.

4

Личная библиотека. Картотека домашней библиотеки: выходные данные книги (авторы, название, издательство и т. д.), раздел библиотеки (специальная литература, хобби, домашнее хозяйство, беллетристика и т. д.), происхождение (покупка, кража, подарок) и наличие книги в данный момент. Выбор книг по автору, году; инвентаризация библиотеки (вывод всего списка книг по категориям).

Происхождение реализовать с помощью перечисления.

5

Ломбард. База хранимых товаров и недвижимости: анкетные данные клиента; наименование товара; оценочная стоимость; сумма, выданная под залог; дата сдачи; срок хранения. Выбор товаров по истечении срока хранения, по наименованию товара.

Дату сдачи реализовать с помощью битового поля.

6

Склад. Наименование товара, цена, количество, процент торговой надбавки (5, 10, 15, 20, 30, 35). Выбор по наименованию, цене. Вывод всего списка товаров на складе с расчетом сумм.

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

7

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

Дату вылета реализовать с помощью битового поля.

Пункт назначения реализовать с помощью перечисления.

8

Ученик. Ф. И. О., класс (цифра + буква), предметы, оценки, средний балл. Выбор по фамилии, выбор по среднему баллу.

Класс реализовать с помощью битового поля.

Предметы реализовать через перечисление.

9

База данных «Студент». Ф. И. О., дата поступления, специальность, группа, факультет, дата отчисления, средний балл. Выбор по году поступления, фамилии, среднему баллу, группе.

Дату поступления и отчисления реализовать с помощью битового поля.

Факультет реализовать с помощью перечисления.

10

Справочник работника ГИБДД. Марка, цвет, заводской и бортовой номера, дата выпуска, особенности конструкции и окраски, дата последнего техосмотра транспортного средства (автомобиля, мотоцикла, прицепа и т. д.), паспортные данные владельца. Выбор транспортных средств по марке или номеру. Формирование приглашений на техосмотр в соответствии со сроком.

Дату выпуска реализовать с помощью битового поля.

Марку реализовать с помощью перечисления.

11

Записная книжка. Анкетные данные, адреса, телефоны, место работы или учебы, должность знакомых, коллег и родственников, характер знакомства, деловые качества и т. д. Автоматическое формирование поздравления с днем рождения (по текущей дате). Поиск по фамилии.

Дату рождения реализовать с помощью битового поля.

Характер знакомства реализовать с помощью перечисления.

12

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

Форму правления реализовать с помощью перечисления.

13

Вокзал. Номер поезда, пункт назначения, дни следования, время выбытия, время прибытия, цена. Выбор по пункту назначения, дате. Вывод расписания по времени.

Дни следования реализовать с помощью перечисления.

Время выбытия и прибытия реализовать с помощью битового поля (часы, минуты).

14

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

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

Перечень специальностей – через перечисления.

15

Преподаватели. Название экзамена, дата экзамена, фамилия преподавателя, количество оценок, оценки. Выбор по фамилии, дате экзамена.

Дату экзамена реализовать с помощью битового поля.

16

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

Даты реализовать с помощью битового поля.

Должность – с помощью перечисления.


ТЕМА 13. ФАЙЛЫ

Изучите теоретический материал главы 14 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме.

Вопросы для подготовки к тесту

1. Что такое поток, как он связан с файлом?

2. Что такое структура FILE?

3. Как открыть поток и связать его с файлом?

4. Какие существуют режимы открытия файлов?

5. Что вернет функция fopen, если файл не был открыт?

6. Какую функцию можно использовать для закрытия нескольких файлов?

7. Что такое дескриптор файла, для чего он используется в программе?

8. Приведите формат функции fread.

9. Приведите формат функции fwrite.

10. Что вернут функции fread и fwrite, если произошла ошибка чтения-записи?

11. Какие функции используются для построчного чтения-записи?

12. Поясните, как работает функция ftell?

13. Поясните, как работает функция fseek?


Задача 13.1

Дано число k и строковый файл с именем name1, содержащий непустые строки. Создать два новых файла: строковый с именем name2, содержащий последние k символов каждой строки исходного файла (если строка короче k символов, то она сохраняется целиком), и символьный с именем name3, содержащий k-й символ каждой строки (если строка короче k, то в файл name3 записывается пробел).

Листинг задачи 13.1

#include "stdafx.h"

#include <string.h>

#include <stdio.h>

#include <fstream>

using namespace std;

int main()

{

FILE *fin = fopen("name1.txt", "rt");

ofstream fout1("name2.txt");

ofstream fout2("name3.txt");

printf("Vvedite 4islo k\n");

int k;

scanf("%d", &k);

while (!feof(fin))

{

char s[255] = "";

fgets(s, 254, fin);

if (strlen(s) <= k) fout1 << s;

else

for (int i = strlen(s) - k - 1; i < strlen(s); i++)

fout1 << s[i];

if (strlen(s) < k) fout2 << " " << endl;

else fout2 << s[k - 1] << endl;

}

fclose(fin);

fout1.close();

fout2.close();

return 0;

}


Задача 13.2

Дан строковый файл с именем nameS, содержащий даты в формате «день/месяц/год», причем под день и месяц отводится по две позиции, а под год – четыре. Создать файлы целых чисел с именами name1, name2, name3, содержащие соответственно значения [дней и месяцев]; [дней и лет]; [месяцев и лет] для дат из исходного строкового файла (в том же порядке).

Листинг задачи 13.2

#include "stdafx.h"

#include <string>

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <locale>

#include <conio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "rus");

cout << "Внимание идет работа с файлами" << endl;

FILE *f = fopen("nameS.txt", "a+");

ofstream fout1("nameS1.txt");

ofstream fout2("nameS2.txt");

ofstream fout3("nameS3.txt");

fout1 << "Месяц/Год" << endl;

fout2 << "День/Месяц" << endl;

fout3 << "День/Год" << endl;

while (!feof(f))

{

char s[200];

fgets(s, 20, f);

for (int i =3; i <= 9; i++)

fout3 << s[i];

fout3 << endl;

for (int i = 0; i <= 4; i++)

fout2 << s[i];

fout2 << endl;

for (int i = 0; i <= 9; i++)

{

if( i < 3 || i > 5)

fout1 << s[i];

}

fout1 << endl;

}

fclose(f);

fout1.close();

fout2.close();

fout3.close();

cout << "Работа с файлами успешно завершена" << endl;

getch();

return 0;

}

Результат выполнения задачи 13.2


ВОПРОСЫ К ЗАЧЕТУ

1. Алгоритм и его свойства. Разновидности структур алгоритмов.

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

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

4. Классификация языков программирования.

5. Состав и структура языка программирования C/С++. Общая структура программы.

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. Файлы.


II семестр

ТЕМА 1. СЛОЖНОСТЬ АЛГОРИТМОВ. АЛГОРИТМЫ СОРТИРОВКИ

Изучите теоретический материал главы 15 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Какие сортировки существуют?

2. Какие из перечисленных сортировок не требуют резерва памяти:

a) Шелла;

b) пирамидальная;

c) Хоара;

d) вставка?

3. Какие свойства характеризуют сортировку методом «пузырька»:

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

b) n(n – 1) / 2 сравнений и n(n – 1) / 2 перестановок;

c) cреднее число сравнений и перестановок имеет порядок n2;

d) мax число перестановок (n – 1)?

4. Какие свойства характеризуют сортировку методом вставки:

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

b) (n – 1) / 2 сравнений и n(n – 1) / 2 перестановок;

c) число сравнений максимальное (n2 + n) / 2 – 1;

d) количество пересылок максимальное (n2 + 3n – 4) / 2?

5. Какие свойства характеризуют шейкер-сортировку:

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

b) (n – 1) / 2 сравнений и n(n – 1) / 2 перестановок;

c) число сравнений максимальное (n2 + n) / 2 – 1;

d) количество пересылок максимальное (n2 + 3n – 4) / 2?

6. Какие свойства характеризуют сортировку Шелла:

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

b) каждая часть сортируется отдельно любым алгоритмом;

c) число сравнений максимальное (n2 + n) / 2 – 1;

d) выбирается меньший шаг и повтор?

7. Какие свойства характеризуют пирамидальную сортировку:

a) новый элемент Х помещаем в вершину дерева;

b) после каждого шага очередной элемент берется из вершины пирамиды;

c) cортировка не требует дополнительной памяти;

d) анализируется элемент слева и элемент справа – выбирается наибольший?

8. Определить алгоритм сортировки.

void    sort(int A[], int count)

{

int j, k, l, r, x;

l = 2; r = count; k = count;

do

{for (j = r; j >= 1; j--)

{

if (A[j - 1])

{

x = A[j - 1];  A[j - 1] = A[j];  A[j] = x;

k = j;

}

l = k + 1;

for (j = l; j <= r; j++)

if (A[j - 1] > A[j])

{

x = A[j - 1];

A[j - 1] = A[j];

A[j] = x;

k = j;

}

r = k - 1;

}

} while l <= r

}

9. В чем заключается правило сумм, используемое при оценке трудоемкости?

10. Пусть есть два фрагмента программы с временами выполнения соответственно О(n2), О(n3). Какой порядок имеет верхняя асимптотическая оценка трудоемкости алгоритма последовательного выполнения двух фрагментов?

11. Пусть имеются два алгоритма с разными степенями роста сложности. Какой алгоритм будет более эффективным для n > 1000?

12. Истинно ли O(1) < O(log2n)?

13. Истинно ли O(n2) > O(n3)?

14. Равенство T(n) = Θ(f(n)) выполняется тогда и только тогда, когда:

T(n) = O(f(n)) и T(n) = Ω (f(n));

T(n) = O(f(n)) или T(n) = Ω (f(n));

T(n) < O(f(n)) и T(n) > Ω (f(n)).

15. Какова сложность алгоритма последовательного поиска в наихудшем случае?

16. По способу выбора элементов сортировки делятся на … .

17. По тексту программы определите алгоритм

void F1(int arr[], int n)

{

int temp;

for(int i = n - 1; i > 0; --i)

                                    //для каждого элемента массива

for (int j = 0; j < i; ++j)

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

                                    //процесс всплытия

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

18. По описанию определите алгоритм сортировки. Отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве. Далее находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.

19. По тексту программы определите вид сортировки

void Sort(int arr[], int n)

{

int i = 0, j = n;

int temp, p;

p = arr[n >> 1];

                                   //медиана - средний элемент

//p
= arr[i];

        //медиана - первый
элемент

//p = x[i + rand() % n - i];      //медиана - случайный элемент

do

{                                  //процедура разделения

while (arr[i] < p) i++;

while (arr[j] > p) j--;

if (i <= j)          //обмен

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++;

j--;

}

}

while (i <= j);

                                   //если есть что сортировать

if (j > 0) Sort(arr, j);

                                  //рекурсивный вызов для

                                  //левой части

if (n > i) Sort(arr + i, n - i);

                                  //рекурсивный вызов для

                                  //правой части

}

20. Для пирамидальной сортировки была построена пирамида, представленная на рисунке:

Правильно ли построена пирамида?

21. По данному описанию сортировки определите алгоритм. Сортировка основана на том, что все числа упорядочиваются при помощи устойчивой сортировки сначала по младшему разряду, затем – по всем остальным в порядке их возрастания.


Примеры решения задач

#pragma once

namespace my_sort

{

//=================================================================

//  Быстрая сортировка с итерационным циклом вычисления медианы

//=================================================================

//     Параметры: m[] - массив чисел

//                last - номер последнего элемента сортируемой части

//     Результат: ссылка на уже отсортированный массив

int* QuickSortIteretion(int m[], int last);

//=================================================================

//     Шейкерная сортировка с изменением направления в одном цикле

//=================================================================

//     Параметры: m[] - массив чисел

//               last - номер последнего элемента массива

//     Результат: ссылка на уже отсортированный массив

int* ShakerSort(int m[], int last);

//=================================================================

//     Сортировка циклическим слиянием с двумя входными массивами

//=================================================================

//     Параметры: b1 - первый массив чисел

//               b2 - второй массив чисел

//               size1 - размер первого массива

//               size2 - размер второго массива

//     Результат: ссылка на уже отсортированный массив

int* SortCycleMerge2M(int m[], int b1[], int b2[], int size1, int size2);

//=================================================================

//     Сортировка методом «пузырька»

//=================================================================

//     Параметры: m[] - массив чисел

//               size - размер массива

//     Результат: ссылка на  уже отсортированный массив

int* SortBuble(int m[], int size);

//=================================================================

//     Сортировка выбором

//=================================================================

//     Параметры: m[] - размер массива

//               size - размер массива

//     Результат: ссылка на уже отсортированный массив

int* SortSelect(int m[], int size);

}

#include "stdafx.h"

#include <stdlib.h>

#include "MySort.h"

namespace my_sort

{

//=================================================================

//  Быстрая сортировка с итерационным циклом вычисления медианы

//=================================================================

//     Параметры: m[] - массив чисел

//                last - номер последнего элемента сортируемой части

//     Результат: ссылка на уже отсортированный массив

int* QuickSortIteretion(int m[], int last)

{

       int first = 0, buf, k = 1, i, j, mode;

       while(k != 0)

       {

            k = 0;

            for (i = first, j = last, mode = 1;

i != j; mode > 0 ? j-- : i++)

            if (m[i] > m[j])

            {

                 buf = m[i]; m[i] = m[j]; m[j] = buf;

                 k++;

                 mode =- mode;

            }

            if ((first + last) / 2 > i)first = i + 1;

            else last = i - 1;

       }

       return m;

}

//=================================================================

//     Шейкерная сортировка с изменением направления в одном цикле

//=================================================================

//     Параметры: m[] - массив чисел

//               last - номер последнего элемента массива

//     Результат: ссылка на уже отсортированный массив

int* ShakerSort(int m[], int last)

{

int buf, first = 0, mode = 1;

for (; first < last; mode > 0 ? ++first : --last)

{

for (int i = mode > 0 ? first : last;

mode > 0 ? (i < last) : (i > first);

mode > 0 ? ++i : --i)

{

if ((m[i] >m [i + 1]) && (mode > 0))

{

buf = m[i];

m[i] = m[i+1];

m[i+1] = buf;

}

if ((m[i] < m[i - 1]) && (mode < 0))

{

buf = m[i];

m[i] = m[i-1];

m[i-1] = buf;

}

}

mode =- mode;

}

return m;

}

//=================================================================

//     Сортировка циклическим слиянием с двумя входными массивами

//=================================================================

//     Параметры: b1 - первый массив чисел

//               b2 - второй массив чисел

//               size1 - размер первого массива

//               size2 - размер второго массива

//     Результат: ссылка на уже отсортированный массив

int* SortCycleMerge2M(int m[], int n1[], int n2[], int size1, int size2)

{

int i, i1, i2, s, k, size = size1 + size2;

int *b1 = new int[size];

int *b2 = new int[size];

for (int j = 0; j < size1; j++)

*(b1 + j) = *(n1 + j);

for (int j = 0; j < size2; j++)

*(b2 + j) = *(n2 + j);

for (s = 1; ;)

{

i1 = i2 = 0;

for (i = 0, k = 0; i < size; i++)

{

if (i1 == s && i2 == s)

k += s, i1 = 0, i2 = 0;

if (i1 == s || k + i1 == size1)

m[i] = b2[k + i2++];

else if (i2 == s || k + i2 == size2)

m[i] = b1[k + i1++];

else if (b1[k + i1] < b2[k + i2])

m[i] = b1[k + i1++];

else m[i] = b2[k + i2++];

}

s *= 2;

int ssize = size / s;

if (size % s != 0) ssize++;

size1 = ssize / 2*s;

size2 = size - size1;

if (size1 <= 0 || size2 <= 0) break;

for (i = 0; i < size1; i++) b1[i] = m[i];

for (i = 0; i < size2; i++) b2[i] = m[i + size1];

}

return m;

}

//=================================================================

//     Сортировка методом «пузырька»

//=================================================================

//     Параметры: m[] - массив чисел

//               size - размер массива

//     Результат: ссылка на  уже отсортированный массив

int* SortBuble(int m[], int size)

{

int buf;

for (int i = 0; i < size; i++)

for (int j = 0; j < size – i - 1; j++)

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

{

buf = m[j];

m[j] = m[j + 1];

m[j + 1]=buf;

}

return m;

}

//=================================================================

//     Сортировка выбором

//=================================================================

//     Параметры: m[] - размер массива

//               size - размер массива

//     Результат: ссылка на уже отсортированный массив

int* SortSelect(int m[], int size)

{

for (int j = 0; j < size - 1; j++)

{

int min = m[j], imin = j;

for (int i = j + 1; i < size; i++)

if (m[i] < min)

{

min = m[i];

imin = i;

}

m[imin] = m[j];

m[j] = min;

}

return m;

}

}

#include "stdafx.h"

#include "MySort.h"

#include <ctime>

#include <locale>

#include <vector>

#include <algorithm>

#include <iostream>

int GetRandKey()

{

int rmin = 0;

int rmax = 100000;

return (int)(((double) rand()/(double) RAND_MAX) * (rmax - rmin) + rmin);

}

int* GetArray(int* m, const int size)

{

srand((unsigned)time(NULL));

for (int i = 0; i < size; i++)

*(m + i) = GetRandKey();

return m;

}

void PrintArray(int m[], const int size)

{

for (int i = 0; i < size; i++)

std::cout << *(m + i) << "  ";

std::cout << "\n";

}

int compare_int(int *a, int *b)

{

return(*a - *b);

}

void SortArray(int size)

{

std::cout << "Исследование сортировок\n\n";

std::cout << "Количество элементов: " << size << "\n\n";

clock_t begin_qi = 0, end_qi = 0;

clock_t begin_shs = 0, end_shs = 0;

clock_t begin_sb = 0, end_sb = 0;

clock_t begin_ss = 0, end_ss = 0;

clock_t begin_qs = 0, end_qs = 0;

clock_t begin_s = 0, end_s = 0;

int* m = new int[size];

//=================================================================

//     Быстрая сортировка с итерационным циклом вычисления медианы

//=================================================================

GetArray(m, size);

begin_qi = clock();

my_sort::QuickSortIteretion(m, size - 1);

end_qi = clock();

//=================================================================

//     Шейкерная сортировка с изменением направления в одном цикле

//=================================================================

GetArray(m, size);

begin_shs = clock();

my_sort::ShakerSort(m, size - 1);

end_shs = clock();

//=================================================================

//     Сортировка методом «пузырька»

//=================================================================

GetArray(m, size);

begin_sb = clock();

my_sort::SortBuble(m, size);

end_sb = clock();

//=================================================================

//     Сортировка выбором

//=================================================================

GetArray(m, size);

begin_ss = clock();

my_sort::SortSelect(m, size);

end_ss = clock();

//=================================================================

//     Стандартная функция qsort

//=================================================================

GetArray(m, size);

begin_qs = clock();

qsort(m, size, sizeof(int),(int (*) (const void *, const void *)) compare_int);

end_qs = clock();

//=================================================================

//     Стандартная функция sort

//=================================================================     GetArray(m, size);

begin_s = clock();

std::sort(m, m + size);

end_s = clock();

std::cout << "Время выполнения: \n\n";

std::cout << "Быстрая сортировка с итерационным циклом вычисления медианы: \t" << (double)(end_qi - begin_qi) / (double)CLOCKS_PER_SEC << std::endl;

std::cout << "Шейкерная сортировка с изменением направления в одном цикле: \t" << (double)(end_shs - begin_shs) / (double)CLOCKS_PER_SEC << std::endl;

std::cout << "Сортировка методом пузырька: \t\t\t\t\t" << (double)(end_sb - begin_sb) / (double)CLOCKS_PER_SEC << std::endl;

std::cout << "Сортировка выбором: \t\t\t\t\t\t" << (double)(end_ss - begin_ss) / (double)CLOCKS_PER_SEC << std::endl;

std::cout << "Стандартная функция qsort: \t\t\t\t\t" << (double)(end_qs - begin_qs) / (double)CLOCKS_PER_SEC << std::endl;

std::cout << "Стандартная функция sort: \t\t\t\t\t" << (double)(end_s - begin_s) / (double)CLOCKS_PER_SEC << std::endl;

delete [] m;

}

void SortMergeArray(int size)

{

//=================================================================

//     Сортировка циклическим слиянием с двумя входными массивами

//================================================================

int* n = new int[2 * size];

int* k = new int[2 * size];

int* l = new int[2 * size];

clock_t begin_sc = 0, end_sc = 0;

GetArray(k, size);

GetArray(l, size);

begin_sc = clock();

my_sort::SortCycleMerge2M(n, k, l, size, size);

end_sc = clock();

std::cout << "\n\nКоличество элементов: 2х" << size << "\n\n";

std::cout << "Время выполнения: \n\n";

std::cout << "Сортировка циклическим слиянием с двумя входными массивами: \t" << (double)(end_sc - begin_sc) / (double)CLOCKS_PER_SEC << std::endl;

delete [] k;

delete [] l;

delete [] n;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL,"rus");

//=================================================================

//     Проверка работы сортировочных функций

//=================================================================

std::cout << "Проверка работы сортировочных функций\n\n";

int a[] = {1,2,3,4,5,0,7,5,2};

int b[] = {5,4,3,2,1};

int c[] = {2,4,6,1,3,5,9};

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

int e[] = {6,5,4,7,9,2,8};

int f[] = {0,3,1,7,2,1,5};

int g[sizeof(e) / sizeof(int) + sizeof(f) / sizeof(int)];

my_sort::QuickSortIteretion(a, sizeof(a) / sizeof(int) - 1);

my_sort::ShakerSort(b, sizeof(b) / sizeof(int) - 1);

my_sort::SortBuble(c, sizeof(c) / sizeof(int));

my_sort::SortSelect(d, sizeof(d) / sizeof(int));

my_sort::SortCycleMerge2M(g, e, f, sizeof(e) / sizeof(int), sizeof(f) / sizeof(int));

PrintArray(a, sizeof(a) / sizeof(int));

PrintArray(b, sizeof(b) / sizeof(int));

PrintArray(c, sizeof(c) / sizeof(int));

PrintArray(d, sizeof(d) / sizeof(int));

PrintArray(g, sizeof(g) / sizeof(int));

system("Pause");

//=================================================================

//     Исследование сортировок

//=================================================================

system("cls");

SortArray(100000);

SortMergeArray(50000);

system("Pause");

return 0;

}


Задачи для самостоятельного решения

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

1

Сортировка Шелла. Частичную сортировку с определенным шагом, начиная с заданного элемента, оформить в виде функции. Алгоритм частичной сортировки – вставка погружением.

Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр «направление движения» (+1/–1) и меняя местами нижнюю и верхнюю границы просмотра.

2

Сортировка методом «пузырька».

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

3

Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр «направление движения» (+1/–1) и меняя местами нижнюю и верхнюю границы просмотра.

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

4

«Быстрая» сортировка с итерационным циклом вычисления медианы. Для заданного интервала массива, в котором производится разделение, ищется медиана обычным способом. Затем выбирается та часть интервала между границей и медианой, в которой находится середина исходного интервала, и процесс повторяется.

Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.

5

Сортировка подсчетом. Выходной массив заполняется значениями «–1». Затем для каждого элемента определяется его место в выходном массиве подсчетом количества элементов, строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений «–1». После чего оставшиеся в выходном массиве позиции со значением «–1» заполняются копией предыдущего значения.

Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.

6

Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.

Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр «направление движения» (+1/–1) и меняя местами нижнюю и верхнюю границы просмотра.

7

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

Сортировка методом «пузырька».

8

Сортировка Хоара.

Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр «направление движения» (+1/–1) и меняя местами нижнюю и верхнюю границы просмотра.

9

Сортировка Шелла. Частичную сортировку с определенным шагом, начиная с заданного элемента, оформить в виде функции. Алгоритм частичной сортировки – обменная (методом «пузырька»).

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

Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.

10

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

Сортировка методом «пузырька».


ТЕМА 2. РЕКУРСИЯ

Изучите теоретический материал главы 16 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме.

Вопросы для подготовки к тесту

1. Что такое рекурсия?

2. Выберите верные утверждения. Рекурсия бывает:

a) линейная;

b) двусвязная;

c) смешанная;

d) ветвящаяся;

e) гнездовая.

3. Что выполняет фрагмент программы?

int fact(int n)

{

for (int s = 1; n != 0; n--) s *= n;

return s;

}

4. Записать рекурсивную структуру данных.

5. Написать рекурсивную функцию для поиска максимального элемента в одномерном массиве.

6. Написать рекурсивную функцию для поиска минимального элемента в одномерном массиве.

7. Написать рекурсивную функцию возведения в степень.

8. Какие есть способы возврата значений из рекурсивной функции?

9. Как решается задача о Ханойских башнях?


Примеры решения задач

Задача 2.1

Для целых неотрицательных чисел n, m разрешены операции: нахождения последующего (n + 1) и предыдущего числа n - 1 (n > 0). Промоделировать с помощью рекурсивных функций операции нахождения суммы (n + m), разности (n - m), умножения (n * m), возведения в степень nm (n > 0).

Листинг задачи 2.1

#include "stdafx.h"

#include <iostream>

int plus(int a, int b)

{

if (b == 0)

return a;

else return plus(a + 1, b - 1);

}

int minus(int a,int b)

{

if (b == 0)

return a;

else return minus(a - 1, b - 1);

}

int multi(int a, int b)

{

if (b == 0)

return 0;

if (b == 1)

return a;

else return plus(multi(a, b - 1),a);

}

int power(int a, int b)

{

if(b == 0)

return 1;

if(b == 1)

return a;

else return multi(power(a, b - 1),a);

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "rus");

std::cout << "Сумма: ";

std::cout << plus(5, 7) << '\n';

std::cout << "Разность: ";

std::cout << minus(30, 13) << '\n';

std::cout << "Произведение: ";

std::cout << multi(3, 7) << '\n';

std::cout << "Возведение в степень: ";

std::cout << power(4, 2) << '\n';

system("Pause");

return 0;

}

Результат выполнения задачи 2.1


Задача 2.2

Рекурсивно описать функцию C(m, n) где 0 <= m <= n, для биноминального коэффициента Сn по следующей формуле:

Сn0 = Cnn = 1; Cnm = Cn-1m + Cn-1m-1; при 0 < m < n.

Листинг задачи 2.2

#include "stdafx.h"

#include <iostream>

int c(int n, int m)

{

if (m == 0 || m == n)     return 1;

return (c(n - 1, m) + c(n - 1, m - 1));

};

int _tmain(int argc, _TCHAR* argv[])

{

std::cout << c(5, 2);

std::cout << std::endl;

system("Pause");

return 0;

}

Результат выполнения задачи 2.2


ТЕМА 3. АБСТРАКТНЫЙ ТИП ДАННЫХ. СПИСКИ

Изучите теоретический материал главы 17 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое линейный список?

2. Выберите свойства, которые характерны для динамических структур:

a) отсутствие физической смежности элементов;

b) физическая смежность элементов;

c) непостоянство и непредсказуемость размера (числа элементов) структуры в процессе ее обработки;

d) фиксированное число элементов структуры;

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

3. Какие операции могут быть выполнены со списком?

4. Что выполняет фрагмент программы?

bool Object::Copy(const Object& from)

{

bool rc = true;

Element* e = Head, *el;

while (e != NULL)

{

el = e -> Next;

rc = Delete(e);

e = el;

}

rc = Append(from);

return rc;

}

5. Верно ли, что при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей?

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

7. От чего зависит последовательность обхода списка?

8. Если p – текущий элемент списка, то

p -> pred -> next = p -> next;

означает:

a) исключение текущего элемента списка (если он не первый);

b) включение после текущего элемента;

c) включение в конец непустого списка.

9. Если p – текущий элемент списка, то

pnew -> next = p -> next;

p -> next = pnew;

означает:

a) исключение текущего элемента списка (если он не первый);

b) включение pnew после текущего элемента;

c) включение в конец непустого списка.

10. Пусть задана следующая структура данных:

struct List

{

int     val;

list     *next;

}

a = {0, NULL}, b = {1, &a}, c = {2, &b}, *ph = &c;

Какое число содержит последний элемент списка?

11. Пусть задана следующая структура данных:

struct List

{

int     val;

list     *next;

}

a = {0, NULL}, b = {1, &a}, c = {2, &b}, *ph = &c;

Сколько элементов содержит список?

12. Если ph – заголовок списка, что выполняет функция F9?

List    F9(List *ph, int n)

{

List *pnew;

pnew = new List;

pnew -> val = n;

pnew -> next = *ph;

ph = pnew;

return ph;

}

13. Какова асимптотическая сложность операции включения элемента в начало списка при числе элементов n?

14. Определите назначение функции F10.

struct Element

{

Element*   Prev;

void*    Data;

Element* Next;

}

bool  F10(Element* e)

{

bool rc = false;

if (rc = (e != NULL))

{

if (e -> Next != NULL) e -> Next -> Prev = e -> Prev;

if (e -> Prev != NULL) e -> Prev -> Next = e -> Next;

else { Head = x -> Next; Head -> Prev = NULL; }

delete e;

}

return rc;

}

15. Что такое нелинейный разветвленный список?

16. По заданному рисунку определите выполняемую операцию.

17. По заданному рисунку определите выполняемую операцию.

18. По заданному рисунку определите выполняемую операцию.

19. Что выполняет функция F1?

struct list

{

int val;

list *next,*pred;

};

int F1(list *p)

{

int n;

for (n = 0; p != NULL; p = p -> next, n++);

return(n);

}

20. Как можно получить доступ к списку?

21. Чему равен заголовок пустого списка?

22. От чего зависит конкретный тип структуры данных (список, дерево, граф)?


Примеры решения задач

Задача 3.1

Создать однонаправленный список. Написать функции работы со списком.

Листинг задачи 3.1

List.h

struct list

{

list *next;

int  data;

bool Empti;

void InsertToBegin(int data);

list* Create(int data);

int GetLast();

int SeeLast();

void Deletelist();

void Copylist(list &head);

list();

int SeeFirst();

int GetFirst();

void DeleteKlast(int k);

void InsertToEnd(int data);

void SeeList();

int CountList();

};

List.cpp

#include "stdafx.h"

#include "list.h"

#include "iostream"

list::list()

{

this -> next = this;

this -> Empti = true;

};

void list::InsertToBegin(int data)        //вставка в начало

{

if (this -> Empti == true)

{

this -> next = this;

this -> data = data;

}

else

{

list *l = new list;

l -> next = this -> next;

l -> data = this -> data;

this -> next = l;

this -> data = data;

}

this -> Empti = false;

};

list* list::Create(int data)            //создать

{

list *s = new list;

this -> data = data;

this -> next = this;

this -> Empti = false;

return s;

};

int list::GetFirst()                    //получить первый

{

int rc;

if (this -> next == this && this -> Empti == false)

{

this -> next = NULL;

this -> Empti = true;

return this -> data;

}

list *l = this -> next;

rc = this -> data;

this -> next = l -> next;

this -> data = l -> data;

delete l;

return rc;

};

int list::SeeFirst()                   //просмотр

{

if (this -> Empti == false)

return this -> data;

else return 0;

};

void list::Deletelist()               //удалить список

{

list *l = this, *d;

if (this -> Empti == false)

{

while (l -> next != this)

{

d = l-> next;

l -> next = d -> next;

delete d;

}

}

this -> Empti = true;

};

void list::Copylist(list &head)       //копировать

{

this -> Deletelist();

list *l1 = &head, *l2 = this;

if (head.Empti == false)

{

l2 -> data = l1 -> data;

l2 > next = this;

while (l1 -> next != &head)

{

l2 -> next = new list;

l2 -> next -> data = l1 -> next -> data;

l2 -> next -> next = l2;

l1 = l1 -> next;

l2 = l2 -> next;

}

this -> Empti = false;

l2 -> next = this;

}

};

int list::GetLast()                 //получить последний

{

int rc;

if (this -> next == this)

{

this -> Empti = true;

return this -> data;

}

if (this -> next -> next == this)

{

rc = this -> next -> data;

delete this -> next;

this -> next = this;

return rc;

}

list *q = this, *q2;

if (this -> Empti == false)

while (q -> next != this)

{

q = q -> next;

if (q -> next -> next == this) q2 = q;

}

rc = q -> data;

q2 -> next = this;

delete q;

return rc;

};

int list::SeeLast()

{

list *q = this;

if (this -> Empti == false)

{

while (q -> next != this) q = q-> next;

return q -> data;

}

else return 0;

};

void list::DeleteKlast(int k)

{

list *l = this, *d;

int q = 0;

while (l -> next != this)

{

L = l -> next;

q++;

}

l = this;

while ((q-- -k) > 0) l = l -> next;

for (int i = 0; i < k; i++)

{

d = l -> next;

l -> next = d -> next;

delete d;

}

};

void list::InsertToEnd(int data)

{

list *l = this, *l2 = new list;

while (l -> next != this)

l = l -> next;

l2 -> data = data;

l2 -> next = this;

l -> next = l2;

};

void list::SeeList()

{

list *l = this;

if (l -> Empti == false)

{

while (l -> next != this)

{

std::cout << l-> data;

l = l-> next;

}

std::cout << l -> data << '\n';

}

else std::cout << "List is empty";

};

int list::CountList()

{

list *l = this;

int q = 1;

while (l -> next != this)

{

q++;

l = l-> next;

};

return q;

}

Solution.cpp

#include "stdafx.h"

#include "list.h"

#include "iostream"

int _tmain(int argc, _TCHAR* argv[])

{

list l;

l.InsertToBegin(5);

l.InsertToBegin(4);

l.InsertToBegin(3);

l.InsertToBegin(2);

l.InsertToBegin(1);

l.SeeList();

std::cout << "kol-vo" << l.CountList() << '\n';

l.DeleteKlast(3);

l.SeeList();

std::cout << "kol-vo" << l.CountList() << '\n';

std::cout << '\n' << l.GetLast();

l.SeeList();

l.Deletelist();

l.SeeList();

return 0;

}

Результат выполнения задачи 3.1


Задача 3.2

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

Листинг задачи 3.2

List.h

#pragma once

#define LISTNULL (Element*) - 1

struct Element

{

Element* Prev;

Element* Next;

void* Data;

Element(Element* prev, void* data, Element* next)

{

Prev = prev;

Data = data;

Next = next;

};

Element* GetNext()

{

return Next;

};

Element* GetPrev()

{

return Prev;

};

};

static Element* NIL = LISTNULL;

struct Object

{

Element* Head;

Object(){Head = NULL;};

Element* GetFirst(){return Head;};

Element* GetLast();

Element* Search(void* data);

Element* FindMin();

bool Insert(void* data);

bool Delete(Element* e);

bool Delete(void* data);

bool DeleteList();

bool InsertEnd(void* data);

int CountList();

};

Object Create();

#undef LISTNULL

List.cpp

#include "stdafx.h"

#include "list.h"

#include <iostream>

bool Object::Insert(void *data)

{

bool rc = 0;

if(Head == NULL)

{

Head = new Element(NULL, data, Head);

rc = 1;

}

else

{

Head = (Head -> Prev = new Element(NULL, data, Head));

rc = 1;

};

return rc;

};

Element* Object::FindMin()

{

Element* rc = Head;

Element* min = rc;

while (rc != NULL)

{

//std::cout << *(int *)rc -> Data << std::endl;

if (*(int *)min -> Data > *(int *)rc -> Data)

min -> Data = rc -> Data;

rc = rc -> GetNext();

};

return (Element *)min -> Data;

};

int Object::CountList()

{

Element* rc = Head;

int i;

for (i = 0; rc != NULL; i++)

{

rc = rc -> GetNext();

};

return i;

};

bool Object::InsertEnd(void* data)

{

Element* last = GetLast();

Last -> Next = new Element(last, data, NULL);

return true;

}

//-----------------------------------------------------------------

bool Object::DeleteList()

{

Head = NULL;

return true;

}

Element* Object::GetLast()

{

Element* e = Head, *rc = e;

while (e != NULL)

{

rc = e;

e = e -> GetNext();

}

return rc;

}

Object Create()

{

return *(new Object());

}

Solution.cpp

#include "stdafx.h"

#include <iostream>

#include "list.h"

#include <locale>

using namespace std;

struct Data

{

int val;

};

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL,"rus");

Object l1 = Create();

bool rc;

Data a[100];

Data* d;

int n, main;

Element* e;

cout << "***********ВВОД СПИСКА***************" << endl;

cout << "Кол-во элементов списка: ";

cin >> n;

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

{

cin >> a[i].val;

rc = l1.Insert(&a[i]);

}

do {

cout << "[1 для вывода min значения]" << endl;

cout << "[0 для выхода ]" << endl;

cout << endl;

cin >> main;

switch(main)

{

case 1:

cout << "Минимальное значение: "

<< *(int *)l1.FindMin() << endl;

break;

case 0:

system("Pause");

return 0;

break;

};

} while (1);

}

Результат выполнения задачи 3.2


Задачи для самостоятельного решения

1 | Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить элемент с заданным номером.
2 | Записи в линейном списке содержат ключевое поле типа *char (строка символов). Сформировать двунаправленный список. Удалить K элементов из конца списка. Добавить элемент после элемента с заданным ключом.
3 | Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить К элементов, начиная с заданного номера.
4 | Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него К элементов, начиная с заданного номера, добавить К элементов, начиная с заданного номера.
5 | Записи в линейном списке содержат ключевое поле типа int. Сформировать двунаправленный список. Удалить из него элемент с заданным номером, добавить элемент в начало списка.
6 | Сформировать двунаправленный список. Удалить из него первый элемент, добавить элемент в конец списка.
7 | Записи в линейном списке содержат ключевое поле типа *char (строка символов). Сформировать двунаправленный список. Удалить из него элемент с заданным ключом, добавить элемент с указанным номером.
8 | Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него К элементов, начиная с заданного номера, добавить элемент перед элементом с заданным ключом.
9 | Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным ключом, добавить элемент перед элементом с заданным ключом.
10 | Записи в линейном списке содержат ключевое поле типа *char (строка символов). Сформировать двунаправленный список. Удалить из него К элементов с указанными номерами. Добавить К элементов с указанными номерами.


ТЕМА 4. СТЕКИ И ОЧЕРЕДИ

Изучите теоретический материал главы 18 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. В чем отличие между стеком и очередью?

2. В чем отличие между стеком и деком?

3. Поясните работу дека.

4. Определите область использования стека в вычислительных системах.

5. Определите область использования очереди в вычислительных системах.

6. Какие операции могут быть выполнены с очередью?

7. Какие операции могут быть выполнены со стеком?

8. Что выполняет данная функция?

int     sp, LIFO[100];

int     lst, fst, FIFO[100];

void    F3()

{

LIFO[sp + 1] = LIFO[sp];

sp++;

}

9. Можно ли в очереди FIFO (см. фрагмент листинга) разместить 150 элементов?

int     sp, LIFO[100];

int     lst, fst, FIFO[100];

void    F5()

{

int n;

if (fst == lst) return;

n = (lst - 1) % 100;

FIFO[lst] = FIFO[n];

lst = ++lst % 100;

}

10. Что выполняет функция F5?

int     sp, LIFO[100];

int     lst, fst, FIFO[100];

void    F5()

{

int n;

if (fst == lst) return;

n = (lst - 1) % 100;

FIFO[lst] = FIFO[n];

lst = ++lst % 100;

}

11. Что выполняет функция F1?

#define SIZE 100               //максимальная длина очереди

int QUEUE[SIZE];               //массив элементов очереди

int fst;                       //указатель на первый элемент очереди

int lst;                       //указатель на следующий за последним

void F1()

{

fst = lst = 0;

}

12. Что выполняет функция F6?

#define SIZE 100              //максимальная длина очереди

int QUEUE[SIZE];              //массив элементов очереди

int fst;                      //указатель на первый элемент очереди

int lst;                      //указатель на следующий за последним

int F6(int val)

{

int next;

if ((next = (lst + 1) % SIZE) == fst)

return 0;

QUEUE[lst] = val;

lst = next;

return 1;

}

13. Что выполняет функция F7?

#define SIZE 100             //максимальная длина очереди

int QUEUE[SIZE];             //массив элементов очереди

int fst;                     //указатель на первый элемент

//очереди

int lst;                     //указатель на следующий за

//последним

int F7()

{

int val;

if (fst == lst) return 0;

val = QUEUE[fst++];

fst %= SIZE;

return val;

}

14. Можно ли сказать, на основании приведенной функции, является ли очередь циклической?

#define SIZE 100            //максимальная длина очереди

int QUEUE[SIZE];            //массив элементов очереди

int fst;                    //указатель на первый элемент

//очереди

int lst;                    //указатель на следующий за

//последним

int F7()

{

int val;

if (fst == lst) return 0;

val = QUEUE[fst++];

fst %= SIZE;

return val;

}

15. В некую структуру данных записали символы A-B-C-В-С, а когда извлекли из нее все элементы, получили последовательность C-B-С-B-A. Какая структура данных использовалась?

16. Чем определяется порядок выборки элементов из приоритетной очереди:

a) приоритетами элементов;

b) порядковым номером;

c) значением элемента?


Примеры решения задач

Задача 4.1

Разработать обобщенный (т. е. имена функций одинаковые – Create, Insert, Delete) интерфейс для стека и очереди, использовать пространство имен stack, queue. Создать стек и очередь на основе динамических массивов. Выполнить операции со структурами.

Листинг задачи 4.1

MyStack1.h

#pragma once

#define MYSTACK_ESE   0x0000              //возврат в случае пустоты стека

#define MYSTACK1_EXC   200

//***************************************************************************************

struct Stack                              //блок управления стеком

{

 int    Top;                         //вершина стека

 int    Size;                        //размер стека

 void** Storage;                     //хранилище данных стека

};

//***************************************************************************************

struct StackException

{

int Code;

#define MYSTACK1_EXC_OVERFLOW     MYSTACK1_EXC + 1

#define MYSTACK1_EXC_POPEMPTY     MYSTACK1_EXC + 2

#define MYSTACK1_EXC_PEEKEMPTY    MYSTACK1_EXC + 3

#define MYSTACK1_EXC_APPOVERFLOW  MYSTACK1_EXC + 4

#define MYSTACK1_EXC_COPYOVERFLOW MYSTACK1_EXC + 5

char Msg[100];

#define MYSTACK1_EXC_OVERFLOW_MSG    "Stack overfow"

#define MYSTACK1_EXC_EMPTY_MSG       "Stack empty"

const Stack *St;

StackException (int code, char msg[], const Stack* st);

};

//***************************************************************************************

Stack CreateStack(int n);             //выделить ресурсы для стека

Stack CreateStack(const Stack& ps);   //создать стек по образцу

bool  Push(Stack& s, void* x);        //добавить x на вершину стека s

void* Pop(Stack& s);                  //удалить элемент с вершины стека s

void* Peek(const Stack& s);           //получить вершину стека

bool isStackFull(const Stack& s);     //стек заполнен?

bool isStackEmpty(const Stack& s);    //стек пуст?

int  ClearStack(Stack& s);            //очистить стек s

void ReleaseStack(Stack& s);          //освободить ресурсы стека

bool CopyStack(Stack& to, const Stack& from);

bool AppendStack(Stack& to, const Stack& from);

MyStack1.cpp

#include <string.h>

#include "MyStack1.h"

//***************************************************************************************

Stack CreateStack(int n)

{

Stack *s = new Stack;

s -> Top = -1;

s -> Size = n;

s -> Storage = new void*[n];

return *s;

}

//***************************************************************************************

Stack CreateStack(const Stack& ps)        //создать стек по образцу

{

Stack *s = new Stack;

s -> Storage = new void*[s -> Size = ps.Size];

for (int i
= 0; i <= (s -> Top = ps.Top);
i++) s -> Storage[i] = ps.Storage[i];

return *s;

}

//***************************************************************************************

bool isStackFull(const Stack& s)          //стек заполнен?

{

return (s.Top >= s.Size - 1);

}

//***************************************************************************************

bool isStackEmpty(const Stack& s)        //стек пуст?

{

return (s.Top < 0);

}

//***************************************************************************************

void* Pop(Stack& s)                      //удалить элемент с вершины стека s

{

void* vp = (void*)MYSTACK_ESE;

if (!isStackEmpty (s)) vp = s.Storage[s.Top--];

else throw StackException(MYSTACK1_EXC_POPEMPTY,MYSTACK1_EXC_EMPTY_MSG, &s);

return vp;

}

//***************************************************************************************

bool Push(Stack& s, void* x)            //добавить x на вершину стека s

{

bool vp = true;

if (vp =! isStackFull (s)) s.Storage[++(s.Top)] = x;

else throw StackException(MYSTACK1_EXC_OVERFLOW, MYSTACK1_EXC_OVERFLOW_MSG, &s);

return vp;

}

//***************************************************************************************

void* Peek(const Stack& s)              //получить вершину стека

{

void* vp = (void*)MYSTACK_ESE;

if (!isStackEmpty (s)) vp = s.Storage[s.Top];

else throw StackException(MYSTACK1_EXC_PEEKEMPTY, MYSTACK1_EXC_EMPTY_MSG, &s);

return vp;

}

//***************************************************************************************

int  ClearStack(Stack& s)

{

int w = s.Top + 1;

s.Top = -1;

return w;

}

//***************************************************************************************

void ReleaseStack(Stack& s)

{

s.Size = 0;

s.Top = -1;

delete[] s.Storage;

}

//***************************************************************************************

bool AppendStack(Stack& to, const Stack& from)

{

try

{

bool rc = true;

for (int i = 0; i <= from.Top && rc; i++)

rc = Push(to, from.Storage[i]);

return rc;

}

catch (StackException se)

{

throw StackException(MYSTACK1_EXC_APPOVERFLOW, se.Msg, se.St);

}

}

//***************************************************************************************

bool CopyStack(Stack& to, const Stack& from)

{

ClearStack(to);

bool rc = false;

try

{

rc = AppendStack(to, from);

}

catch (StackException se)

{

throw StackException(MYSTACK1_EXC_COPYOVERFLOW, se.Msg, se.St);

}

return rc;

}

//**************************************************************************************

StackException::StackException(int code, char msg[], const Stack *st)

{

Code = code;

strcpy_s(Msg, sizeof(Msg), msg);

St = st;

}

MyQueue_1.h

#pragma once

#define MYQUEUE1_EQE   0x0000        //возврат в случае пустоты очереди

#define MYQUEUE1_EXC   100           //серия кодов исключений

//**************************************************************************************

struct Queue                         //блок управления очередью

{

int    Head;                    //голова очереди

int    Tail;                    //хвост очереди

int    Size;                    //размер очереди (максимальное кол-во элементов + 1)

void** Storage;                 //хранилище данных очереди

Queue(int size)

{

Head = Tail = 0;

Storage = new void*[Size = size + 1];

      //физический размер очереди =

      //(максимальное количество элементов + 1)

};

bool isFull() const;             //очередь заполненa?

bool isEmpty() const;            //очередь пустa?

};

//**************************************************************************************

struct QueueException                 //блок обработки исключения

{

int  Code;                       //код исключения (определяет место возникновения)

#define MYQUEUE1_EXC_OVERFLOW     MYQUEUE1_EXC + 1//переполнение очереди Enq

#define MYQUEUE1_EXC_DEQEMPTY     MYQUEUE1_EXC + 2//очередь пуста Deq

#define MYQUEUE1_EXC_PEEKEMPTY    MYQUEUE1_EXC + 3//очередь пуста Peek

#define MYQUEUE1_EXC_APPOVERFLOW  MYQUEUE1_EXC + 4//переполнение  AppendQueue

#define MYQUEUE1_EXC_COPYOVERFLOW MYQUEUE1_EXC + 5//переполнение  CopyQueue

#define MYQUEUE1_EXC_RMOVOVERFLOW MYQUEUE1_EXC + 6//переполнение  RemoveQueue

char Msg[100];                                    //диагностическое соообщение

#define MYQUEUE1_EXC_OVERFLOW_MSG    "Queue overfow"

#define MYQUEUE1_EXC_EMPTY_MSG       "Queue empty"

const Queue *Q;                                   //блок управления очередью,

            //которая вызвала исключение

QueueException (int code, char msg[], const Queue* q);

            //структурная обработка исключений

};

//**************************************************************************************

Queue CreateQueue(int n);

                                               //выделить ресурс для очереди:

                                               //n - максимальное

                                               //количество элементов очереди

Queue CreateQueue(const Queue& pq);                   //создать очередь по образцу

bool  Enq(Queue& q, void* x);                         //добавить x в очередь s

void* Deq(Queue& q);                                  //удалить элемент из очереди

void* Peek(const Queue& q);                           //получить первый элемент очереди

int  ClearQueue(Queue& q);                            //очистить очередь

void ReleaseQueue(Queue& q);                          //освободить ресурсы очереди

void AppendQueue(Queue& to, const Queue& from);       //добавить одну очередь к другой ()

void CopyQueue(Queue& to, const Queue& from);         //копировать очередь

void RemoveQueue(Queue& to, Queue& from);             //переместить очередь

MyQueue_1.cpp

#include <string.h>

#include "MyQueue_1.h"

//**************************************************************************************

Queue CreateQueue(int n)                             //выделить ресурс для очереди

{

return *(new Queue(n));

};

//**************************************************************************************

Queue CreateQueue(const Queue& pq)                   //создать очередь по образцу

{

Queue *rc = new Queue(pq.Size  -1);

rc -> Head = pq.Head;

rc -> Tail = pq.Tail;

for (int i = 0; i < pq.Size; i++) rc -> Storage[i] = pq.Storage[i];

return *rc;

}

//**************************************************************************************

bool  Enq(Queue& q, void* x)                        //добавить x в очередь s

{

bool rc = true;

if (rc =! q.isFull())

{

q.Storage[q.Tail] = x;

q.Tail = (q.Tail + 1) % q.Size;

}

else throw QueueException(MYQUEUE1_EXC_OVERFLOW, MYQUEUE1_EXC_OVERFLOW_MSG, &q);

return rc;

};

//**************************************************************************************

void* Deq(Queue& q)                                //удалить элемент из очереди

{

void* rc = (void*)MYQUEUE1_EQE;

if (!q.isEmpty())

{

rc = q.Storage[q.Head];

q.Head = (q.Head + 1) % q.Size;

}

else throw QueueException(MYQUEUE1_EXC_DEQEMPTY, MYQUEUE1_EXC_EMPTY_MSG, &q);

return rc;

}

//**************************************************************************************

void* Peek(const Queue& q)

{

void* rc = (void*)MYQUEUE1_EQE;

if (!q.isEmpty())

rc = q.Storage[q.Head];

else  throw QueueException(MYQUEUE1_EXC_PEEKEMPTY, MYQUEUE1_EXC_EMPTY_MSG, &q);

return rc;

}

//**************************************************************************************

int  ClearQueue(Queue& q)                            //очистить очередь

{

int rc =  (q.Tail - q.Head) >= 0?(q.Tail - q.Head):(q.Size - q.Head + q.Tail + 1);

q.Tail = q.Head = 0;

return rc;                                      //количество элементов в очереди

                                                     //до очистки

}

//**************************************************************************************

void ReleaseQueue(Queue& q)                          //освободить ресурсы очереди

{

delete[] q.Storage;

q.Size = 1;

q.Head = q.Tail = 0;

}

//**************************************************************************************

void AppendQueue(Queue& to, const Queue& from)       //добавить одну очередь к другой

{

try

{

for (int i = from.Head; i != from.Tail; (++i) % from.Size)

Enq(to, from.Storage[i]);

}

catch (QueueException qe)

{

throw QueueException(MYQUEUE1_EXC_APPOVERFLOW, qe.Msg, qe.Q);

}

}

//**************************************************************************************

void CopyQueue(Queue& to, const Queue& from)                      //копировать очередь

{

ClearQueue(to);

try

{

AppendQueue(to, from);

}

catch (QueueException qe)

{

throw QueueException(MYQUEUE1_EXC_COPYOVERFLOW, qe.Msg, qe.Q);

}

}

//**************************************************************************************

void RemoveQueue(Queue& to, Queue& from)                          //переместить очередь

{

try

{

CopyQueue(to, from);

}

catch (QueueException qe)

{

throw QueueException(MYQUEUE1_EXC_RMOVOVERFLOW, qe.Msg, qe.Q);

}

ClearQueue(from);

}

//**************************************************************************************

bool Queue::isFull() const

{return (Head % Size == (Tail + 1) % Size);};                     //очередь заполненa?

bool Queue::isEmpty()const

{return (Head % Size == Tail % Size);};                           //очередь пустa?

//**************************************************************************************

QueueException::QueueException (int code, char msg[], const  Queue* q)

                                           //структурная обработка ошибок

{

Code  = code;

strcpy_s(Msg, sizeof(Msg), msg);

Q = q;

}

Common.h

#pragma once

#include "MyStack1.h"

#include "MyQueue_1.h"

                                                               //обобщенные интерфейсы

namespace stack                                                //интерфейс стека

{

typedef Stack Object;

const void* Empty = MYSTACK_ESE;

Object Create(int n){return CreateStack(n);};             //выделить ресурс для стека

Object Create(Object& o){return CreateStack(o);};         //создать стек по образцу

bool  Insert(Object& o, void* x)

{return Push(o, x);};                                     //добавить x на вершину

                                                          //стека

void* Delete(Object& o)

{return Pop(o);};                                         //удалить элемент с

                                                               //вершины стека

void* Select(const Object& o){return Peek(o);};           //получить вершину стека

void  Release(Object& o){ReleaseStack(o);};               //освободить ресурсы стека

bool  isFull(const Object& o) {return isStackFull(o);};   //стек заполнен?

bool  isEmpty(const Object& o) {return isStackEmpty(o);}; //стек пуст?

int   Clear(Object& o){return ClearStack(o);};            //очистить стек

bool  Append(Object& to, const Object& from){return AppendStack(to, from);};

                                                 //добавить один стек в другой

bool  Copy(Object& to, const Object from){return CopyStack(to, from);};

}

namespace queue                                                    //интерфейс очереди

{

typedef Queue Object;                                    //новое имя блока управления

typedef QueueException  Exception;                       //блок для  обработки исключения

const void* Empty = MYQUEUE1_EQE;                        //возврат в случае пустоты очереди

Object Create(int n){return CreateQueue(n);};            //выделить ресурс для очереди

Object Create(Object& o){return CreateQueue(o);};        //создать очередь по образцу

bool  Insert(Object& o, void* x){return Enq(o, x);};     //добавить x в очередь s

void* Delete(Object& o){return Deq(o);};                 //удалить элемент из очереди

void* Select(const Object& o){return Peek(o);};          //получить первый элемент очереди

void  Release(Object& o){ReleaseQueue(o);};              //освободить ресурсы очереди

bool  isFull(const Object& o) {return o.isFull();};      //очередь заполнена?

bool  isEmpty(const Object& o) {return o.isEmpty();};    //очередь пуста?

int   Clear(Object& o){return ClearQueue(o);};           //очистить очередь

void  Append(Object& to, const Object from){AppendQueue(to,from);};

                         //добавить одну очередь к другой

void  Copy(Object& to, const Object from){CopyQueue(to, from);};

}

Solution.cpp

#include "Common.h"

#include <iostream>

#include <locale>

using namespace std;

int main()

{

setlocale(LC_ALL,"RUS");

std::cout << "Стек на основе списка " << std::endl;

          //стек

Stack s1, s2, s;

int a[] = {1, 3, 5, 7, 9, 11, 13};

s1 = CreateStack(sizeof(a) / sizeof(int));

for (int i = 0; i < sizeof(a) / sizeof(int); i++)

Push(s1, (void*)(a + i));

int b[] = {1, 3, 5, 8, 10, 12, 14};

s2 = CreateStack(sizeof(b) / sizeof(int));

for (int I = 0; i < sizeof(b) / sizeof(int); i++)

Push(s2, (void*)(b + i));

                                                             //очередь

int c[] = {1, 2, 3, 4, 5, 6, 7};

int d[] = {2, 3, 4, 8, 9};

std::cout << " Очередь на основе списка : " << std::endl;

Queue q1 = Queue(sizeof(c) / sizeof(int));

for (int i = 0; i < sizeof(c) / sizeof(int); i++)

Enq(q1, (c + i));

Queue q2 = Queue(sizeof(d) / sizeof(int));

for (int i = 0; i < sizeof(d) / sizeof(int); i++)

Enq(q2, (d + i));

Queue q = CreateQueue(q1, q2, 1);

for (int i = 0; i < q.Size - 1; i++)

std::cout << *(int*)Deq(q) << "  " << std::endl;

Queue qq = CreateQueue(q1, q2, 2);

for (int i = 0; i < qq.Size - 1; i++)

std::cout << *(int*)Deq(qq) << "  " << std::endl;

system("Pause");

return 0;

}

Результат выполнения задачи 4.1


Задача 4.2

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

Листинг задачи 4.2

Stack.h

#pragma once

#define NULL         0x0000

#define STACK_ESE    -1                         //возврат в случае пустоты стека

//**************************************************************************************

struct Node

{

int    key;

Node* prev;

};

struct Stack                                    //блок управления стеком

{

Node*  Top;                                //вершина стека

void Push(int x);                          //добавить x на вершину стека s

int  Pop();                                //удалить элемент с вершины стека s

bool isEmpty();                            //стек пуст?

};

//**************************************************************************************

Stack CreateStack();

Stack.cpp

#include "stack.h"

bool Stack::isEmpty()

{

return ((*Top).prev == NULL);

}

//**************************************************************************************

int Stack::Pop()

{

int vp = STACK_ESE;

if (!isEmpty())

{

vp = (*Top).key;

Node* pr = (*Top).prev;

delete Top;

Top = pr;

}

return vp;

}

//**************************************************************************************

void Stack::Push(int x)

{

Node *nd = new Node;

nd -> key = x;

nd -> prev = Top;

Top = nd;

}

//**************************************************************************************

Stack CreateStack()

{

Stack *st = new Stack;

st -> Top = NULL;

st -> Push(STACK_ESE);

return *st;

}

Solution.cpp

#include "stack.h"

int main()

{

bool fl = true;

int  x = 0;

//**************************************************************************************

Stack st = CreateStack();

fl = st.isEmpty();

st.Push(3);                                           //3

fl = st.isEmpty();

x = st.Pop();

fl = st.isEmpty();

st.Push(2);

st.Push(3);

st.Push(4);                                           //4 3 2

x = st.Pop();

x = st.Pop();

x = st.Pop();

x = st.Pop();

fl = st.isEmpty();

return 0;

}


Задача 4.3

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

Листинг задачи 4.3

#include "stdafx.h"

#include <conio.h>

#include <iostream>

#include <stdlib.h>

using namespace std;

const int MAX_SIZE = 1000;

class deque

{

int m_size;                //количество элементов в очереди

int m_start;               //номер элемента, с которого начинается очередь

int m_elems[MAX_SIZE];     //массив для хранения элементов

public:

deque();                   //конструктор

~deque();                  //деструктор

void push_front(int a);    //добавить (положить) в начало дека новый элемент

void push_back(int a);     //добавить (положить) в конец дека новый элемент

int pop_front();           //извлечь из дека первый элемент

int pop_back();            //извлечь из дека последний элемент

int front();               //узнать значение первого элемента (не удаляя его)

int back();                //узнать значение последнего элемента (не удаляя его)

int size();                //узнать количество элементов в деке

void clear();              //очистить дек (удалить из него все элементы)

void print();              //просмотр дека

};

//**************************************************************************************

deque::deque()

{

m_size = 0;

m_start = 0;

for (int i = 0; i < 1000; i++)

m_elems[i] = NULL;

}

//**************************************************************************************

deque::~deque()

{

m_size = 0;

m_start = 0;

for (int i = 0; i < 1000; i++)

m_elems[i] = NULL;

}

//**************************************************************************************

void deque::push_front(int a)      //добавить (положить) в начало дека новый элемент

{

if (m_size == MAX_SIZE)

{

wcout << L"Очередь полна" << endl;

}

else

{

for (int i = 0; i < m_size; i++)

m_elems[i + 1] = m_elems[i];

m_elems[0] = a;

m_size++;

}

}

//**************************************************************************************

void deque::push_back(int a)        //добавить (положить) в конец дека новый элемент

{

if (m_size == MAX_SIZE)

{

wcout << L"Очередь полна" << endl;

}

else

{

m_elems[m_size] = a;

m_size++;

}

}

//**************************************************************************************

int deque::pop_front()             //извлечь из дека первый элемент

{

if (m_size == 0)

{

wcout << L"Дек пуст." << endl;

return NULL;

}

else

{

int temp = m_elems[0];

for (int i = 1; i < m_size; i++)

m_elems[i - 1] = m_elems[i];

m_size--;

m_elems[m_size] = NULL;

return temp;

}

}

//**************************************************************************************

int deque::pop_back()             //извлечь из дека последний элемент

{

if (m_size == 0)

{

wcout << L"Дек пуст." << endl;

return NULL;

}

else

{

m_size--;

int temp = m_elems[m_size];

m_elems[m_size] = NULL;

return temp;

}

}

//**************************************************************************************

int deque::front()                //узнать значение первого элемента (не удаляя его)

{

if (m_size == 0)

{

wcout << L"Дек пуст." << endl;

return NULL;

}

else

{

return m_elems[0];

}

}

//**************************************************************************************

int deque::back()                //узнать значение последнего элемента (не удаляя его)

{

if (m_size == 0)

{

wcout << L"Дек пуст." << endl;

return NULL;

}

else

{

return m_elems[m_size - 1];

}

}

//**************************************************************************************

int deque::size()            //узнать количество элементов в деке

{

return m_size;

}

void deque::clear()          //очистить дек (удалить из него все элементы)

{

m_size = 0;

m_start = 0;

for (int i = 0; i < 1000; i++)

m_elems[i] = NULL;

}

//**************************************************************************************

void deque::print()          //просмотр дека

{

if(m_size == 0)

{

wcout << L"Дек пуст." << endl;

}

else

{

for (int i = 0; i < m_size; i++)

wcout << m_elems[i] << L" ";

}

}

//**************************************************************************************

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL,"rus_rus.866");

deque a;

while (true)

{

wcout << L"Основное меню." << endl

<< L"Выберите действие:" << endl

<< L"0 - выход;" << endl

<< L"1 - добавление элемента в начало;" << endl

<< L"2 - добавление элемента в конец;" << endl

<< L"3 - извлечение элемента из начала;" << endl

<< L"4 - извлечение элемента из конца;" << endl

<< L"5 - просмотр первого элемента;" << endl

<< L"6 - просмотр последнего элемента;" << endl

<< L"7 - размер дека;" << endl

<< L"8 - просмотр всего дека;" << endl

<< L"9 - очистка дека." << endl;

int q;

cin >> q;

switch(q)

{

case 0:      return 0;

break;

case 1:

{

wcout << L"Введите элемент (целое число): ";

int temp;

cin >> temp;

a.push_front(temp);

}

break;

case 2:

{

wcout << L"Введите элемент (целое число): ";

int temp;

cin >> temp;

a.push_back(temp);

}

break;

case 3:

wcout << L"Элемент " << a.pop_front() << L" извлечен" << endl;

break;

case 4:

wcout<<L"Элемент " << a.pop_back() << L" извлечен" << endl;

break;

case 5:

wcout << L"Первый элемент дека: " <<a.front() << endl;

break;

case 6:

wcout << L"Последний элемент дека: " << a.back() << endl;

break;

case 7:

wcout << L"Размер дека: " << a.size() << endl;

break;

case 8:

a.print();

break;

case 9:

a.clear();

break;

}

wcout << L"Нажмите любую клавишу для продолжения.";

_getch();

system("cls");

}

return 0;

}

Результат выполнения задачи 4.3


Задачи для самостоятельного решения

1 | Разработать функции для работы со стеком: добавление элемента в стек; удаление элемента из стека; очистка стека; просмотр содержимого стека. Стек реализовать с использованием динамического массива.
2 | Разработать функции работы с деком: добавление элемента в дек; удаление элемента из дека; очистка дека; просмотр содержимого дека. Дек организован на массиве с циклическим заполнением. Операции выполняются с разных концов дека.
3 | Разработать функцию, которая по одному стеку строит два новых: Stack1 – из положительных элементов и Stack2 – из остальных.
4 | Разработать функцию, которая формирует стек Stack, включив в него по одному разу элементы, входящие в один из стеков Stack1 и Stack2, но в то же время не входящие в другой из них.
5 | Разработать процедуру, которая формирует стек Stack, включив в него по одному разу элементы, входящие в стек Stack1, но не входящие в стек Stack2.
6 | Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие – подряд из младших адресов (начало очереди). Очередь организована на массиве со сдвигом после каждого чтения и на массиве со сдвигом после достижения границы памяти, которая выделена для очереди. Приоритет: min значение числового параметра, при совпадении параметров – LIFO.
7 | Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие – подряд из старших адресов (конец очереди). Очередь организована на массиве. Приоритет: min значение числового параметра, при совпадении параметров – LIFO.
8 | Разработать функцию, которая по одной очереди строит две новые: Queue1 – из положительных элементов и Queue2 – из остальных.
9 | Разработать функцию, которая из очереди, содержащей не менее двух элементов, удаляет все элементы с «одинаковыми соседями».
10 | Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие – подряд из младших адресов (начало очереди). Очередь организована на массиве с циклическим заполнением и со сдвигом. Приоритет: min значение числового параметра, при совпадении параметров – LIFO.


ТЕМА 5. ДЕРЕВЬЯ. БИНАРНЫЕ ДЕРЕВЬЯ

Изучите теоретический материал главы 19 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме. Выполните задачи для самостоятельного решения в соответствии с вариантом.

Вопросы для подготовки к тесту

1. Что такое бинарное дерево?

2. Перечислите основные свойства бинарного дерева.

3. Какие существуют способы обхода деревьев?

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

5. Перечислите виды балансировки бинарного дерева.

6. Установите правильную последовательность удаления элемента из дерева:

a) произвести балансировку полученного дерева и откорректировать показатели сбалансированности;

b) удалить найденный элемент, не разрушив структуры связей между элементами;

c) cледовать по дереву, пока не будет найден удаляемый элемент.

7. Перечислите основные свойства RB-бинарного дерева.

8. Что такое бинарная куча?

9. Перечислите основные свойства бинарной кучи.

10. Является ли представленное на рисунке деверево сбалансированным?

11. Является ли представленное далее деверево бинарным?

12. Перечислите значения узлов дерева при восходящем, смешанном и нисходящем обходе.

13. Является ли данная структура бинарным деревом?

14. По заданному массиву постройте бинарное дерево.

22 182 10 13 91 102 7

15. По заданному массиву постройте бинарное дерево.

22 1 10 12 91 11 7

16. Выполните балансировку представленного на рисунке дерева.

17. По листингу нарисовать структуру данных.

struct tree3

{

int vv;

struct tree3 *l, *r;

}

A3 = {1, NULL, NULL},

B3 = {2, NULL,NULL},

C3 = {3, &A3, &B3},

D3 = {4, &C3, NULL},

*p3 = &D3;

18. По листингу нарисовать структуру данных.

struct tree4

{

int vv;

struct tree4 *l,*r;

}

F[3] =

{

{1, NULL, NULL},

{2, NULL, NULL},

{3, &F[0], &F[1]}

}

19. Выполните раскраску дерева, представленного на рисунке, в красно-черные вершины (черный – закрашенный, красный – белый).

20. Является ли данная структура кучей?

21. Постройте кучу.

22. Постройте кучу.

23. Постройте кучу.


Примеры решения задач

Задача 5.1

Разработать функции работы с бинарным деревом.

Листинг задачи 5.1

Tree.h

#define BTREENULL (Node*) - 1

namespace btree                                 //бинарное дерево, не допускается дублирование ключей

{

enum CMP {

LESS = -1,

EQUAL = 0,

GREAT = 1

};

struct Node                                    //узел бинарного списка

{

Node* Parent;                             //указатель на родителя

Node* Left;                               //указатель налево

Node* Right;                              //указатель направо

void* Data;                               //данные

Node(Node* p, Node* l, Node* r, void* d)  //конструктор

{

Parent = p;

Left = l;

Right = r;

Data = d;

}

Node* Next();                             //следующий по ключу

Node* Prev();                             //предыдущий по ключу

Node* Min();                              //минимум в поддереве

Node* Max();                              //максимум в поддереве

void Scan(void (*f)(void* n));            //обход поддерева с корнем в узле

int TreeH(int h = 0);

};

struct Object                                 //интерфейс бинарного дерева

{

Node* Root;                              //указатель на корень

CMP (*Compare)(void*, void*);            //функция сравнения

Object(CMP(*f)(void*, void*))

{

Root = NULL;

Compare = f;

};

Node* Max(){return Root -> Max();};

Node* Min(){return Root -> Min();};

bool isLess(void* x1, void* x2)const {return Compare(x1, x2) == LESS;};

bool isGreat(void* x1, void* x2)const {return Compare(x1, x2) == GREAT;};

bool isEqual(void* x1, void* x2)const {return Compare(x1, x2) == EQUAL;};

bool Insert(void* data);                //добавить элемент

Node* Search(void* d, Node* n );        //найти по ключу

Node* Search(void* d){return Search(d, Root);};

bool Delete(Node* e);                   //удалить по адресу элемента

bool Delete(void* data){return Delete(Search(data));};

                                        //удалить по ключу

void Scan(void (*f)(void* n)){Root -> Scan(f);};

        //обход дерева

int TreeH(int h = 0){return Root -> TreeH();};

};

Object Create(CMP (*f)(void*, void*));  //создать бинарное дерево

};

#undef BTREENULL

Tree.cpp

#include "stdafx.h"

#include "tree.h"

namespace btree                             //бинарное дерево, не допускается дублирование ключей

{

Object Create(CMP (*f)(void*, void*))       //создать бинарное дерево

{

return *(new Object(f));

}

//**************************************************************************************

Node* Node::Min()

{

Node* rc = this;

if (rc -> Left != NULL) rc = rc -> Left -> Min();

return rc;

}

//**************************************************************************************

Node* Node::Max()

{

Node* rc = this;

if (rc -> Right != NULL) rc = rc -> Right -> Max();

return rc;

}

//**************************************************************************************

Node* Node::Next()

{

Node* rc = this, *x = this;

if (rc -> Right != NULL) rc = rc-> Right - >Min();

else

{

rc = this->Parent;

while (rc != NULL && x == rc -> Right)

{

x = rc;

rc = rc -> Parent;

}

}

return rc;

}

//**************************************************************************************

Node* Node::Prev()

{

Node* rc = this, *x = this;

if (rc -> Left != NULL) rc = rc -> Left -> Max();

else

{

rc = this -> Parent;

while (rc != NULL && x == rc -> Left)

{

x = rc;

rc = rc -> Parent;

}

}

return rc;

}

//**************************************************************************************

void Node::Scan(void (*f)(void* n))

{

f(this -> Data);

std::cout << std::endl;

if (this -> Left != NULL) this -> Left -> Scan(f);

//f(this -> Data);

if (this -> Right != NULL) this -> Right -> Scan(f);

}

//**************************************************************************************

Node* Object::Search(void* d, Node* n)

{

Node* rc = n;

if (rc != NULL)

{

if (isLess(d, n -> Data)) rc = Search(d, n -> Left);

else if (isGreat(d, n -> Data)) rc = Search(d, n -> Right);

}

return rc;

}

//**************************************************************************************

bool Object::Insert(void* d)

{

Node* x = this -> Root, *n = NULL;

bool rc = true;

while (rc == true && x != NULL)

{

n = x;

if (isLess(d, x -> Data))

x = x -> Left;

else  if (isGreat(d, x -> Data))

x = x -> Right;

else  rc = false;

}

if    (rc == true && n == NULL)

this -> Root = new  Node(NULL, NULL, NULL, d);

else  if (rc == true && isLess(d, n -> Data))

n -> Left  = new  Node(n, NULL, NULL, d);

else  if (rc == true && isGreat(d, n -> Data))

n -> Right = new  Node(n, NULL, NULL, d);

return rc;

};

//**************************************************************************************

bool  Object::Delete(Node* n )

{

bool rc = true;

if (rc = (n !=  NULL))

{

if (n -> Left == NULL && n -> Right == NULL)

{

if (n -> Parent == NULL)

this -> Root = NULL;

else if (n -> Parent -> Left == n)

n -> Parent -> Left = NULL;

else n -> Parent -> Right = NULL;

delete n;

}

else if (n -> Left == NULL && n -> Right != NULL)

{

if (n -> Parent == NULL) this -> Root = n -> Right;

else if (n -> Parent -> Left == n) n -> Parent -> Left = n -> Right;

else     n -> Parent -> Right = n -> Right;

n -> Right -> Parent = n -> Parent;

delete n;

}

else if (n -> Left != NULL && n -> Right == NULL)

{

if (n -> Parent == NULL)  this -> Root = n -> Left;

else if (n -> Parent -> Left == n) n -> Parent -> Left  = n -> Left;

else     n -> Parent -> Right = n -> Left;

n -> Right -> Parent = n-> Parent;

delete n;

}

else if (n -> Left != NULL && n -> Right != NULL)

{

Node* x = n -> Next();

N -> Data = x -> Data;

rc = Delete(x);

}

}

return  rc;

}

//**************************************************************************************

int max(int a, int b)

{

int c;

if (a > b) c = a;

else c = b;

return c;

}

//**************************************************************************************

int Node::TreeH(int h)

{

Node *x = this;

static int maxh = 0;                                 //max h BD

if (x != NULL)

{

if (x - >Parent == NULL) maxh = 0;

else maxh = max(maxh, h);                      //save max zn h

if (x -> Left != NULL) x -> Left -> TreeH(++h);

--h;

if (x -> Right != NULL) x -> Right -> TreeH(++h);

--h;

}

return maxh;

}

}

BTree.cpp

//

#include "stdafx.h"

#include <ctime>

#include "tree.h"

#include "rand.h"

using namespace std;

#define NN 100000

struct NodeTree

{

char c[20];

int  key;

};

//**************************************************************************************

btree::CMP cmpfnc(void* x, void* y)

{

btree::CMP rc =  btree::EQUAL;

if   (((NodeTree*)x) -> key < ((NodeTree*)y) -> key) rc = btree::LESS;

else if (((NodeTree*)x) -> key > ((NodeTree*)y) -> key) rc = btree::GREAT;

return rc;

}

//**************************************************************************************

void Print(void* x)                               //вывод при обходе

{

cout  << ((NodeTree*)x) -> key << "-" << ((NodeTree*)x) -> c << ends;

}

//**************************************************************************************

int _tmain(int argc, _TCHAR* argv[])

{

int h = 0;

NodeTree a1 = {"mother", 1},

a2 = {"father", 2},

a3 = {"Ann", 3},

a4 = {"Boris", 4},

a5 = {"Nina", 5},

a6 = {"Liza", 6},

a0 = {"Dima", 0};

btree::Object t1 = btree::Create(cmpfnc);

bool rc = t1.Insert(&a4);                         //true                     4

rc =  t1.Insert(&a1);                        //true                1

rc =  t1.Insert(&a5);                        //true                        5

rc =  t1.Insert(&a2);                        //true                  2

rc =  t1.Insert(&a3);                        //true                    3

rc =  t1.Insert(&a6);                        //true                             6

t1.Root -> Scan(Print);

rc  =  t1.Insert(&a3);                       //false

rc  =  t1.Insert(&a4);                       //false

rc  =  t1.Insert(&a0);                       //true           0

btree::Node* m = t1.Root
-> Min();
    //&a0

m = t1.Root -> Max();                        //&a6

 btree::Node* n = t1.Search(&a2);                 //2

 int mh = t1.TreeH();

               n = n -> Next();                   //3

               n = n -> Next();                   //4

               n = n -> Next();                   //5

               n = n -> Next();                   //6

               n = n -> Next();                  //NULL

               n = t1.Search(&a5);               //5

               n = n -> Prev();                  //4

               n = n -> Prev();                  //3

               n = n -> Prev();                  //2

               n = n -> Prev();                  //1

               n = n -> Prev();                  //0

               n = n -> Prev();                  //NULL

               n = t1.Search(&a3);

               rc = t1.Delete(n);                //OK

               n = t1.Search(&a5);

               rc = t1.Delete(n);                //OK

               n  = t1.Search(&a4);

               rc = t1.Delete(n);                //OK

                  t1.Root -> Scan(Print);

                  cout << endl;

clock_t tm1, tm2, dt[10];

int dh[10];

int mas[NN];

GetRandKey(0, 10, 1);

for (int i=0; i<NN; i++)

{

mas[i] = GetRandKey(0, 1000000);

}

int jj = 0;

for (int i = 10000; i <= 100000; i += 20000)

{

btree::Object tre1 = btree::Create(cmpfnc);

tm1 = clock();

for (int j = 0; j <= i; j++) tre1.Insert(&mas[j]);

tm2 = clock();

dt[jj]= tm2 - tm1;

dh[jj]=tre1.TreeH();

jj++;

}

return 0;

}

Результат выполнения задачи 5.1


Задачи для самостоятельного решения

1 | Вершина бинарного дерева содержит ключ, N целых значений и два указателя на потомков. Написать функцию удаления вершины с минимальной суммой N целых значений узла.
2 | Вершина бинарного дерева содержит ключ и два указателя на потомков. Вычислить среднее арифметическое всех элементов дерева.
3 | Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Составить функцию распечатки всех элементов дерева по уровням: корень дерева, вершины 1-го уровня, вершины 2-го уровня, ...
4 | Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Составить функцию распечатки всех элементов дерева по уровням: листья, … вершины 2-го уровня, вершины 1-го уровня, корень дерева.
5 | Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Написать функцию, которая подсчитывает число ветвей от корня до ближайшей вершины с заданным ключом и выводит часть дерева от вершины до данного элемента на экран.
6 | Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Написать функцию определения числа ветвей n-го уровня этого дерева и вывода этих элементов на экран.
7 | В текстовом файле построчно записаны целые числа. Написать функцию, которая по файлу F (все элементы в нем различны) строит соответствующее бинарное дерево поиска T.
8 | Вершина бинарного дерева содержит ключ, целое и два указателя на потомков. Написать функцию, которая записывает в файл G элементы дерева в порядке их возрастания.
9 | Вершина бинарного дерева содержит ключ, целое и два указателя на потомков. Написать функцию, которая записывает в файл G элементы дерева в порядке их убывания.
10 | Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Описать рекурсивную функцию, которая печатает элементы из всех листьев дерева.


ТЕМА 6. ХЭШ-ТАБЛИЦЫ

Изучите теоретический материал главы 20 [1]. Ответьте на вопросы. Рассмотрите предложенные решения задач по теме.

Вопросы для подготовки к тесту

1. Дайте определение хэш-таблицы.

2. Коллизия:

a) разным значениям ключей таблицы хэш-функция генерирует одинаковые адреса;

b) одинаковым значениям ключей таблицы хэш-функция генерирует одинаковые адреса;

c) разным значениям ключей таблицы хэш-функция генерирует разные адреса.

3. В чем отличие открытой адресации от прямой в хэш-таблицах?

4. Приведите пример хэш-функции. Для чего она используется?

5. Перечислите недостатки открытой адресации в хэш-таблицах.

6. Перечислите недостатки прямой адресации в хэш-таблицах.

7. Приведите формулу, используемую для вычисления хэша, при мультипликативном методе.

8. Приведите формулу, используемую для вычисления хэша, при универсальном хэшировании.

9. Как вычисляется коэффициент заполнения хэш-таблицы?

10. Перечислите основные свойства хэш-таблиц.


Примеры решения задач

Задача 6.1

Создать хэш-таблицу с открытой адресацией.

Листинг задачи 6.1

Hash.h

#pragma once

#define HASHDEL (void*) - 1

struct Object

{

void** Data;

Object(int, int (*)(void*));

int Size;

int N;

int (*GetKey)(void*);

bool Insert(void*);

int SearchInd(int key);

void* Search(int key);

void* Delete(int key);

bool Delete(void*);

};

static void* DEL = (void*)HASHDEL;

Object Create(int size, int (*getkey)(void*));

#undef HASHDEL

Hash.cpp

#include "stdafx.h"

#include "Hash.h"

int HashFunction(int key, int size, int p)         //хэш-функция

{

return (p + key) % size;

}

Object Create(int size, int(*getkey)(void*))

{

return *(new Object(size, getkey));

}

//**************************************************************************************

Object::Object(int size, int(*getkey)(void*))

{

N = 0;

this -> Size = size;

this -> GetKey = getkey;

this -> Data = new void*[size];

for (int i = 0; i < size; ++i) Data[i] = NULL;

}

//**************************************************************************************

bool Object::Insert(void* d)

{

bool b = false;

if (N != Size)

for (int i = 0, t = GetKey(d), j = HashFunction(t, Size, 0);

i != Size && !b; j = HashFunction(t, Size, ++i))

if (Data[j] == NULL || Data[j] == DEL)

{

Data[j] = d;

N++;

b = true;

}

return b;

}

//**************************************************************************************

int Object::SearchInd(int key)

{

int t = -1;

bool b = false;

if (N != 0)

for (int i = 0, j = HashFunction(key, Size, 0);

Data[j] != NULL && i != Size && !b;

j = HashFunction(key, Size, ++i))

if (Data[j] != DEL)

if (GetKey(Data[j]) == key)

{

t = j;

b = true;

}

return t;

}

//**************************************************************************************

void* Object::Search(int key)

{

int t = SearchInd(key);

return(t >= 0) ? (Data[t]) : (NULL);

}

//**************************************************************************************

void* Object::Delete(int key)

{

int i = SearchInd(key);

void* t = Data[i];

if(t != NULL)

{

Data[i] = DEL;

N--;

}

return t;

}

//**************************************************************************************

bool Object::Delete(void* d)

{

return(Delete(GetKey(d)) != NULL);

}

Solution.h

#include "stdafx.h"

#include "Hash.h"

#include <iostream>

struct AAA

{

int key;

char *mas;

AAA(int k, char*z)

{

key = k;

mas = z;

}

};

int key(void* d)

{

AAA* f = (AAA*)d;

return f -> key;

}

int _tmain(int argc, _TCHAR* argv[])

{

AAA    a1(1, "one"),

a2(2, "two"),

a3(4, "three");

Object H = Create(5, key);                     //создать

bool    b1 = H.Insert(&a1),

b2 = H.Insert(&a2),

b3 = H.Insert(&a3);

void*  a4 = H.Search(4);                      //найти

bool    b6 = H.Delete(&a1);

void*  a5 = H.Delete(1);                      //удалить

return 0;

}


Задача 6.2

Создать хэш-таблицу с прямой адресацией.

Листинг задачи 6.2

Lists.h

pragma once

#define LISTNIL (Element*)  -1

namespace listx

{

struct Element

{

Element* Prev;

Element* Next;

void* Data;

Element(Element* prev, void* data, Element* next)

{

Prev = prev;

Data = data;

Next = next;

}

Element* GetNext(){return Next;};

Element* GetPrev(){return Prev;};

};

static Element* NIL = LISTNIL;

enum Permit

{

ALL = 0,

NOINSERT = 1,

NODELETE = 2,

NOUPDATE = 3

};

struct Object

{

Element* Head;

Object(){Head = NIL;};

Element* GetFirst(){return Head;};

Element* GetLast();

Element* Search(void* data);

bool Insert(void* data);

bool Delete(Element* e);

bool Delete(void* data);

static Permit Perm;

bool isLockInsert(){return (Perm == NOINSERT || Perm == NOUPDATE);};

bool isLockDelete(){return (Perm == NODELETE || Perm == NOUPDATE);};

bool isListEmpty(){return (Head == NIL);};

};

Object Create();

void AppendList(Object& to, const Object& from);

void CopyList(Object& to, const Object& from);

}

#undef LISTNIL

Lists.cpp

#include "stdafx.h"

#include "Lists.h"

namespace listx

{

Permit Object::Perm = ALL;

//**************************************************************************************

/*bool Object::Insert(void* data)

{

bool rc;

if (rc !=isLockInsert())

{

if (Head == NIL) Head = new Element(NIL, data, NIL);

else

this -> GetLast() -> Next =

new Element(this -> GetLast(), data, NIL);

}

return rc;

}*/

//**************************************************************************************

bool Object::Insert(void* data)

{

bool rc;

if (rc =! isLockInsert())

{

if (Head == NIL) Head = new Element(NIL, data, Head);

else Head = (Head -> Prev = new Element(NIL, data, Head));

}

return rc;

}

//**************************************************************************************

Element* Object::Search(void* data)

{

Element* rc = Head;

while ((rc != NIL) && (rc -> Data != data)) rc = rc -> Next;

return rc;

}

//**************************************************************************************

bool Object::Delete(Element* e)

{

bool rc;

if (rc =! isLockDelete())

{

if(rc =(e != NIL))

{

if(e -> Next != NIL) e -> Next -> Prev = e -> Prev;

if(e -> Prev != NIL) e -> Prev -> Next = e -> Next;

else Head = e -> Next;

delete e;

}

}

return rc;

}

//**************************************************************************************

bool Object::Delete(void* data)

{

return Delete(Search(data));

}

//**************************************************************************************

Element* Object::GetLast()

{

listx::Element* e = this -> GetFirst(), *rc = this -> GetFirst();

while(e != listx::NIL)

{

rc = e;

e = e -> GetNext();

};

return rc;

}

//**************************************************************************************

void AppendList(Object& to, const Object& from)

{

to.GetLast() -> Next = from.Head -> Next;

}

//**************************************************************************************

void CopyList(Object& to, const Object& from)

{

to.Head -> Next = from.Head -> Next;

}

//**************************************************************************************

Object Create() {return *(new Object());};

}

Hash_Twin_Chain.h

#pragma once

#include "Lists.h"

namespace hashTC

{

struct Object

{

int Size;

int (*FunKey)(void*);

listx::Object* Hash;

Object(int size, int (*f)(void*))

{

Size = size;

FunKey = f;

Hash = new listx::Object[Size];

};

int HashFunction(void* data);

bool Insert(void* data);

listx::Element* Search(void* data);

//bool Delete(int key);

bool Delete(void* data);

};

Object Create(int size, int (*f)(void*));

}

Hash_Twin_Chain.cpp

#include "stdafx.h"

#include "Hash_Twin_Chain.h"

#include "Lists.h"

namespace hashTC

{

Object Create(int size,int (*f)(void*)) {return *(new Object(size, f));}

//**************************************************************************************

int Object::HashFunction(void* data){return (FunKey(data) % Size);};

//**************************************************************************************

bool Object::Insert(void* data){return (Hash[HashFunction(data)].Insert(data));};

//**************************************************************************************

bool Object::Delete(void* data){return (Hash[HashFunction(data)].Delete(data));};

//**************************************************************************************

listx::Element* Object::Search(void* data){return Hash[HashFunction(data)].Search(data);};

//**************************************************************************************

}

HashTables.cpp

#include "stdafx.h"

#include "Hash_Twin_Chain.h"

#include <iostream>

struct AAA

{

int key;

char *mas;

AAA(int k, char*z)

{

key = k;

mas = z;

}

};

int hf(void* d)

{

AAA* f = (AAA*)d;

return f -> key;

}

int _tmain(int argc, _TCHAR* argv[])

{

AAA    a1(1, "one"),

a2(1, "two"),

a3(1, "three");

hashTC::Object H = hashTC::Create(20, hf);

bool    rc01 = H.Insert(&a1),

rc02 = H.Insert(&a2),

rc03 = H.Insert(&a3),

rc04 = H.Delete(&a3);

listx::Element* eee = H.Search(&a1);

return 0;

}


ВОПРОСЫ К ЭКЗАМЕНУ

ЧАСТЬ 1

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. Битовые поля, объединения, перечисления.

ЧАСТЬ 2

26. Основы теории сложности. Анализ трудоемкости алгоритмов. Классы сложности: NP, P.

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. Жадные алгоритмы. Поиск с возвратом (полный перебор). Алгоритмы локального поиска.


ЛИТЕРАТУРА

1. Пацей, Н. В. Основы алгоритмизации и программирования: учеб.-метод. пособие / Н. В. Пацей. – Минск: БГТУ, 2010. – 285 с.

2. Пацей, Н. В. Конструирование программ и языки программирования: практикум: в 2 ч. / Н. В. Пацей, Д. В. Занько. – Минск: БГТУ, 2005. – Ч. 1.– 104 с.

3. Пацей, Н. В. Конструирование программ и языки программирования: практикум: в 2 ч. / Н. В. Пацей, Н. Н. Дорожкина. – Минск: БГТУ, 2006. – Ч. 2. – 130 с.

4. Кормен, Т. Алгоритмы: Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – СПб.: Питер, 2003. – 356 с.

5. Уилсон, С. Принципы проектирования и разработки программного обеспечения. Учебный курс / С. Уилсон. – СПб.: Питер, 2003. – 276 с.

6. Павловская, Т. А. С/С++ программирование на языке высокого уровня / Т. А. Павловская. − СПб.: Питер, 2007. − 461 с.

7. Павловская Т. А. С/С++. Структурное программирование: практикум / Т. А. Павловская, Ю. А. Щупак. − СПб.: Питер, 2007. − 239 с.

8. Шильдт, Г. Полный справочник по С++ / Г. Шильдт; пер. с англ. – 4-е изд. – М.: Издательский дом «Вильямс», 2007. − 800 с.

9. Страуструп, Б. Язык программирования С++ / Б. Страуструп. − М.: Бином, 2000. − 990 с.

10. Седжвик, Р. Фундаментальные алгоритмы на C++: в 5 ч. / Р. Седжвик. – М.: ДиаСофт, 2002. – Ч. 5. − 496 с.

11. Ахо, А. Структуры данных и алгоритмы / А. Ахо, В. Хопкрофт, Д. Уильям. – М.: Вильямс, 2000. − 384 с.


Выходные сведения

Основы алгоритмизации
и программирования

Составитель

Пацей Наталья Владимировна

Редактор Ю. А. Ирхина

Компьютерная верстка Д. В. Чернушевич

Корректор Ю. А. Ирхина

Издатель и полиграфическое исполнение:

УО «Белорусский государственный технологический университет».

ЛИ № 02330/0549423 от 08.04.2009.

ЛП № 02330/0150477 от 16.01.2009.

Ул. Свердлова, 13а, 220006, г. Минск.