Программирование

1. Разные задачи. (Придумать алгоритм.)

В задачах на составление алгоритма требуется найти эффективный алгоритм.

1. Пусть задана последовательность скобок. Требуется проверить правильная ли она.

Примеры правильных последовательностей: (), (())(), (()(()())). Примеры неправильных последовательностей: (, )(, ()), (()(()).

2. Дана таблица n´m, заполненная плюсами и минусами. Алгоритм на каждом шаге выбирает какую-то строку или столбец, в котором плюсов меньше, чем минусов, и в нем меняет плюсы на минусы и минусы на плюсы. Если такой строки или столбца не существует, то алгоритм заканчивает работу. Доказать, что это рано или поздно произойдет.

3. Дана строка из нулей и единиц. Найти в ней симметричную подпо­следовательность максимальной длины идущих подряд чисел. Последо­вательность a­­1, 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.

а) Подпоследовательность из подряд идущих чисел;

б) из необязательно подряд идущих чисел.

В подпоследовательности (по определению подпоследовательности) члены идут в том же порядке, что и в последовательности.

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.

3. Алгоритм параллельного поиска.

лабиринт
 
10. Дан лабиринт nxn клеток. Непроходимые клетки помечены звездочками. Лабиринт можно проходить, двигаясь на одну клетку по горизонтали или вертикали. Программа должна вписать в каждую клетку число, обозначающее кратчайшее расстояние до нее от клетки A, и найти количество различных кратчайших путей из клетки A в клетку B.

11. Графом называется множество вершин и соединяющих их ребер. Ориентированным или направленным графом называется граф, в котором на каждом ребре стоит стрелочка от одной вершины к другой. Часто к графу предъявляется требование отсутствия дубли­рованных ребер, то есть двух ребер, соединяющих одни и те же вершины, и циклических ребер, соединяющих вершину саму с собой. Вершина, не соединенная ребрами с другими вершинами называется изолированной. Граф может распадаться на несвязанные между собой ребрами части.

Пусть на каждом ребре графа стоит неот­рицательное число. Путем от одной вершины графа до другой назовем путь, проходящий по ребрам. Если граф ориентированный, то ребро можно проходить только по стрелочке. Длиной пути назовем сумму чисел, стоящих на пройденных ребрах. Минимальным путем от одной вершины до другой назовем путь с минимальной длиной. Составьте алгоритм, находящий длину минимального пути между двумя заданными вершинами.

12. Дана последовательность из n чисел. Требуется найти в ней возрастающую подпоследовательность с максимальным количеством членов. Рассматриваются подпоследовательности из необязательно подряд идущих членов.

13. Даны две последовательности из нулей и единиц. Найти подпосле­довательность максимальной длины, которая содержится в обеих последовательностях.(Рассматриваются подпоследовательности из необязательно подряд идущих чисел.)

4. Простые числа.

14. Найти простые числа от 1 до n методом решета Эрастофена. Этот метод заключается в последовательном вычеркивании чисел, делящихся на k-ое простое число.

15. Найти простые числа близнецы от 1 до n. Такими числами называют­ся простые числа, отличающиеся на 2.

16. Рассмотрим расстояние (то есть разность) между двумя соседними простыми числами. Оно в среднем увеличивается. Требуется найти простые числа, побивающие рекорд по расстоянию до следующего прос­того числа и соответствующие расстояния.

5. Рекуррентные формулы.

17. а) Сколькими способами можно представить заданное натуральное число в виде суммы натуральных чисел? Найти алгоритм, вычисляющий искомое число по рекуррентным формулам, используя систему чисел с двумя индексами, по рекуррентным формулам.

б) Найти алгоритм, перечисляющий все такие представления. (Не на рекуррентные формулы.)

18. а) Определить, сколькими способами можно представить заданное натуральное число n в виде суммы k целых чисел, каждое из которых может быть от 0 до m.

б) Найти количество счастливых билетов, состоящих из 2k цифр. Счастливым билетом называется билет (например, автобусный) с номе­ром  таким, что . Билеты имеют номера от 00...0 до 99...9.

6. Сортировка.

Задача сортировки заключается в расположении 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. Создадим бинарную структуру, показанную на рисунке.

а) По каким алгоритмам можно: добавить новое число в структуру, проверить наличие какого-то числа в структуре и выписать отсорти­рованную последовательность? Оцените быстродействие этих операций и средний объем памяти, затрачиваемый на одно данное.

б) Как развить описанную здесь идею для организации словаря, в котором к каждому слову прилагается некоторый текст. Слова могут состоять из различного количества букв. Должна быть возможность по заданному слову находить соответствующий ему текст и добавлять в словарь новые слова с текстом.

7. Структуры данных.

 Опишем некоторые часто используемые структуры данных.

Список. (См. рис.) Используется для работы с последовательностью данных a1, a2,... an .Позволяет добавлять и удалять данные из любого места последовательности, работать с переменным количеством данных.

23. Как добавить и удалить данное из списка, находящееся между какими-то двумя данными? Как можно организовать список, чтобы добавление и удаление данного перед первым и после последнего элемента списка выполнялось точно так же?

Стек. Стек можно описать как последовательность данных, в которую кладут и берут данные только с одного конца.(Берется то данное, которое позже всего положили.)

Очередь. Очередь - последовательность данных, в которую кладут и берут данные с противоположенных концов. (Берется то данное, которое раньше всего положили.)

24. Как реализовать стек и очередь

а) с помощью списка;

б) с помощью массива из n элементов (если количество данных начи­нает превышать n, то новые данные не кладутся.

Граф. Каждой вершине графа соответст­вует список вершин, которые с ней связа­ны ребрами.

25. Придумайте другие способы задания графа.

Дерево. Является частным случаем графа. Определение дерева можно понять из рисунка. Для каждой вершины указыва­ются вершины, которые соединены с ней ребрами и находятся ниже нее. Причем у каждой вершины, кроме верхней, есть ровно одна вышележащая вершина, с которой она соединена ребром. Структуры, имеющие вид дерева также называют иерар­хическими структурами.

26. Дайте строгое определение дерева. Придумайте другие способы задания дерева.

8. Приемы программирования.

Представление данных в компактном виде.

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. Опишите, как выбирается данное по своему номеру при таком хра­нении.

9. Рекомендуемые задачи.

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.