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

Пример 10

Пример 9

' Имя файла Find_4.vbs

' Бинарный поиск индекса заданного элемента одномерного "случайного"

' числового массива, строго упорядоченного по возрастанию (рекурсивный вариант).

Option Explicit

Dim i, s, key

Const n=8

Dim B (8)

'-------------------------------------------------------------------------------------

Function Bin_Search (B, low, high, x)

Dim mid

If low>high Then

Bin_Search=0

Else

mid=(low+high)\2

If x=B(mid) Then

Bin_Search=mid

Else

If x<B(mid) Then

Bin_Search=Bin_Search (B, low, mid-1, x)

Else

Bin_Search=Bin_Search (B, mid+1, high, x)

End If

End If

End If

End Function

'-------------------------------------------------------------------------------------

' Ввод одномерного массива, отсортированного строго по возрастанию

For i=0 to n

B(i)=CDbl(InputBox("Введите "&i&"-й элемент одномерного массива",_

"Ввод строго возрастающего вектора B:", i))

s=s&B(i)&" "

Next

s=s&vbCrLf

key=CDbl(InputBox("Введите искомый элемент: ","Окно ввода:", 5))

If Bin_Search (B, 1, n, key)=0 Then

MsgBox "Массив: "&s&vbCrLf&_

"Элемент "&key&" не найден в массиве!"

Else MsgBox "Массив: "&s&vbCrLf&_

"Элемент "&key&" найден в массиве!"&vbCrLf&_

"Его индекс в массиве: "&Bin_Search (B, 1, n, key)

End If

' Имя файла Mediana.vbs

' Поиск медианы в массиве.

' Реализация алгоритма Ч. Хоара.

' Медианой массива, содержащего N элементов, называется элемент, значение которого 'меньше (или равно) половины N элементов и больше (или равно) другой половины.

'Например, медианой массива 16 22 99 95 18 87 10 является 18. Задачу поиска медианы 'можно связать с сортировкой следующим образом: вначале произвести сортировку массива, 'а затем выбрать “средний элемент”. Но приведённая ниже программа позволяет найти 'медиану значительно быстрее.

Option Explicit

Dim i, s, k

Const n=8

Dim B (8)

'-------------------------------------------------------------------------------------

Sub Find (k)

Dim l, r, i, j, w, x

l=1: r=n

While l<r

x=B(k): i=l: j=r

Do

While B(i)<x

i=i+1

Wend

While x<B(j)

j=j-1

Wend

If i<=j Then

w=B(i): B(i)=B(j): B(j)=w: i=i+1: j=j-1

End If

Loop Until i>j

If j<k Then

l=i

End If

If k<i Then

r=j

End If

Wend

End Sub

'-------------------------------------------------------------------------------------

' Заполнение одномерного массива случайными числами

For i=0 to n

Randomize

B(i)=Fix(Rnd(1)*20)

s=s&B(i)&" "

Next

s=s&vbCrLf

k=n\2

Find (k)

MsgBox "Массив: "&s&vbCrLf&_

"Медиана данного массива: "&B(k),_

vbInformation,_

"Результат: "

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.

Дата добавления: 2014-12-29