Задачи для самостоятельного решения

Однажды Монпертюи, развалившись в кресле и позевывая, сказал: "С каким удовольствием я занялся бы сейчас решением красивой и не очень трудной задачи!". В этих словах - весь человек.

Себастьен Шамфор. Характеры и анекдоты

6.1. Пусть L обозначает кольцевой однонаправленный список с уда­ленным заглавным звеном. Определить, является ли кольцо пустым.

6.2. Разработать функцию для подсчета количества звеньев в за­данном кольцевом списке с удаленным заглавным звеном.

6.3. Пусть L обозначает кольцевой однонаправленный список с уда­ленным заглавным звеном. Написать функцию, которая подсчитывает количество элементов списка L, у которых равные "соседи".

6.4. Пусть L обозначает кольцевой однонаправленный список с уда­ленным заглавным звеном. Написать функцию, выводящую на экран дисплея элементы списка L в обратном порядке.

6.5. Пусть L обозначает кольцевой однонаправленный список с уда­ленным заглавным звеном. Написать функцию удаления из списка L первого звена, содержащего отрицательный элемент (если такое зве­но найдется).

6.6. Пусть L обозначает кольцевой однонаправленный список с уда­ленным заглавным звеном. Написать функцию, которая в "конец" кольца добавляла бы все его звенья, располагая их в обратном по­рядке (например, по кольцу, содержащему целые числа 1,2,3, требу­ется построить кольцо, содержащее числа 1,2,3,3,2,1).

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

6.8. Предположим, что уже построен кольцевой однонаправленный список с удаленным заглавным звеном, элементами которого являются стpоки. Написать программу, подсчитывающую количество строк в кольце, которые начинаются и оканчиваются одним и тем же симво­лом.

6.9. Предположим, что уже построен и задан указателем P кольце­вой однонаправленный список с удаленным заглавным звеном, элемен­тами которого являются целые числа. Написать программу, которая находит минимальное значение элементов кольца и номер первого звена, содержащего элемент с этим значением.

6.10. "Считалка". N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая круг после каждого уда­ления. Определить порядок удаления ребят из круга. Решение этой задачи описать в виде программы, которая должна вывести на экран номера ребят в том порядке, в каком они удаляются из круга.

6.11. Предположим, что уже построены два однонаправленных кольца с удаленным заглавным звеном, элементами которых являются целые числа. Написать функцию, которая определяет, является ли содержи­мое данного кольца "перевертышем" содержимого другого кольца.

6.12. Пусть L обозначает кольцевой однонаправленный список с включенным заглавным звеном. Определить, является ли кольцо пус­тым.

6.13. Разработать функцию для подсчета количества звеньев в за­данном кольцевом списке с включенным заглавным звеном.

6.14. Пусть L обозначает кольцевой однонаправленный список с включенным заглавным звеном. Написать функцию, которая подсчиты­вает количество элементов списка L, у которых равные "соседи".

6.15. Пусть L обозначает кольцевой однонаправленный список с включенным заглавным звеном. Написать функцию, выводящую на экран дисплея элементы списка L в обратном порядке.

6.16. Пусть L обозначает кольцевой однонаправленный список с включенным заглавным звеном. Написать функцию удаления из списка L первого звена, содержащего отрицательный элемент (если такое звено найдется).

6.17. Пусть L обозначает кольцевой однонаправленный список с включенным заглавным звеном. Написать функцию, которая в "конец" кольца добавляла бы все его звенья, располагая их в обратном по­рядке (например, по кольцу, содержащему целые числа 1,2,3, требу­ется построить кольцо, содержащее числа 1,2,3,3,2,1).

6.18. Пусть L обозначает кольцевой однонаправленный список с включенным заглавным звеном. Определить, есть ли в списке L хотя бы одно звено, содержащее элемент, равный элементу следующего за ним звена.

6.19. Предположим, что уже построен кольцевой однонаправленный список с включенным заглавным звеном, элементами которого являют­ся стpоки. Написать программу, подсчитывающую количество строк в кольце, которые начинаются и оканчиваются одним и тем же символом.

