Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
коди
Сообщений: n/a
#1

Очень интересно :) - C++

16.12.2010, 13:14. Просмотров 283. Ответов 0
Метки нет (Все метки)

НА длинной перфоленте записаны N попарно разлычных положительных целых чисел.Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим.Внутренняя паметь машины может хранить только несколько целых чисел.Требуется найти наименьшее положительное целое число,которого нет на ленте.Опигите алгорит,который сделает это за небольшое количество перемоток лент.


РЕШЕНИЕ
очевидно,что при в воде n натуральных чисел по крайней мере одно число из интервала [1,n-1] отсутствуе.

Определим начало a и b некоторого интервала индексом, которого нас интересует. Возможно ли за один просмотр ленты установить, все ли числа из интервала [a,b] присутствуют на ленте? Учитывая факт, что записанные числа различны,можно определить, сколько чисел, записынныч на ленте, попадают в интересуещий нас интревал. С жругой стороны, нетрудно определить количество натуральный чисел на интервале [a,b] - это (b-a+1)

Поэтому алгоритм состоит в следующем:
Определим значения начало и конте интересуещенго нас интревала. Очевидно, что вначале они равны 1 и N+1 соответственно.

Пусть на некотором шаге значения начала и конца интересуещего нас интреваоа равны f и 1 соответственно. Определим индекс среднего элемента интервала m=(f+1)/2.

Определим теперь колчисество элементов k на ленте, лежащих в интервале [f,m].

Возможный следующие ситуации:
1.Количество элементов k<m-f+1

В этом случае нас интересует интервал от m до 1, так как на интервале [f,m] хотя бы одно число отсутствует. Поэтому интересующим нас интервалом можно считать [f,m].
Поэтому полагаем 1=m.

2.Количество элементов k=m-f+1.

В этом случае нас не интересует интерва от f до m, так как на интервале [f,m] все натуральные присутствуют. Поэтому интересующим нас интервалом можно считать [m+1,1]. Поэтому полагаем 1=m+1.

Процесс оканчиватеся , когда f=1.



Помогите пожалуйста составть прогу
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2010, 13:14     Очень интересно :)
Посмотрите здесь:

Головоломка с матрицей. Очень интересно! C++
В чем интересно загвоздка???интересно разобраться! C++
C++ интересно
Интересно где же я запутал код C++
ну очень интересно C++
Матрица, очень интересно C++
C++ Просто интересно спросить
C++ Просто интересно
C++ Кому интересно поломать голову
C++ Кому интересно. Покер
Это интересно C++
C++ Интересно мнение программистов с опытом

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 05:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru