Задача 11.
На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память машины может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Опишите алгоритм, который сделает это за небольшое количество перемоток ленты.
|
Решение задачи 11.
Очевидно, что при вводе n натуральных чисел по крайней мере одно число из интервала [1,n+1] отсутствует.
Определим начало a и конец b некоторого интервала индексов, который нас интересует. Возможно ли за один просмотр ленты установить, все ли числа из интервала [a,b] присутствуют на ленте? Учитывая факт, что записанные числа различны, можно определить, сколько чисел, записанных на ленте, попадают в интересующий нас интервал. С другой стороны, нетрудно определить количество натуральных чисел на интервале [a,b] - это (b-a+1).
Поэтому алгоритм состоит в следующем.
Определим значения начала и конца интересующего нас интервала. Очевидно, что вначале они равны 1 и N+1 соответственно.
Пусть на некотором шаге значения начала и конца интересующего нас интервала равны f и l соответственно. Определим индекс среднего элемента интервала m=(f+l) div 2.
Определяем теперь количество элементов k на ленте, лежащих в интервале [f,m].
Возможны следующие ситуации:
1. Количество элементов k<m-f+1 .
В этом случае нас не интересует интервал от m до l, так как на интервале [f,m] хотя бы одно число отсутствует. Поэтому интересующим нас интервалом можно считать [f,m]. Поэтому полагаем l:=m.
2. Количество элементов k=m-f+1 .
В этом случае нас не интересует интервал от f до m, так как на интервале [f,m] все натуральные присутствуют. Поэтому интересующим нас интервалом можно считать [m+1,l]. Поэтому полагаем l:=m+1.
Процесс оканчивается, когда f=l.
|
