В.Д. Валединский - Задачи по программированию (1109575)
Текст из файла
Задачи по программированиюПреподаватель — В. Д. ВалединскийI–II семестр, 2002–2003 г.1. I семестр1.1. Задачи на обработку последовательностиВ следующих задачах предполагается, что в файле записана последовательность чисел неизвестной длины (возможно, пустая). Требуется за один просмотр файла и без запоминания последовательности в массивеопределить требуемую характеристику последовательности.Программа должна содержать функцию, которая получает в качестве параметра имя файла длиной неболее 20 символов (или указатель на файл) и возвращает требуемое значение. Функция main запрашивает склавиатуры имя файла, обращается к функции и выводит результат на экран.1.2.3.4.5.6.7.8.9.10.11.12.13.Сумма и произведение чисел из последовательности.Среднее арифметическое чисел из последовательности.Количество чисел, больших предыдущего.Есть ли в последовательности число X?Номер первого числа, равного X.Номер последнего числа, равного X.Все ли элементы последовательности равны между собой?Является ли последовательность возрастающей, убывающей?Количество различных элементов неубывающей последовательности.Номер первого числа, равного максимуму из всех чисел.Количество чисел, равных минимальному.Удовлетворяет ли последовательность заданному рекуррентному соотношению axk + bxk+1 + cxk+2 = d?Пусть последовательность неубывает.
Найти количество чисел, которые появляются более 2 раз.NP14. Среднее квадратическое отклонение: D = N1(xi − M )2 , где M — среднее арифметическое.i=115.16.17.18.19.20.Длина наибольшего постоянного участка.Длина наибольшего возрастающего участка.Количество постоянных участков, имеющих длину не меньше n.Количество невозрастающих участков, имеющих длину больше n.Максимальное расстояние между локальными минимумами.Последовательность чисел представляет собой коэффициенты многочлена по возрастанию степеней. Вычислить многочлен и его производную в точке X.21.
Последовательность чисел представляет собой коэффициенты многочлена по убыванию степеней. Вычислить многочлен и его производную в точке X.1.2. Задачи на работу с массивамиРешения следующих задач должны содержать функцию, которая получает в качестве параметров указательна массив и его длину и без использования дополнительных массивов выполняет требуемые действия.Функция main должна заполнить массив числами из файла, определить его фактическую длину и вызватьэту функцию. Предполагается, что количество чисел в файле не превосходит некоторой заданной величины,например, не более 1000.
Вывести на экран и в файл исходный массив и результат.1. Симметричен ли массив?2. Переставить элементы массива в обратном порядке.3. Циклически сдвинуть элементы на одну позицию вправо.14.5.6.7.Циклически сдвинуть элементы на K позиций вправо с затратой O(N ) действий, где N — длина массива.Каждый элемент массива, кроме первого и последнего, заменить на полусумму соседей.Сгруппировать положительные элементы в начале, а отрицательные — в конце с сохранением их порядка.Элементы массива не убывают. Двоичным поиском определить позицию, где в этот массив можно вставитьданное число X, не нарушая упорядоченности.8.
Определить значение и индекс минимального элемента массива.9.10.11.12.13.В следующих задачах предполагается преобразовать массив так, что он изменит свою длину. При этомсчитаем, что в исходном массиве зарезервировано достаточно места для расширения массива.
Функции,решающие эти задачи, должны возвращать новую длину массива.Удалить элементы, превосходящие данный x, а оставшиеся сдвинуть к началу массива.Продублировать рядом каждый элемент массива, превосходящий данный x.Удалить из массива каждый элемент, делящийся нацело на x, а оставшиеся уплотнить к началу массива.Вставить между каждыми двумя положительными элементами их среднее арифметическое.Заменить каждый отрицательный элемент на три элемента, равных его абсолютной величине.1.3. Задачи на разбор чисел и битовые операции1.2.3.4.5.6.7.8.9.10.Ввести целое число.
Получить целое число, записанное теми же цифрами в обратном порядке.Вычислить представление числа 1/N в виде десятичной дроби (начало и период). То же для дроби M/N .Возвести число в степень N не более, чем за 2 log2 N операций.Вывести в файл все подмножества множества {1, 2, . . . , N }.Вывести в файл все k-элементные подмножества множества {1, 2, . . . , N }.Найти НОД двух целых чисел.Определить чётность перестановки из N чисел.Вычислить первые N простых чисел.Вычислить разложение числа на простые множители.Вывести значение целого числа в словесной форме, например, для «123530» напечатать «Сто двадцатьтри тысячи пятьсот тридцать».1.4. Задачи на сортировку массивовВ следующих задачах предполагается, что в файле записаны несколько чисел.
Функция main заполняетэтими числами массив, определяет его фактическую длину N и с этими параметрами обращается к функции,которая упорядочивает массив по возрастанию. Вывести в файл исходный и упорядоченный массив.1.2.3.4.5.6.7.8.Перестановка минимального.Вставка с последовательным поиском.Вставка с бинарным поиском.Пузырьковая сортировка.Сортировка просеиванием.Сортировка слиянием.Быстрая сортировка (QuickSort).Турнирная сортировка (HeapSort).1.5. Задачи на обработку множества точекВ следующих задачах предполагается, что в файле записано несколько пар чисел, которые можно рассматривать как координаты множества точек на плоскости или как координаты множества концов отрезков напрямой.1.2.3.4.Множество точек определяет ломаную. Имеет ли она самопересечения?Множество точек определяет многоугольник.
Является ли он выпуклым?Дано множество отрезков. Покрывает ли их объединение отрезок [a, b]?Дано множество отрезков. Найти точку, которая принадлежит наибольшему количеству отрезков, определить это количество.5. Дано множество точек. Найти центр и радиус минимального круга, который содержит эти точки.6.
Дано множество отрезков. Вывести те отрезки, объединение которых даёт отрезок наибольшей длины.22. II семестр2.1. Простейшие вычислительные задачиСледующие 3 задачи являются упражнениями по этой теме.1. Решить уравнение z N = C в комплексных числах.2. Для заданного N вычислить суммы в прямом и обратном порядке. При каких N получается максимальноерасхождение в этих двух значениях?NX1√ ,kk=1NXln kk=1kNX1,k,k=1NX1,k2k=1NX1k!k=13.
Написать программу, определяющую машинную точность, т.е. максимальное a > 0, такое что 1 + a = 1.Усложнённый вариант: найти два ближайших к 1 представимых вещественных числа.В следующих задачах требуется оформить решение в виде функции, получающей в качестве параметрауказатель на функцию f, имеющую прототип (double)(*f)(double x).1. Вычислить первую и вторую производную аналитически заданной функции по следующим приближённымформулам при разных значениях x и h. Сравнить с точным значением производной и определить h, длякоторого в данной точке x достигается наибольшая точность.f ′ (x) ∼f (x + h) − f (x),hf ′ (x) ∼f (x + h) − f (x − h),2hf ′′ (x) ∼f (x + h) − 2f (x) + f (x − h)h22. Вычислить корень уравнения f (x) = 0 на данном отрезке с заданной точностью εа. Методом деления пополам;б. Методом Ньютона (касательных);в.
Методом хорд.3. Вычислить интеграл от данной функции f (x) на данном отрезке [a, b] по составной формулеа.б.в.г.Прямоугольников с N отрезками;Трапеций с N отрезками;Симпсона с N отрезками;Гаусса (двухточечной) с N отрезками.и сравнить с точным ответом.4. Вычислить минимальное значение данной функции f (x) с заданной точностью ε методом поиска трёхточек.5.
Вычислить значения одной из элементарных функций (sin, cos, exp, ln) в заданной точке x и с заданнойточностью ε суммированием ряда Тейлора. Сравнить с точным ответом.6. Написать программу, которая по значениям x1 , . . . , xn и y1 , . . . , yn вычисляет в данной точке x приближённое значение функции с помощью:а.б.в.г.д.Интерполяционного многочлен Лагранжа;Кусочно-линейной аппроксимации;Кусочно-квадратичной аппроксимации;Эрмитовой аппроксимации (по функции и производной);Построения наилучшего среднеквадратичного приближения линейной функцией.Сравнить с точными значениями функции.2.2. Задачи на работу с матрицами и метод ГауссаПрограммы решения этих задач должны состоять из двух файлов: файл с функциями, решающими поставленную задачу, и файл с функциями формирования матриц и вывода ответа.
Для формирования данных задачи(матрицы, правой части системы) предусмотреть два метода: вводом из файла и вычислением по формулам.Каждую задачу из этого раздела нужно выполнить в двух представлениях матрицы: в виде линейного массиваdouble * matrix, и в виде массива строк-массивов, т.е. в виде double ** matrix.Упражнения: написать функции умножения матрицы на вектор, умножения двух матриц соответствующихразмеров и функцию для форматирования и вывода матриц.31.2.3.4.Определить ранг вещественной матрицы N × M .Вычислить определитель квадратной матрицы размера N .Вычислить матрицу, обратную к данной.Решить систему линейных уравнений. В случае бесконечного множества решений или их отсутствия выдавать соответствующее сообщение.2.3.
Обработка текстового файлаПрограмма должна состоять, как минимум, из двух файлов. В следующих задачах словом называется последовательность символов в пределах одной строки, не содержащая символов из заранее заданного набора (например, !,.()[]). При решении задач рекомендуется пользоваться стандартными функциями strcmp, strcpy,strstr, strtok и др. (см.
string.h). Результатом работы программы должен быть преобразованный файл.Упражнение: реализовать функции strcmp, strcat, strstr, strcpy, strset для работы со строками.1. Заменить в файле каждую последовательность заданных одинаковых символов (например, пробелов) наодин такой символ.2. Реализовать инструкцию типа #include, т.е. вставить содержимое файла filename в то место файла, гдевстречается строка #include filename.3. Заменить всюду в файле один заданный набор символов на другой, с учётом разницы в их длине.4.
Вывести все слова из файла в другой файл в порядке их появления.5. Вывести номера строк исходного файла и номер позиции в строке, где встречается заданное слово.6. Определить максимальную, минимальную и среднюю длину слов из данного файла, а также частоту(процент) появления каждого символа.7.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
