Производная алгоритмическая структура "Поиск по ключу"

1. Производная алгоритмическая структура «ПОИСК ПО КЛЮЧУ»

Условие поиска задается следующим
логическим выражением:
<Элемент
массива>
<Операция сравнения>
ПГУПС, каф. ИнИБ
<Ключ
поиска>
1

2. Особенности алгоритма

1. Ключу поиска присваивается
конкретное значение
2. Организуется циклический процесс,
телом которого служит структура
«Развилка» с одной ветвью.
Логическое выражение определяет
условие поиска элементов
ПГУПС, каф. ИнИБ
2

3.

3. Если логическое выражение истинно,
то это значит, что элемент
удовлетворяет условию поиска.
Значения его индексов запоминаются
и, при необходимости, выводятся на
печать.
Если логическое выражение ложно –
осуществляется проверка следующего
элемента.
ПГУПС, каф. ИнИБ
3

4.

4. В алгоритме необходимо
предусмотреть случай, когда поиск не
дал результатов (здесь возможна
такая ситуация в отличие от поиска
max и min)
Для этого вводится понятие
«Флажок»
ПГУПС, каф. ИнИБ
4

5.

«Флажок» - это, как правило,
переменная логического типа
(Boolean), которой изначально
присваивается значение «False»
(Ложь).
В процессе поиска, как только будет
найден первый элемент,
удовлетворяющий условию поиска,
«Флажок» сразу изменяет свое
значение на «True» (Истина)
ПГУПС, каф. ИнИБ
5

6.

5. После окончания процесса поиска
анализируется значение переменной
«Флажок».
Если она изменила свое значение,
значит найден хотя бы один элемент,
удовлетворяющий условию поиска.
Если «Флажок» не изменил своего
значения – таких элементов не
найдено.
ПГУПС, каф. ИнИБ
6

7. Пример 1 (Поиск по ключу)

ПГУПС, каф. ИнИБ
7

8. 1. Постановка задачи

Дан вектор В размерности X. Напечатать
индексы элементов, значения которых
находятся в интервале [0;10]
Входные данные:
{В}-массив вещественных чисел
X-размерность массива, целое число
N-начало интервала, вещественное число
K-конец интервала, вещественное число
Выходные данные:
i- индексы искомых элементов, целые числа
ПГУПС, каф. ИнИБ
8

9. 2. Математическая модель

flag=ложь
Если Bi [N,K], то
flag=истина
печать i
i=1,2..X
Если по окончании поиска
flag=ложь, вывести сообщение
«Таких элементов не найдено»
ПГУПС, каф. ИнИБ
9

10. 3. Схема алгоритма

Начало
3. Схема алгоритма
X,{B},N,K
{B}
flag=false
i=1
i<=x
Да
Нет
N<=Bi<=K
Да
flag=true
i
Нет
i=i+1
flag=false
Да
Таких эл-тов
не найдено
Конец
ПГУПС, каф. ИнИБ
10

11. 4. Код приложения

