1. Задачи второго, среднего уровня

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

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

3. Из рассортированного списка целых чисел удалить повторяющиеся числа, оставив их по одному разу.

4. В нерассортированный список целых чисел после каждого положительного числа вставить его номер в исходном списке.

5. В нерассортированный список вещественных чисел после каждого максимального числа вставить номер в списке и номер среди максимальных элементов этого же списка.

6. В нерассортированный список вещественных чисел после каждой тройки чисел вставить их среднеарифметическое значение. Если в конце списка осталось меньше трёх чисел, вставить среднеарифметическое значение из двух чисел или вставить последнее число.

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

8. Создать список, элементом которого является прямая плоскости y=k*x +b, т. е. два числа k и b. Удалить все прямые, перпендикулярные оси OX.

9. Создать список, элементом которого является прямая плоскости y=k*x +b, т. е. два числа k и b. Удалить все прямые, параллельные первой прямой этого же списка.

10. Создать список, элементом которого являются координаты вершин треугольников на плоскости. Удалить все треугольники с одинаковым наименьшим периметром.

11. Создать список, элементом которого являются координаты вершин треугольников на плоскости. После каждого треугольника, вершины которых находятся в разных четвертях, вставить треугольник, симметричный относительно оси OY.

12. Создать список, элементом которого являются координаты центра и радиус окружности на плоскости. После каждой окружности первой четверти вставить окружность, центр которой сдвинут на r (радиус) величин вправо.

13. Создать список, элементом которого являются координаты вершин четырёхугольников на плоскости. После каждого квадрата со сторонами, параллельными осям координат, вставить квадрат с тем же центром, стороны которого параллельны осям координат и в два раза меньше.

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

15. Пусть матрица записана в оперативной памяти в виде списка (см. прим. 14). Из матрицы удалить строки, у которых первый ненулевой элемент положительный, а последний ненулевой элемент – отрицательный.

16. Пусть матрица записана в оперативной памяти в виде списка (см. прим. 14). После каждой строки, содержащей только отрицательные числа, вставить новую строку, которая получается умножением каждого элемента этой строки на -1.

17. Пусть матрица записана в оперативной памяти в виде списка (см. прим. 14). Поменять местами первую строку с той, в которой находится наибольший элемент всей матрицы.

18. Пусть матрица записана в оперативной памяти в виде списка (см. прим. 14). Поменять местами строку с наибольшим элементом со строкой с наименьшим элементом матрицы. Если таких строк несколько, т. е. наибольших (наименьших) элементов матрицы несколько и они находятся в разных строках, то переставить любые такие строки.

19. Создать список слов. Из списка удалить слова наименьшей длины, кроме первого.

20. Создать список слов. Из списка удалить слова, у которых гласных больше половины и которые начинаются с гласной буквы.

21. Из введённого текста создать список слов. Из списка удалить те слова, которые начинаются на заданную букву.

22. Создать стек слов. Удалить все слова, пока не встретится слово заданной длины.

С. Задачи повышенной сложности

1. Из нерассортированного списка целых чисел удалить повторяющиеся числа, оставив их по одному разу.

2. Создать список вещественных чисел. После серии подряд идущих повторяющихся чисел вставить количество их повторений.

3. Создать два списка целых чисел. Рассортировать каждый из них, используя алгоритм обмена. Из двух рассортированных списков путём их слияния получить новый рассортированный список, не используя третий раз алгоритм сортировки.

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

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

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

7. Создать список слов. Рассортировать список (слова) по их длине. Слова с одинаковой длиной сортировать по двум первым буквам.

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

Лабораторная работа 9

Тема. Работа с текстовым файлом.

Требования и общие указания к заданиям:

Необходимо разработать и проверить функции для реализации следующих действий с текстовым файлом:

• создание файла;

• просмотр файла, т. е. вывод его содержимого на экран;

• добавление текста в файл;

• реализация функциональной части, указанной в варианте, и запись полученного результата во второй текстовый файл.

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

Варианты заданий

B. Задачи второго среднего уровня

1. Каждую букву заменить её номером в алфавите. В одной строке экрана одним цветом вывести символы строки с двумя пробелами между ними, а ниже другим цветом — номера символов.

