VB_VBA

70	Програмування мовою Visual Basic/VBA

Приклад 4.13. Дано натуральне число n і послідовність цілих чисел а1, а2,..., аn. Визначити, скільки разів трапляється у цій послідовності найменше число. Замінити цим найменшим числом відповідну кількість елементів від початку масиву.

Option Explicit

Dim a() As Integer

Public Sub main()

Dim min As Integer

Dim nmin As Byte, i As Byte, n As Byte

'Введення n - див. приклад 4.10!

ReDim a(n)

'Введення послідовності чисел - див. приклад 4.10! min = a(1) : nmin = 1

For i=2 To n

If a(i) < min Then

min = a(i) : nmin = 1

ElseIf a(i)=min Then

nmin = nmin + 1

End If Next i

For i=1 To nmin a(i) = min

Next i

' Виведення масиву а – див. приклад 4.10!

End Sub

На перший погляд здається, що для визначення кількості однакових найменших значень необхідно організувати два цикли:

•перший – для визначення найменшого значення (мінімуму);

•другий – для визначення кількості повторень цього мінімуму. Однак, скориставшись спеціальним прийомом скидання на-

копиченого значення, можна обійтися одним циклом. Якщо умова a(i) < min справджується, то знайдено нове найменше число і відлік кількості повторень найменшого числа необхідно починати з одиниці (скидання накопиченого значення кількості повторень).

4. Структуровані типи даних

71

Якщо ж умова a(i) < min не справджується, то з двох можливих значень (a(i) = min чи a(i) > min) нас цікавить одне: a(i) = min – означає, що знайдено елемент, який збігається з поточним найменшим числом (збільшуємо лічильник кількості повторень).

Скидання накопиченого значення – досить поширений при-

йом, який використовують при розв’язуванні багатьох задач. Скористаємося ним і при розв’язанні наступного прикладу.

Приклад 4.14. Дано натуральне число n і послідовність цілих чисел а1, а2,..., аn. Визначити найбільшу кількість однакових чисел, розташованих поруч.

Option Explicit Dim a() As Integer Public Sub main()

Dim i As Byte, n As Byte, q As Byte, k As Byte

'Введення n - див. приклад 4.10!

ReDim a(n)

'Введення послідовності чисел - див. приклад 4.10!

'Послідовність одинакових чисел назвемо серією

k=1 ' Кількість елементів поточної серії q=1 ' Шукана величина

For i=2 To n

If a(i)=a(i-1) Then

k=k+1 ' Продовження/початок серії Else ' Кінець серії

If q<k Then q=k ' Формування max k=1 ' Нова ініціалізація

End If

Next i

If q<k Then q = k ' Врахування останньої серії

MsgBox "Максимум повторів= " & Str(q)

End Sub

Приклад 4.15. Дано натуральне число n і послідовність цілих чисел а1, а2,..., аn. Визначити, чи є у послідовності розташовані поруч два однакових числа, що дорівнюють 12.

72	Програмування мовою Visual Basic/VBA

Option Explicit

Dim a() As Integer

Public Sub main()

Dim n As Byte, i As Byte

Dim f As Boolean

'Введення n - див. приклад 4.10!

ReDim a(n)

'Введення послідовності чисел - див. приклад 4.10! i = 0 : f = False

Do

i = i + 1

If a(i) = 12 Then i = i + 1: f = a(i) = 12

Loop Until f Or i >= n - 1

If f Then MsgBox "Так " Else MsgBox "Ні "

End Sub

Приклад 4.16. Включення нового елемента у задану позицію k. При включенні нового елемента (рис. 4.1) необхідно попередньо розсунути масив, тобто пересунути підмасив аk,..., аn вправо на одну позицію. Переміщення підмасиву необхідно виконувати з кінця і перевіряти, чи достатньо пам’яті виділено під масив.

6	9	5	1	12	18	24
6	9	5	1	1000	12	18	24

Рис. 4.1. Включення елемента (1000) у п’яту позицію

Option Explicit Const nmax = 20

Public Sub main()

Dim a(1 To nmax) As Single, x As Single Dim n As Byte, k As Byte, i As Integer

Do

n = InputBox("Введіть n <" & nmax)

Loop Until n < nmax And n >= 1 For i = 1 To n

a(i) = InputBox("Введіть" & i & "число")

Next i

4. Структуровані типи даних

73

Debug.Print "Початковий масив: ";

For i = 1 To n

Debug.Print a(i); " ";

Next i Debug.Print " "

x = InputBox("Введіть нове число!", "Введення")

Do

k = InputBox("Введіть позицію <=" & n, "Введення")

Loop Until k <= n And k >= 1 For i = n To k Step -1

