В задачах на составление алгоритма требуется найти эффективный алгоритм.
1. Пусть задана последовательность скобок. Требуется проверить правильная ли она.
Примеры правильных последовательностей: (), (())(), (()(()())). Примеры неправильных последовательностей: (, )(, ()), (()(()).
2. Дана таблица n´m, заполненная плюсами и минусами. Алгоритм на каждом шаге выбирает какую-то строку или столбец, в котором плюсов меньше, чем минусов, и в нем меняет плюсы на минусы и минусы на плюсы. Если такой строки или столбца не существует, то алгоритм заканчивает работу. Доказать, что это рано или поздно произойдет.
3. Дана строка из нулей и единиц. Найти в ней симметричную подпоследовательность максимальной длины идущих подряд чисел. Последовательность a1, a2 ...an называется симметричной, если a1=an , a2=an-1 ...
4. Что делать, если нужно завести неизвестное заранее число вложенных циклов, обеспечивающих пробегание переменной n1 от 1 до m1; n2 - от 1 до m2 ... nk - от 1 до mk?
5. В последовательности чисел a1, a2 ... an найти максимальную пилообразную подпоследовательность, то есть такую подпоследовательность, в которой чередуются возрастание и убывание от предыдущего члена к последующему, например: 4, 2, 3, -1, 5, 0, 1, -2.
а) Подпоследовательность из подряд идущих чисел;
б) из необязательно подряд идущих чисел.
В подпоследовательности (по определению подпоследовательности) члены идут в том же порядке, что и в последовательности.
6. Распечатать звездочками таблицу nxm ячеек, размер ячейки - kxp.
7. Вводится предложение. Программа должна выдать новое предложение, в котором буквы в каждом слове написаны в обратном порядке, а порядок слов сохранен.
8. Используя часы, узнайте быстродействие машины, на которой работаете (нужно написать тестовую программу).
9. Напишите программу, которая выдает последовательность случайных чисел.
а) Случайные числа от 0 до 1.
A |
1 |
|
13 |
12 |
11 |
1 |
2 |
3 |
|
|
10 |
|
3 |
|
7 |
8 |
9 |
5 |
4 |
5 |
6 |
|
10 |
6 |
|
6 |
|
|
11 |
7 |
|
7 |
8 |
9 |
B |
б) Случайные числа из 0,1,2,...n-1.
в) Программа выдает последовательность из нулей и единиц, в которой 1 на каждом месте стоит с вероятностью p.
лабиринт
10. Дан лабиринт nxn клеток. Непроходимые клетки помечены
звездочками. Лабиринт можно проходить, двигаясь на одну клетку по горизонтали
или вертикали. Программа должна вписать в каждую клетку число, обозначающее
кратчайшее расстояние до нее от клетки A, и найти количество различных
кратчайших путей из клетки A в клетку B.
11. Графом называется множество вершин и соединяющих их ребер. Ориентированным или направленным графом называется граф, в котором на каждом ребре стоит стрелочка от одной вершины к другой. Часто к графу предъявляется требование отсутствия дублированных ребер, то есть двух ребер, соединяющих одни и те же вершины, и циклических ребер, соединяющих вершину саму с собой. Вершина, не соединенная ребрами с другими вершинами называется изолированной. Граф может распадаться на несвязанные между собой ребрами части.
Пусть
на каждом ребре графа стоит неотрицательное число. Путем от одной вершины
графа до другой назовем путь, проходящий по ребрам. Если граф ориентированный,
то ребро можно проходить только по стрелочке. Длиной пути назовем сумму чисел,
стоящих на пройденных ребрах. Минимальным путем от одной вершины до другой
назовем путь с минимальной длиной. Составьте алгоритм, находящий длину минимального
пути между двумя заданными вершинами.
12. Дана последовательность из n чисел. Требуется найти в ней возрастающую подпоследовательность с максимальным количеством членов. Рассматриваются подпоследовательности из необязательно подряд идущих членов.
13. Даны две последовательности из нулей и единиц. Найти подпоследовательность максимальной длины, которая содержится в обеих последовательностях.(Рассматриваются подпоследовательности из необязательно подряд идущих чисел.)
14. Найти простые числа от 1 до n методом решета Эрастофена. Этот метод заключается в последовательном вычеркивании чисел, делящихся на k-ое простое число.
15. Найти простые числа близнецы от 1 до n. Такими числами называются простые числа, отличающиеся на 2.
16. Рассмотрим расстояние (то есть разность) между двумя соседними простыми числами. Оно в среднем увеличивается. Требуется найти простые числа, побивающие рекорд по расстоянию до следующего простого числа и соответствующие расстояния.
17. а) Сколькими способами можно представить заданное
натуральное число в виде суммы натуральных чисел? Найти алгоритм, вычисляющий
искомое число по рекуррентным формулам, используя систему чисел с двумя индексами, по рекуррентным формулам.
б) Найти алгоритм, перечисляющий все такие представления. (Не на рекуррентные формулы.)
18. а) Определить, сколькими способами можно представить заданное натуральное число n в виде суммы k целых чисел, каждое из которых может быть от 0 до m.
б) Найти количество счастливых
билетов, состоящих из 2k цифр. Счастливым билетом называется билет (например,
автобусный) с номером таким, что
. Билеты имеют номера от 00...0 до 99...9.
Задача сортировки заключается в расположении n чисел a1, a2, ... an в порядке возрастания.
19. Метод пузырька. На каждом шаге алгоритм выбирает два соседних числа ak и ak+1 , удовлетворяющие условию ak+1<ak, если такие числа существуют, и меняет их местами. Если таких чисел нет, то алгоритм заканчивает работу. Докажите, что если алгоритм кончит работу, то числа будут отсортированы. Докажите, что алгоритм кончит работу, причем количество шагов не зависит от последовательности выполнения таких перестановок. Метод называется методом пузырька, потому что большие числа как бы всплывают наверх. Оцените порядок количества операций, при сортировке n чисел. Например, f(n) порядка n3 (f(n)~n3), если $c1>0 $c2>0 $N "n>N: c1n3<f(n)<c2n3.
20. Сортировка слиянием. В этом методе сначала сортируются числа в группах по 2 числа, потом - по 4, потом - по 8 и т. д. При этом используется алгоритм слияния двух отсортированных последовательностей в одну отсортированную. Опишите алгоритм слияния и оцените количество операций в алгоритме слияния и во всей сортировке. Примечание: Если ax=y, то пишут: x=logay ("логарифм по основанию a от y"), например, log21024=10.
21. Сортировка по ключам. Пусть надо рассортировать
карточки, на каждой из которых написано k целых чисел: n1, n2,...nk , причем i-ое число
может принадлежать диапазону от 0 до mi‑1. Числа n называются ключами. Считается, что
карточка с числами n1, n2,...nk больше карточки с числами l1, l2
,...lk ,
если n1>l1, или n1=l1, n2>l2,
или n1=l1, n2=l2, n3>l3,...
или n1=l1,... nk-1=lk-1,
nk>lk. То есть, сравнение
этих карточек происходит так же, как и сравнение чисел и
в позиционной системе
счисления, в которой i-ая цифра может быть от 0 до mi-1.Заметим, что
. (*)
Предлагается следующий алгоритм сортировки карточек. Рассортируем карточки сначала по k-ому ключу, затем по k-1-ому и т. д. по всем ключам, заканчивая первым.
Сортировка по i-ому ключу заключается в следующем. Пусть карточки образуют последовательность. Разложим карточки на mi новых последовательностей следующим образом. Сначала все новые последовательности пустые. Будем брать карточки, начиная с первой, и класть каждую карточку в конец новой последовательности с номером равным i-ому ключу на карточке (последовательности пронумерованы от 0 до mi-1).Затем сложим все образовавшиеся последовательности в одну, в порядке возрастания их номеров.
а) Докажите, что после работы этого алгоритма карточки будут рассортированы.
б) Как реализовать этот алгоритм на вычислительной машине? Рассмотрите случай, когда в памяти не умещается Nmi чисел при каком-то i, где N - количество карточек. Допустим, что ключей много и переписывать каждый раз всю карточку из одного места памяти в другое трудоемко. Как можно сэкономить время?
в) Пусть надо рассортировать целые числа, принадлежащие диапазону от 0 до m-1.Число можно разбить на ключи в соответствии с (*) и применить метод сортировки по ключам. Проанализировать оптимальную стратегию такой сортировки и оценить количество операций и объем затрачиваемой памяти.
22.
Ссылочный словарь. Пусть надо рассортировать целые числа, принадлежащие
диапазону от 0 до 2k-1.Представим
эти числа в двоичном виде. Допустим, это будут числа 1010, 0011, 0001, 1100. Создадим
бинарную структуру, показанную на рисунке.
а) По каким алгоритмам можно: добавить новое число в структуру, проверить наличие какого-то числа в структуре и выписать отсортированную последовательность? Оцените быстродействие этих операций и средний объем памяти, затрачиваемый на одно данное.
б) Как развить описанную здесь идею для организации словаря, в котором к каждому слову прилагается некоторый текст. Слова могут состоять из различного количества букв. Должна быть возможность по заданному слову находить соответствующий ему текст и добавлять в словарь новые слова с текстом.
Опишем некоторые часто используемые структуры данных.
Список. (См. рис.) Используется для работы с последовательностью данных a1, a2,... an .Позволяет добавлять и удалять данные из любого места последовательности, работать с переменным количеством данных.
23. Как добавить и удалить данное из списка, находящееся между какими-то двумя данными? Как можно организовать список, чтобы добавление и удаление данного перед первым и после последнего элемента списка выполнялось точно так же?
Стек. Стек можно описать как последовательность данных, в которую кладут и берут данные только с одного конца.(Берется то данное, которое позже всего положили.)
Очередь.
Очередь - последовательность данных, в которую кладут и берут данные с
противоположенных концов. (Берется то данное, которое раньше всего положили.)
24. Как реализовать стек и очередь
а) с помощью списка;
б) с помощью массива из n элементов (если количество данных начинает превышать n, то новые данные не кладутся.
Граф. Каждой вершине графа соответствует список вершин, которые с ней связаны ребрами.
25. Придумайте другие способы задания графа.
Дерево. Является частным случаем графа. Определение дерева можно понять из рисунка. Для каждой вершины указываются вершины, которые соединены с ней ребрами и находятся ниже нее. Причем у каждой вершины, кроме верхней, есть ровно одна вышележащая вершина, с которой она соединена ребром. Структуры, имеющие вид дерева также называют иерархическими структурами.
26. Дайте строгое определение дерева. Придумайте другие способы задания дерева.
Представление данных в компактном виде.
1) Представление нескольких
чисел в виде одного числа, например, если 0£a<m, bÎZ,
тогда паре чисел (a,b) ставим в соответствие a+bm или, если a>0, bÎ{0;
1}, тогда паре (a,b) ставим в соответствие .
2) Использование значений, выходящих за обычный диапазон какой-то величины, для обозначения особых случаев, вместо использования для этого дополнительных данных. Например, в задаче 10 про лабиринт непроходимые летки можно метить -1, тогда не потребуется отдельный массив для задания непроходимых клеток.
3) Допустим, возможно n взаимно исключающих случаев. Тогда можно хранить вместо n логических переменных одну переменную, показывающую номер случая.
Во всех этих случаях экономится память, может уменьшаться количество пересылок данных и упроститься их обработка.
Расширение структур данных новыми данными для упрощения логики алгоритма, уменьшения количества рассматриваемых случаев. Например, добавление в список нулевого элемента перед первым (задача 23), добавление в лабиринт двух строк и двух столбцов окаймляющих непроходимых клеток, чтобы не делать проверку выхода за границу (задача 10).
Заводить массивы для величин, которые можно было бы не помнить, а постоянно вычислять, например, степени 10. При этом экономится время выполнения и упрощается программа.
Многомерный массив заменять одномерным, например, вместо двумерного массива a[n,m] использовать одномерный a[nm]. При этом координаты элемента массива будут одним числом, и любое смещение на фиксированный вектор будет эквивалентно прибавлению фиксированного числа.
27. Найти путь, по которому конь может обойти шахматную доску, побывав на каждом поле ровно один раз. Предлагается окаймить поле "занятыми" конем клетками, использовать для шахматной доски одномерный массив и хранить в отдельном массиве смещения, соответствующие 8 ходам коня.
Поддерживать динамические данные одного типа самостоятельно, заводя для них массив, вместо использования стандартных возможностей языка. Динамическими называются данные, которые могут создаваться и уничтожаться во время работы программы. Преимущество заведения для них массива и самостоятельного осуществления операций создания и удаления заключается в большей надежности и наглядности работы с этими данными. При этом ссылки на эти данные являются номером элемента массива, а не адресом ячейки памяти.
Хранение данных по имени. Допустим, данное содержит имя, которое можно представить в виде натурального числа, меньшего либо равного N. Требуется хранить такие данные, вынимать их по их имени и запоминать новые данные. Возможны следующие варианты хранения таких данных.
· Данные можно хранить в отсортированном по имени виде.
· Можно завести массив из N элементов, если N не слишком велико.
·
Метод
хеширования. Какой-то объем памяти разделяется на k блоков. Каждый блок
содержит m ячеек памяти, например m=5. Данное кладется в одну из пустых ячеек
памяти блока с номером k=f(n), где функция f близка к случайной, она должна
распределять данные равномерно по блокам. Эта функция называется хэш-функцией.
Если блок, в который нужно положить данное полностью заполнен, то выделяется
резервный блок, в который кладутся данные, относящиеся к тому же номеру блока и
делается указатель на этот резервный блок. Если резервный блок переполнится, то
выделяется следующий резервный блок и т.д.
28. Опишите, как выбирается данное по своему номеру при таком хранении.
29. Написать программу перевода из n-ричной системы счисления в m-ричную.
30. Написать программу перевода из римской в десятичную систему счисления и наоборот. Римские цифры: I=1, V=5, X=10, L=50, C=100, D=500, M=1000.
31. Найти все способы расположения 8 ферзей на шахматной доске так, чтобы они не били друг друга.
32. Найти все способы расположения 5 ферзей на шахматной доске так, чтобы они били все поля, в том числе и те, на которых находятся.
33. В таблице nxn (например, 10x10) каждая клетка с вероятностью p закрашена. Написать программу, которая при данной закраске находит количество связных закрашенных областей. Найти приближенно зависимость среднего количества связных областей от p, многократно запуская эту программу. Множество клеток связно, если от любой до любой клетки этого множества можно дойти по клеткам этого же множества, передвигаясь по одной клетке по вертикали или горизонтали.
34. а) Придумать алгоритм, который рисует прямую ax+b на прямоугольном экране nxm точек (каждая точка может гореть или не гореть).
б) Как сделать так, чтобы все прямые казались одинаковой толщины?
35. Написать программу, помогающую рисовать псевдографическими символами (символами типа ┐, ╟, ╪) с автоматическим сопряжением линий.
36. Сделать редактор графа, то есть программу, в которой можно составлять и изменять произвольный граф (имеется в виду не изображение графа на плоскости, а структуру связей вершин).
37. Сделать редактор иерархической структуры (то есть, дерева).
38. Написать программу автоматического переноса русских слов. При выборе места переноса можно учитывать расстояния до границ слова, анализировать, являются ли буквы гласными, согласными, "ь", "ъ", "й" и т.д.
39. Пусть имеется словарь из какого-то множества русских слов. Предлагается составить программы для различных игр со словами, например:
а) составление слов из букв заданного слова;
б) нахождение всех слов, отличающихся от данного не более чем в n буквах (n=1,2,3,...).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в) составление цепочек из слов, в которых в соседних словах может различаться только одна буква;
г) нахождение всех слов, имеющих заданные буквы на каких-то фиксированных местах (например, ?и?е????р?);
д) составление кроссвордов, например вида:
40. Какое максимальное число можно описать текстом не больше заданного объема? Чтобы исследовать этот вопрос предлагается придумать алгоритмический язык для выражения больших чисел.
41. Как сделать программу, которая печатает текст, совпадающий с ее собственным текстом (нельзя обращаться к памяти, содержащей текст этой программы)? Предлагается придумать наиболее простой алгоритмический язык, на котором можно проиллюстрировать решение этой задачи.
42. По клетчатой полоске длиной n клеток ходит путник по заданной программе. Его программа составлена из следующих команд: шаг влево на одну клетку, шаг вправо на одну клетку, проверок есть ли стенка справа, слева, условного оператора, оператора безусловного перехода, перехода на подпрограмму и подпрограмм. В его программе не может быть использована рекурсия при вызове подпрограмм, то есть не может быть вызова какой-то подпрограммой самой себя, возможно через другие подпрограммы. Памяти у путника нет, и он не может использовать числа, например, считать количество шагов.
а) Как сделать покороче программу, продвигающую путника на миллион клеток?
б) Доказать, что не существует конечной программы, которая ставит путника в центральную клетку полоски длиной 2n+1 при любом n.
43. Требуется раскрасить вершины заданного графа в минимальное число цветов так, чтобы никакие две смежные вершины (вершины, соединенные ребром) не были окрашены в один цвет.
44. Теорема Ван дер Вардена утверждает, что "m "k $n " раскраска полоски длиной n клеток в m цветов $ арифметическая прогрессия из k одноцветных клеток на этой полоске. Найти минимальное n(m,k).
45. Дано n. Найти максимальное число подряд идущих натуральных чисел, каждое из которых делится на какое-то из первых n простых чисел. Другая формулировка этой задачи: найти максимальное количество подряд идущих целых чисел, которые можно покрыть n решетками с шагами p1, p2,... pn. Решеткой с шагом a называется множество {an+b: nÎZ}, где b - фиксированное число.
46.
Найдите все n-угольники (например, пятиугольники), которыми можно замостить
плоскость, то есть заполнить ее без перекрытий и пустых мест n-угольниками,
равными данному. Можно рассмотреть случай, когда в замощении не используются
многоугольники зеркально-симметричные данному и случай, когда никакая вершина
одного многоугольника не лежит на стороне другого. Все множество искомых
многоугольников делится на классы, многоугольники одного класса характеризуются
тем, что для них возможна одна и та же схема заполнения плоскости. Оказывается,
что класс можно задать определенными соотношениями на углы и стороны
многоугольников. Эти соотношения для всех классов и требуется найти.
47. Написать программу, решающую следующую головоломку. На прямоугольнике nxm клеток находятся фишки, составленные из клеток (например, прямоугольные фишки 1x1, 2x1, 2x2, как в примерах, показанных на рисунке). Эти фишки не перекрывают друг друга. Некоторое количество клеток прямоугольника свободны от фишек (в примерах на рисунке - 2 клетки). За один ход можно передвинуть одну фишку по горизонтали или вертикали на одну клетки клетку, пользуясь свободными клетками. Требуется такими перемещениями перевести фишки из одного положения в другое за наименьшее количество ходов.
48.
Написать программу, решающую головоломку "перевертыши". На прямоугольнике
nxm на каждой клетке, кроме одной, лежит кубик, каждая грань которого окрашена
в свой цвет. Все кубики раскрашены одинаково. За один ход можно перекатить
кубик через ребро на свободную клетку. Вначале все кубики ориентированы
одинаково и свободна угловая клетка. Требуется за минимальное количество ходов
перевести кубики в состояние, когда сверху у них будет грань одного и того же
цвета, отличного от начального. Можно задать дополнительные условия на
ориентацию кубиков и на положение свободной клетки в конечной позиции. Варианты
размеров поля - 3x2 и 3x3.