![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Трудности циклов
Возможность повторять некоторые вычисления произвольное число раз, не поддаваясь усталости, без случайных потерь чего-либо важного, - в этом принципиальное отличие компьютерных вычислений от возможностей человека. Вот почему циклы так важны. Трудно вообразить, что можно было бы делать в языках, в которых были бы только две управляющие структуры - последовательность и выбор, - но не было бы циклов и не было бы поддержки рекурсии, еще одного базисного механизма поддержки итеративных вычислений. Но с мощностью приходят и риски. У циклов дурная слава, - их трудно заставить работать правильно. Типичными для циклов являются: [x]. Ошибки " больше-меньше" (выполнение цикла слишком много или слишком мало раз). [x]. Ошибки управления пограничными ситуациями, например пустыми структурами. Цикл может правильно работать на больших массивах, но давать ошибки, когда у массива один элемент или он вообще пуст. [x]. Ошибки завершения (" зацикливание") в некоторых ситуациях. Бинарный поиск - один из ключевых элементов базового курса " Введение в информатику" (Computer Science 101) - хорошая иллюстрация " коварства" циклов даже в относительно тривиальной ситуации. Рассмотрим целочисленный, упорядоченный по возрастанию массив t с индексами от 1 до n. Используем алгоритм бинарного поиска для ответа на вопрос: появляется ли целое x среди элементов массива. Если массив пуст, ответ должен быть " нет", если в массиве ровно один элемент, то ответ " да" тогда и только тогда, когда элемент массива совпадает с x. Суть бинарного поиска, использующего упорядоченность массива, проста: вначале x сравнивается со средним элементом массива, если есть совпадение, то задача решена, если x меньше среднего элемента, то поиск продолжается в верхней половине массива, в противном случае - в нижней половине. Каждое сравнение уменьшает размер массива вдвое. Ниже представлены четыре попытки реализации этой простой идеи. К несчастью, все они содержат ошибки. Вам предоставляется случай поупражняться в поиске ошибок и установить, в какой ситуации каждый из алгоритмов не работает нужным образом. Напомню, t @ m означает элемент массива t с индексом m. Знак операции // означает деление нацело, так что 7 // 2 и 6 // 2 дают значение 3. Синтаксис цикла будет дан ниже, но он должен быть и так понятен. Предложение from вводит инициализацию цикла. BS1 from i: = 1; j: = n until i = j loop m: = (i + j) // 2 if t @ m & lt; = x then i: = m else j: = m end end Result: = (x = t @ i)
BS2 from i: = 1; j: = n; found: = false until i = j and not found loop m: = (i + j) // 2 if t @ m & lt; x then i: = m + 1 elseif t @ m = x then found: = true else j: = m - 1 end end Result: = found
BS3 from i: = 0; j: = n until i = j loop m: = (i + j + 1) // 2 if t @ m & lt; = x then i: = m + 1 else j: = m end end if i & gt; = 1 and i & lt; = n then Result: = (x = t @ i) else Result: = false end
BS4 from i: = 0; j: = n + 1 until i = j loop m: = (i + j) // 2 if t @ m & lt; = x then i: = m + 1 else j: = m end end if i & gt; = 1 and i & lt; = n then Result: = (x = t @ i) else Result: = false end
Таблица 11.3. Четыре (ошибочных) попытки реализации бинарного поиска
|