a(i + 1) = a(i)

Next i

a(k) = x : n = n + 1 Debug.Print "Кінцевий масив: ";

For i = 1 To n

Debug.Print a(i); " ";

Next i Debug.Print " "

End Sub

При видаленні k-го елемента з масиву необхідно зсунути підмасив аk+1,..., аn вліво на одну позицію. Відповідний фрагмент програми виглядає так:

…

n = n - 1 for i=k to n

a(i) = a(i+1)

Next i

…

Циклічне зсування масиву відзначається тим, що розмір масиву не змінюється. Циклічне зсування масиву вправо на одну позицію зображено на рис. 4.2. При зсуванні вправо напрям перегляду масиву і команди присвоювання у циклі такі ж самі, як і при

74 Програмування мовою Visual Basic/VBA

включенні елемента у масив, а при зсуванні вліво – такі ж самі, як і при видаленні елемента з масиву.

6	9	5	1	12	18	24
24	6	9	5	1	12	18

Рис. 4.2. Циклічне зсування масиву вправо на одну позицію

Фрагмент програми циклічного зсування масиву вправо на k позицій виглядатиме так:

…

for j=1 to k

x = a(n) ' x – проміжна величина for i=n to 2 Step -1

a(i) = a(i-1)

Next i a(1) = x

Next j

…

Приклад 4.17. Дано натуральне число n і послідовність дійсних чисел а1, а2,..., аn. Переставити члени послідовності так, щоб спочатку розмістилися всі її невід’ємні члени, а потім – всі від’ємні. Порядок розміщення як серед невід’ємних членів, так і серед від’ємних має зберегтися.

Option Explicit Dim a() As Single Public Sub main() Dim x As Single

Dim n As Byte, i As Byte, j As Byte, k As Byte

'Введення n - див. приклад 4.10!

ReDim a(n)

'Введення послідовності чисел - див. приклад 4.10! i = 1 ' початковий індекс невід'ємного члена

For k = 1 To n

If a(i) < 0 Then

x= a(i) ' збереження від'ємного члена ' зсування масиву вліво на 1 позицію

4. Структуровані типи даних

75

For j = i To n - 1 a(j) = a(j + 1)

Next j

a(n) = x ' від'ємний член у кінець масиву

Else

i = i + 1

End If Next k

Debug.Print "Кінцевий масив: ";

For i = 1 To n

Debug.Print a(i); " ";

Next i Debug.Print " "

End Sub

Якщо a(i)<0, то ми розміщуємо його наприкінці масиву, попередньо зсунувши підмасив від a(i+1) до a(n) на одну позицію вліво. Перший від’ємний член спочатку займе останнє місце, а в подальшому при виявленні нового від’ємного члена зсуватиметься на одну позицію вліво.

Приклад 4.18. Дано натуральне число n і послідовність дійсних різних чисел а1, а2,..., аn. Вибрати випадково k (1 ≤ k ≤ n) чисел так,

щоб жодне з них не повторилося.

Option Explicit Dim a() As Single Public Sub main() Dim x As Single

Dim n As Byte, i As Byte, j As Byte, k As Byte

'Введення n - див. приклад 4.10!

ReDim a(n)

'Введення послідовності чисел - див. приклад 4.10!

Do : k=InputBox("Введіть кількість обраних чисел <= " & n)

Loop Until k <= n And k >= 1 For i = 1 To k

j = i + Rnd * (n - i + 1) ' випадковий індекс x = a(j): a(j) = a(i): a(i) = x ' обмін

Next i

76	Програмування мовою Visual Basic/VBA

Debug.Print "Обрані числа: ";

For i = 1 To k

Debug.Print a(i); " ";

Next i

Debug.Print " "

End Sub

Вибираємо випадковий індекс j з проміжку [1; n] і відповід-

ний йому елемент a(j) міняємо місцями з першим елементом масиву. Наступного разу індекс j обирається з проміжку [2; n] і еле-

мент a(j) міняється місцями з другим елементом масиву і т.д. Вибрані елементи розташовуються на початку масиву і не беруть участі у наступних вибірках (вибірка без повторень).

Приклад 4.19. Дано натуральні числа n, m і два масиви дійсних чисел а1, а2,..., аn і b1, b2,..., bm, впорядковані за неспаданням. Утворити з елементів цих масивів впорядкований за неспаданням масив с.

Option Explicit Dim a() As Single Dim b() As Single Dim c() As Single Public Sub main()

Dim n As Byte, i As Byte, j As Byte, k As Byte, m As Byte Do : n = InputBox("Введіть n <=20")

Loop Until n < 21 And n >= 1 ReDim a(n)

'Введення першого масиву чисел - див. приклад 4.10!

