ЗАДАЧИ ДЛЯ ЗАЧЕТА ВО ВТОРОМ СЕМЕСТРЕ
------------------------------------
Перед задачами в скобках обозначена их трудность по 10-баль╨
ной шкале. 0 этой шкалы соответствует задаче типа "напечатать
слово "ура" на терминале", а 10 баллов - задаче типа "доказать,
что не существует натуральных x,y,z, n>2: x**n + y**n = z**n".
Несложные численные методы
--------------------------
(3) Найти корни первых 30 полиномов Лежандра:
Ln = Dn( (x**2-1)**n ), с точностью 1e-6.
(3) Зная коэффициенты многочленов Е(X,Y), F(X,Y), G(X,Y), найти
коэффициенты E(F(X,Y),G(X,Y)).
В следующих задачах не должны использоваться соответствующие
встроенные функции фортрана (кроме как в целях контроля). Точ╨
ность результата должна быть не хуже 1Е-5. Время, затрачиваемое
на вычисление не должно превышать одной секунды.
(2) Вычислить LN(T) ДЛЯ 10**(-37)<T<10**(37).
(2) Вычислить ATAN(T) ДЛЯ 10**(-37)<T<10**(37).
(2) Вычислить ASIN(T) ДЛЯ -1<T<1.
(4) Извлечь квадратный корень из матрицы 2*2, т.е. найти все
такие матрицы X, что X*X=A.
(2) Найти все (в том числе и комплексные) корни кубического
уравнения с вещественными коэффициентами с абсолютной погреш╨
ностью не хуже 1Е-5.
(2) Вычислить exp(а), где а - комплексная n*n матрица.
(2) Дан многочлен А с ненулевым свободным членом. Найти первые
n коэффициентов разложения 1/A в ряд Тейлора в нуле.
(2) Вычислить минимум Гамма-функции
(2) Вычислить приближенное значение пи, используя метод Мон╨
те-Карло для вычисления интеграла от 0 до 2 sqrt(4.-x**2) dx.
(4) В очень большой прямоугольной сетке из одинаковых сопро╨
тивлений к концам одного из них присоединили батарейку с напря╨
жением 1В. Найти распределение напряжений в окрестности этого
сопротивления.
(3) Считая, что значения одного и того же многочлена вычисляют╨
ся много раз для различных значений, уменьшите количество необ╨
ходимых для этого умножений по сравнению с методом Горнера (ум╨
ножение на многих ЭВМ выполняется сравнительно медленно).
Арифметика произвольной точности
--------------------------------
(3) Найти первые 1000 знаков десятичной записи чисел "Пи", "Е"
(3) Найти первые 1000 знаков десятичной записи "Золотого сече╨
ния" (1.+sqrt(5.))/2.
(3) Найти первые 1000 знаков десятичной записи sin(1) и cos(1).
(3) Определить первые два десятичных знака числа SIN(10**30).
2.
(2) Вычислить точно 100!
(2) Вычислить десятичное разложение 1000-го члена последова╨
тельности Фибоначчи.
(3) Найти два тысячезначных натуральных числа, последние 1000
цифр квадратов которых совпадали бы с самими числами.
(3) Доказать, что для любого k найдется n, такое что в десятич╨
ной записи 2**n встречается подряд k нулей. Найти наименьшие n
для 1 <= к <= 7.
(5) Эйлер в 1769 году выдвинул гипотезу, что не существует це╨
лых положительных чисел, удовлетворяющих условию: a**5 + b**5 +
c**5 + d**5 = e**5. Опровергните эту гипотезу.
Разреженные векторы и матрицы
-----------------------------
(4) Создать исполнитель для работы с вещественными матрицами
размером 1000 x 1000, содержащими не более 1000 ненулевых эле╨
ментов на базе двух целых и одного вещественного векторов длины
1000. В него должны входить предписания для сложения матриц,
умножения матрицы на число и т.д.
(3) Создать исполнитель для работы с вещественными векторами
размером 32000, содержащими не более 1000 ненулевых элементов
на базе целого и одного вещественного векторов длины 1000. В
него должны входить предписания для сложения векторов, умноже╨
ния вектора на число и т.д.
Компиляция
----------
(4) Составить программу проверки правильности арифметического
выражения фортрана. Облегчение: можно исключить вещественные
константы (4 баллa).
(3) Составить программу вычисления арифметического выражения из
целых констант и знаков со скобочной структурой.
(2) Составить программу, которая по двум данным степеням мно╨
гочленов порождает линейную (без циклов) подпрограмму на
фортране для умножения этих многочленов.
(3) Формула содержит односимвольные переменные, знаки + - * / и
круглые скобки. Перевести ее в префиксную форму записи:
A*(B+C)-D --> -*A+BCD
(4) Дана правильная формула, содержащая односимвольные перемен╨
ные, знаки + - * /, круглые скобки. Выбросить максимальное ко╨
личество пар скобок так, чтобы смысл формулы не изменился.
(4) Дана правильная формула, содержащая односимвольные перемен╨
ные, знаки + - * /, круглые скобки. Добавить минимальное число
пар скобок так, чтобы смысл формулы не зависел от приоритетов
операций.
3.
(5) Язык включает в себя оператор присваивания =, знаки опера╨
ций +, -, *, /, переменные A..Z, круглые скобки. Реализовать
компилятор с этого простейшего языка в ассемблер PDP-11.
Пример mov C, r1
результата A=B*(C+D) --> add D, r1
компиляции: mul B, r1
mov r1, A
(5) Логическое выражение состоит из знаков операций !("не"),
&("и"), |("или"), односимвольных логических переменных A..Z и
круглых скобок. Реализовать компилятор, переводящий его в прог╨
рамму на ассемблере PDP-11. Результат (0 или 1) должен поме╨
щаться в регистр r0. Выражение должно вычисляться "сокращенно":
если в выражении a&b а=0, не надо вычислять b, аналогично в a|b
не надо вычислять b, если a!=1.
clr R0
Пример tst A
результата А & ( B | !C ) --> beq L0
компиляции: tst B
bne L1
tst C
bne L0
L1: inc R1
L0:
Разные задачи по программированию
---------------------------------
(2) Напечатать перестановки порядка n в лексикографическом по╨
рядке.
(3) Напечатать перестановки чисел от 1 до n так, чтобы каждая
пара соседних перестановок отличалась одной транспозицией со╨
седних элементов.
(4) Определить, можно ли расстановкой знаков арифметических
операций и скобок между некоторыми цифрами шестизначного номера
автобусного билета получить число 100. Примеры: номер 123456,
100 = (-1)*2+(3*4+5)*6; номер 654321, 100 = 65+4+32-1. Програм╨
ма должна напечатать формулу (как в приведенных примерах). Не
обязательно, чтобы программа всегда находила формулу, требует╨
ся, чтобы она не очень сильно проигрывала человеку по времени
поиска.
(2) Найти все числа, равные сумме факториалов своих цифр.
(3) Найти все числа, равные сумме n-ных степеней своих цифр для
n от 1 до 10
(4) Отсортировать по возрастанию 5000 вещественных чисел, почти
равномерно распределенных в диапазоне 0..1 за время менее 1 ми╨
нуты методом отличным от QuickSort или HeapSort.
(2) Пусть p - m*n матрица с элементами типа "да/нет". Известно,
что множество элементов, равных "да", есть объединение непере╨
секающихся прямоугольников. Найти число прямоугольников и число
тех из них, которые являются квадратами.
4.
(5) Из четырех одинаковых кубиков можно собрать 6 разных непа╨
раллелепипедов, из трех - еще один. Сколькими различными спосо╨
бами можно собрать куб из этих 7 деталей?
(2) Перечислить все способы расстановки скобок в неассоци╨
ативном произведении n сомножителей
(2) Перечислить все возможные разбиения множества 1..N на K
частей.
(2) Напечатать все возможные разбиения числа N на сумму слага╨
емых.
(3) Напечатать все последовательности цифр 0,1,2 длины n, в ко╨
торые ни одна группа цифр не входит два раза подряд
(2) Отображение целочисленного отрезка в себя задано в виде
функции y=f(x). Найти минимальный период этого отображения.
Графы
-----
(2) Найти число связных компонент графа.
(2) Пусть с каждым ребром графа связано число - его длина. Сос╨
тавить программу для определения кратчайшего пути между двумя
заданными вершинами графа.
(2) Найти в графе кратчайший путь, состоящий ровно из l ребер.
(2) Составить программу для определения наличия циклов в графе.
(3) Дано множество кругов на плоскости, их объединение связно.
Для кругов a, b найти цепочку a=a1,a2,...,an=b такую, что ai
пересекается с ai+1 для i из 1..n-1 и такую, что сумма квадра╨
тов площадей пересечения минимальна.
Обработка текстов
-----------------
(4) Написать программу на Фортране (или на Си), которая печата╨
ет свой собственный текст. Операторами ввода или трюками типа
"call system('type program.f')" пользоваться, естественно,
нельзя. (Наилучшее известное решение содержит 5 строчек).
(2) Найти в файле все слова, отличающиеся от заданного заменой
одной буквы, пропуском, вставкой буквы или перестановкой двух
соседних букв (типичные опечатки).
(3) В векторе из символов найти отрезок-палиндром максимальной
длины (палиндром - текст, который одинаково читается в прямом и
обратном направлении).
(2) Подсчитать число слов, букв и строчек в текстовом файле
(слова могут быть разделены пробелами и знаками препинания, и
соединены знаками переноса ("-" в конце строки).
(3) Напечатать 100 наиболее часто встречающихся в текстовом
файле слов вместе с числом их появлений.
5.
(4) Отсортировать строчки текстового файла в лексикографическом
порядке. Файл может быть довольно большим и не поместиться в
память целиком.
(2) Дано целое 0 <= N <= 10**6. Напечатать по-русски фразу "N
ворон". Например, "миллион ворон" или "двести сорок три тысячи
семьсот пятьдесят одна ворона".
(3) Разбить слово русского языка на "слоги", в местах пригодных
для переноса. Эвристические правила: слово можно переносить в
следующих местах: г-г, гс-сг, сг-сг, а также после й,ь. Нельзя
переносить одну букву, с обеих сторон от знака переноса должны
встречаться гласные. Например: прог-рам-ми-ро-ва-ние. Попытай╨
тесь улучшить эти правила (5 баллов).
(3) Напишите программу для форматирования абзацев текста. Абза╨
цы отделяются друг от друга пустыми строчками. Слова в отформа╨
тированном абзаце должны размещаться возможно более плотно,
правый край должен быть выровнен. Первая строка абзаца должна
быть с отступом.
(3) Шаблон - строка обычных символов, среди которых могут
встречаться "*", обозначающая последовательность (в том числе и
пустую) любых символов и "?", обозначающий один любой символ.
Напечатать все строчки файла, в которых встречаются слова, под╨
ходящие под заданный шаблон.
(5) Даны два немного различающихся текстовых файла (например,
оба получены из одного оригинала некоторым количеством вставок,
удалений или замен строчек). Получить их объединение, с отме╨
ченными различиями. Разметка должна быть такого вида:
совпадающий текст
<<<1>>>
вариант первого файла
<<<2>>>
вариант второго файла
<<<*>>>
совпадающий текст
...
Геометрия
---------
(4) Найти выпуклую оболочку n окружностей ненулевого радиуса.
(4) Найти выпуклую оболочку N точек за O(N*log(N)) операций.
(3) Найти диаметр выпуклого многоугольника за О(N) операций.
(4) Нарисовать вид поверхности z=f(x,y) (точнее координатной
сетки x=const, y=const на ней) из точки (x0,y0,z0) с "удалением
невидимых линий".
(2) Нарисовать линии уровня функции z=f(x,y)
(2) Нарисовать кривую Пеано.
(2) Нарисовать двумерное Канторово множество.
6.
(3) Даны k отрезков на прямой. Найти максимальное n, для кото╨
рого существует точка, принадлежащая одновременно n отрезкам за
время меньшее O(k**2).
Алгебра
-------
(2) Сколько из первых 1000 чисел вида (p**2-2), где p-простое,
являются составными?
(2) Проверить положительную определенность квадратичной формы
(2) Найти собственные числа и собственные векторы матрицы (2*2)
(3) Линейным преобразованием привести квадратичную форму к ка╨
ноническому виду. (Найти матрицу преобразования и сигнатуру
формы).
(4) Найти число вещественных корней полинома на заданном отрез╨
ке (используя, например, теорему Штурма).
(3) Найти все неприводимые над полем Z(p) многочлены степени n
(n небольшое).
(5) Реализовать асимптотически быстрый способ умножения матриц,
основанный на следующем тождестве, с помощью которого умножение
матриц размера 2*k производится с помощью 7 умножений матриц
размера k, что дает сложность k**log2(7) (алгоритм Штрассена):
─┬┬│─┬┬│ ─┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬│
┴ab┴┴AB┴=┴(a+d)(A-D)+(b+d)(C+D)-d(A+C)+(a-b)D a(D+B)-(a-b)D┴
┴cd┴┴CD┴ ┴d(A+C)-(d-c)A (a+c)(B+A)-(a+d)(A-D)-a(D+B)+(d-c)A┴
┌┬┬┐┌┬┬┐ ┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
(3) Пусть F:A->A отображает множество А из N элементов в себя.
Найти S - максимальное подмножество A - такое, что сужение F на
S взаимно однозначно. (Можно считать, что A - множество целых
чисел от 1 до N; F - вектор элементов типа 1..N с индексом
1..N). Время работы программы не должно быть больше O(N).
(4) Теорема Ван дер Вардена утверждает, что при любой раскраске
целочисленной оси координат в два цвета существуют одноцветные
арифметические прогрессии любой длины. Для небольших K найти
наименьшее N такое, что при любой раскраске отрезка длины N су╨
шествует одноцветная арифметическая прогрессия длины K.
(5) Напечатать все неизоморфные полугруппы из 4 элементов
(5) Код Грэя степени 4 - перестановка 4-разрядных слов 0000,
0001, 0010, ..., 1111 такая, что два соседних слова (первое и
последнее также считаются соседями) отличаются только одним би╨
том. Два кода считаются эквивалентными, если один можно полу╨
чить из другого размещением слов в обратном порядке, цикличес╨
ким сдвигом последовательности, инверсией некоторого подмно╨
жества битов и перестановкой битов. Найти число неэквивалентных
кодов порядка 4.
(3) "Китайская теорема об остатках". Дано k взаимно простых чи╨
сел m[i]. Найти число, меньшее произведения m[i], если известны
остатки от деления его на все m[i].
7.
(3) Число m называется кармайкловым, если для всех b взаимно
простых с m выполняется mod(b**(m-1)-1,m) = 0 (т.е. число ведет
себя как простое в малой теореме Ферма) Найти все кармайкловы
числа в диапазоне 1..32767
(5) Определить, является ли 30-50-значное число простым с по╨
мощью следующего вероятностного теста (далее все вычисления
ведуться в кольце вычетов Z/pZ):
выбрать случайноe число a в диапазоне 2..p,
если НОД(p,a)!=1 или a**(p-1)!= 1, то p - составное;
иначе пусть (p-1)=q*2**k, где q - нечетно;
рассмотрим последовательность
a**q, a**(2*q), a**(4*q)..., a**(p-1) = 1
если в ней существует фрагмент ...x, 1,... и x != +-1,
то p - составное,
иначе p - выдержало тест на простоту для данного а.
Если p - составное, то оно не проходит тест по крайней мере для
3/4 значений a в диапазоне 1..p; выполнив тест для k различных
a, можно надеятся, что p - простое с вероятностью 1-0.25**k.
(4) Разложить 20-значное число на множители методом Монте-Карло.
(6) Разложить 20-значное число на множители методом квадратич-
ного решета.
Шахматы
-------
(4) Сколько ферзей (коней) достаточно расставить на шахматной
доске так, чтобы каждая клетка доски находилась под боем? Найти
все расстановки.
(3) Составить программу для определения числа расстановок фер╨
зей на шахматной доске, так что ни один из них не бьет другого.
(Симметричные решения считать один раз)
(3) Составить программу для обхода шахматной доски ходом коня,
начиная с произвольного поля. Конь должен побывать на каждом
поле ровно по одному разу. Указание: существует эвристический
алгоритм - ходить каждый раз на то поле, с которого можно уйти
меньшим число ходов. Всегда ли он работает?
Разное
------
(4) Реализовать редактор шрифта для а/ц-терминала "Грамм". Его
функции должны включать редактирование изображения отдельного
знака, сохранение, восстановления всего шрифта в файле, загруз╨
ку шрифта в терминал.
(3) Реализовать игру "Реверси" (известную также под названием
"Отелло"). Играют два человека, программа только рисует поле,
переворачивает фишки, проверяет правильность ходов и подсчиты╨
вает очки. Развитие темы: программа не слишком бездарно играет
за одного игрока (6 баллов).
(3) Реализовать игру НИМ: имеется 3 (или N) кучи камней, за
один ход игрок может взять любое количество камней из какой-ни╨
будь одной кучи. Выигрывает тот, кто берет последний камень.
Программа должна выигрывать в выигрышных позициях.
(6) Реализовать игру Калах (программа должна выигрывать у но╨
вичка).
- Конец списка задач -