2. В тексте одну введённую подстроку, не обязательно являющуюся словом, заменить другой введённой подстрокой. При выводе исходной и изменённой строки старую и новую подстроку выделить другим цветом.

3. В каждом слове текста k-ю букву заменить заданным символом. Если k больше длины слова, корректировку не выполнять.

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

5. После каждого слова текста вставить указанную подстроку.

6. После k-го символа слова вставить указанную подстроку. Если k больше длины слова, вставку не выполнять.

7. После одного слова текста вставить другое слово.

8. Удалить все символы (кроме пробелов), не являющиеся буквами. Между последовательностями подряд идущих букв оставить хотя бы один пробел.

9. Удалить все слова заданной длины.

10. Удалить все слова-палиндромы.

11. Удалить из текста его часть, заключённую между двумя вводимыми с экрана символами (например, между скобками “{“ и “}”, между звёздочками и т. п.). Считать, что эти символы могут быть только в одной строке.

12. Обработка текста программы на языке С++ как последовательности строк символов. В качестве входной информации разрабатываемой программы задан некоторый элемент языка или небольшой фрагмент программы. Необходимо записать его в файл и найти количество всех символов (длину) каждого комментария, записанного после символов “//”. Для других целей эти символы не используются. В строке может быть записан только один комментарий.

13. Из текста программы (см. 12) удалить комментарии, ограниченные символами “/*” и “*/”. Для других целей эти символы не используются. Считать, что эти символы могут быть только в одной строке.

14. Сколько раз в тексте программы (см. 12) используется вывод с помощью cout ? Предусмотреть, что это ключевое слово может быть в текстовой константе.

15. Сколько раз в тексте программы (см. 12) используется ввод с помощью cin ? Предусмотреть, что это ключевое слово может быть в комментариях после символов //.

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

С. Задачи повышенной сложности

1. Найти и вывести те предложения (см. 16), в которых есть одинаковые слова.

2. Найти одно любое слово в каждом предложении (см. 16), которое есть в следующем предложении. Последнее предложение не анализируется.

3. В каждом вопросительном предложении текста (см. 16) найти и вывести без повторений слова заданной длины.

4. В каждом предложении текста (см. 16) поменять местами первое слово с последним словом.

5. Удалить из текста его часть, заключённую между двумя вводимыми с экрана символами (например, между скобками “{“ и “}”, между звёздочками и т. п.) или между двумя парами символов (например, между “/*” и “*/”, то есть комментарии из текста программы). Считать, что эти символы могут быть в разных строках.

6. Текст шифруется по следующему правилу: из исходного текста выбирается 1-й, 4-й, 7-й, 10-й и т. д. символы, затем 2-й, 5-й, 8, 11-й и т. д. символы, затем 3-й, 6-й, 9-й, 12-й и т. д. символы. Зашифровать заданный текст, то есть на основании исходного текстового файла получить новый файл по указанному выше правилу.

7. Пусть зашифрован текст по правилу, описанному в предыдущем примере, то есть в файле хранится зашифрованный текст. Расшифровать заданный текст, то есть получить второй новый файл.

8. Обработка текста программы на языке С++ как последовательности строк символов. В качестве входной информации разрабатываемой программы задан некоторый элемент языка или небольшой фрагмент программы. Необходимо записать его в файл и проанализировать в зависимости от варианта. Найти все вложенные операторы if.

9. Задана полная форма оператора if (см 8). Пусть в каждой его ветви записан простой оператор, присваивающий целой переменной значение константы. В качестве логического выражения в скобках if записано сравнение двух простых переменных с помощью операций сравнения. Определить правильность записи оператора if.

10. Задан заголовок оператора for (см. 8). Есть ли в нём синтаксические ошибки? Предполагается, что каждое из трёх выражений имеет простой вид. В первом из них одной переменной присваивается значение константы. Во втором выражении используются только операции сравнения перменной с целой константой типа n<10 и нет логических операций. В третьем выражении используются только операции ++, - - (например, i++) , +=, - = (типа x+=2), где слева переменная, а справа константа целого типа.

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

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

13. Найти количество операторов в теле цикла каждого оператора do … while (см. 8). Независимо от количества операторов тела цикла фигурные скобки всегда записываются. В теле цикла отсутствуют операторы, которые требуют фигурных скобок.

14. Проанализировать баланс фигурных скобок при условии, что они используются только для объединения нескольких простых операторов в один блок (см. 8).

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

