АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Упражнения и задачи. 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 | Просмотры: 620 | Нарушение авторских прав