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

Найти наименьшее натуральное число отсутствующее в последовательности - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Указатели на массив объектов http://www.cyberforum.ru/cpp-beginners/thread16873.html
здравствуйте! есть такой код: #include <cstdlib> #include <iostream> using namespace std; class samp {
C++ Нужны полные таблицы кодировок Очень нужны полные таблицы кодировок cp866_dos, win1251, koi-8, unicode, если есть у кого, дайте плиз Заранее спасибо http://www.cyberforum.ru/cpp-beginners/thread16861.html
C++ Вхождение буквы в строку
Дана строка М и символ А.Составить программу коорая подсчитает количество вхождений буквы в строку. #include<iostream.h> #include<conio.h> #include<math.h> #include<string.h> int main() {int...
Проверка на симметричность слова C++
void main() { char line; printf("vvedite stroku\n"); scanf("%s",line); for (int i=strlen(line)-1,j=0; i!=strlen(line)/2; i--,j++) if (line != line) printf("ne palindrom\n"); else...
C++ Работа со строками на Turbo C http://www.cyberforum.ru/cpp-beginners/thread16847.html
Помогите решить задачу на Turbo C! Найти в тексте все слова со спаренными согласными(например, это слова программирование, add, accomodation). Что,никто не знает?
C++ Матрицы на Turbo C Помогите написать задачу на Turbo C! Задача: В заданной прямоугольной матрице найти в последнем ряду первый отрицательный элемент.Все элементы столбца, где найден этот отрицательный элемент,... подробнее

Показать сообщение отдельно
lukan2
0 / 0 / 0
Регистрация: 28.01.2010
Сообщений: 16

Найти наименьшее натуральное число отсутствующее в последовательности - C++

27.11.2008, 16:44. Просмотров 1945. Ответов 5
Метки (Все метки)

Помогите пожалуйста разобраться с решением следующей задачки.

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

Алгоритм следующий:

Очевидно, что при вводе n натуральных чисел по крайней мере одно число из интервала [1,n+1] отсутствует.

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

Если все числа от 1 до n 'зарегистрированы', то минимальное отсутствующее натуральное - n+1.

В данном алгоритме не могу понять как реализовать саму регистрацию пришедших чисел.
Подскажите пожалуйста метод регистрации чисел. Язык Си начал изучать недавно, но очень хочется решить задачку. Зараннее спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.