Тема. Файлы в экономических задачах.

Требования и общие указания к заданиям:

Необходимо разработать и проверить функции для реализации следующих действий с файлами:

• создание файла, записи которого имеют указанную структуру;

• просмотр файла, т. е. “чистый” вывод его содержимого на экран в удобном для анализа виде без никакой обработки и анализа;

• добавление записей в конец файла (аналогично созданию, только файл открываем с режимом “a”);

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

Замечание. Кроме предложенных здесь вариантов заданий можно использовать задачи из лабораторной работы 6 этого второго семестра.

Варианты заданий

A. Задачи первого, простого уровня

1. Структура записей файла: отделение; фамилия, имя, отчество; массив из пяти оценок. Для заданного отделения вывести фамилии, имена, отчества “двоечников”.

2. Структура записей файла: курс; фамилия, имя, отчество; массив из пяти оценок по десятибалльной системе. Для заданного курса вывести фамилии, имена, отчества “отличников”, у которых только оценки “9” и (или) “10”.

3. Структура записей файла: отделение; фамилия, имя, отчество; массив оценок; признак. Для каждого студента получить одно из следующих значений признака: 5 – отличник с оценками “9”, “10”; 4 – хорошист, у которого есть хотя бы одна хорошая оценка (“6”, “7”, “8”), но нет оценок, меньше “6”; 3 – троечник, у которого есть хотя бы одна удовлетворительная оценка ( “4”, “5”), но нет оценок, меньше “4”; 2 – неуспевающий, у которого есть хотя бы одна неудовлетворительная оценка (“1”, “2”, или “3”).

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

5. Структура записей файла: отделение; фамилия, имя, отчество; массив оценок. Вывести список (фамилия, инициалы; массив оценок) неуспевающих студентов.

6. Структура записей файла: шифр подразделения; фамилия, имя, отчество; год рождения; образование (например: 0 – неоконченное базовое, 1 – базовое, 2 – общее среднее и т. д.). Для заданного подразделения, шифр которого вводим, вывести фамилии и инициалы сотрудников с неоконченным базовым и базовым образованием.

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

8. Структура записей файла: шифр подразделения; фамилия, имя, отчество сотрудника; год поступления на работу. Найти количество и процент работников со стажем работы до пяти лет и вывести их фамилии и инициалы.

9. Структура записей файла: шифр темы; шифр книги; фамилия, имя, отчество автора; название книги; издательство; год издания. Вывести список книг по заданной теме, изданных позже указанного года.

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

11. Структура записей файла: шифр подразделения; план выпуска продукции по кварталам одного года в виде массива; фактическое выполнение плана по кварталам одного года в виде массива; процент выполнения плана по кварталам одного года в виде массива. Для каждого подразделения получить процент выполнения плана по кварталам.

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

13. Структура записей файла: номер телефона; фамилия, имя, отчество абонента; адрес (улица, дом, квартира). По введённому номеру телефона вывести фамилию, инициалы и адрес абонента или сообщение, что такого телефона в файле нет.

14. Структура записей файла: номер телефона; фамилия, имя отчество абонента; адрес (улица, дом, квартира). Скорректировать файл после установки новых телефонов, информация о которых (см. структуру записей) вводится с экрана.

15. Структура записей файла: шифр сбербанка; номер счёта; размер вклада. Найти и вывести номера счетов и шифры сбербанков с максимальным размером вклада.

B. Задачи второго, среднего уровня

1. Структура записей файла: отделение; фамилия, имя, отчество; массив из пяти оценок. Для заданного отделения вывести фамилии и инициалы “двоечников” по убыванию общего количества плохих оценок (“1”, “2”, “3”).

2. Структура записей файла: курс; фамилия, имя, отчество; массив из пяти оценок по десятибалльной системе. Для заданного курса вывести фамилии и инициалы “отличников” с оценками “9” и “10” по убыванию среднего бала.