6.20. Предположим, что уже построен и задан указателем P кольце­вой однонаправленный список с включенным заглавным звеном, эле­ментами которого являются целые числа. Написать программу, кото­рая находит минимальное значение элементов кольца и номер первого звена, содержащего элемент с этим значением.

6.21. Предположим, что уже построены два однонаправленных кольца с включенным заглавным звеном, элементами которых являются целые числа. Написать функцию, которая определяет, является ли содержимое данного кольца "перевертышем" содержимого другого кольца.

 

Стеки на базе однонаправленных списков

А люди все роптали и роптали,

А люди справедливости хотят:

Мы в очереди первые стояли,

А сзади нас, - уже едят.

В.Высоцкий

Перед решением задач данного раздела нужно повторить следующий теоретический материал:

1) информационная модель стека на базе линейного однонаправ­ленного списка;

2) построение стека;

3) включение звена в стек;

4) удаление звена из стека.

Задачи для самостоятельного решения

Вопрос о том, как мне надлежит начать рассказ, старался я решить двумя спосо­бами. Во-первых, я почесал в голове; это не привело ни к чему. Во-вторых, посове­товался с моей дочерью Пенелопой, кото­рая и подала мне совершенно новую мысль.

Уилки Коллинз. Лунный камень

При работе со стеками необходимо уметь составлять функции, ре­ализующие операции:

1) формирование стека;

2) помещение элемента в стек;

3) удаление элемента из стека.

Построение

9.1. Напишите функцию формирования стека, причем учтите, что стек может содержать не более K звеньев (переполнение стека) и не может быть пустой (опустошение стека).

9.2. Дан текстовый файл t. Напечатать его содержимое, выписы­вая литеры каждой его строки в обратном порядке.

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

9.4. Дан файл, элементами которого являются целые числа, упоря­доченные по возрастанию (убыванию). При помощи структуры данных стек провести "обратную" сортировку файла по убыванию (возраста­нию!).

9.5. Дан файл, элементами которого являются целые числа, упоря­доченные по убыванию. Написать программу, разбивающую файл f на два файла, элементы которых упорядочены по возрастанию так, чтобы каждый элемент 1-го файла (a1), был больше соответствующего эле­мента 2-го файла (b1), но меньше его следующего элемента (b2): b1<a1<b2.

9.6. Исполнитель "Стековый калькулятор" [31] имеет следующую систему предписаний:

· начать работу;

· добавить <вх: число> в стек;

· сложить/вычесть/умножить/разделить;

· показать результат;

· кончить работу.

Запись "добавить <вх: число> в стек" означает, что это предпи­сание имеет один входной объект (входной параметр), который явля­ется числом.

Исполнитель "Стековый калькулятор" имеет два глобальных объек­та: стек чисел (то есть стек, элементами которого являются числа) и табло, на котором по предписанию "показать результат" изображает­ся вершина стека (сам стек при этом не меняется).

После вызова предписания "начать работу" стек калькулятора пуст, а на табло ничего не изображено. Предписание "добавить <вх: число> в стек" добавляет указанное при вызове число в стек. Пред­писание "показать результат" изображает на табло вершину стека. После этого табло не меняется до следующего вызова предписания "показать результат". При выполнении арифметических операций (сложить, вычесть, умножить, разделить) стековый калькулятор дос­тает из стека последовательно сначала правый, а затем левый аргу­менты операции, выполняет операцию и полученный результат помеща­ет в стек.

При выполнении любой арифметической операции число элементов в стеке уменьшается на 1. Попытки выполнить операцию, когда в стеке меньше двух элементов, или показать результат, когда стек пуст, приводят к отказу.

Промоделировать работу исполнителя.

9.7. Исполнитель "Стек элементов типа E" [31] имеет следующую систему предписаний:

• начать работу;
• сделать стек пустым;
• стек пуст / стек не пуст (да/нет);
• добавить элемент <вх: E> в стек;
• взять элемент из стека в <вых: E>;
• вершина стека::E;
• удалить вершину стека;
• кончить работу.

Предписания "стек пуст" / "стек не пуст" вырабатывают в ка­честве ответа значение "да" или "нет".

