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

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

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

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

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

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

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

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

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

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

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

В данном алгоритме не могу понять как реализовать саму регистрацию пришедших чисел.
Подскажите пожалуйста метод регистрации чисел. Язык Си начал изучать недавно, но очень хочется решить задачку. Зараннее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2008, 16:44     Найти наименьшее натуральное число отсутствующее в последовательности
Посмотрите здесь:

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

Определить наименьшее натуральное число, отсутствующее в массиве - C++
В одномерном массиве, состоящем из п натуральных чисел, вычислить: - определить наименьшее натуральное число, отсутствующее в массиве.

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

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

Найти наименьшее натуральное число, непредставимое в виде суммы элементов массива Р - C++
Дан массив P, содержащий N натуральных чисел. Найти наименьшее натуральное число, непредставимое в виде суммы элементов массива Р

Найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N - C++
Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N. Входные данные В...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Varlock
365 / 68 / 2
Регистрация: 25.09.2008
Сообщений: 402
27.11.2008, 17:32     Найти наименьшее натуральное число отсутствующее в последовательности #2
Мне кажется что у вас логика решения немного неправильная... почему обязательно отсутствующее число должно находится в [1,н+1]?
поподробней про вашу последовательность:
может она 2,4,6,8,10...? что тогда? или всятки у нас по умолчанию она 1,2,3,4,5...? и начинается ваша последовательность всегда с единицы? или она может начаться с 5-ёрки?

хотя если взять ваш вариант решения, то мы делаем во что:
есть у нас матрица с этими числами, которые последовательность.
Мы создаём матрицу на н+1 элемент булевого типа.. при желании можно и инт, не суть важно тут.
далее мы эту матрицу обнуляем полностью.
теперь в цикле проходим по всей нашей введённой последовательности и выполняем примерно такие действия:
считываем элемент из массива, если его значение меньше н+1, записываем единицу в ячейку булева массива с номером равным значению элемента.
если больше н+1, то игнорируем.
после окончания этого цикла, во втором цикле проходим по всему булеву массиву и ищем первый нолик. его номер и будет минимальным элементом.
могу набрасать примерный код, но за орфографию я не отвечаю, т.к. писать его буду в блокноте, и код на Си не писал уже давно +)))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(i:=1, i<=n+1, i++)
{
    a=Posled[i];
    if a<n+1 then
        {
        BoolArr[a]:=1;
        }
    }
for(i=1, i=n+1, i++)
    {
    if BoolArr[i] == 0 then
        {
        MinEl:=i;
        //непомню как выйти из цикла фор по условию.. там какой-нить ретёрн или что подобное ещё написать +))
        }
    }
либо ещё лучше наверно во втором цикле юзать while (MinEl==0) do ...
lukan2
Сообщений: n/a
27.11.2008, 20:58     Найти наименьшее натуральное число отсутствующее в последовательности #3
Данная последовательность увеличивается с интервалом в единицу, но может начинаться не только с единицы, но и с двойки, тройки и т.д.
Helen
1 / 1 / 0
Регистрация: 23.10.2008
Сообщений: 13
27.11.2008, 21:42     Найти наименьшее натуральное число отсутствующее в последовательности #4
Последовательность упорядоченная или нет? Из последнего сообщения я так поняла что да, если числа увеличиваются с интервалом в единицу, просто в определенный момент какое-то число пропускается. Если так, то можно написать:
C++
1
2
3
4
5
6
7
8
9
10
int A[n];  //исходная последовательность
int Min = 0;   //минимальное пропущенное число
for(int i = 0; i < n-1; i++)
{
    if((A[i+1] - A[i]) > 1)
    {
          Min = A[i]+1;
          break;
    }  
}
Добавлено через 14 минут 25 секунд
Если последовательность неупорядоченная, то сначала ищешь минимальный элемент последовательности, а потом юзаешь указанный выше алгоритм.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int A[n];   //исходник
int BoolArr[n];   //массив регистраций
int MinArr = 0; // минимальный существующий элемент
int Min = 0;    //минимальный пропущенный элемент 
 
for(int i = 0; i < n; i++)
     if(A[i] < MinArr)
          MinArr = A[i];
 
ZeroMemory(BoolArr, n);  //почистили массив
for(int i = 0; i < n; i++)
    BoolArr[A[i] - MinArr] = true;
int j = 0;
while(BoolArr[j])
    j++;
Min = j + MinArr;   //вышли из while - Значит наткнулись на мин. пропущ. число
                         //j-его номер, добавляем смещение в виде мимального существующего числа, получаем искомое пропущенное
lukan2
Сообщений: n/a
27.11.2008, 23:07     Найти наименьшее натуральное число отсутствующее в последовательности #5
примного благодарен, очень исчерпывающие комментарии и советы!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2008, 08:13     Найти наименьшее натуральное число отсутствующее в последовательности
Еще ссылки по теме:

Найти наименьшее число среди четных элементов последовательности - C++
Напишите пожалуйста программу по условию задачи :Вводится последовательность из N положительных целых чисел. Найти наименьшее число среди...

В последовательности натуральных чисел найти наименьшее число, кратное 3 - C++
Напишите программу, которая в последовательности натуральных чисел находит наименьшее число, кратное 3. Программа получает на вход целые...

Дано натуральное число n, действительные числа q1, q2, ... qn. Найти номер первого четного члена последовательности q1, q2, ... qn - C++
Добрый вечер. Пожалуйста помогите написать код небольшой программы на С++. Условие: Дано натуральное число n, действительные...

Найдите наименьшее натуральное число удовлетворяющее условию - C++
Найдите наименьшее натуральное число n, такое, что делится на 2n-2, но не делится на 3n-3.

Наименьшее натуральное число n, представимое двумя различными способами - C++
Найти наименьшее натуральное число n, представимое двумя различными способами в виде суммы кубов двух натуральных чисел X^3 + Y^3 (X ≥ Y) ....

Вывести наименьшее число пропущенное в последовательности - C++
Вводится последовательность из К натуральных чисел. Необходимо вывести наименьшее число, отсутствующего в последовательности. То есть,...


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

Или воспользуйтесь поиском по форуму:
Helen
1 / 1 / 0
Регистрация: 23.10.2008
Сообщений: 13
28.11.2008, 08:13     Найти наименьшее натуральное число отсутствующее в последовательности #6
Тока у меня тут маленькая ошибочка
C++
1
bool BoolArray[n];
Yandex
Объявления
28.11.2008, 08:13     Найти наименьшее натуральное число отсутствующее в последовательности
Ответ Создать тему
Опции темы

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