3. Структура записей файла: отделение; фамилия, имя, отчество; массив оценок; признак. Для каждого студента получить одно из следующих значений признака: 5 – отличник с оценками “9”, “10”; 4 – хорошист, у которого есть хотя бы одна хорошая оценка (“6”, “7”, “8”), но нет оценок, меньше “6”; 3 – троечник, у которого есть хотя бы одна удовлетворительная оценка (“4”, “5”), но нет оценок, меньше “4”; 2 – неуспевающий, у которого есть хотя бы одна неудовлетворительная оценка (“1”, “2”, или “3”). Студентов заданного отделения рассортировать по этому полученному признаку. Для одинакового признака сортировать по среднему баллу.

4. Структура записей файла: курс; фамилия, имя, отчество; массив оценок в десятибалльной системе; материальное положение (например: 0, 1); размер стипендии. Для каждого студента определить размер стипендии, выбрав самостоятельно критерий. Рассортировать студентов по курсам, внутри курса – по полученной стипендии.

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

6. Структура записей файла: шифр подразделения; фамилия, имя, отчество; год рождения; образование (например, 0 – неоконченное базовое, 1 – базовое, 2 – общее среднее и т. д.). Для заданного подразделения, шифр которого вводим, вывести информацию о сотрудниках сначала по образованию, а затем для одинакового образования по возрасту.

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

8. Структура записей файла: шифр подразделения; фамилия, имя, отчество сотрудника; год поступления на работу. Для каждого подразделения найти количество и процент работников со стажем работы до 5 лет, от 6 до 10 лет, от 11 до 15лет и т. д.

9. Структура записей файла: шифр темы; шифр книги; фамилия, имя, отчество автора; название книги; издательство; год издания. Вывести список книг по заданной теме указанного издательства по убыванию года издания.

10. Структура записей файла: шифр темы; шифр книги; фамилия, имя, отчество автора; название книги; издательство; год издания. Вывести список книг, изданных в заданном издательстве, по возрастанию шифра темы.

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

12. Структура записей файла: фамилия, имя, отчество; результат соревнований по некоторому виду спорта. Найти три лучших результата и соответствующие фамилии участников. Таких победителей может быть больше трёх, так как одинаковые результаты могли показать несколько участников.

13. Структура записей файла: фамилия, имя, отчество; пол; результат соревнований по некоторому виду спорта. Найти лучший результат среди женщин и соответствующие фамилии участников (не обязательно одна) и лучший результат среди мужчин и соответствующие фамилии участников (также не обязательно одна).

14. Структура записей файла: шифр сбербанка; номер счёта; размер вклада. Для каждого сбербанка найти общее количество вкладчиков и средний размер вклада.

15. Структура записей файла: шифр сбербанка; номер счёта; размер вклада. Ввести информацию о поступлении денег на счета и об их снятии со счетов. Выполнить корректировку файла.

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

17. Структура записей файла: шифр подразделения; шифр сотрудника; фамилия, имя, отчество; год поступления на работу. С экрана вводим следующие данные об уволенных сотрудниках: шифр подразделения и шифр сотрудника. Выполнить удаление соответствующих записей

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

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

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

20. Составить программу планирования и учёта нагрузки одного преподавателя.

21. В файле хранится расписание занятий студентов одного курса некоторого факультета. Вывести расписание для заданной подгруппы.

22. В файле хранится расписание занятий студентов одного курса некоторого факультета. Вывести номера тех подгрупп (и дни), у которых есть “форточки”.

23. В файле хранится расписание занятий студентов одного курса некоторого факультета. Вывести номера тех подгрупп, у которых более одного дня в неделю есть занятия позже введённого времени (например, позже 19 час.).

24. В файле хранится расписание аудиторных занятий преподавателей кафедры. В какие дни у преподавателя нет занятий?

25. В файле хранится расписание аудиторных занятий преподавателей кафедры. Для заданного преподавателя вывести расписание его занятий.

26. В файле хранится расписание аудиторных занятий одного преподавателя. Вывести преподавателей с наибольшим количеством аудиторных занятий в неделю.

Лабораторная работа 11

Тема: Файлы в математических задачах.

Требования и общие указания к заданиям:

Необходимо разработать и проверить функции для реализации следующих действий с файлами:

• создание файла;

• просмотр файла, т. е. “чистый” вывод его содержимого на экран в удобном для анализа виде без никакой обработки и анализа;

• добавление записей в конец файла (аналогично созданию, только файл открываем с режимом “a”);

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

При работе с матрицей оперативную память резервировать не более чем для одной (в некоторых вариантах для двух) строк матрицы. Всю матрицу в оперативной памяти не хранить.