Запись::E в предписании "вершина стека" означает, что это предписание в зависимости от использования либо принимает, либо вырабатывает значение типа E (то есть его можно использовать как в правой, так и в левой части предписания присваивания).

Промоделировать работу исполнителя.

9.8. Реализуйте стек стеков со следующими операциями [38]:

• Remvq - удаляет стек из стека стеков qq и присваивает его q;
• Insrtq - помещает стек q в стек стеков qq;
• Remvonq - удаляет элемент из первого стека в qq и присваивает его x;
• Insrtonq - помещает элемент x в первый стек qq.

9.9. Реализуйте следующие операции для стека очередей [38]:

• Remvq - удаляет стек из стека очередей qq и присваивает его q;
• Insrtq - помещает стек q в стек очередей qq;
• Remvonq - удаляет элемент из первого стека в qq и присваивает его x;
• Insrtonq - помещает элемент x в первый стек qq.

9.10. Реализуйте следующие операции для очереди стеков [38]:

• Remvq - удаляет стек из очереди стеков qq и присваивает его q;
• Insrtq - помещает стек q в очередь стеков qq;
• Remvonq - удаляет элемент из первого стека в qq и присваивает его x;
• Insrtonq - помещает элемент x в первый стек qq.

9.11. Операции над стеком s:

• функция push(s,i) помещает элемент i в стек s;
• функция pop(s) удаляет из стека s верхний элемент и возвра­щает его в качестве значения;
• функция stacktop(s) возвращает значение верхнего элемента стека s; например, i=stacktop(s) эквивалентно i=pop(s), push(s,i);
• функция empty(s) возвращает значение "истина", если стек s пуст.

Реализуйте стек [38].

9.12. Напишите подпрограммы pop, push, empty для стеков, содер­жащих символьные строки. Заметьте, что если в программе имеются два независимых стека - один для целых чисел и другой для сим­вольных строк, то в ней должны присутствовать две версии подпрог­рамм pop, push, empty [38].

9.13. Реализовать следующие операции [38]:

• popandtest(und,s), которая проверяет стек на потерю значимости и в случае ее отсутствия удаляет верхний элемент из стека s;

· pushandtest(overflow,s,i), которая проверяет стек на перепол­нение и в случае его отсутствия помещает элемент i в стек s.

Модификация

9.14. Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая добавляет в конец стека S элемент, находящийся в его вершине.

9.15. Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая добавляет в вершину стека S элемент, находящийся в его конце.

9.16. Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая удаляет из стека все элементы, кратные 4 (использовать для промежуточного хранения элементов стека однонаправленный список с заглавным звеном).

9.17. Записать элементы стека в другой стек в обратном порядке.

9.18. При помощи операций push, pop, stacktop и empty реализуйте следующие операции [38]:

· установить в i второй элемент стека, считая от его вершины, удалив из него два верхних элемента;

· установить в i второй элемент стека, считая от его вершины, оставив содержимое стека без изменения;

· для заданного n установить в i n-й элемент стека, считая от его вершины, и удалить из стека верхние n элементов;

· для заданного n установить в i n-й элемент стека, считая от его вершины, оставив содержимое стека без изменения;

· установить в i нижний элемент стека и удалить из него все элементы;

· установить в i нижний элемент стека, оставив содержимое стека без изменения;

Указание. Используйте вспомогательный стек.

· установить в i третий элемент стека, считая от его "дна".

9.19. Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая удаляет из стека все элементы, кратные 5 (использовать для промежуточного хранения элементов стека однонаправленный список без заглавного звена).

9.20. Напишите программу, вычисляющую выражение, записанное в постфиксной форме.

Предикаты

9.21. Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, проверяющую, является ли стек пустым.

9.22. Напишите алгоритм, определяющий, имеет ли вводимая символьная строка вид xCy, где:

· C - символ-разделитель,

· x - строка, состоящая из букв A и B,

· y - строка, обратная строке x (то есть если x=ABABBA, то y должен равняться ABBABA). При чтении можно считывать только каждый следующий символ строки [38].

9.23. Напишите алгоритм, определяющий, имеет ли вводимая символьная строка следующую форму:

