Теперь нужно в явном виде записать последние три строки. Для этого необходимо сравнить t и х[т], после чего выполнить определенное действие для сохранения инварианта. Действие это будет выполняться по следующей схеме:
case
x[m] < t action a x[m] == t action b x[m] > t action с
Действие b, очевидно, будет состоять в присваивании р=т и выходе из цикла, поскольку выполнение условия означает, что мы нашли элемент, равный t. Оставшиеся два случая симметричны, мы займемся первым, а второй получим из него по соображениям симметрии (это одна из причин, по которым мы будем очень аккуратны при проверке кода в следующем разделе).
Если x[m]<t, мы понимаем, что x[0]<=x[l]<=...<=x[m]<t, поэтому t не может принадлежать диапазону х[0..т]. Поскольку мы знаем также, что t не может не принадлежать x[L.u], мы понимаем, что если t где-нибудь есть, то оно принадлежит диапазону x[m+l..u], что мы запишем в форме mustbe(m+l, и). Поэтому мы восстановим инвариант mustbe(l, и) путем присваивания 1= т+1. Уточнив, таким образом, предыдущий набросок, получим листинг 4.3.
Листинг 4.3. Двоичный поиск на псевдокоде: версия 3
1 = 0. u = п - 1
1 оор
{ mustbe(l.u) }
i f 1 > u
p = -1, break m = (1 + u) / 2 case
x[m] < t. 1 = m + 1 x[m] == t p = m. break x[m] > t. u = m - 1
Программа получилась короткой: десяток строк кода и один инвариант. Простейший способ проверки программы — запись инварианта и сохранение его неизменным в процессе написания программы — оказался очень полезным при переписывании наброска алгоритма па псевдокоде. Этот процесс дал нам некоторую уверенность в программе, по мы ни в коем случае не можем считать ее правильной. Прежде чем читать дальше, потратьте несколько минут, чтобы проверить, правильно ли она работает.
Опубликовал vovan666
April 16 2013 23:58:00 ·
0 Комментариев ·
3474 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.