Варианты заданий

A. Задачи первого, простого уровня.

1. В файл записать координаты точек трёхмерного пространства. Найти количество точек, принадлежащих шару, координаты центра и радиус которого заданы и вводятся с экрана.

2. Из заданного множества точек на плоскости, координаты которых должны храниться в файле, найти точки с максимальным расстоянием от заданной точки, координаты которой вводятся с экрана.

3. В файл записать коэффициенты уравнений прямых на плоскости. Посчитать количество прямых, параллельных оси ОХ и количество прямых, параллельных оси ОY.

4. В файл записать координаты вершин выпуклых четырёхугольников на плоскости. Вывести на экран координаты вершин квадратов и найти их количество.

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

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

7. В файл записать построчно вещественную матрицу. Найти строку (одномерный массив из файла) с наибольшим количеством положительных чисел.

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

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

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

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

12. В файл записать вещественную матрицу A. С экрана ввести k — номер строки матрицы. Получить и вывести на экран скалярное произведение k-й строки матрицы на её первую строку.

B. Задачи второго, среднего уровня.

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

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

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

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

5. В один файл записать координаты множества точек плоскости A, а в другой — коэффициенты уравнений прямых B этой же плоскости. Найти две такие различные точки из A, что проходящая через них прямая параллельна наибольшему количеству прямых из B.

6. В один файл записать координаты конечного множества точек плоскости, а в другой — координаты центра и радиусы m концентрических окружностей. Между какими окружностями (первой и второй, второй и третьей и т. д., (m-1)-й и m-й) больше всего точек заданного множества?

7. В файл записать построчно вещественную матрицу. Найти такие две различные строки матрицы, что их скалярное произведение наибольшее.

8. В файл записать построчно целочисленную матрицу, у которой в строке хранятся оценки одного студента на всех экзаменах. Найти номера строк отличников с оценками “9”, “10”; хорошистов, у которых есть хотя бы одна хорошая оценка (“6”, “7”, “8”), но нет оценок, меньше “6”; троечников, у которых есть хотя бы одна удовлетворительная оценка (“4”, “5”), но нет оценок, меньше “4”; неуспевающих, у которых есть хотя бы одна неудовлетворительная оценка (“1”, “2”, или “3”).

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

10. В файл записать построчно целочисленную матрицу. Найти наибольшее из чисел, встречающихся в матрице более одного раза.

11. В файл записать построчно вещественную матрицу. Найти наибольшее среди всех чисел тех строк матрицы, которые упорядочены либо по возрастанию, либо по убыванию.

12. В файл записать вещественную матрицу A. Получить и записать в файл вектор B, i-й элемент которого равен скалярному произведению i-й строки матрицы на её первую строку. Матрицу и полученный вектор вывести на экран.

С. Задачи повышенной сложности

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

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

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

4. Методом Гаусса решить систему n линейных алгебраических уравнений c n неизвестными. Матрица коэффициентов системы и вектор свободных членов хранятся в двух файлах.

5. Методом Гаусса, используя схему выбора главного элемента, решить систему n линейных алгебраических уравнений c n неизвестными. Матрица коэффициентов системы и вектор свободных членов хранятся в двух файлах.

6. В файл записать построчно вещественную квадратную матрицу. Обратить её по схеме единственного деления.

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

8. Методом простой итерации решить систему n линейных алгебраических уравнений c n неизвестными. Матрица коэффициентов системы и вектор свободных членов хранятся в двух файлах.

9. Методом Зейделя решить систему n линейных алгебраических уравнений c n неизвестными. Матрица коэффициентов системы и вектор свободных членов хранятся в двух файлах.

10. Найти собственные числа и собственные векторы записанной в файл матрицы методом непосредственного вычисления определителя.

11. Методом итераций найти наибольшее по модулю собственное значение и соответствующий ему собственный вектор записанной в файл матрицы.

12. В файл записать построчно вещественную матрицу A. Найти все такие i и j, что скалярное произведение i-й строки на j-ю наибольшее.

Лабораторная работа 12

Тема. Указатели на функции.

Требования и общие указания к заданиям:

• составить функцию, которая по заданной формуле (Симпсона, трапеций, прямоугольников и др.) вычисляет значение определённого интеграла от произвольной функции одной переменной или решает произвольное нелинейное уравнение f(x)=0 с помощью заданного численного метода;