Do : m = InputBox("Введіть m <=20")

Loop Until m < 21 And m >= 1 ReDim b(m)

'Введення другого масиву чисел - див. приклад 4.10!

ReDim с(n + m)

i = 1: j = 1

Do While i <= n And j <= m

If a(i) <= b(j) Then

c(i + j - 1) = a(i): i = i + 1 Else : c(i + j - 1) = b(j): j = j + 1

End If Loop

4. Структуровані типи даних

77

While i <= n : c(m + i) = a(i): i = i + 1 : Wend While j <= m : c(n + j) = b(j): j = j + 1 : Wend Debug.Print " "

Debug.Print "Масив після злиття: ";

For i = 1 To n + m Debug.Print c(i); " ";

Next i Debug.Print " "

End Sub

4.3. Алгоритми пошуку в одновимірному масиві

Алгоритми пошуку застосовуються для визначення у масиві індексу елемента з потрібними властивостями. Розрізняють постановки задачі пошуку для першого та останнього входження елемента. В усіх нижче викладених алгоритмах вважатимемо, що проводиться пошук у масиві а з n цілих чисел індексу елемента, який дорівнює x.

Розрізняють також пошук у впорядкованому та невпорядкованому масивах. У невпорядкованому масиві пошук виконують за допомогою послідовного перегляду всього масиву, це називають

лінійним пошуком.

Лінійний пошук здійснюється у циклі з умовою While або Until з подвійною умовою. Перша умова контролює індекс на приналежність масиву (i<=n). Друга умова – це умова пошуку: у циклі з While – умова продовження пошуку (а(i)<>x), а у циклі з Until – умова завершення пошуку (а(i)=x). У тілі ж циклу є тільки один оператор, який змінює індекс масиву. Після виходу з циклу необхідно перевірити, за якою з умов ми вийшли. В операторі If зазвичай повторюють першу умову циклу.

Приклад 4.20. Лінійний пошук в одновимірному масиві першого входження елемента, який дорівнює x.

Option Explicit

Dim a() As Integer

Public Sub main()

Dim x As Integer

Dim n As Byte, i As Byte

78	Програмування мовою Visual Basic/VBA

' Введення n - див. приклад 4.10!

ReDim a(n)

' Введення послідовності чисел - див. приклад 4.10! x = InputBox("Введіть число", "Введення")

i=1

While i<=n and а(i)<>x i = i + 1

Wend

If i<=n Then

MsgBox "1-e входження " & Str(x) & " у" & Str(i) & " місці"

Else

MsgBox " Не знайдено!"

End If

End Sub

Приклад 4.21. Лінійний пошук в одновимірному масиві останнього входження елемента, який дорівнює x. Подаємо основний фрагмент програми.

...

i=n+1

Do

i = i - 1

Loop Until i<1 Or а(i)=x If i>=1 Then

MsgBox "Останнє входж. " & Str(x) & " у" & Str(i) & " місці"

Else

MsgBox " Не знайдено!"

End If

Існує так званий пошук з бар’єром. Ідея пошуку з бар’єром полягає в тому, щоб не перевіряти кожен раз у циклі умову, зв’я- зану з межами масиву. Це можна забезпечити, встановивши у масиві так званий бар’єр: будь-який елемент, який задовольняє умові пошуку. Тим самим буде обмежена зміна індексу. Існує два способи встановлення бар’єра: додатковим елементом або замість крайнього елемента масиву.

Вихід з циклу, в якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар’єрі.

4. Структуровані типи даних

79

Отже, після виходу з циклу перевіряється, чи не бар’єр ми знайшли? Обчислювальна складність пошуку з бар’єром є меншою, ніж у лінійного пошуку, однак є величиною того ж порядку, що і n – кількість елементів масиву.

Приклад 4.22. Лінійний пошук з бар’єром в одновимірному масиві першого входження елемента, який дорівнює x.

Option Explicit

Dim a() As Integer

Public Sub main()

Dim x As Integer

Dim n As Byte, i As Byte

'Введення n - див. приклад 4.10!

ReDim a(n+1)

'Введення послідовності n чисел - див. приклад 4.10! x = InputBox("Введіть шукане число!")

a(n + 1) = x: i = 1 While a(i) <> x

i = i + 1

Wend

If i <= n Then

MsgBox "1-e входження " & Str(x) & " у " & Str(i) & " місці"

Else

MsgBox " Не знайдено!"

End If

End Sub

Подаємо також головний фрагмент програми, якщо бар’єр є на останньому місці масиву.

…

у = а(n) ' збереження останнього елемента

a(n) = x ' установка бар'єра на останнє місце масиву i = 1

While a(i) <> x i = i + 1

Wend