Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Поиск >> Номер 10

[Назад]    [Содержание ]    [Вперед]

  


Номер 10


  Условие: Номер 10


Задача 10. Вводится последовательность из n натуральных чисел. Необходимо определить наименьшее натуральное число, отсутствующее в последовательности.

  Решение задачи: Номер 10


Решение задачи 10. Очевидно, что при вводе n натуральных чисел по крайней мере одно число из интервала [1,n+1] отсутствует. Поэтому идея решения состоит в том, что отводится массив из n чисел, в котором элемент с индексом i 'регистрирует', пришло ли число со значением i. После 'регистрации' всех элементов последовательности осталось только проверить, какое минимальное число не 'зарегистрировано'. (В качестве признака 'регистрации' числа i можно заносить в i-ый элемент массива 1. Первоначально все числа не 'зарегистрированы' - все элементы массива равны 0). Если все числа от 1 до n 'зарегистрированы', то минимальное отсутствующее натуральное - n+1.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017