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

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

Решение

Содержание Задание 2. ( Программы на зачет Задание 3. ( Задание 4. ( Задание 5. ( Задание 7. (31 Задание 8. ( Задание 9. ( Задание 10. ( Задание 11. (28 Задание 12. (5 Одномерные массивы Рекурсивные алгоритмы Задания по программированию I I семестр ЗАДАНИЕ 1. Очереди и стеки ЗАДАНИЕ 2. Графы, деревья Пример входных данных 3 3 1 2 2 3 3 1Пример выходных данных

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

• Памятка для студентов по изучению философии факультет сервиса и туризма, Энергетический, 129.43kb.
• Олимпиада по истории России X-XIX вв для учащихся 10 класса Первый тур, 442.93kb.
• Утверждено Ученым Советом факультета Бизнес информатики Ученый секретарь Фомичев, 201.17kb.
• Тест оценивается по количеству правильных ответов: менее 3 "0 баллов"; 3 "1";, 10.45kb.
• Экзамен оценивается по 100 бальной шкале по следующим критериям, 18.5kb.
• Экзамен оценивается по 100 бальной шкале по следующим критериям, 25.76kb.
• Курс, 9 семестр Согласно введенной в институте балльно-рейтинговой системы (брс) оценки, 92.26kb.
• Пояснительная записка к тесту, 204.4kb.
• «Среднее арифметическое», 22.6kb.
• Требования к отчетности по брс по курсу «Новейшая история», 56.19kb.

Задания по программированию I семестр


Каждое задание оценивается по 100-бальной системе.

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


ЗАДАНИЕ 1. (19 сентября – 25 сентября) Линейные алгоритмы


Задачи для самостоятельного решения (12 задач – 60 баллов): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.


Программы на зачет (40 баллов):

1. Написать во время занятий в присутствии преподавателя одну из заданных для самостоятельного решения программ.
   

Срок сдачи задач: 26 сентября – 2 октября

Резервный срок: 3 октября – 9 октября


ЗАДАНИЕ 2. (26 сентября – 2 октября) Условные операторы


Задачи для самостоятельного решения (12 задач – 60 баллов): 20, 23, 24, 25, 27, 29, 31, 32, 33, 37, 38, 40


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Решение системы двух линейных уравнений с двумя неизвестными.
   

Срок сдачи задач: 3 октября – 9 октября

Резервный срок: 10 октября – 16 октября


ЗАДАНИЕ 3. (3 октября – 9 октября) Операторы цикла


Задачи для самостоятельного решения (10 задач – 60 баллов): 41, 43, 44, 46, 47, 49, 51, 54, 55, 60


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Нахождение наибольшего общего делителя двух чисел.
   
2. Разложение числа на простые множители.
   
3. Быстрое возведение в степень.
   

Срок сдачи задач: 10 октября – 16 октября

Резервный срок: 17 октября – 23 октября


ЗАДАНИЕ 4. (10 октября – 16 октября) Одномерные массивы


Задачи для самостоятельного решения (10 задач – 60 баллов): 63, 64, 65, 67, 68, 72, 73, 79, 81


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Нахождение простых чисел с помощью решета Эратосфена.
   
2. Перевод числа из десятичной системы счисления в двоичную.
   
3. Проверка, является ли число простым.
   
4. Сложение двух длинных чисел.
   

Срок сдачи задач: 17 октября – 23 октября

Резервный срок: 24 октября – 30 октября


ЗАДАНИЕ 5. (17 октября – 23 октября) Одномерные массивы


Задачи для самостоятельного решения (10 задач – 60 баллов): 82, 84, 85, 86, 93, 94, 95, 99, 100, 102


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Сортировка выбором
   
2. Сортировка вставками
   
3. Сортировка обменом (методом пузырька).
   

Срок сдачи задач: 24 октября – 30 октября

Резервный срок: 31 октября – 6 ноября


ЗАДАНИЕ 6. (24 октября – 30 октября) Двумерные массивы


Задачи для самостоятельного решения (10 задач - 60 баллов): 103, 104, 105, 106, 107, 108, 109, 110, 111, 112.


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

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


Срок сдачи задач: 31 октября – 6 ноября

Резервный срок: 7 ноября – 13 ноября


ЗАДАНИЕ 7. (31 октября – 6 ноября) Двумерные массивы


Задачи для самостоятельного решения (10 задач - 60 баллов): 113, 114, 115, 116, 117, 118, 119, 120, 121, 122.


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

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


Срок сдачи задач: 7 ноября – 13 ноября

Резервный срок: 14 ноября – 20 ноября


ЗАДАНИЕ 8. (7 ноября – 13 ноября) Функции


Задачи для самостоятельного решения (10 задач - 60 баллов): 136, 137, 141, 142, 143, 144, 145, 147, 151, 152.


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Одна из задач раздела «Функции», не входящая в список задач для самостоятельного решения.


Срок сдачи задач: 14 ноября – 20 ноября

Резервный срок: 21 ноября – 27 ноября


ЗАДАНИЕ 9. (14 ноября – 20 ноября) Функции


Задачи для самостоятельного решения (10 задач - 60 баллов): 156, 157, 158, 159, 160, 161, 162, 163, 164, 165.


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Нахождение корня уравнения f(x)= 0 методом деления пополам.
   
2. Нахождение корня уравнения f(x)= 0 методом хорд.
   
3. Нахождение корня уравнения f(x)= 0 методом касательных.
   

Срок сдачи задач: 21 ноября – 27 ноября

Резервный срок: 28 ноября – 4 декабря


ЗАДАНИЕ 10. (21 ноября – 27 ноября) Рекурсивные алгоритмы


Задачи для самостоятельного решения (10 задач - 60 баллов): 168, 169, 170, 171, 172, 173, 174, 175, 176, 177.


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Нахождение элемента в упорядоченном массиве методом деления пополам (двоичный поиск).
   
2. Ханойские башни.
   

Срок сдачи задач: 28 ноября – 4 декабря

Резервный срок: 5 декабря – 11 декабря


ЗАДАНИЕ 11. (28 ноября – 4 декабря) Символы и строки


Задачи для самостоятельного решения (6 задач - 60 баллов): 179, 180, 181, 182, 186, 187.


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Одна из задач раздела «Символы и строки», не входящая в список задач для самостоятельного решения.


Срок сдачи задач: 5 декабря – 11 декабря

Резервный срок: 12 декабря – 18 декабря


ЗАДАНИЕ 12. (5 декабря – 11 декабря) Файлы


Задачи для самостоятельного решения (6 задач 60 баллов): 188, 189, 190, 191, 192, 193


Программы на зачет (написать во время занятий в присутствии преподавателя одну из следующих задач) (40 баллов):

1. Одна из задач раздела «файлы», не входящая в список задач для самостоятельного решения.


Срок сдачи задач: 12 декабря – 18 декабря

Резервный срок: 19 декабря – 25 декабря


ЗАДАЧИ


Линейные алгоритмы

1. Ввести с клавиатуры два целых ненулевых числа. Найти их сумму, разность, произведение и частное.
   

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

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

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

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

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

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

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

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

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

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

12. Дано целое четырехзначное число. Используя операции деления / и нахождения остатка от деления %, найти сумму и произведение его цифр.
    

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

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

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

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

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

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

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

Условные операторы

20. Даны три целых числа. Возвести в квадрат отрицательные числа и в третью степень — положительные (число 0 не изменять).
    

21. Из трех данных чисел выбрать наименьшее.
    

22. Из трех данных чисел выбрать наибольшее. 
    

23. Из трех данных чисел выбрать наименьшее и наибольшее.
    

24. Перераспределить значения переменных X и Y так, чтобы в X оказалось меньшее из этих значений, а в Y — большее. 
    

25. Значения переменных X, Y, Z поменять местами так, чтобы они оказались упорядоченными по возрастанию. 
    

26. Значения переменных X, Y, Z поменять местами так, чтобы они оказались упорядоченными по убыванию. 
    

27. Даны две переменные целого типа: A и B. Если их значения не равны, то присвоить каждой переменной сумму этих значений, а если равны, то присвоить переменным нулевые значения. 
    

28. Даны две переменные целого типа: A и B. Если их значения не равны, то присвоить каждой переменной максимальное из этих значений, а если равны, то присвоить переменным нулевые значения. 
    

29. Даны три переменные: X, Y, Z. Если их значения упорядочены по убыванию, то удвоить их; в противном случае заменить значение каждой переменной на противоположное. 
    

30. Даны три переменные: X, Y, Z. Если их значения упорядочены по возрастанию или убыванию, то удвоить их; в противном случае заменить значение каждой переменной на противоположное. 
    

31. Даны целочисленные координаты точки на плоскости. Если точка не лежит на координатных осях, то вывести 0. Если точка совпадает с началом координат, то вывести 1. Если точка не совпадает с началом координат, но лежит на оси OX или OY, то вывести соответственно 2 или 3. 
    

32. Даны вещественные координаты точки, не лежащей на координатных осях OX и OY. Вывести номер координатной четверти, в которой находится данная точка. 
    

33. На числовой оси расположены три точки: A, B, C. Определить, какая из двух последних точек (B или C) расположена ближе к A, и вывести эту точку и ее расстояние от точки A. 
    

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

35. Дан номер некоторого года (положительное целое число). Вывести соответствующий ему номер столетия, учитывая, что, к примеру, началом 20 столетия был 1901 год. 
    

36. Дан номер некоторого года (положительное целое число). Вывести число дней в этом году, учитывая, что обычный год насчитывает 365 дней, а високосный — 366 дней. Високосным считается год, делящийся на 4, за исключением тех годов, которые делятся на 100 и не делятся на 400 (например, годы 300, 1300 и 1900 не являются високосными, а 1200 и 2000 — являются). 
    

37. Для данного x вычислить значение следующей функции f, принимающей значения целого типа: 0, если x < 0, f(x) = 1, если x принадлежит [0,1) или [2,3), f(x) = –1 в остальных случаях. 
    

38. Найти действительные корни квадратного уравнения A·x² + B·x + C = 0, заданного своими коэффициентами A, B, C (коэффициент A не равен 0), или вывести сообщение, что действительных корней нет.
    

39. Дано целое число, лежащее в диапазоне от –999 до 999. Вывести строку — словесное описание данного числа вида "отрицательное двузначное число", "нулевое число", "положительное однозначное число" и т.д. 
    

40. Дано целое число, лежащее в диапазоне от 1 до 9999. Вывести строку — словесное описание данного числа вида "четное двузначное число", "нечетное четырехзначное число" и т.д.
    

Операторы цикла

41. Даны два целых числа A и B (A < B). Вывести все целые числа, расположенные между данными числами (включая сами эти числа), в порядке их возрастания, а также количество N этих чисел. 
    

42. Даны два целых числа A и B (A < B). Вывести все целые числа, расположенные между данными числами (не включая сами эти числа), в порядке их убывания, а также количество N этих чисел. 
    

43. Дано вещественное число A и целое число N (> 0). Вывести A в степени N: AN = A·A·...·A (числа A перемножаются N раз). 
    

44. Дано вещественное число A и целое число N (> 0). Вывести все целые степени числа A от 1 до N. 
    

45. Дано вещественное число A и целое число N > 0. Вывести 1 + A + A*2 + A*3 + ... + A*N.
    

46. Дано вещественное число A и целое число N > 0. Вывести 1 – A + A*2 – A*3 + ... + (–1)^NA*N. 
    

47. Дано целое число N (> 1). Вывести наименьшее целое K, при котором выполняется неравенство 3K > N, и само значение 3K. 
    

48. Дано целое число N (> 1). Вывести наибольшее целое K, при котором выполняется неравенство 3K < N, и само значение 3K. 
    

49. Дано вещественное число A (> 1). Вывести наименьшее из целых чисел N, для которых сумма 1 + 1/2 + ... + 1/N будет больше A, и саму эту сумму. 
    

50. Дано вещественное число A (> 1). Вывести наибольшее из целых чисел N, для которых сумма 1 + 1/2 + ... + 1/N будет меньше A, и саму эту сумму. 
    

51. Дано целое число N (> 0). Вывести произведение 1·2·...·N. Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и выводить его как вещественное число. 
    

52. Дано целое число N (> 0). Если N — нечетное, то вывести произведение 1·3·...·N; если N — четное, то вывести произведение 2·4·...·N. Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и выводить его как вещественное число. 
    

53. Дано целое число N (> 0). Вывести сумму 2 + 1/(2!) + 1/(3!) + ... + 1/(N!) (выражение N! — "N факториал" — обозначает произведение всех целых чисел от 1 до N: N! = 1·2·...·N). Полученное число является приближенным значением константы e = exp(1) (= 2.71828183...). 
    

54. Дано вещественное число X и целое число N (> 0). Вывести 1 + X + X²/2! + ... + X^N/N! (N! = 1·2·...·N). Полученное число является приближенным значением функции exp в точке X. 
    

55. Дано вещественное число X и целое число N (> 0). Вывести X – X³/3! + X⁵/5! – ... + (–1)^NX^2N+1/(2N+1)! (N! = 1·2·...·N). Полученное число является приближенным значением функции sin в точке X. 
    

56. Дано вещественное число X и целое число N (> 0). Вывести 1 – X²/2! + X⁴/4! – ... + (–1)^NX^2N/(2N)! (N! = 1·2·...·N). Полученное число является приближенным значением функции cos в точке X. 
    

57. Дано вещественное число X (|X| < 1) и целое число N (> 0). Вывести X – X²/2 + X³/3 – ... + (–1)^N–1X^N/N. Полученное число является приближенным значением функции ln в точке 1+X. 
    

58. Дано вещественное число X (|X| < 1) и целое число N (> 0). Вывести X – X³/3 + X⁵/5 – ... + (–1)^NX^2N+1/(2N+1). Полученное число является приближенным значением функции arctg в точке X. 
    

59. Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A < B). Отрезок [A, B] разбит на равные отрезки длины H с концами в N точках вида A, A + H, A + 2H, A + 3H, ..., B. Вывести значение H и набор из N точек, образующий разбиение отрезка [A, B]. 
    

60. Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A < B). Функция F(X) задана формулой F(X) = 1 – sin(X). Вывести значения функции F в N равноотстоящих точках, образующих разбиение отрезка [A, B]: F(A), F(A + H), F(A + 2H), ..., F(B). 
    

61. Дано число D (> 0). Последовательность чисел AN определяется следующим образом: A1 = 2, AN = 2 + 1/AN–1, N = 2, 3, ... Найти первый из номеров K, для которых выполняется условие |AK – AK–1| < D, и вывести этот номер, а также числа AK–1 и AK. 
    

62. Дано число D (> 0). Последовательность чисел AN определяется следующим образом: A1 = 1, A2 = 2, AN = (AN–2+ AN–1)/2, N = 3, 4, ... Найти первый из номеров K, для которых выполняется условие |AK AK–1| < D, и вывести этот номер, а также числа AK–1 и AK.
    

Одномерные массивы

63. Дан массив размера N. Вывести его элементы в обратном порядке. 
    

64. Дан массив размера N. Вывести вначале его элементы с четными индексами, а затем — с нечетными. 
    

65. Дан целочисленный массив A размера 10. Вывести номер первого из тех его элементов A[i], которые удовлетворяют двойному неравенству: A[1] < A[i] < A[10]. Если таких элементов нет, то вывести 0. 
    

66. Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам последний элемент. Первый и последний элементы массива не изменять. 
    

67. Дан целочисленный массив размера N. Вывести вначале все его нечетные элементы, а затем — четные. 
    

68. Поменять местами минимальный и максимальный элементы массива размера 10. 
    

69. Заменить все отрицательные элементы целочисленного массива размера 10 на значение максимального. 
    

70. Дан массив размера 10. Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами. 
    

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

72. Дан массив размера N и число k (0 < k < 5, k < N). Осуществить циклический сдвиг элементов массива вправо на k позиций. 
    

73. Проверить, образуют ли элементы целочисленного массива размера N арифметическую прогрессию. Если да, то вывести разность прогрессии, если нет — вывести 0. 
    

74. Дан массив ненулевых целых чисел размера N. Проверить, чередуются ли в нем [четные и нечетные]1|[положительные и отрицательные]2 числа. Если чередуются, то вывести 0, если нет, то вывести номер первого элемента, нарушающего закономерность. 
    

75. Дан массив размера N. Найти количество его локальных минимумов1|максимумов2. 
    

76. Дан массив размера N. Найти максимальный1|минимальный2 из его локальных минимумов1|максимумов2. 
    

77. Дан массив размера N. Определить количество участков, на которых его элементы монотонно возрастают1|убывают2. 
    

78. Дан массив размера N. Определить количество его промежутков монотонности (то есть участков, на которых его элементы возрастают или убывают). 
    

79. Дано вещественное число R и массив размера N. Найти элемент массива, который наиболее близок к данному числу. 
    

80. Дано вещественное число R и массив размера N. Найти два элемента массива, сумма которых наиболее1|наименее2 близка к данному числу. 
    

81. Дан массив размера N. Найти номера двух ближайших чисел из этого массива. 
    

82. Дан целочисленный массив размера N. Определить максимальное количество его одинаковых элементов. 
    

83. Дан целочисленный массив размера N. Удалить из массива все элементы, встречающиеся [менее двух раз]1|[более двух раз]2|[ровно два раза]3|[ровно три раза]4. 
    

84. Дан целочисленный массив размера N. Если он является перестановкой, то есть содержит все числа от 1 до N, то вывести 0, в противном случае вывести номер первого недопустимого элемента. 
    

85. Дан массив размера N. Преобразовать его, вставив после каждого отрицательного элемента нулевой элемент. 
    

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

87. Дан целочисленный массив размера N. Преобразовать массив, увеличив1|уменьшив2 каждую его серию на один элемент. 
    

88. Дан целочисленный массив размера N. Преобразовать массив, увеличив первую1|последнюю2|все3 серии наибольшей длины на один элемент. 
    

89. Дан целочисленный массив размера N. Вставить перед1|после2 каждой серии нулевой элемент. 
    

90. Дано число k и целочисленный массив размера N. Поменять местами первую1|последнюю2 и k-ю серии массива. Если серий в массиве меньше k, то вывести массив без изменений. 
    

91. Дано число k и целочисленный массив размера N. Удалить из массива все серии, длина которых меньше1|равна2|больше3 k. 
    

92. Дано число k и целочисленный массив размера N. Заменить  серию, длина которой меньше1|равна2|больше3 k, на один нулевой элемент. 
    

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

94. Упорядочить массив размера N по убыванию. 
    

95. Дан массив размера N. Вывести индексы массива в том порядке, в котором соответствующие им элементы образуют возрастающую последовательность.
    

96. Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее близкой1|удаленной2 от точки A. 
    

97. Дано множество A из N точек. Среди всех точек этого множества, лежащих в первой1|второй2|третьей3|четвертой4 четверти, найти точку, наиболее близкую5|удаленную6 от начала координат. Если таких точек нет, то вывести точку с нулевыми координатами. 
    

98. Дано множество A из N точек. Найти пару различных точек этого множества с минимальным1|максимальным2 расстоянием между ними и само это расстояние (точки выводятся в том же порядке, в котором они перечислены при задании множества A). 
    

99. Дано множество A из N точек. Найти такую точку из данного множества, сумма расстояний от которой до остальных его точек минимальна, и саму эту сумму. 
    

100. Даны множества A и B, состоящие соответственно из N1 и N2 точек. Найти минимальное расстояние между точками этих множеств и сами точки, расположенные на этом расстоянии. 
     

101. Дано множество A из N точек. Найти наименьший1|наибольший2 периметр треугольника, вершины которого принадлежат различным точкам множества A, и сами эти точки (точки выводятся в том же порядке, в котором они перечислены при задании множества A). 
     

102. Дано множество A из N точек с целочисленными координатами. Порядок на координатной плоскости определим следующим образом: (x1,y1) < (x2,y2), если либо x1 < x2, либо x1 = x2 и y1 < y2. Расположить точки данного множества по возрастанию1|убыванию2 в соответствии с указанным порядком.
     

Двумерные массивы

103. Дано число k (0 < k < 11) и матрица размера 4 x 10. Найти сумму и произведение элементов k-го столбца данной матрицы.
     
104. Дана матрица размера 5 x 9. Найти суммы элементов всех ее четных строк.
     
105. Дана матрица размера 5 x 10. Найти максимальное значение в каждой строке.
     
106. Дана матрица размера 5 x 10. В каждой строке найти количество элементов, меньших среднего арифметического всех элементов этой строки.
     
107. Дана матрица размера 5 x 10. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждой строке. 
     
108. Дана матрица размера 5 x 10. Найти максимальное значение среди сумм элементов всех ее столбцов и номер столбца с этим максимальным значением. 
     
109. Дана матрица размера 5 x 10. Найти минимальный среди максимальных элементов каждой строки. 
     
110. Дана целочисленная матрица размера 5 x 10. Вывести номер ее последней строки, содержащей равное количество положительных и отрицательных элементов (нулевые элементы не учитываются). Если таких строк нет, то вывести 0. 
     
111. Дана матрица размера 5 x 10. Вывести номер ее первой строки, содержащей только положительные элементы. Если таких строк нет, то вывести 0. 
     
112. Дана целочисленная матрица размера M x N. Различные строки (столбцы) матрицы назовем похожими, если совпадают множества чисел, встречающихся в этих строках (столбцах). Найти количество столбцов, похожих на первый столбец. 
     
113. Дана целочисленная матрица размера M x N. Найти количество ее столбцов, все элементы которых различны. 
     
114. Дана целочисленная матрица размера M x N. Вывести номер ее первой строки, содержащего максимальное количество одинаковых элементов. 
     
115. Дана квадратная матрица порядка M. Найти сумму элементов ее главной диагонали. 
     
116. Дана квадратная матрица порядка M. Найти суммы элементов ее диагоналей, параллельных побочной (начиная с одноэлементной диагонали A[1,1]). 
     
117. Дана квадратная матрица порядка M. Вывести минимальные из элементов каждой ее диагонали, параллельной главной (начиная с одноэлементной диагонали A[1,M]).
     
118. Дана квадратная матрица порядка M. Заменить нулями элементы матрицы, лежащие выше главной диагонали. 
     
119. Дана квадратная матрица порядка M. Заменить нулями элементы, лежащие одновременно выше главной диагонали (включая эту диагональ) и ниже побочной диагонали (также включая эту диагональ). 
     
120. Дана квадратная матрица порядка M. Зеркально отразить ее элементы относительно главной диагонали матрицы. 
     
121. Дана квадратная матрица порядка M. Повернуть ее на 180 градусов в положительном направлении. 
     
122. Дана матрица размера 5 x 10. Вывести количество столбцов, элементы которых монотонно убывают. 
     
123. Дана матрица размера 5 x 10. Найти минимальный1|максимальный2 среди элементов тех строк3|столбцов4, которые упорядочены либо по возрастанию, либо по убыванию. Если такие строки3|столбцы4 отсутствуют, то вывести 0. 
     
124. Даны два числа k1 и k2 и матрица размера 4 x 10. Поменять местами строки1|столбцы2 матрицы с номерами k1 и k2. 
     
125. Дана матрица размера 5 x 10. Поменять местами строки1|столбцы2, содержащие минимальный и максимальный элементы матрицы. 
     
126. Дана матрица размера 5 x 10. Поменять местами столбец с номером 11|102 и первый3|последний4 из столбцов, содержащих только положительные элементы. 
     
127. Дано число k и матрица размера 4 x 10. Удалить строку1|столбец2 матрицы с номером k.
     
128. Дана матрица размера 5 x 10. Удалить строку1|столбец2, содержащий минимальный3|максимальный4 элемент матрицы. 
     
129. Дана матрица размера 5 x 10. Удалить первый1|последний2|все3 столбцы, содержащие только положительные элементы. 
     
130. Дано число k и матрица размера 4 x 9. Перед1|после2 qrpnjh3|столбца4 матрицы с номером k вставить строку3|столбец4 из нулей. 
     
131. Дана матрица размера 4 x 9. Продублировать строку1|столбец2 матрицы, содержащий ее минимальный3|максимальный4 элемент. 
     
132. Дана матрица размера 5 x 9. Перед1|после2 первого3|последнего4 столбца, содержащего только положительные элементы, добавить столбец, состоящий из единиц. 
     
133. Дана целочисленная матрица размера M x N. Найти элемент, являющийся максимальным в своей строке и минимальным в своем столбце. Если такой элемент отсутствует, то вывести 0. 
     
134. Дана матрица размера M x N. Элемент называется локальным минимумом (максимумом), если он меньше (больше) всех окружающих его элементов. Заменить все локальные минимумы1|максимумы2 данной матрицы на 0. 
     
135. Дана матрица размера M x N. Поменять местами ее строки1|столбцы2 так, чтобы их минимальные3|максимальные4 элементы образовывали возрастающую5|убывающую6 последовательность.
     

Функции

136. Описать функцию Min2(A,B) вещественного типа, находящую минимальное из двух вещественных чисел A и B. С помощью этой функции найти минимальные из пар чисел A и B, A и C, A и D, если даны числа A, B, C, D. 
     
137. Описать процедуру Minmax(A,B), записывающую в переменную A минимальное из значений A и B, а в переменную B — максимальное из этих значений (A и B — вещественные параметры, являющиеся одновременно входными и выходными). Используя четыре вызова этой процедуры, найти минимальное и максимальное из чисел A, B, C, D. 
     
138. Используя процедуру Minmax из задания Proc2, описать функцию Min3(A,B,C)1|Max3(A,B,C)2 вещественного типа, находящую минимальное1|максимальное2 из трех вещественных чисел A, B и C. С помощью этой функции найти минимальные1|максимальные2 из наборов (A,B,C), (A,B,D), (A,C,D), если даны числа A, B, C, D. 
     
139. Используя функцию Min21|Max22 из задания Proc1, описать функцию Min4(A,B,C,D)1|Max4(A,B,C,D)2 вещественного типа, находящую минимальное1|максимальное2 из четырех вещественных чисел A, B, C и D. С помощью этой функции найти минимальные1|максимальные2 из наборов (A,B,C,D), (A,B,C,E), (A,C,D,E), если даны числа A, B, C, D, E. 
     
140. Описать функцию Fact(N) целого типа, вычисляющую значение факториала N! = 1·2·...·N (N > 0 — параметр целого типа). С помощью этой функции вычислить факториалы 10 данных чисел. 
     
141. Описать функцию FactR(N) вещественного типа, позволяющую вычислять приближенное значение факториала N! = 1·2·...·N для целых N (> 0). С помощью этой функции вычислить факториалы пяти данных чисел. 
     
142. Описать функцию Fact2(N) целого типа, вычисляющую значение "двойного факториала": N!! = 1·3·5·...·N, если N — нечетное, N!! = 2·4·6·...·N, если N — четное (N > 0 — параметр целого типа). С помощью этой функции вычислить двойные факториалы десяти данных чисел. 
     
143. Описать нерекурсивную функцию Fib(N) целого типа, вычисляющую N-е число Фибоначчи F(N) по формуле: F(1) = F(2) = 1, F(k) = F(k–2) + F(k–1), k = 3, 4, ... . С помощью этой функции вычислить 10 чисел Фибоначчи с указанными номерами. 
     
144. Описать процедуру SumDigit(N,S), находящую сумму цифр S целого числа N (N — входной, S — выходной параметр). Используя эту процедуру, найти суммы цифр пяти данных чисел. 
     
145. Описать нерекурсивную функцию NOD2(A,B) целого типа, находящую наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида: НОД(A,B) = НОД(B mod A,A), если A <> 0; НОД(0,B) = B. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D. 
     
146. Используя функцию NOD2 из задания Proc10, описать процедуру Frac(a,b,p,q), преобразующую дробь a/b к несократимому виду p/q (все параметры процедуры — целого типа). Знак результирующей дроби p/q приписывается числителю (т.е. q > 0). С помощью этой процедуры найти несократимые дроби, равные a/b + c/d, a/b + e/f, a/b + g/h (числа a, b, c, d, e, f, g, h даны). 
     
147. Описать функцию Exp1(x,eps) вещественного типа (параметры x, eps — вещественные, eps > 0), находящую приближенное значение функции exp(x): exp(x) = 1 + x + x2 / 2! + x3 / 3! + ... + xn / n! + ... . В сумме учитывать все слагаемые, большие eps. С помощью Exp1 найти приближенное значение экспоненты для данного x при шести данных eps. 
     
148. Описать функцию Sin1(x,eps)1|Cos1(x,eps)2 вещественного типа (параметры x, eps — вещественные, eps > 0), находящую приближенное значение функции sin(x)1|cos(x)2: [sin(x) = x – x3 / 3! + x5 / 5! – ... + (–1)n x2n+1 / (2n+1)! + ...]1| [cos(x) = 1 – x2 / 2! + x4 / 4! – ... + (–1)n x2n / (2n)! + ...]2. В сумме учитывать все слагаемые, большие по модулю eps. С помощью Sin11|Cos12 найти приближенное значение синуса1|косинуса2 для данного x при шести данных значениях eps. 
     
149. Описать функцию Ln1(x,n)1|Arctg1(x,n)2 вещественного типа (параметры x, eps — вещественные, |x| < 1, eps > 0), находящую приближенное значение функции ln(1+x)1|arctg(x)2: [ln(1+x) = x – x2 / 2 + x3 / 3 – ... + (–1)n xn+1 / (n+1) + ...]1| [arctg(x) = x – x3 / 3 + x5 / 5 – ... + (–1)n x2n+1 / (2n+1) + ...]2. В сумме учитывать все слагаемые, большие по модулю eps. С помощью Ln11|Arctg12 найти приближенное значение ln(1+x)1|arctg(x)2 для данного x при шести данных значениях eps. 
     
150. Описать функцию PowerA(x,a,eps) вещественного типа (параметры x, a, eps — вещественные, |x| < 1, a > 0, eps > 0), находящую приближенное значение функции (1+x)a: (1+x)a = 1 + a·x + a·(a–1)·x2 / 2! + ... + a·(a–1)·...·(a–n+1)·xn / n! + ... . В сумме учитывать все слагаемые, большие по модулю eps. С помощью PowerA найти приближенное значение (1+x)a для данных x и a при шести различных значениях eps. 
     
151. Описать функцию Otr(Ax,Ay,Bx,By) вещественного типа, находящую длину отрезка AB на плоскости по координатам его концов: |AB| = sqrt((Ax-Bx)2 + (Ay-By)2) (Ax, Ay, Bx, By — вещественные параметры). С помощью этой функции найти длины отрезков AB, AC, AD, если даны координаты точек A, B, C, D. 
     
152. Используя функцию Otr из задания Proc16, описать функцию Perim(Ax,Ay,Bx,By,Cx,Cy) вещественного типа, находящую периметр треугольника ABC по координатам его вершин (Ax, Ay, Bx, By, Cx, Cy — вещественные параметры). С помощью этой функции найти периметры треугольников ABC, ABD, ACD, если даны координаты точек A, B, C, D. 
     
153. Используя функции Otr и Perim из заданий Proc16 и Proc17, описать функцию Area(Ax,Ay,Bx,By,Cx,Cy) вещественного типа, находящую okny`d| треугольника ABC по формуле Герона: SABC = sqrt(p·(p–|AB|)·(p–|AC|)·(p–|BC|)), где p — полупериметр. С помощью этой функции найти площади треугольников ABC, ABD, ACD, если даны координаты точек A, B, C, D. 
     
154. Используя функции Otr и Area из заданий Proc16 и Proc18, описать процедуру Dist(Px,Py,Ax,Ay,Bx,By,D), находящую расстояние D от точки P до прямой AB по формуле D = 2SPAB / |AB|, где SPAB — площадь треугольника PAB. С помощью этой процедуры найти расстояния от точки P до прямых AB, AC, BC, если даны координаты точек P, A, B, C. 
     
155. Используя процедуру Dist из задания Proc19, описать процедуру Heights(Ax,Ay,Bx,By,Cx,Cy,hA,hB,hC), находящую высоты hA, hB, hC треугольника ABC, проведенные соответственно из вершин A, B, C. С помощью этой процедуры найти высоты треугольников ABC, ABD, ACD, если даны координаты точек A, B, C, D.
     
156. Написать функцию, которая находит минимальный и максимальный из данных n элементов. 
     
157. Написать функцию, которая находит номера минимального и максимального из данных n элементов. 
     
158. Написать функцию, которая находит номера первого и последнего максимального из данных n целочисленных элементов. 
     
159. Написать функцию, которая находит количество минимальных из данных n целочисленных элементов. 
     
160. Написать функцию, которая находит минимальный четный из данных n ненулевых целочисленных элементов. Если требуемые элементы отсутствуют, то вывести 0. 
     
161. Написать функцию, которая находит минимальный положительный из данных n элементов. Если требуемые элементы отсутствуют, то вывести 0. 
     
162. Написать функцию, которая для данных чисел a, b (0 < a < b) и набора из n элементов находит максимальный из элементов, содержащихся в интервале (a, b). Если требуемые элементы отсутствуют, то вывести –1. 
     
163. Написать функцию, которая для данного набора из n целочисленных элементов находит количество элементов, расположенных после первого максимального. 
     
164. Написать функцию, которая находит номер первого экстремального (то есть минимального или максимального) из данных n целочисленных элементов. 
     
165. Написать функцию, которая для данного набора из n целочисленных элементов. находит количество элементов, содержащихся между первым и последним минимальным. Если в наборе имеется единственный минимальный элемент, то вывести 0. 
     
166. Написать функцию, которая находит два наименьших из данных n элементов. 
     
167. Написать функцию, которая для данного набора из n целочисленных элементов. находит максимальное количество подряд идущих максимальных элементов.
     

Рекурсивные алгоритмы

168. Описать рекурсивные функции Fact(N) и Fact2(N) вещественного типа, вычисляющие значения факториала N! и двойного факториала N!! соответственно (N > 0 — параметр целого типа). С помощью этих функций вычислить факториалы и двойные факториалы пяти данных чисел. 
     
169. Описать рекурсивную функцию PowerN(x,n) вещественного типа, находящую значение n-й степени числа x по формуле: x0 = 1, x_n = x·x_n–1 при n > 0, x_n = 1 / x–n при n < 0 (x >= 0 — вещественное число, n — целое). С помощью этой функции найти значения XN при 5 различных значениях N для данного X. 
     
170. Описать рекурсивную функцию SqrtK(x,k,n) вещественного типа, находящую приближенное значение корня k-й степени из числа x по формуле: y(0) = 1, y(n+1) = y(n) – (y(n) – x / y(n)k–1) / k, где y(n) обозначает SqrtK(x,k,n) (x — вещественный параметр, k и n — целые; x > 0, k > 1, n > 0). С помощью этой функции найти приближенные значения корня K-й степени из X при 6 различных значениях N для данных X и K. 
     
171. Описать рекурсивную функцию FibRec(N) целого типа, вычисляющую N-е число Фибоначчи F(N) по формуле: F(1) = F(2) = 1, F(k) = F(k–2) + F(k–1), k = 3, 4, ... . С помощью этой функции найти пять чисел Фибоначчи с указанными номерами и вывести эти числа. 
     
172. Описать рекурсивную функцию C(m,n) целого типа, находящую число сочетаний из n элементов по m, используя формулу: C(0,n) = C(n,n) = 1, C(m,n) = C(m,n–1) + C(m–1,n–1) при 0 < m < n (m и n — целые параметры; n > 0, 0 <= m <= n). Дано число N и пять различных значений M. Вывести числа C(M,N) вместе с количеством рекурсивных вызовов функции C, потребовавшихся для их нахождения. 
     
173. Описать рекурсивную функцию NOD(A,B) целого типа, находящую наибольший общий делитель двух натуральных чисел A и B, используя алгоритм Евклида: NOD(A,B) = NOD(B mod A,A), если A <> 0; NOD(0,B) = B. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D. 
     
174. Описать рекурсивную функцию MinRec(A,N) вещественного типа, которая находит минимальный элемент вещественного массива A размера N, не используя оператор цикла. С помощью функции MinRec найти минимальные элементы массивов A, B, C размера NA, NB, NC соответственно. 
     
175. Описать рекурсивную функцию Digits(S) целого типа, находящую количество цифр в строке S без использования оператора цикла. С помощью этой функции найти количество цифр в данных пяти строках. 
     
176. Описать рекурсивную функцию Simm(S) логического типа, проверяющую, является ли симметричной строка S, без использования оператора цикла. С помощью этой функции проверить данные пять строк.
     
177. Описать рекурсивную функцию быстрого возведения в натуральную степень.
     

Символы и строки

178. Описать функцию IsIdent(S) целого типа, проверяющую, является ли строка S допустимым идентификатором С++. При утвердительном ответе возвращается 0. Если S является пустой строкой, то возвращается –1, если строка начинается с цифры, то возвращается –2. Если S содержит недопустимые символы, то возвращается номер первого недопустимого символа. Проверить с помощью этой функции пять данных строк. 
     
179. Описать функцию FillStr(S,Len) строкового типа, возвращающую строку длины Len, заполненную повторяющимися копиями строки-шаблона S (последняя копия строки-шаблона может входить в результирующую строку частично). Используя эту функцию, сформировать по данному числу Len и пяти данным строкам-шаблонам пять результирующих строк длины Len. 
     
180. Описать процедуру UpCase(S), преобразующую все строчные буквы строки S в прописные (остальные символы строки S не изменяются). Используя эту процедуру, преобразовать пять данных строк. 
     
181. Описать процедуру TrimL(S), удаляющую в строке S начальные пробелы. Используя эту процедуру, преобразовать пять данных строк. 
     
182. Описать функцию PosLast(subS,S) целого типа, возвращающую номер позиции, с которой в строке S содержится последнее вхождение подстроки subS. Если в строке S отсутствуют подстроки subS, то функция возвращает 0. Вывести значения этой функции для пяти данных пар subS и S. 
     
183. Описать функцию PosK(subS,S,k) целого типа, возвращающую номер позиции, с которой в строке S содержится k-е вхождение подстроки subS (k > 0). Если количество вхождений subS в строке S меньше k, то функция возвращает 0. Вывести значения этой функции для пяти данных троек: k, subS и S. 
     
184. Описать функцию WordN(S,k) строкового типа, возвращающую k-е слово строки S (под словом понимается набор символов, не содержащий пробелов и ограниченный пробелами или началом/концом строки). Если количество слов в строке меньше k, то функция возвращает пустую строку. Используя эту функцию, выделить из данной строки S слова с номерами k1, k2, k3. 
     
185. Описать процедуру SplitStr(S,W,N), которая формирует по данной строке S набор слов W, входящих в S (W — выходной строковый массив; N — его размер; предполагается, что N не будет превышать 10). Под словом понимается набор символов, не содержащий пробелов и ограниченный пробелами или началом/концом строки. Используя эту функцию, вывести количество слов N, содержащихся в данной строке S, и сами эти слова. 
     
186. Описать функцию DecToBin(N) строкового типа, которая возвращает строковое представление целого неотрицательного числа N в двоичной системе счисления. Результирующая строка состоит из символов ['0'–'1'] и не содержит ведущих нулей (за исключением представления числа 0). Используя эту функцию, получить двоичные представления данных пяти чисел. 
     
187. Описать функцию HexToDec(S)2 целого типа, которая определяет целое неотрицательное число по его строковому представлению S в 16-ричной системе счисления. Строка S состоит из символов ['0'–'9', 'A'–'F'] и не содержит ведущих нулей (за исключением значения '0'). Используя эту функцию, вывести пять чисел, для которых даны их 16- ричные представления.
     

Файлы

188. Описать функцию getInt(Name,k) целого типа, возвращающую k-й элемент файла целых чисел с именем Name (элементы нумеруются от 0). Если файл не существует или не содержит k-го элемента, то функция возвращает 0. С помощью этой функции вывести пять элементов данного файла с указанными номерами. 
     
189. Описать функцию getLine(Name,k) строкового типа, возвращающую k-ю строку текстового файла с именем Name (строки нумеруются от 0). Если файл не существует или не содержит k-й строки, то функция возвращает пустую строку. С помощью этой функции вывести пять строк данного файла с указанными номерами. 
     
190. Описать функцию IntFileSize(Name) целого типа, возвращающую размер файла целых чисел с именем Name. Если файл не существует, то функция возвращает –1. С помощью этой функции определить размер трех файлов с данными именами. 
     
191. Описать функцию TextSize(Name) целого типа, возвращающую число строк в текстовом файле с именем Name. Если файл не существует, то функция возвращает –1. С помощью этой функции определить размер трех файлов с данными именами. 
     
192. Описать процедуру InvertIntFile(Name), меняющую порядок следования элементов файла целого типа с именем Name на противоположный. Если файл не существует или содержит менее двух элементов, то процедура не выполняет никаких действий. Обработать с помощью этой процедуры три файла с данными именами. 
     
193. Описать процедуру SplitIntFile(Name0,k,Name1,Name2), jnohps~ys~ первые k (>= 0) элементов существующего файла целых чисел с именем Name0 в файл Name1, а остальные элементы — в файл Name2 (прежнее содержимое результирующих файлов стирается). Один из результирующих файлов может оказаться пустым. Применить эту процедуру к файлу Name0, используя указанные значения Name1, Name2 и k. 
     
194. Описать процедуру SplitText(Name0,k,Name1,Name2), копирующую первые k (>= 0) строк существующего текстового файла с именем Name0 в файл Name1, а остальные элементы — в файл Name2 (прежнее содержимое результирующих файлов стирается). Один из результирующих файлов может оказаться пустым. Применить эту процедуру к файлу Name0, используя указанные значения Name1, Name2 и k. 
     
195. Описать процедуру ConcatFile(NameA,NameB,NameAB), позволяющую объединить содержимое двух двоичных файлов NameA и NameB одного и того же типа в новом файле NameAB. Использовать процедуры BlockRead и BlockWrite. Применить эту процедуру к парам исходных файлов Name1–Name2, Name1–Name3 и Name2–Name3, создав файлы с именами Name12, Name13, Name23. 
     
196. Описать процедуру StringFileToText(Name)1|TextToStringFile(Name)2, преобразующую [двоичный строковый]1|текстовый2 файл с именем Name в текстовый1|[двоичный строковый]2 файл с тем же именем. Используя эту процедуру, преобразовать два данных строковых1|текстовых2 файла с именами Name1 и Name2 в текстовые1|строковые2. 
     
197. Описать процедуру CodeText(Name,k), шифрующую текстовый файл с именем Name, выполняя циклическую замену каждой русской буквы на букву, расположенную в алфавите на k-й позиции после исходной (0 < k < 11). Например, при k = 3 "А" перейдет в "Г", "а" — в "г", "Я" — в "В". Букву "ё" в алфавите не учитывать, прочие символы файла не изменять. Используя эту процедуру и зная k, зашифровать1|расшифровать2 данный файл.
     

Задания по программированию I I семестр


Каждое задание оценивается по 100-бальной системе.

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


ЗАДАНИЕ 1. Очереди и стеки


Задачи для самостоятельного решения (6 задач – 100 баллов): A, B, C, D, E, F.


Решения проверяются на заранее подготовленных преподавателем тестах. Задача считается решенной, если она проходит все тесты.

Problem A. Простой стек

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

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

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

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Пример протокола работы программы

Stdin	stdout
push 2 push 3 push 5 back size pop size push 7 pop clear size exit	ok ok ok 5 3 5 2 ok 7 ok 0 bye

Problem B. Стек с защитой от ошибок

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

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

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

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.


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

Пример протокола работы программы

stdin	stdout
push 2 back pop size pop push 1 size exit	ok 2 2 0 error ok 1 bye

Problem C. Стек неограниченного размера

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

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

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

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

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

Пример протокола работы программы

stdin	stdout
push 2 push 3 push 5 back size pop size push 7 pop clear size exit	ok ok ok 5 3 5 2 ok 7 ok 0 bye

Problem D. Простая очередь

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

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

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

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Problem E. Очередь с защитой от ошибок

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

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

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

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

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

Problem F. Очередь неограниченного размера

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

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

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

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

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


ЗАДАНИЕ 2. Графы, деревья


Problem A. Матрица смежностей


В первой строке стандартного потока ввода заданы два натуральных числа, разделенных пробелом – количество узлов неориентированного графа N и количество ребер M. В последующих М строках заданы ребра графа в виде пары натуральных чисел, разделенных пробелом.

Необходимо заполнить матрицу смежности для заданного графа и ввести ее на экран.

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

Пример входных данных

3 3

1 2

2 3

3 1

Пример выходных данных

0 1 1

1 0 1

1 1 0


2 2 2


Problem B. Списки смежностей


В первой строке стандартного потока ввода заданы два натуральных числа, разделенных пробелом – количество узлов неориентированного графа N и количество ребер M. В последующих М строках заданы ребра графа в виде пары натуральных чисел, разделенных пробелом.

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

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

Пример входных данных

4 5

1 2

2 3

3 4

4 1

1 3

Пример выходных данных

1 2 3 4

2 1 3

3 1 2 4

4 1 3


3 2 3 2