• в качестве одного из параметров этой функции использовать указатель на подынтегральную функцию или указатель на функцию левой части уравнения f(x)=0;

• функцию для вычисления определённого интеграла проверить, используя аналитическое выражение для первообразной или с помощью какой-нибудь системы компьютерной математики (Mathcad, Mathematica и др.);

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

• предусмотреть программную проверку найденных решений нелинейных уравнений.

Варианты заданий

В. Задачи второго, среднего уровня

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

,

где n фиксировано, . Составленную функцию проверить для вычисления интеграла . Значение функции y=sin(t) вычислять с заданной точностью ., используя разложение в ряд Тейлора:

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

,

где n фиксировано, . Составленную функцию проверить для вычисления интеграла . Значение функции y=cos(t) вычислять с заданной точностью , используя разложение в ряд Тейлора:

.

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

,

где n фиксировано, Составленную функцию проверить для вычисления интеграла Значение функции y=e^t , где t= 1/x, вычислять с заданной точностью , используя разложение в ряд Тейлора:

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

где n фиксировано, . С помощью составленной функции вычислить значение интеграла для n=3, 6, 9. Для вычисления y = , где t=, составить и использовать функцию, которая реализует следующий итерационный алгоритм: … Вычисления продолжаются до тех пор, пока не выполнится условие . Массив y не формируется, достаточно двух переменных для старого и нового значений y.

5. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной, используя составную формулу трапеций

где n фиксировано, . С помощью составленной функции вычислить значения интеграла для с = 1, 1.2, 1.4, …, 2.8, 3. Для вычисления y = можно использовать стандартную встроенную функцию или вычислять по итерационной формуле, приведенной в варианте 4.

6. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной, используя составную формулу Симпсона

где n фиксировано, . С помощью составленной функции вычислить значение интеграла . Значение функции y=e^t , где t= -x², вычислять с заданной точностью , используя разложение в ряд Тейлора:

7. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной, используя составную формулу Симпсона

где n фиксировано, . С помощью составленной функции вычислить значение интеграла для n=6. Значение функции y=ln(1+t), где t=x², вычислять с заданной точностью , используя разложение в ряд Тейлора: .

8. Составить функцию для вычисления определённого интеграла от произвольной функции одной переменной по следующей формуле:

I,

где n фиксировано и кратно трём, , , С помощью составленной функции вычислить значения интегралов для k = 1/4, 1/2, 1, 2, 4.

9. Составить функцию для приближённого решения произвольного нелинейного уравнения f(x)=0 методом деления отрезка пополам с точностью . Используя эту функцию, решить уравнения

для a = 0.5+0.1k, k=0,1,2,3,4,5 с точностью ₁=0.1.

9. Составить функцию для приближённого решения произвольного нелинейного уравнения f(x)=0 методом простой итерации с точностью . Используя эту функцию, решить уравнения с точностью ₁=0.0001.

Указание. В методе простой итерации исходное уравнение приводится к виду x=(x). Начиная с некоторого заданного начального значения , строим последовательность по правилу. Вычисления прекращаем, если на некотором шаге получим , где — заданная точность решения уравнения.

9. Составить функцию для приближённого решения произвольного нелинейного уравнения f(x)=0 методом Ньютона с точностью . Используя эту функцию, решить уравнения 3x-e^kx = 0 для k = 1, 2, 3, 4, 5 с точностью ₁=10^-5. Значение e^t вычислять с заданной точностью ₂ = 10^-6 с помощью разложения в ряд Тейлора:

e^t=1+t+ .

Указание. В методе Ньютона по заданному начальному приближению x_о строим последовательность по правилу

; n=0,1, 2, 3, …

Вычисления продолжаются до тех пор, пока не выполнится условие . Массив x не формируется, достаточно двух переменных для старого и нового значений x.

12. Составить функцию для приближённого решения нелинейного уравнения f(x)=0 с точностью  методом секущих. Используя эту функцию, решить уравнения для = 2(0.1)3 с точностью ₁=10^-5.

Указание. В методе секущих по двум начальным приближениям строим последовательность по правилу

; n= 1,2, 3, …

