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

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

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

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

16.12.2010, 13:14. Просмотров 295. Ответов 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++
дана f(x). дан отрезок на котором расположены положительные корни дана точность E могу написать функцию, для нахождения одного корня...

Матрица, очень интересно - C++
как зделать так чтоб програма сама делала матрицу вида - - + - - + + + а также еще большую - - - + - - - + - + + -

Головоломка с матрицей. Очень интересно! - C++
Не в корысных целях(мне эта программа не нужна, просто интересно стало, как такое реализовать) пишите свои соображения по поводу решения:...

В чем интересно загвоздка???интересно разобраться! - C++
Помогите разобраться в чем дело? Switch постоянно зацикливается и бесконечный цикл получается если вводить символы вместо цифр как от этого...

интересно - C++
Необходимо разработать программу, в которой выполняется ввод списка записей определенного типа, а затем - обработка списка. Сначала в...

Странная ошибка при компиляции очень очень большой проги ,,boomerang,, - C++
Я в общем, даже и не представляю, куда смотреть в поисках ошибки. Ошибка 1 error LNK2019: ссылка на неразрешенный внешний символ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2010, 13:14
Привет! Вот еще темы с ответами:

Просто интересно - C++
#include &lt;iostream&gt; using namespace std; int main() { double z=0; double x=-2; cout&lt;&lt; x*z; system...

Это интересно - C++
П.5.18.Правил Запрещено размещать задания и решения в виде картинок и других файлов с их текстом. Редактор формул внизу страницы ...

Просто интересно спросить - C++
Бывали ли случаи когда люди без необходимого знания математики становились серьезными программистами в крупных конторах или вносили...

Кому интересно. Покер - C++
Вообщем, давно ничего не кодил и на днях накатал немного говно кода на тему Покера. Кому будет интересно, посмотрите и предложите если...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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