Лектор В. В. Борисенко
Все задания разбиты на два типа - задачи и упражнения. Упражнения помечены буквой "У".
В задачах 01-14 требуется за один проход (просмотр файла) вычислить ту или иную характеристику последовательности чисел, находящейся в файле "tmp.dat".
У01. Сумма и произведение элементов.
У02. Номер первого и последнего максимального элемента.
У03. Число минимальных элементов.
У04. Число элементов, больших предыдущего.
05. Средне квадратичное уклонение от среднего арифметического:
s = sqrt((x1-M)2 +...
+ (xn-M)2)/n
(n - число элементов, М - среднее арифметическое).
У06. Есть ли в последовательности число х?
У07. Номер первого и последнего элемента, равного числу х (если таких нет, считать номер равным нулю).
У08. Все ли элементы последовательности равны между собой ?
У09. Является ли последовательность возрастающей, неубывающей ?
У10. Вычислить число различных элементов неубывающей последовательности.
11. Сколько раз в последовательности встречается фрагмент 1, 2, 3, 4, 5 ?
12. Сколько раз в последовательности встречается фрагмент 1, 2, 1, 3?
13. Коэффициенты многочлена сведены в последовательность в порядке возрастания степеней. Найти значение многочлена и его производной в точке х.
14. Коэффициенты многочлена сведены в последовательность в порядке убывания степеней. Найти значение многочлена и его производной в точке х.
15. Нарисуйте на растре отрезок, заданный координатами концов.
16. Дано целое число. Получить число, десятичная запись которого содержит цифры исходного числа в обратном порядке.
17. Вычислить представление числа 1/n в виде десятичной дроби (указать ее начало и период).
18. Возвести число A в степень N, используя не более 2*log(N) умножений.
В задачах 19-26 требуется составить программу, аргументами которой являются длина N линейной таблицы А и сама таблица А[1:N]. Использовать дополнительные таблицы нельзя.
У19. Симметрична ли таблица?
У20. Записать элементы таблицы в обратном порядке: первый элемент должен оказаться на последнем месте, второй - на предпоследнем и т.д.
У21. Циклически сдвинуть элементы таблицы вправо: первый элемент должен оказаться на втором месте, второй - на третьем и т.д. Последний элемент должен оказаться на первом месте.
22. Циклически сдвинуть элементы таблицы из N элементов на k мест влево за время O(N).
23. Каждый элемент таблицы с индексом от 2 до N-1 заменить на полусумму соседей.
24. Известно, что элементы таблицы не убывают. Проведя не более 1+log(N) сравнений числа х с элементами таблицы, выяснить, встречается ли х среди элементов таблицы.
У25. Дано,что первые k-1 элементов таблицы не убывают. Переставить первые k элементов так, чтобы они не убывали.
26. Переставить элементы таблицы так, чтобы они не убывали.
27. Даны k отрезков на прямой. Вычислить, образуют ли они покрытие отрезка [0, 1].
28. Даны k отрезков на прямой. Найти максимальное n, для которого существует точка, принадлежащая одновременно n отрезкам.
В задачах 29-30 известно, что первые N элементов таблицы А возрастают и первые M элементов таблицы В возрастают.
29. Найти число К и построить таблицу С, в которой первые K элементов возрастают, причем число х встречается среди первых K элементов С если и только если оно встречается либо в А либо в В.
30. Найти число К и построить таблицу С, в которой первые K элементов возрастают, причем число х встречается среди первых K элементов С если и только если оно встречается и в А и в В (пересечение).
Элемент называется локальным максимумом, если у него нет соседа, большего, чем он сам. Например, в последовательности из одного элемента - один локальный максимум. В последовательности 3, 3, 1, 0, 2, -1 три локальных максимума: первый, второй и предпоследний элементы.
31. Вычислить число локальных максимумов последовательности.
32. Вычислить число локальных максимумов матрицы.
Число n называется периодом последовательности, если любые два элемента последовательности начиная с некоторого, номера которых отличаются на n совпадают.
33. Отображение целочисленного отрезка [1,N] в себя задано в виде y=f(x). Найти минимальный период последовательности 1, f(1), f(f(1)), ...
34. Вывести в файл "tmp.res" список:
a) всех подмножеств
б) всех K-элементных подмножеств множества чисел (1, 2, ..., n).
Стандартным прямоугольником на плоскости называется множество точек (x1, x2: a1<=x1<=b1, a2<=x2<=b2). Стандартный прямоугольник может вырождаться в вертикальный или горизонтальный отрезок, в точку или в пустое множество.
35. Нарисовать стандартный прямоугольник и заштриховать его под углом 45 градусов.
36. Найти периметр и площадь а) пересечения; б) объединения двух стандартных прямоугольников на плоскости.
37. Нарисовать границу объединения двух стандартных прямоугольников а) пользуясь "рисованием инверсией"; б) не используя этот режим.
k-мерным яшиком называется множество (x1,...,xk: a1<=x1<=b1, ..., ak<=xk<=bk).
38. Найти плошадь поверхности и объем пересечения и объединения двух k-мерных яшиков (k >= 1).
Машинной точностью вычислительной системы называется наибольшее вещественное число MACHEPS (машинное эпсилон) среди вещественных чисел х, представимых в этой вычислительной системе и удовлетворяющих в ней соотношению 1+x=1
У01. Написать программу, определяющую MACHEPS.
02. Придумайте последовательность из 1000 чисел, по модулю не превосходящих 1, при суммировании которой в прямом и обратном порядке результаты будут отличаться не менее, чем на 0.00001.
03. Написать программу, которая для любого вещественного числа х>0 находит его порядок и 24 значащих цифры мантиссы в двоичной системе счисления. Сравните с помощью этой программы мантиссы чисел х и 2*х-х для нескольких значений х.
04. Пусть f(x) - кубический многочлен, например х3+3*х-1. Вычислить производную f'(x) функции f(x) приближенно по формулам (f(x+h)-f(x-h))/(2*h) и (f(x+h)-f(x))/h при различных x и h. Какая формула точнее при фиксированном h? При каком h получаются лучшие приближения к точному значению производной?
05. Объясните результат работы программы "сумма". Указание: Попробуйте константы 1.000976 и 1000.976.
У06. Вычислить максимальное значение кубического многочлена на заданном отрезке.
При решении задач 07-11 функцию f нужно оформлять отдельной подпрограммой: алг double f(douиle х).
У07. Нарисовать график функции f(x).
08. Вычислить корень уравнения f(x)=0 на отрезке методом деления пополам.
09. Вычислить корень уравнения f(x)=0 на отрезке методом хорд.
10. Вычислить корень уравнения f(x)=0 на отрезке методом Ньютона, считая, что производная df(x) задана программой.
У11. Вычислить интеграл функции на отрезке методом трапеций.
12. Вычислить корень n-ой степени методом итераций.
13. Функции х(t) и y(t), где 0 =< t =< 1, задают кривую на плоскости. Найти длину этой кривой, используя a) линейную интерполяцию; б) квадратичную интерполяцию.
14. Нарисовать кривую из предыдущей задачи
15. Вычислить sin(х) для -1000<х<1000 с точностью 0.001, используя формулы приведения и разложение sin(х) в ряд по степеням х.
16. Вычислить сумму ряда с k-ым членом вида 1/(k*(k+x)) для x = 0, 0.1,..., 1 с 4 верными знаками.
17. Нарисовать ломаные, заданные рекуррентными соотношениями и
объяснить результаты (h-маленькое число):
а) x[n+1] = x[n]+h*y[n], y[n+1] = y[n]-h*x[n]
б) x[n+1] = x[n]+h*y[n], y[n+1] = y[n]-h*x[n+1].
В задачах 18-19 функция на отрезке задана массивом double Т[n] значений в равноотстоящих точках отрезка [А,В].
18. Используя а) квадратичную, б) линейную интерполяцию, вычислить значение функции у и ее производной dу в заданной точке х.
19. Используя квадратичную интерполяцию, вычислить при каком значении аргумента функция достигает максимального значения на отрезке.
20. Нарисовать линии уровня функции z=f(x,y).
21. Написать программу, которая по n значениям аргумента x[1:n] и n заданным значениям y[1:n] многочлена степени n-1 находит значение этого многочлена в точке x.
22. В качестве данных для предыдущей задачи взять 5, 10, 20 равноотстоящих точек функции y=1/(1+25*x**2) на отрезке [-1,1]; нарисовать графики функции и многочлена.
23. В точках А и В заданы значения функции и ее производной. Вычислить приближенные значения функции и производной в заданной точке отрезка [A,B].
24. Линейные таблицы I[1:n], U[1:n] содержат результаты n измерений тока и напряжения на неизвестном сопротивлении R. Найти приближенное значение R методом наименьших квадратов. Нарисовать точки и аппроксимирующую прямую.
25. Построить а) линейную; б) параболическую аппроксимацию результатов n измерений значений функции по методу наименьших квадратов. Нарисовать точки и аппроксимацию.
26. Тело падает с высоты h, испытывая сопротивление, пропорциональное квадрату скорости, т.е. ускорение тела определяется формулой а = 9.8 - k*v**2 Найти время падения и скорость удара о землю для h=1000 м, k=0.004 1/м
27. В квадратном биллиарде [0,1] x [0,1] оказался шар с координатами (X0,Y0) и скоростью (VX,VY). Нарисовать его траекторию.
01. В файл "tmp.res" записать биномиальные коэффициенты.
02. Вычислить четность произвольной перестановки чисел (1, 2,..., n) за время O(n).
У03. Вычислить обратную перестановку.
В задачах 04-08 требуется представлять комплексные числа парами действительных чисел вида struct {double re; double im} c1,с2,.. Первый элемент пары - вещественная, второй - мнимая часть комплексного числа.
У04. Написать программы сложения, вычитания, умножения, деления двух комплекc- ных чисел.
У05. Написать программы умножения комплексного числа на действительное, сравнения двух комплексных чисел.
У06. Написать программы вычисления модуля, аргумента, корня квадратного числа. Проверить на ЭВМ правило сложения аргументов при умножении комплексных чисел.
07. Найти комплексные корни квадратного уравнения с комплексными коэффициентами.
У08. В файл "tmp.res" записать все комплексные корни уравнения ZN=C, где C - произвольное комплексное число.
09. Найти наибольший общий делитель (необязательно положительных) целых чисел, не равных одновременно нулю.
10. Для натуральных чисел М и N найти целые числа х, у, НОД,
удовлетворяющие условиям х*М+у*N=НОД, х=
11. Для натуральных чисел М и N найти НОД=НОД(М,N) и обратимую
в кольце всех целочисленных квадратных матриц второго порядка
матрицу
Элементы кольца Z/nZ будем представлять целыми числами от 0 до n-1. При таком представлении кольца вычетов операция x%n, сопоставляющая каждому целому неотрицательному числу х его остаток от деления на n, задает естественную проекцию Z-->Z/nZ.
12. Написать программу поиска обратного элемента в кольце Z/nZ.
У13. Найти все делители нуля кольца Z/nZ (n=<1000), записать ответ в файл "tmp.res".
У14. Для любого n=0,1,2,... найти в поле Z/pZ количество различных решений уравнения xN=1.
15. Определить ранг матрицы с коэффициентами из поля Z/pZ.
16. Определить ранг целочисленной матрицы.
17. Написать программу приведения вещественной матрицы к ступенчатому виду методом Гаусса с выбором максимального по модулю элемента в столбце.
18. Написать программу умножения многочленов P и Q.
19. Написать программу вычисления коэффициентов P(Q(x)).
20. Написать программу, которая записывает в файл "tmp.res" первые 50 (500) простых чисел.
21. Написать программу, которая записывет в файл "tmp.res" разложение на простые множители натурального числа n=<10000.
Частным и остатком от деления многочлена P на многочлен Q называются такие многочлены R, S, что P=Q*S+R, deg(R) < deg(Q).
22. Написать программу деления с остатком двух многочленов, заданных своими коэффициентами.
У23. Записать все порождающие элементы мультипликативной группы поля Z/pZ (p < 128) в файл "tmp.res".
24. Определить, есть ли у заданного многочлена с целыми коэффициентами кратные корни.
01. Записать в файл все способы расстановки скобок в неассоциативном произведении n сомножителей.
02. Вычислить число возможных разбиений множества 1..N на K частей (число Стирлинга).
03. Записать в файл все возможные разбиения множества 1..N на K частей.
04. Вычислить число возможных разбиений числа N на слагаемые.
05. Записать в файл все возможные разбиения числа N на сумму слагаемых.
06. Записать в файл все последовательности цифр 0,1,2 длины n, в которые ни одна группа цифр не входит два раза подряд.
07. Записать в файл "tmp.res" все перестановки чисел от 1 до n а) в лексикографическом порядке б) так, чтобы каждая пара соседних перестановок отличалась одной транспозицией.
08. Корабли на поле для морского боя заданы матрицей nxn из нулей и единиц. Определить число кораблей
09. Отношение на множестве из N элементов задано матрицей NxN из нулей и единиц. Получить транзитивное замыкание этого отношения.
10. Матрица NxN содержит длины ребер графа с N вершинами (и +бесконечность в случае отсутствия ребра). Найти длины кратчайших путей между вершинами графа.
11. Переставить элементы таблицы из N элементов так, чтобы они не убывали, сделав О(N*log(N)) сравнений.
12. Даны n точек на плоскости. Построить их выпуклую оболочку (список точек в порядке обхода) за время O(n*log(n)).
13. Найти а) объединение б) пересечение трех упорядоченных числовых последовательностей.
14. В очень большой прямоугольной сетке из одинаковых сопротивлений к концам одного из них присоединили батарейку с напряжением 1В. Найти распределение напряжений в окрестности этого сопротивления.
15. Нарисовать кривую Пеано.
16. Нарисовать вид поверхности z=f(x,y) из точки (x0,y0,z0) с "удалением невидимых линий".
17. Вычислить интеграл xn*exp(x-1) на отрезке 0..1 при n=1..15.
18. Алгоритмы p(x) и q(x) вычисляют значения двух многочленов в точке x. Составить алгоритм, который выдавал бы коэффициенты частного p/q, когда p делится на q без остатка, и ответ "не делится" в ином случае.
19. Найти число неприводимых многочленов степени M над Z/pZ.
20. Найти все неприводимые многочлены степени M над Z/pZ.
21. Считая, что значения одного и того же многочлена вычисляются много раз, уменьшите количество необходимых для этого умножений по сравнению с методом Горнера (умножение на многих ЭВМ выполняется сравнительно медленно).
22. (Китайская теорема об остатках). Дано k взаимно простых чисел m[i]. Найти число, меньшее произведения m[i], если известны остатки от деления его на все m[i]. Решение перебором не принимается!
23. Найти число неизоморфных полугрупп из 2, 3 и 4 элементов.
24. Теорема Ван дер Вардена утверждает, что при любой раскраске целочисленной оси координат в два цвета существуют одноцветные арифметические прогрессии любой длины. Для небольших K найти наименьшее N такое, что при любой раскраске отрезка длины N сушествует одноцветная арифметическая прогрессия длины K.
Число m называется кармайкловым, если оно не простое, и для всех b, взаимно простых с m, выполняется (b**(m-1))-1==0 mod m (т.е. число ведет себя как простое в малой теореме Ферма).
25. Найти все кармайкловы числа в диапазоне 1..32767.
1. Даны декартовы координаты нескольких точек плоскости. Получить полярные координаты этих точек.
2. Даны сферические координаты нескольких точек пространства. Получить декартовы координаты этих точек.
3. Даны декартовы координаты нескольких точек пространства. Получить сферические координаты этих точек.
4. Дано множество точек на плоскости. Существует ли в этом множестве тройка точек, лежащих на одной прямой?
5. В пространстве дано N точек с массами М1, ... , МN. Найти их центр тяжести.
6. Даны декартовы координаты N (N>=3) точек пространства. Отобрать три из них, которые видны из начала координат под наименьшими углами по отношению к вектору (X,Y,Z).
7. Выяснить, пересекаются ли два отрезка на плоскости, и если да, то найти точку пересечения.
8. Дана замкнутая ломаная на плоскости. Определить, является ли она: а) самопересекающейся, б) выпуклой.
9. Выяснить расположение точки и замкнутой ломаной в R2.
10. Найти расстояние от точки до отрезка в R2, R3.
11. Два треугольника на плоскости заданы координатами своих вершин. Проверить, будут ли они а) равны, б) подобны.
12. Два тетраэдра в пространстве заданы координатами своих вершин. Проверить, будут ли они а) равны, б) подобны.
13. Найти объем/площадь поверхности пересечения/объединения двух К-мерных (К<=10) стандартных ("ящиков").
14. Найти пересечение отрезка с "ящиком": а) на плоскости, б) в пространстве, в) в K-мерном пространстве.
15. Пересекает ли треугольник ABC положительный луч оси OZ?
16. Лежит ли точка X внутри, вне или на поверхности невырожденного тетраэдра ABCD?
17. Выяснить расположение сферы и тетраэдра, заданного координатами вершин.
18. Даны непересекающиеся окружность и треугольник в пространстве. Зацеплены ли они?
19. Дана система векторов пространства R**k. Ортогонализировать эту систему.
20. Выяснить расположение точки и треугольника в R2.
21. Найти вектора биссектрис треугольника: а) в R2, б) в R3.
22. Найти площадь поверхности тетраэдра.
23. Под каким углом виден из нуля треугольник на плоскости ?
24. Найти высоты тетраэдра в R3.
25. В пространстве заданы плоскость Р координатами трех точек и тетраэдр. Найти площадь и периметр проекции тетраэдра на Р.
26. В момент T=0 сферы с центрами С1,С2 и радиусами R1,R2 начинают двигаться со скоростями V1,V2. Столкнутся ли они ?
27. Цилиндр X**2 + Y**2 = R**2 и плоскость АХ + ВY + CZ = 0 пересекаются по эллипсу. Найти его эксцентриситет.
28. Под каким углом из точки X0,Y0 видна парабола Y**2=2РХ ?
29. Конус X**2 + Y**2 - Z**2 = 0 пересекается плоскостью АХ + ВY + CZ = 1. Какая кривая получится в сечении ?
30. Дан эллипс Х**2/А**2 + Y**2/В**2 = 1 и точка (X0,Y0). Под каким углом эллипс виден из точки?
31. Найти уравнение гиперболы, проходящей через точку (X0,Y0), если ее асимптотами служат прямые А1*Х+B1*Y+C1=0, А2*Х+B2*Y+C2=0.
32. Дан эллипсоид - найти минимальный ящик, его содержащий.
33. Дан эллипсоид - найти его ортогональную проекцию на направление Х(1,3).
34. Найти диаметр выпуклого плоского N-угольника, заданного координатами последовательно занумерованных вершин за O(N*LN(N)) операций.
35. Найти минимальный круг, покрывающий множество точек на плоскости.
36. Множество отрезков образует покрытие отрезка [0,1].
a) Найти максимальную кратность этого покрытия.
б) Показать, что из него всегда можно выбрать подпокрытие
кратности не выше два, т.е. такое подмножество отрезков, что
каждая точка отрезка [0,1] покрыта одним или двумя отрезками;
написать программу, которая ищет такое подпокрытие.
37. Все стороны (невыпуклого) многоугольника параллельны координатным осям. Представить его в виде объединения попарно непересекающихся прямоугольников. ("Разрезать на ящики".)
38. Дано N>2 точек плоскости, никакие три из них не лежат на одной прямой. Построить выпуклую оболочку этих точек.
39. Найти пересечение/объединение двух выпуклых многоугольников на плоскости.
40. Выбрать из множества N точек на плоскости две самые дальние друг от друга точки, быстрее, чем за O(N**2) операций.
- Конец материалов -