ЗАДАЧИ ДЛЯ ПЕРВОГО СЕМЕСТРА
Все задания разбиты на два типа - задачи и упражнения. Уп-
ражнения помечены буквой "У".
Тема 1. Программирование
!! В задачах 01-14 требуется за один проход (просмотр файла)
!! вычислить ту или иную характеристику последовательности чи-
!! сел, находящейся в файле "tmp.dat".
У01. Сумма и произведение элементов.
алг сумпро (рез вещ s,p)
? арг \ последовательность чисел в файле "tmp.dat"
? рез s,p \ равны сумме и произведению элементов
нач
У02. Номер первого и последнего максимального элемента.
У03. Число минимальных элементов.
У04. Число элементов, больших предыдущего.
05. Среднее квадратичное уклонение от среднего арифметическо-
го: D = ( (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. Симметрична ли таблица?
алг симметрия (арг цел N,вещтаб А[1:N], рез лит ответ)
? дано: | N,А
? надо: | рез = "да", если А симметрична
нач
У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" список а) всех подмножеств б)
всех 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 ).
Тема 2. Анализ и вычислительная математика
!! Машинной точностью вычислительной системы называется на-
!! ибольшее вещественное число 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.
алг сумма(арг вещ а,S, рез err)
? дано | S=1.001,1001
? надо
нач цел k, ВЕЩ Т
? Т:=0
? для k от 1 до 1000
? нц
? ? Т:=Т+а
? кц
? еrr:=S-Т
кон
У06. Вычислить максимальное значение кубического многочлена на
заданном отрезке.
!! При решении задач 07-11 нужно использовать функцию f,
!! оформляя ее отдельной программой: алг вещ f(вещ х)
У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 Функция на отрезке задана таблицей Т[1: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). Нарисовать его траек-
торию.
Тема 3. Алгебра
01. В файл "tmp.res" записать биномиальные коэффициенты
02. Вычислить четность произвольной перестановки чисел 1, 2,
..., n за время O(n)
У03. Вычислить обратную перестановку
!! В задачах 04-08 требуется представлять комплексные числа па-
!! рами действительных чисел вида вещтаб с1[1:2], с2[1:2] и
!! т.д. Первый элемент пары - вещественная, а второй - мнимая
!! часть комплексного числа.
У04. Написать программы сложения, вычитания, умножения, деления
двух комплексных чисел.
У05. Написать программы умножения комплексного числа на дей-
ствительное, сравнения двух комплексных чисел.
У06. Написать программы вычисления модуля, аргумента, корня
квадратного числа. Проверить на ЭВМ правило сложения аргу-
ментов при умножении комплексных чисел.
07. Найти комплексные корни квадратного уравнения с комплек-
сными коэффициентами
У08. В файл "tmp.res" записать все комплексные корни уравнения
Z**N = C, где C - произвольное комплексное число.
09. Найти наибольший общий делитель (необязательно положитель-
ных) целых чисел, не равных одновременно нулю.
10. Для натуральных чисел М и N найти целые числа х,у,НОД,
удовлетворяющие условиям х*М+у*N=НОД, х=<N, у=<М,
НОД=НОД(М,N)
11. Для натуральных чисел М и N найти НОД=НОД(М,N) и обратимую
в кольце всех целочисленных квадратных матриц второго по-
рядка матрицу
?х у? ?х у? ?M? ?НОД?
? ? , для которой ? ? * ? ? = ? ?
?z t? ?z t? ?N? ? 0 ?
!! Элементы кольца Z/nZ будем представлять целыми числами от 0
!! до n-1. При таком представлении кольца вычетов встроенная
!! функция Е-практикума mod(х,n), сопоставляющая каждому целому
!! положительному числу х его остаток от деления на n, задает
!! естественную проекцию Z --> Z/nZ.
12. Написать программу поиска обратного элемента в кольце
Z/nZ.
У13. Найти все делители нуля кольца Z/nZ (n=<1000), записать
ответ в файл "tmp.res".
У14. Для любого n=0,1,2,... найти в поле Z/pZ количество раз-
личных решений уравнения x**N=1 .
15. Определить ранг матрицы с коэффициентами из поля Z/pZ.
16. Определить ранг целочисленной матрицы.
17. Написать программу приведения вещественной матрицы к сту-
пенчатому виду методом Гаусса с выбором максимального
по модулю элемента в столбце.
18. Написать программу умножения многочленов P и Q
19. Написать программу вычисления коэффициентов P(Q(x))
20. Написать программу, которая записывает в файл "tmp.res"
первые 50 простых чисел.
21. Написать программу, которая записывет в файл "tmp.res"
разложение на простые множители натурального числа
n=<1000.
!! Частным и остатком от деления многочлена 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. Вычислить интеграл x**n*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, выполняется mod(b**(m-1)-1,m)=0
!! (т.е. число ведет себя как простое в малой теореме Ферма).
25. Найти все кармайкловы числа в диапазоне 1..32767.
- Конец материала -