Вычисления продолжаются до тех пор, пока не выполнится условие . Массив x не формируется, достаточно двух переменных для старого и нового значений x.

13. Составить функцию для решения произвольного нелинейного уравнения f(x) модифицированным методом секущих с точностью . Используя эту функцию, решить уравнение для =3(0.5)7 с точностью ₌.

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

для n=1, 2, …, при . Вычисления прекращаем, если на некотором шаге получим , где — заданная точность решения уравнения.

13. Составить функцию, которая находит приближенно, с точностью 0,001, минимум произвольной функции от одной переменной на отрезке [u, v]. С помощью составленной функции найти минимум функции y=+sin(x) на отрезке [-0.9, 0.9]. Значение функции y= sin (x) вычислять с заданной точностью , используя разложение в ряд Тейлора:

13. Составить функцию, которая выводит таблицу значений произвольной функции от одной переменной на отрезке [u, v] с шагом h. С помощью составленной функции построить таблицу значений функции y=arctg(x) на отрезке [-1, 1] с шагом h=0.1. Значение функции y=arctg(x) вычислять с заданной точностью , используя разложение в ряд Тейлора:

С. Задачи повышенной сложности.

1—8. Найти приближённое значение определённого интеграла

с заданной точностью , используя соответствующие (см. уровень В) квадратурные формулы. Это означает, что значение интеграла вычисляем не для одного фиксированного количества (n) разбиений отрезка [a, b], а используем двойной пересчёт. Сначала интеграл вычисляем для n разбиений, затем для 2n, 4n и т. д. Вычисления прекращаем, если на некотором шаге получим значение интеграла, полученное на предыдущем шаге, а – значение интеграла, полученное на данном текущем шаге.

Лабораторная работа 13

Тема: Рекурсивные функции.

Требования и общие указания к заданиям.

Выполнить задания двумя способами:

1) используя механизм рекурсии;

2. разработав нерекурсивный алгоритм и запрограммировав его с помощью обычного цикла.

Оба варианта включить в один проект в виде отдельных функций.

B. Задачи второго, среднего уровня.

1. Вычислить для заданного натурального n:

.

2. Найти n-й член числовой последовательности, которая определяется рекуррентной формулой

a₁ = 1, a₂ = 2, a₃ = 3, a_n+1 = 3a_n + 2a_n– + a_n–2.

3. Для заданных вещественного x и натурального n найти значение полинома Чебышева Т_n(x) по рекуррентной формуле

T₀(x) = 1, T₁(x) = x, T_n+1(x) = 2xT_n(x) – T_n–1(x).

1. Найти значение функции С(m,n), где 0 < m < n, если:

.

3. С помощью признака делимости на три проверить, кратно ли данное натуральное число трём.

4. Найти n-ю степень (n – натуральное число) числа а.

5. Найти n-й член арифметической прогрессии с заданными первым членом а и разностью прогрессии d.

6. Найти n-й член геометрической прогрессии с заданными первым членом b и знаменателем прогрессии q.

7. Методом половинного деления уточнить корень уравнения f(х) = 0.

8. Найти максимальный элемент массива а₁, а₂, …, а_n.

9. В одномерном массиве найти i и j такие, что подпоследовательность а_i, а_i+1, …, а_j является перевертышем.

10. В одномерном числовом массиве найти подпоследовательность подряд идущих элементов, сумма которых максимальна.

11. Рассортировать одномерный массив методом простого выбора.

12. В одномерном числовом массиве найти заданное число, используя алгоритм двоичного поиска.

13. Найти значение функции Аккермана, которая определяется для всех неотрицательных целых аргументов m и n следующим образом:

А(0, n) = n + 1;

A(m, 0) = A(m – 1, 1), если (m > 0);

A(m, n) = A(m – 1, A(m, n – 1)), если (m, n > 0).

С. Задачи повышенной сложности.

1. С помощью рекурсивной функции найти с заданной точностью квадратный корень , воспользовавшись итерационной формулой Ньютона:

Y₀=1,

Вычисления продолжать пока |Y_i – Y_i-1| не станет меньше заданного . Используя эту функцию, составить другую рекурсивную функцию, которая для заданного а вычисляет

.

