Контрольная работа №1 содержит два задания, которые имеют непосредственное отношение к повышению эффективности процесса поиска информации в таблицах. В задании №1 необходимо построить древовидные и хеш-таблицы для заданной последовательности ключей. В задании №2 рассматривается сортировка списков с использованием эффективных алгоритмов Шелла и Хоара. Трансляция выражений – одна из основных задач транслятора. Она рассматривается в задании №4. В настоящее время классическим является метод трансляции выражений, основанный на использовании польской инверсной записи (ПОЛИЗ). Этот метод хорошо иллюстрирует идею использования прямых методов трансляции в современных системах программирования. Суть этих методов – использование некоторой руководящей общей идеи, применение которой позволяет для каждой языковой конструкции разработать индивидуальный алгоритм трансляции. Задания с номерами 3 и 5 посвящены разработке программ на языках Java (C) для выполнения на ПЭВМ заданий 1,2,4.
4.1. Построить древовидную и ХЕШ-таблицы для заданной последовательности ключей. Размер ХЕШ-таблицы — N+6. (N - длина заданной последовательности ключей).ХЕШ-функция определяется как: (остаток целочисленного деления ключа на N)+1. Способ устранения коллизий выбрать в соответствии с вариантом задания:1 ‑ открытое перемешивание;2 ‑ перемешивание с цепочками переполнения. Варианты заданий представлены в табл.1.
4.2. Упорядочить элементы массива с использованием алгоритмов Хоара и Шелла.В качестве массива рассмотреть последовательность ключей в соответствии с вариантом задания в табл.1.
Таблица 4.1 Варианты заданий к задачам 4.1, 4.2.
| № варианта | Последовательность ключей | Способ устранения коллизий в ХЕШ-таблице |
| 1 | 2 | 3 |
| 0 | 13,3,17,4,5,2,1,8,9,6,12 | 1 |
| 1 | 12,4,16,5,7,13,2,14,11,9,8 | 1 |
| 2 | 11,5,15,1,3,2,9,8,7,6,5 | 1 |
| 3 | 10,6,14,13,12,11,9,1,2,4,3 | 1 |
| 4 | 9,7,13,10,8,4,3,2,1,14,15 | 1 |
| 5 | 8,9,12,13,14,2,1,5,4,3,6 | 2 |
| 6 | 7,8,11,1,16,15,14,13,12,5,4 | 2 |
| 7 | 6,10,13,17,21,1,3,5,11,9,7 | 2 |
| 8 | 5,11,12,10,9,8,7,6,4,3,2 | 2 |
| 9 | 4,12,11,1,2,7,8,6,5,22,3 | 2 |
4.3. Написать и отладить на ПЭВМ типа IBM PC программу на языке JAVA (СИ) для решения задачи построения таблицы или упорядочения элементов массива. Варианты заданий представлены в табл.2.
4.4. Построить ПОЛИЗ для заданного выражения. Варианты заданий представлены в табл.3.
4.5. Разработать и отладить программу построения ПОЛИЗ в соответствии с вариантом задания в табл.4.
Таблица 4.2 Варианты заданий к задаче 4.3
| № варианта | Наименование задачи | Тип таблицы – алгоритм сортировки | Язык програмирования |
| 1 | 2 | 3 | 4 |
| 0 | Построение таблицы | Древовидная | JAVA |
| 1 | Построение таблицы | Древовидная | СИ |
| 2 | Построение таблицы | ХЕШ-табл (откр. перемеш) | JAVA |
| 3 | Построение таблицы | ХЕШ-табл(откр. перемеш) | СИ |
| 4 | Упорядочение элементов | Алгоритм Шелла | JAVA |
| 5 | Упорядочение элементов | Алгоритм Шелла | СИ |
| 6 | Упорядочение элементов | Алгоритм Хоара | JAVA |
| 7 | Упорядочение элементов | Алгоритм Хоара | СИ |
| 8 | Построение таблицы | ХЕШ-табл (цеп. переп) | JAVA |
| 9 | Построение таблицы | ХЕШ-табл (цеп. переп) | СИ |
Таблица 4.3 Варианты заданий к задачам 4.4
| № варианта | Выражение |
| 0 | X[I,J]*SIN(A+(A-B[I])*EXP(C+D/B[I])) |
| 1 | A[I]*EXP(C+D)*(SQR(C*C+D*D)+C-A[I]^3) |
| 2 | B[I,K,R]+EXP(A[I]^2+B[I]^2+SQR(C-D)) |
| 3 | R*(1-R*K[I+2,J*J-3]+COS(X[I]+A[I]^2) |
| 4 | A+B[R,S]*(SIN(X[I]+A)^2+COS(X[I+A]^2) |
| 5 | R-A*(B-(C/(A-B))*COS(X[I,J]+X[I+1,J+1]) |
| 6 | SQR(A+B*(X[I*K+J*K]-1/SIN(A+Y[I,J]) |
| 7 | R*A*EXP(X[I]^2+X[I+1]^3+R*B[I,J,K]) |
| 8 | K*LOG(X[I,J]^2+Y^2)*X[I+1,J*J]*SIN(X) |
| 9 | B[I]-C*(A[I]+B[I]*X[I,J]*(COS(A[I]+B[I])) |
Таблица 4.4 Варианты заданий к задаче 4.5
| № варианта | Тип выражения | Наименование задачи | Язык программирования |
| 1 | 2 | 3 | 4 |
| 0 | Простое арифметическое JAVA | Построение ПОЛИЗ | JAVA |
| 1 | Простое арифметическое JAVA | Построение ПОЛИЗ | СИ |
| 2 | Простое логическое | Построение ПОЛИЗ | JAVA |
| 3 | Простое логическое | Построение ПОЛИЗ | СИ |
| 4 | Переменная с индексами | Построение ПОЛИЗ | JAVA |
| 5 | Переменная с индексами | Построение ПОЛИЗ | СИ |
| 6 | Указатель функции | Построение ПОЛИЗ | JAVA |
| 7 | Указатель функции | Построение ПОЛИЗ | СИ |
| 8 | Простое арифметическое СИ | Построение ПОЛИЗ | JAVA |
| 9 | Простое арифметическое СИ | Построение ПОЛИЗ | СИ |
2018-01-08
514