a D b D c D... D z,

где каждая строка a, b, c,..., z имеет форму строки, определенной в задаче 9.22. Следовательно, строка имеет правильную форму, если она состоит из любого числа подобных строк, разделенных сим­волом "D". При чтении можно считывать только каждый следующий символ строки [38].

9.24. В строке, признаком конца которой является первая по порядку точка, могут содержаться круглые, квадратные и фигурные скобки как открывающие, так и закрывающие. Требуется проверить баланс скобок в строке.

Баланс скобок соблюдается, если выполнено каждое из следующих условий:

· для каждой открывающей скобки справа от нее есть соответс­твующая закрывающая скобка и наоборот;

· соответствующие пары скобок (открывающие и закрывающие) разных типов правильно вложены друг в друга.

9.25. Для заданной последовательности операций pop и push, а также целого числа, задающего размер массива, используемого под стек, создайте алгоритм, регистрирующий возникновение ситуации переполнения [38].

Подсчет

9.26. Сколько в стеке целых чисел, кратных 5, но не кратных 7?

9.27. Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая находит сумму элементов, находящихся в стеке.

9.28. Подсчитать количество отрицательных элементов в стеке.

9.29. Сколько в стеке простых чисел?

9.30. Найти сумму минимального и максимального из чисел, находящихся в стеке.

Разные задачи

9.31. Представим себе вычислительную машину, в которой имеются один регистр и шесть инструкций [38]:

· LD A - помещает операнд A в регистр;

· ST A - помещает содержимое регистра в переменную A;

· AD A - прибавляет содержимое переменной A к регистру;

· SB A - вычитает содержимое переменной A из регистра;

· ML A - умножает содержимое регистра на переменную A;

· DV A - делит содержимое регистра на переменную A.

Напишите программу, считывающую выражение в постфиксной форме, которое состоит из однобуквенных операндов и операций +, -, * и /. Она должна напечатать последовательность инструкций, необходи­мых для вычисления выражения, и оставить результат в регистре. Используйте переменные в виде Tn в качестве временных. Например, постфиксное выражение ABC*+DE-/ даст такую распечатку инструкций:

LD B ML C ST T1 LD A AD T1 ST T2

LD D SB E ST T3 LD T2 DV T3 ST T4

9.32. Предположим, что операторы FOR имеют следующий формат:

## FOR var=init TO final STEP step,

где ## - номер строки; var - идентификатор языка BASIC, а init, final и step - либо целые числа, либо идентификаторы языка BASIC. Предполагается, что значение step положительно. Напишите программу, которая считывает входные данные, состоящие из таких операторов FOR и операторов NEXT, и переводит их в операторы присваивания, операторы IF и операторы GOTO. Например, входной набор данных:

10 FOR I=1 TO N STEP 3 20 FOR J=N TO 500 STEP 1 30 NEXT J 40 NEXT I 50 FOR I=1 TO 5 STEP K 60 NEXT I   должен быть переведен в:

10 I=1 20 IF I>N THEN GOTO 90 30 J=N 40 IF J>500 THEN GOTO 70 50 J=J+1 60 GOTO 40 70 I=I+3 80 GOTO 20 90 I=1 100 IF I>5 THEN GOTO 130 110 I=I+K 120 GOTO 100 130 'Оставшаяся часть программы

Указание. Воспользуйтесь стеками для переменных, номеров строк и приращений [38].

9.33. Фирма XYZ по хранению и сбыту бытовых инструментов и приспособлений получает грузы с оборудованием по различным ценам. Фирма продает их затем с 20%-ной надбавкой, причем товары, полу­ченные позднее, продаются в первую очередь (поскольку товары, по­лучаемые позднее, стоят дороже - стратегия "последний полученный первым продается"). Напишите программу, считывающую записи о тор­говых операциях двух типов: операции по закупке и операции по продаже. Запись о продаже содержит префикс "S" и количество това­ра, а также стоимость данной партии. Запись о закупке содержит префикс "R", количество товара, стоимость одного изделия и общую стоимость всей партии. После считывания записи об операции прода­жи напечатайте ее и сообщение о цене, по которой были проданы из­делия. Например, если фирмой были проданы 200 единиц оборудова­ния, в которые входили 50 единиц с закупочной ценой 1.25$, 100 единиц с закупочной ценой 1.1$ и 50 единиц с закупочной ценой 1.00$, то напечатается (вспомните о 20%-ной надбавке):

