Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Трудности циклов

⇐ ПредыдущаяСтр 202 из 335Следующая ⇒

 

Возможность повторять некоторые вычисления произвольное число раз, не поддаваясь усталости, без случайных потерь чего-либо важного, - в этом принципиальное отличие компьютерных вычислений от возможностей человека. Вот почему циклы так важны. Трудно вообразить, что можно было бы делать в языках, в которых были бы только две управляющие структуры - последовательность и выбор, - но не было бы циклов и не было бы поддержки рекурсии, еще одного базисного механизма поддержки итеративных вычислений.

Но с мощностью приходят и риски. У циклов дурная слава, - их трудно заставить работать правильно. Типичными для циклов являются:

[x]. Ошибки "больше-меньше" (выполнение цикла слишком много или слишком мало раз).

[x]. Ошибки управления пограничными ситуациями, например пустыми структурами. Цикл может правильно работать на больших массивах, но давать ошибки, когда у массива один элемент или он вообще пуст.

[x]. Ошибки завершения ("зацикливание") в некоторых ситуациях.

Бинарный поиск - один из ключевых элементов базового курса "Введение в информатику" (Computer Science 101) - хорошая иллюстрация "коварства" циклов даже в относительно тривиальной ситуации. Рассмотрим целочисленный, упорядоченный по возрастанию массив t с индексами от 1 до n. Используем алгоритм бинарного поиска для ответа на вопрос: появляется ли целое x среди элементов массива. Если массив пуст, ответ должен быть "нет", если в массиве ровно один элемент, то ответ "да" тогда и только тогда, когда элемент массива совпадает с x. Суть бинарного поиска, использующего упорядоченность массива, проста: вначале x сравнивается со средним элементом массива, если есть совпадение, то задача решена, если x меньше среднего элемента, то поиск продолжается в верхней половине массива, в противном случае - в нижней половине. Каждое сравнение уменьшает размер массива вдвое. Ниже представлены четыре попытки реализации этой простой идеи. К несчастью, все они содержат ошибки. Вам предоставляется случай поупражняться в поиске ошибок и установить, в какой ситуации каждый из алгоритмов не работает нужным образом.

 

Напомню, t @ m означает элемент массива t с индексом m. Знак операции // означает деление нацело, так что 7 // 2 и 6 // 2 дают значение 3. Синтаксис цикла будет дан ниже, но он должен быть и так понятен. Предложение from вводит инициализацию цикла.

 

 

BS2

from

i:= 1; j:= n; found:= false

until i = j and not found loop

m:= (i + j) // 2

if t @ m < x then

i:= m + 1

elseif t @ m = x then

found:= true

else

j:= m - 1

end

end

Result:= found

 

 

BS4

from

i:= 0; j:= n + 1

until i = j loop

m:= (i + j) // 2

if t @ m <= x then

i:= m + 1

else

j:= m

end

end

if i >= 1 and i <= n then

Result:= (x = t @ i)

else

Result:= false

end

 

BS1fromi:= 1; j:= nuntil i = j loopm:= (i + j) // 2if t @ m <= x theni:= melsej:= mendendResult:= (x = t @ i)BS2fromi:= 1; j:= n; found:= falseuntil i = j and not found loopm:= (i + j) // 2if t @ m < x theni:= m + 1elseif t @ m = x thenfound:= trueelsej:= m - 1endendResult:= found   BS1 from i:= 1; j:= n until i = j loop m:= (i + j) // 2 if t @ m <= x then i:= m else j:= m end end Result:= (x = t @ i)    
BS3fromi:= 0; j:= nuntil i = j loopm:= (i + j + 1) // 2if t @ m <= x theni:= m + 1elsej:= mendendif i >= 1 and i <= n thenResult:= (x = t @ i)elseResult:= falseendBS4fromi:= 0; j:= n + 1until i = j loopm:= (i + j) // 2if t @ m <= x theni:= m + 1elsej:= mendendif i >= 1 and i <= n thenResult:= (x = t @ i)elseResult:= falseend   BS3 from i:= 0; j:= n until i = j loop m:= (i + j + 1) // 2 if t @ m <= x then i:= m + 1 else j:= m end end if i >= 1 and i <= n then Result:= (x = t @ i) else Result:= false end    

Таблица 11.3. Четыре (ошибочных) попытки реализации бинарного поиска

 

 


⇐ Предыдущая197198199200201202203204205206Следующая ⇒





Date: 2015-12-13; view: 416; Нарушение авторских прав


mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию