Упражнения и задачи. 3.1. Дан вектор, содержащий очередь и значения указателей начала очереди UN = 7 и конца очереди UK = 3.
3.1. Дан вектор, содержащий очередь и значения указателей начала очереди UN = 7 и конца очереди UK = 3.
Перечислить значения элементов очереди в порядке их поступления.
3.2. Как изменятся значения вектора и указателей после включения числа 15 в очередь из упражнения 3.1?
3.3. Отображающий вектор очереди содержит числа: 6, 9, 1, 3, 7, 2, 8. Перечислить элементы очереди в порядке поступления. Указатель начала - индекс первого элемента, указатель конца - индекс позиции, следующей за последним элементом.
а) Указатель начала равен 3, указатель конца равен 1.
б) Указатель начала равен 2, указатель конца равен 5.
Определить значения элементов вектора и указателей после каждой операции: включения в очередь числа 4, последующего исключения элемента из очереди, последующего включения в очередь числа 5.
3.4. Очередь содержит в порядке поступления слова: бак, вид, гол, дом, пол, фен и представлена вектором из 8 элементов. Определить значения элементов отображающего вектора и указателей для двух вариантов: указатель начала меньше указателя конца и больше указателя конца.
3.5. Дана очередь, содержащая один элемент - букву 'Z', и представленная в виде вектора (списка). Составить трассировочную таблицу выполнения последовательности операций: удалить; включить 'X'; включить 'Y'; удалить; включить 'A'; включить 'B'; удалить; включить 'X'; включить 'Y'.
3.6. Разработать алгоритм вывода в порядке возрастания первых n натуральных чисел, разложение которых на простые множители не содержит других чисел, кроме 2, 3, 5.
3.7. Составить программу для задачи 3.6.
3.8. Отображающий вектор стека содержит числа: 3, 5, 8, 1, 7, 3, 2. Указатель стека равен 5. Перечислить элементы стека в порядке поступления, если указателем стека служит индекс
а) последней занятой позиции;
б) первой свободной позиции.
Определить значения элементов вектора и указателя
1) после выталкивания элемента из стека;
2) после вталкивания в стек числа 6.
3.9. Стек содержит, в порядке поступления, слова: тир, дом, сад, пол, шаг, вал и размещен с конца вектора из 10 элементов. Определить значения элементов отображающего вектора и указателя.
3.10. Дан стек с элементами 'K' и 'Z', представленный в виде
а) вектора;
б) списка.
Составить трассировочную таблицу выполнения следующей последовательности операций: включить 'R'; включить 'S'; удалить; включить 'T'; включить 'U'; удалить; удалить; включить 'S'; включить 'C'.
3.11. Составить описание данных и
а) фрагменты программы;
б) подпрограммы
выполнения типовых операций для стека в виде списка, содержащего до 100 слов длиной до 8 символов. Список организован с помощью
1) ссылочных данных;
2) параллельных массивов.
3.12. Дана последовательность открывающих и закрывающих скобок. Составить программу определения пар номеров соответствующих друг другу скобок.
Пример. Вход: (() (()))
1 2 3 4 5 6 7 8
Выход: 2-3 5-6 4-7 1-8
3.13. Дек. Деком называют структуру, сочетающую очередь и стек: добавлять и удалять элементы можно с обоих концов. Реализовать дек размером до 100 вещественных чисел в виде вектора
- составить описание данных и фрагменты программы выполнения операций.
3.14. Оценить необходимый объем памяти для структур данных из задач: 3.4, 3.5, 3.8, 3.9, 3.11. Недостающие детали представления уточнить самостоятельно.
3.15. Отображающий вектор очереди содержит числа: 7, 3, 2, 5, 8, 4. Перечислить элементы очереди в порядке поступления. Указатель начала - индекс первого элемента, указатель конца - индекс позиции непосредственно за последним элементом.
а) Указатель начала равен 4, указатель конца равен 2. б) Указатель начала равен 1, указатель конца равен 4.
Определить значения элементов вектора и указателей после каждой из следующих операций: исключения элемента из очереди, последующего включения в очередь числа 6, последующего включения в очередь числа 9.
3.16 Отображающий вектор стека содержит числа: 7, 3, 2, 5, 8, 4. Указатель стека равен 4. Перечислить элементы стека в порядке поступления, если указателем стека служит индекс последней занятой (первой свободной) позиции.
Определить значения элементов вектора и указателя
а) после выталкивания элемента из стека;
б) после вталкивания в стек числа 6.
3.17. Очередь (стек) содержит в порядке поступления слова: акт, бор, кол, рот и представлена вектором из 6 элементов. Определить значения элементов отображающего вектора и указателей.
3.18. Дан пустой стек (очередь), представленный в виде вектора (списка). Составить трассировочную таблицу выполнения следующих операций: включить 'A'; включить 'B'; включить 'C'; удалить; включить 'D'; удалить; удалить; включить 'A'; включить 'E'.
3.19. Описать данные для хранения стека (очереди) в виде списка. Составить программы операций включения и исключения элемента. Значением элемента является вещественное число.
3.20. Составить описание данных для представления строки длиной до 100 символов в виде
а) вектора фиксированной длины.
б) вектора переменной длины со счетчиком.
в) вектора переменной длины с признаком конца.
г) списка с односимвольными элементами.
д) двустороннего списка с односимвольными элементами.
е) списка с элементами фиксированной длины 8.
ж) списка с элементами переменной длины.
Необходимые детали представления уточнить самостоятельно.
3.21. Составить фрагменты программы (подпрограммы) ввода строки в виде последовательности символов, заканчивающейся переводом строки, и ее преобразования в представления а-г из задачи 3.20.
3.22. Составить функцию определения меры близости слов X и Y (расстояния между ними) по формуле:
D(X,Y) = (100-100*K/(DX-1))*(100-100*K/(DY-1)),
где DX, DY - длины слов, K - число пар соседних букв, входящих в оба слова одновременно.
Пример:
D("Саша", "Даша") = (100-100*2/(4-1))*(100-100*2/(4-1)) =
= 10000/9 = 1111.11
3.23. Решение задачи из примера 3.20 оформить в виде подпрограмм.
3.24. В каждом байте массива упакованы по 4 двухбитовых числа. Составить фрагмент программы (подпрограмму)
а) распаковки числа: получения значения числа по его номеру;
б) упаковки числа: присвоения данного значения числу с указанным номером.
3.25. Подсчитать объем памяти для доступа с помощью векторов Айлифа к элементам массива с Pascal-описанием
var S: array [1..2, -1..0, 0..2] of char;
3.26. Для массива с Pascal-описанием
1) S: array [1..2, -1..0, 0..2] of char;
2) var S: array [-4..1, 1..3, 0..4] of char;
а) определить количество элементов и объем памяти;
б) подсчитать объем памяти для дескриптора;
в) составить функцию зависимости адреса элемента от его индексов для доступа через дескриптор;
г) подсчитать объем памяти для векторов Айлифа;
д) изобразить структуру хранения с векторами Айлифа.
3.27. Для массивов с элементами
1) U[0,1,1], U[0,1,2], U[0,2,0], U[0,2,1], U[1,0,2], U[1,0,3], U[1,1,1], U[2,2,-1], U[2,2,0], U[2,3,1], U[2,3,2]
2) X[1,0,1], X[1,0,2], X[1,1,0], X[1,1,1], X[1,1,2], X[2,1,0], X[2,1,1], X[2,2,-1], X[2,2,0], X[2,3,2], X[2,3,3]
а) подсчитать объем памяти для векторов Айлифа;
б) изобразить структуру хранения с векторами Айлифа.
3.28. Составить фрагмент программы инициализации пустой очереди с приоритетами из примера 3.23.
3.29. Составить трассировочную таблицу поступления элементов в очередь с приоритетами из примера 3.23 в следующем порядке: 8, 5, 3, 7, 2 и последующего удаления двух элементов.
3.30. Для очереди с приоритетами из примера 3.23 составить фрагменты программ выполнения операций.
3.31. Оформить в виде подпрограмм выполнение операций для очереди с приоритетами из примера 3.23.
3.32. Для примера 3.24 написать фрагмент программы
а) определения множества рабочих дней с дежурствами;
б) проверки, есть ли совпадения дней дежурства с занятиями.
3.33. Составить фрагменты программы (подпрограммы) решений 1, 2 и 4 примера 3.25.
3.34. Даны множества S1 и S2 в виде характеристических векторов: S1 = 10011001, S2 = 01110101. Определить количество элементов в S1 и в S2.
Получить характеристический вектор множества S, равного объединению множеств S1 и S2, из которого вычтено пересечение этих множеств. Записать эти операции в виде фрагмента программы.
3.35. Составить фрагмент программы подсчета количества элементов множества, представленного характеристическим вектором длиной 16 бит.
3.36. Задача W. Взвешивание (Д.Г. Хохлов, турнир ICL-2005 [81]) Из монет c номерами от 1 до N одна фальшивая (легче или тяжелее настоящей), остальные настоящие одного веса. Произведено K взвешиваний. Для каждого взвешивания даны номера равного числа монет на левой и правой чаше весов и результаты в виде знака =, < или >, например 5 4 2 > 1 9 7 (монеты 5, 4, 2 в сумме тяжелее монет 1, 9, 7). Вывести номер фальшивой монеты (или "?", если это невозможно). Сообщить также знаком неравенства, легче "<" фальшивая монета или тяжелее ">" настоящей (или вывести "?", если это невозможно).
Входной файл INPUT.TXT
N K
<номера монет левой чаши> <знак> <номера монет правой чаши>
...
Числа отделены друг от друга и знака пробелами и/или символами новой строки (0 < N < 100000, 0 £ K £ 100).
Выходной файл OUTPUT.TXT
номер знак (через пробел, или "?" вместо номера и/или знака)
Примеры INPUT.TXT OUTPUT.TXT
5 1??
1 = 5
5 1 3?
1 5 = 2 4
5 2 3 <
3 < 5
5 = 1
Дата добавления: 2015-09-27 | Просмотры: 661 | Нарушение авторских прав
|