2. Разработать рекурсивную функцию нахождения наибольшего общего делителя двух чисел m и n, используя алгоритм Евклида. Например, для нахождения НОД(96, 36) число 96 представляем как 2 · 36 + 24. Затем число 36 = 1 · 24 +12 и, наконец, 24 = 2 · 12 + 0. Следовательно, НОД(96, 36) = 12. Используя эту функцию, составить вторую рекурсивную функцию для нахождения наибольшего общего делителя натуральных чисел одномерного массива.

НОД(n₀, n₁, ... n_л-1) = НОД (НОД (n₀, n₁, ... n_л–2), n_л-1)_.

3. Найти количество n-значных чисел в m-ичной системе счисления, у каждого из которых сумма цифр равна k. При этом в качестве n-значного числа мы допускаем и числа, начинающиеся с одного или нескольких нулей.

4. Вычислить количество различных представлений заданного натурального числа n в виде суммы не менее двух попарно различных натуральных слагаемых. Представления, отличающиеся лишь порядком слагаемых, различными не считаются.

5. В матрице, состоящей из нулей и единиц, найти прямоугольную подматрицу из одних единиц максимального размера (т. е. с максимальным произведением высоты на длину).

6. В матрице найти прямоугольную подматрицу, сумма элементов которой максимальна.

7. В матрице A найти путь от элемента A[i1, j1] до элемента A[i2, j2] с максимальной суммой. “Ходить” можно по горизонталям и вертикалям. Каждый элемент матрицы может входить в путь не более одного раза.

8. В матрице найти путь от элемента первой строки матрицы до элемента последней строки с максимальной суммой. “Ходить” можно вниз по вертикали или диагоналям.

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

где матрица В_k получается из матрицы А вычеркиванием первой строки и k-го столбца.

10. Лабиринт задан матрицей a(m, n), состоящей из нулей и единиц, причем а[0, 0] = 0 и a[m-1, n-1] = 0. Разработайте рекурсивную процедуру нахождения пути из клетки а[0, 0] в a[m-1, n-1]. Путь должен состоять из элементов, равных нулю. “Ходить” можно только по вертикалям и горизонталям.

11. Задано число А и два вектора b[n] и c[n]. Найти множество I, являющееся подмножеством множества {0, ..., n-1}, такое, что , а является максимальной из всех возможных.

12. Найти сумму двух натуральных чисел, заданных массивами своих цифр а₀, а₁, …, а_n-1 и b₀, b₁, …, b_m-1.

13. Рассортировать одномерный массив методом слияния.

14. Найти все перестановки заданных n различных натуральных чисел..

15. Для заданных двух натуральных числа m и n найти НОД(m, n) и натуральные x и y такие, что mx + ny = НОД(m, n).

16. Даны три натуральных числа m, n и k, причем k делится на НОД(m, n). Найти какое-нибудь целочисленное решение уравнения mx + ny = k.

17. Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Разработайте рекурсивную процедуру определения, можно ли попасть по этим дорогам из 1-го пункта в n-й.

18. Вводятся три неотрицательных числа d, i, c и две строки X и Y. Найдите преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:

• удалить любой символ из X (стоимость операции d);

• вставить любой символ в X (стоимость операции i);

• заменить символ в X на произвольный (стоимость операции с).

19. Преобразовать строку символов, состоящую из букв ‘А’, ‘В’ и ‘С’,

используя следующие три операции:

• удалить четыре подряд идущие буквы А;

• удалить из последовательности ВАВА одну пару ВА;

• удалить комбинацию АВС.

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

19. Даны две строки x и y. Строка x состоит из нулей и единиц, строка y – из символов ‘A’ и ‘B’. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 – либо в непустую последовательность букв A, либо в непустую последовательность букв B?

20. Задано конечное множество жителей некоего города, причем для каждого из жителей перечислены имена его детей. Жители X и Y считаются родственниками, если:

либо Х – ребенок Y,

либо Y – ребенок X,

либо существует некий Z такой, что Х является родственником Z, а Z является родственником Y.

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

22. На шахматной доске расставьте 8 ферзей так, чтобы они не «били» друг друга.

23. Имеется полоска клетчатой бумаги шириной в одну клетку и длиной в n клеток. На первой клетке установлена шашка. Одним ходом шашку можно передвигать на одну или две клетки. Разработайте рекурсивную функцию, определяющую количество способов продвижения шашки на n-ю клетку.

68