Private Sub CommandButton1_Click()
Dim x As Integer, i As Integer, B() As Single
Dim N As Single, K As Single, flag as boolean
x = InputBox(«Введите размерность вектора")
ReDim B(x)
For i = 1 To x
B(i) = InputBox(“B(" & i & ")=")
Debug.Print B(i);
Next
N = InputBox ("Введите начало интервала")
K = InputBox ("Введите конец интервала ")
ПГУПС, каф. ИнИБ
11

12.

flag = False
Debug.Print
Debug.Print «Индексы эл., входящих в заданный интервал:"
For i = 1 To x
If B(i) >= N And B(i) <= K Then
flag = True
Debug.Print “ I =“& i
End If
Next
If flag = False Then
Debug.Print «Таких элементов не найдено"
End If
End Sub
ПГУПС, каф. ИнИБ
12

13.

Результат решения
ПГУПС, каф. ИнИБ
13

14. Пример 2 (Поиск по ключу)

ПГУПС, каф. ИнИБ
14

15. 1. Постановка задачи

Найти индекс последнего
положительного элемента вектора Х
размерности n
Входные данные:
{Х}-массив вещественных чисел
n - размерность массива, целое число
Выходные данные:
ind - индекс последнего положительного
элемента, целое число
ПГУПС, каф. ИнИБ
15

16. 2. Математическая модель

flag=ложь
Если Xi>0 то
flag=истина
ind= i
i=1,2..n
Если по окончании поиска
flag=ложь, вывести сообщение
«Положительных элементов нет»
ПГУПС, каф. ИнИБ
16

17. 3. Схема алгоритма

Начало
3. Схема алгоритма
n,{X}
{X}
flag=false
i=1
i<=n
i=i+1
Да
Да
xi >0
Да
flag=true
Ind=i
Нет
flag=false
ind
Положительных
элементов нет
Конец
ПГУПС, каф. ИнИБ
17

18. 4. Код приложения

Private Sub CommandButton1_Click()
Dim n As Integer, i As Integer, ind As Integer
Dim X() As Single, flag As Boolean
n = InputBox("Введите размерность вектора")
ReDim X(n)
For i = 1 To n
X(i) = InputBox("x(" & i & ")=")
Debug.Print X(i);
Next
flag = False
Debug.Print
ПГУПС, каф. ИнИБ
18

19.

For i = 1 To n
If X(i) > 0 Then
flag = True
ind = i
End If
Next
If flag = False Then
Debug. Print "Положительных элементов нет "
Else
Debug.Print «Индекс последнего
положительного элемента " & ind
End If
End Sub
ПГУПС, каф. ИнИБ
19

20. 5. Отладка программы

ПГУПС, каф. ИнИБ
20

21. Пример №2 можно реализовать другим способом!

Начало
Пример №2 можно
реализовать
другим способом!
n,{X}
{X}
flag=false
i=n
i > =1
Да
Нет
flag=false
xi >0
Нет
i=i-1
Да
i
Да
Положительных
элементов нет
flag=true
Конец
ПГУПС, каф. ИнИБ
21

22.

Private Sub CommandButton1_Click()
Dim n As Integer, i As Integer
Dim X() As Single, flag As Boolean
n = InputBox(" Введите размерность вектора")
ReDim X(n)
For i = 1 To n
X(i) = InputBox("x(" & i & ")=")
Debug.Print X(i);
Next
ПГУПС, каф. ИнИБ
22

23.

flag = False
Debug.Print
For i = n To 1 Step -1
If X(i) > 0 Then
Debug.Print "Индекс последнего положительного элемента" & i
flag = True
Exit For
End If
Next
If flag = False Then
Debug.Print “Положительных элементов нет"
End If
End Sub
ПГУПС, каф. ИнИБ
23

24.

5. Отладка программы
ПГУПС, каф. ИнИБ
24

25. Пример 3 (Поиск по ключу)

ПГУПС, каф. ИнИБ
25

26. 1. Постановка задачи

Дана матрица А размерности m x m.
Напечатать индекс строки, в которой на главной
диагонали лежит нулевой элемент. При наличии
нескольких таких строк напечатать индекс первой
из них
Входные данные:
А-массив вещественных чисел
m - размерность массива, целое число
Выходные данные:
i - индекс строки, целое число
ПГУПС, каф. ИнИБ
26

27. 2. Математическая модель

Flag=ложь
Если aii=0 flag=истина, напечатать i
и закончить процесс поиска
i=1,2…m
Если по окончании поиска
flag=ложь, вывести сообщение
«На главной диагонали нулевых элементов
нет»
ПГУПС, каф. ИнИБ
27

28. 3. Схема алгоритма

Начало
3. Схема алгоритма
m,{A}
{A}
flag=false
i=1
Да
i <=m
Нет
flag=false
Нет
aii =0
i=i+1
Да
i
Да
Нулевых эл-тов
на гл. диаг-ли нет
flag=true
Конец
ПГУПС, каф. ИнИБ
28

29. 4. Код приложения

Private Sub CommandButton1_Click()
Dim m As Integer, i As Integer, j As Integer
Dim A() As Single, flag As Boolean
m = InputBox("Введите размерность матрицы")
ReDim A(1 to m, 1 to m)
For i = 1 To m
For j = 1 To m
A(i, j) = InputBox("a(" & i & "," & j & ")=")
Debug.Print A(i, j);
Next
Debug.Print
Next
flag = False
Debug.Print
ПГУПС, каф. ИнИБ
29

30.

For i = 1 To m
If A(i, i) = 0 Then
Debug.Print "Индекс первой из строк с нулевым "
Debug.Print "элементом на главной диагонали " & i
flag = True
Exit For
End If
Next
If flag = False Then
Debug.Print "Нулевых элементов на главной диагонали нет”
End If
End Sub
ПГУПС, каф. ИнИБ
30

31.

5. Отладка программы
ПГУПС, каф. ИнИБ
31