Similar presentations:
Производная алгоритмическая структура "Поиск по ключу"
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 = FalseDebug.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 nIf 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 = FalseDebug.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 mIf 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