ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

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

2. Напишите программу, осуществляющую линейный поиск с "барьером" наибольшего индекса элемента с заданным значением в массиве, элементы которого заданы "случайным" образом.

3. Модой массива называется число M, которое встречается в массиве наиболее часто. Если в массиве имеется несколько наиболее часто встречающихся элементов и число их вхождений совпадает, то считается, что массив не имеет моды. Напишите программу, которая либо вычисляет моду массива, либо устанавливает, что последний её не имеет.

4. (*) Дано N целых чисел. Упорядочить их по неубыванию методом фон Неймана: завести два массива A и B и записать исходные числа в A; упорядочить пары соседних чисел (А₁ и А₂, A₃ и A₄ и т.д.) и записать их в B; взять из B по две соседние упорядоченные пары и, слив их в упорядоченные четверки, снова записать в A; затем каждые две соседние четверки из B слить в упорядоченные восьмерки и перенести в A; и т.д.

5. (*) (По [Окулов,2002,с.270]) Напишите программу, осуществляющую поиск k-го элемента в неупорядоченном массиве следующим образом, называемым случайным поиском. Выбирается случайным образом элемент с номером q. Массив X разбивается на три части: элементы, меньшие X[q], равные X[q] и большие X[q]. А затем, в зависимости от количества элементов в каждой части, рекурсивно выбирается одна из частей для дальнейшего поиска.

6. (*) [Шень,1995] Ещё один практически важный алгоритм сортировки таков: чтобы отсортировать массив, выберем случайный его элемент b, и разобьем массив на три части: меньшие b, равные b и большие b. Теперь осталось отсортировать первую и третью части: это делается тем же способом. Время работы этого алгоритма - случайная величина; можно доказать, что в среднем он работает не больше C*n*log n (на практике - он один из самых быстрых). Приведите его рекурсивную и нерекурсивную реализации.

7. В одномерном числовом массиве найдите максимальный элемент.

8. Дан одномерный массив целых чисел. Проверьте, является ли он упорядоченным по убыванию (возрастанию).

9. (*) Найдите количество различных чисел среди элементов данного массива. Число действий порядка n*log n.

Указание: Отсортируйте массив, а затем посчитайте количество различных элементов, просматривая элементы массива по порядку.

10. (*) [Шень,1995] Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. Соседним отрезкам ломаной разрешается лежать на одной прямой. Число действий порядка n*log n.

Указание: Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

ЛАБОРАТОРНАЯ РАБОТА 8.
СТРОКОВЫЙ ТИП ДАННЫХ В ПРОГРАММАХ НА VBSCRIPT

8.1 ЦЕЛЬ РАБОТЫ

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