ФИРМА XYZ ПРОДАЛА 200 ИЗДЕЛИЙ

50 ШТУК ПО 1.50 ДОЛЛАРОВ КАЖДЫЙ НА СУММУ: 75.00

100 ШТУК ПО 1.32 ДОЛЛАРОВ КАЖДЫЙ НА СУММУ: 132.00

50 ШТУК ПО 1.20 ДОЛЛАРОВ КАЖДЫЙ НА СУММУ: 60.00

ВСЕГО ПРОДАНО НА СУММУ: 267.00

Если на складе отсутствует требуемое в заказе число изделий, то продайте все имеющиеся, а затем напечатайте:

ОСТАЛЬНОЙ ЧАСТИ ИЗДЕЛИЙ XXX НЕТ НА СКЛАДЕ [38].

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

Напишите программу обработки группы входных строк. Каждая входная строка содержит символ "A" для прибывающей машины и "D" для отъезжающей, а также номер каждой автомашины. Предполагается, что машины прибывают и отъезжают в порядке, заданном входными строками. Программа должна напечатать сообщение при прибытии или отъезде любой машины. При прибытии машины сообщение должно инфор­мировать о том, имеется ли место на стоянке. Если места нет, то машина уезжает и на стоянку не принимается. При выезде машины со стоянки сообщение должно содержать число раз, которое машина уда­лялась со стоянки для обеспечения выезда других автомобилей [38].

9.35. Проанализируйте язык, в котором среди типов данных отсутс­твуют массивы, но имеются стеки, т.е. в этом языке разрешена за­пись:

DEFSTACK S.

Операции pop, push, empty определены как часть языка. Покажите, каким образом двухмерный массив может быть представлен в этом языке с помощью двух стеков [38].

9.36. Используя стек, "перевернуть" заданный целочисленный массив.

Сложные задачи

9.37. Напишите программу, преобразующую:

а) строку в префиксной форме в строку в постфиксной форме;

б) строку в постфиксной форме в строку в префиксной форме;

в) строку в префиксной форме в строку в инфиксной форме;

г) строку в постфиксной форме в строку в инфиксной форме;

д) строку в инфиксной форме в строку в постфиксной форме.

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

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

9.40. Напишите программу, считывающую строку в инфиксной форме и формирующую эквивалентную ей строку в инфиксной форме с удаленны­ми необязательными скобками. Можно ли это сделать без использова­ния стека?

9.41. Напишите программу, которая преобразует входную символьную строку, состоящую из операндов и операций постфиксного выражения, в инфиксную форму со скобками. Например, выражение AB+ должно быть преобразовано в (A+B), а AB+C- должно быть преоб­разовано в ((A+B)-C).

 

Двунаправленные списки

Фрагмент теории

Кто управляет прошлым, тот управляет будущим. Кто управляет настоящим, тот управляет прошлым.

Дж.Оруэлл. 1984

Здесь мы рассмотрим лишь двунаправленные списки с заглавным звеном, которые имеют следующую структуру:

 

Здесь nsp - указатель на заглавное звено двунаправленного списка, ksp - указатель на последнее звено двунаправленного списка.

Тип каждого звена списка можно описать так:

struct node

{ int elem;//Информационное поле.

node *sled; // Указатель на следующее звено.

node *pred; // Указатель на предыдущее звено.

};

Приступим к построению алгоритма формирования двунаправленного списка с заглавным звеном. Опишем необходимые переменные:

node *nsp; // Указатель на заглавное звено списка.

node *ksp; // Указатель на последнее звено списка.

node *rsp; // Рабочий указатель для перемещения по списку.

Построим заглавное звено:

 

 

Построен двунаправленный список с заглавным звеном, содержащий одно звено. Мы предоставляем возможность читателю проделать самостоятельно несколько последующих шагов алгоритма.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: