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

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

Войти
Регистрация
Восстановить пароль
 
Kolbusdkiy
0 / 0 / 0
Регистрация: 14.10.2013
Сообщений: 112
#1

Найдите количество ее возрастающих подпоследовательностей - C++

05.04.2014, 10:46. Просмотров 459. Ответов 8
Метки нет (Все метки)

Задана последовательность целых чисел.

Найдите количество ее возрастающих подпоследовательностей
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2014, 10:46     Найдите количество ее возрастающих подпоследовательностей
Посмотрите здесь:

Максимальная последовательность возрастающих чисел C++
C++ Даны два возрастающих массива x[k] и y[l]. Найти количество общих элементов
C++ Найти минимум среди максимумов всех возрастающих подпоследовательностей
C++ Найдите количество наименьших элементов массива
Найти наибольшую сумму цифр подпоследовательностей, ограниченных отрицательными числами C++
C++ Найти количество непрерывно возрастающих серий в массиве
Найти наименьшее количество строго возрастающих участков в массиве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
6245 / 5848 / 1891
Регистрация: 18.12.2011
Сообщений: 14,982
Завершенные тесты: 1
05.04.2014, 16:55     Найдите количество ее возрастающих подпоследовательностей #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N=100;
int A[N];
// ... заполняем массив
int amount=0;
bool vozr=false;
for(int i=1;i<N;i++)
{
    if(A[i]>A[i-1])
        vozr=true; //Нашлась возрастающая последовательность
    else
    {
        if(vozr)
        {
              vozr=false;//Кончилась возрастающая последовательность
              amount++; // сосчитали ее
        }
    }
}
if(vozr)
     amount++; // сосчитали последнюю в конце
cout<<amount;
Dani
1272 / 630 / 53
Регистрация: 11.08.2011
Сообщений: 2,259
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 17:00     Найдите количество ее возрастающих подпоследовательностей #3
Цитата Сообщение от Kolbusdkiy Посмотреть сообщение
подпоследовательностей
Скорее всего имеется ввиду: подпоследовательность - последовательность, которая получается вычеркиванием некоторых элементов из исходной последовательности.
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
05.04.2014, 17:20     Найдите количество ее возрастающих подпоследовательностей #4
Цитата Сообщение от Kolbusdkiy Посмотреть сообщение
Найдите количество ее возрастающих подпоследовательностей
Что имеется в виду под "подпоследовательностью"? Отрезкивида a[2], a[3], a[4]? Тогда решение предложенное zss, похоже на правду (в детали не лез). Или классическое (из матана) определение? Там a[1], a[3], a[7] тоже считается подпоследовательностью. Тогда все будет несколько посложнее.
Еще вопрос. Считать ли последовательность из одного элемента возрастающей подпоследовательностью? Ибо формально это так. Однако, постановщик задачи вправе их не учитывать, специально оговорив.

Добавлено через 42 секунды
Цитата Сообщение от Dani Посмотреть сообщение
Скорее всего имеется ввиду: подпоследовательность - последовательность, которая получается вычеркиванием некоторых элементов из исходной последовательности.
Вот-вот. Именно это я и имел в виду.

Добавлено через 8 минут
zss, в преположении, что нас интересуют только отрезки длины больше 1, ваш код можно несколько упростить...
C++
1
2
3
for(int i=0;i<N-1;i++) {
    if(A[i+1]>A[i]) amount ++;
}
zss
Модератор
Эксперт С++
6245 / 5848 / 1891
Регистрация: 18.12.2011
Сообщений: 14,982
Завершенные тесты: 1
05.04.2014, 17:24     Найдите количество ее возрастающих подпоследовательностей #5
Цитата Сообщение от Day Посмотреть сообщение
if(A[i+1]>A[i]) amount ++;
Не пойдет, т.к. каждая пара будут считаться подпоследовательностью.
Надо отследить начало и конец каждой пп.
Dani
1272 / 630 / 53
Регистрация: 11.08.2011
Сообщений: 2,259
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 17:31     Найдите количество ее возрастающих подпоследовательностей #6
zss, если есть последовательность 1 2 3 4 5. Чем 1 2 3 или 2 3 не возрастающая?
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
05.04.2014, 17:53     Найдите количество ее возрастающих подпоследовательностей #7
Цитата Сообщение от zss Посмотреть сообщение
Не пойдет,
Пожалуй, вы правы. Погорячился. Для исходной 1 2 3 есть 3 возрастающих: 1 2, 1 2 3, 2 3. А у меня получается только 2
C++
1
2
3
4
5
6
7
for(int i=0;i<N-1;i++) {
    if(A[i+1]>A[i]) amount ++;
    for(j=i+1; j<N-1; j++) {
      if (A[j+1] > A[j]) amount++;
      else break;
    }
}
Dani
1272 / 630 / 53
Регистрация: 11.08.2011
Сообщений: 2,259
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 18:01     Найдите количество ее возрастающих подпоследовательностей #8
Цитата Сообщение от Day Посмотреть сообщение
Вот-вот. Именно это я и имел в виду.
Если будет такое значение подпоследовательности, то их будет тьма. И тогда эту задачу лучше всего решать динамикой.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2014, 21:36     Найдите количество ее возрастающих подпоследовательностей
Еще ссылки по теме:

C++ Вывести начальные индексы всех непрерывных неубывающих подпоследовательностей цифр
Создать последовательность без смежных идентичных подпоследовательностей C++
C++ Функция переставляющая элементы положительных подпоследовательностей
Поиск подпоследовательностей в массиве C++
Вывести количество возрастающих последовательностей в массиве, а также длину самой длинной из них C++

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

Или воспользуйтесь поиском по форуму:
zss
Модератор
Эксперт С++
6245 / 5848 / 1891
Регистрация: 18.12.2011
Сообщений: 14,982
Завершенные тесты: 1
05.04.2014, 21:36     Найдите количество ее возрастающих подпоследовательностей #9
Цитата Сообщение от Day Посмотреть сообщение
1 2 3
Это одна подпоследовательность 1 - ее начало, 3 - ее конец
Yandex
Объявления
05.04.2014, 21:36     Найдите количество ее возрастающих подпоследовательностей
Ответ Создать тему
Опции темы

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