Информатика, поток 2022-2024 годов

• Список обучающихся

«Сессионные» задачки

1. Написать программу, получающую от пользователя набор числовых значений (с плавающей точкой) и вычисляющей среднее и дисперсию (среднеквадратичное отклонение) этого множества значений. Сколько именно значений введёт пользователь — неизвестно, для завершения ввода он может использовать какое-то выделенное значение или следить за неуспешностью распознавания вводимого пользователем в качестве числового значения (скажем, пользователь может ввести какое-то слово, «end», например) и трактовке первого такого случая как окончания ввода. Массивами для хранения полного вводимого набора пользоваться нельзя.
2. Написать программу, ищущую в некотором диапазоне длин сторон прямоугольного треугольника все «Пифагоровы» (с целочисленными длинами). Диапазоны длин сторон задаются с клавиатуры. Пользующиеся явными соотношениями, генерирующими все «Пифагоровы» треугольники, должны быть готовы полностью разъяснить способ вывода этих соотношений и корректность нахождения именно всех треугольников с данными ограничениями длин (а не только какого-то подмножества полного набора).
3. Написать программу, находящую объём трёхмерного объекта, состоящего из объединения N шаров. Значение N может быть фиксировано на этапе компиляции программы, координаты центра и значение радиуса каждого шара пользователь вводит с клавиатуры, как и необходимую точность поиска значения объёма.
4. Написать программу, находящую в указываемом пользователем (с клавиатуры) отрезке натурального ряда все пары чисел-близнецов. Оценить константу Бруна на основании найденных пар.
5. Написать программу, считывающую из ввода пользователя натуральное число. Если оно простое, то оценить возможность разложения этого числа в виде суммы двух квадратов натуральных и  если нет серьёзных причин полагать, что это не получится, найти все возможные такие разложения. Если число составное или разложить его не удаётся по общематематическим причинам — просто об этом написать. Пользующиеся любыми готовыми алгоритмами получения такого разложения должны быть в состоянии объяснить все детали алгоритма и его корректность.
6. Написать программу, считающую значения функции распределения простых чисел π(x) для первых N натуральных чисел (N может как вводиться пользователем с клавиатуры, так и задаваться во время компиляции: по выбору автора программы) и вычисляющую асимптотический (в пределах данного N) коэффициент отношения π(x) и x/ln(x). Любые используемые алгоритмы вычисления π(x) необходимо уметь выводить и обосновывать.
7. Написать программу, численно получающую с заданной точностью объём и площадь поверхности объединения двух семимерных шаров радиусов R₁ и R₂, чьи центры лежат на расстоянии d друг от друга. Значения величин радиусов, расстояния и точности вводятся пользователем. При отладке полезно знать, что объём единичного шара в пространстве нечётной размерности — V_2k+1(1) = 2(k!)(4π)^k/(2k + 1)!
8. Написать программу, проверяющую гипотезу Лежандра для всех натуральных чисел, меньших N (которое вводится пользователем с клавиатуры), выводя найденные числа для каждого интервала или информируя об опровержении гипотезы.
9. Написать программу, которая для полинома некоторой фиксированной максимальной степени (задающейся при компиляции программы) просит пользователя ввести все его целочисленные коэффициенты, а далее для любого вводимого (не обязательно целого) значения проверяет, является ли это значение корнем данного полинома и если является, то определяет его кратность (степень двучлена [x - x₀] в разложении данного полинома на множители).
10. Написать программу, которая находит объём, отсекаемый N плоскостями от единичного куба в трёхмерном пространстве. Плоскости задаются уравнением Ax + By + Cz + D = 0, но поскольку у нас именно отсечение, то для определённости примем отсекаемую часть задаваемой неравенством Ax + By + Cz + D > 0. Программа должна оценивать точность находимого объёма. Сдающему лучше приготовить несколько наборов плоскостей, отсекающих от куба «стандартные» тела (параллелепипед, призму, тетраэдр, пирамиду), объём которых известен аналитически: это поможет установить правильность получаемого значения объёма. Значение N может быть фиксировано на этапе компиляции программы, коэффициенты A, B, C, D каждой плоскости вводятся пользователем, как и необходимая точность нахождения ответа.
11. Написать программу, которая для полинома некоторой фиксированной максимальной степени (задающейся при компиляции программы: само значение этой степени может быть произвольным натуральным числом) просит пользователя ввести все его коэффициенты, после чего находит все экстремумы и промежутки монотонности данного многочлена на некотором, задаваемом пользователем с клавиатуры, отрезке вещественной оси.
12. Написать программу, ищущую все (выводящую решения в алгебраически-компактном виде: решений может быть бесконечное количество, а может и не быть вовсе) решения диофантова уравнения ax + by = c. Все коэффициенты (a, b, c) и значения корней (x, y), как и положено для диофантовых уравнений, являются целыми. Коэффициенты задаются пользователем с клавиатуры.
13. Написать программу для поиска всех нечётных псевдопростых чисел Ферма по основанию a, меньших N (таких s, что из взаимной простоты a и s следует, что a^s-1 = 1 + ks; это иногда записывается как a^s-1 ≡ 1 (mod s) и называется «сравнение по модулю s»). Пользователь вводит значения a и N с клавиатуры. При использовании любых алгоритмов поиска этих чисел сдающий должен уметь выводить все необходимые для построения этого алгоритма соотношения и доказывать их справедливость.
14. Написать программу, определяющую аналитическими методами и проверяющую численно устойчивость/неустойчивость неподвижных точек отображения x_n+1 = f(x_n). Функциональная зависимость f(x) фиксируется в момент компиляции программы, но алгоритм не должен зависеть от конкретного вида функции (вы можете накладывать на неё разумные аналитические ограничения — непрерывность, дифференцируемость, etc — по своему разумению). x_s является неподвижной точкой, если она при нашем отображении переходит сама в cебя: x_s = f(x_s). Поиск неподвижных точек — также задача программы: пользователь лишь задаёт диапазон поиска.
15. Написать программу, исследующую обратимость элементов множества остатков от деления на натуральное t (само значение t задаётся пользователем с клавиатуры). Обратимый элемент a обладает свойством, что для него существует элемент α того же множества, дающий при его умножении на a единицу (с точностью до любого кратного t: aα = 1 + nt). Не все элементы обязательно обратимы: если пользователь вводит значение, для которого обратного не существует, то программа должна выводить любой парный a элемент ζ, образующий вместе с a пару нетривиальных делителей нуля: aζ = nt. Значения a вводятся пользователем с клавиатуры. Замечание: эта задача позволяет вам ощутить классификацию элементов кольца вычетов ℤ_t = ℤ/tℤ: они либо обратимы, либо нуль, либо делитель нуля. Но можете не волноваться насчёт этой наукообразной ремарки, а когда напишете программу, там и будет понятнее, надеюсь.
16. Написать программу, реализующую нахождение значения числа π с помощью задачи Бюффона о бросании иглы. Отрезок длины L случайно помещается на плоскость, расчерченную последовательными параллельными прямыми, находящимися на расстоянии d друг от друга, d > L. Вероятность того, что отрезок пересечёт прямую — (2L)/(dπ). Значения L и d, а также точность нахождения числа π вводятся пользователем с клавиатуры. Сдающему лучше иметь некоторые представления (полученные в результате численных экспериментов?) о зависимости времени работы программы от значений вводимых параметров.
17. Написать программу, проверяющую справедливость квадратичного закона взаимности: если заданы два нечётных простых числа p и q, то два уравнения (для x и y)

    x2 = q + pN ≡ q (mod p)

    y2 = p + qN ≡ p (mod q)

    ведут себя следующим образом:
    • если хоть одно из простых чисел имеет вид 4k+1, то либо у обоих уравнений есть корни, либо корней нет ни у одного уравнения из пары;
    • если и p, и q имеют вид 4k+3, то решение есть у одного и только одного из этих уравнений.
    Значения p и q задаются пользователем с клавиатуры, для каждого x проверяется утверждение закона и выводятся результаты проверки. Если вы используете любые алгоритмы проверки того, является ли число a квадратичным вычетом по модулю m (то есть существует x, являющийся решением сравнения x² ≡ a (mod m)), необходимо уметь их доказывать.

В остальном —