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

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

Восстановить пароль Регистрация
 
Kolbusdkiy
 Аватар для Kolbusdkiy
0 / 0 / 0
Регистрация: 14.10.2013
Сообщений: 112
05.04.2014, 10:46     Найдите количество ее возрастающих подпоследовательностей #1
Задана последовательность целых чисел.

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

C++ Даны два возрастающих массива x[k] и y[l]. Найти количество общих элементов
C++ Найти минимум среди максимумов всех возрастающих подпоследовательностей
Найти наибольшую сумму цифр подпоследовательностей, ограниченных отрицательными числами C++
C++ Найти количество непрерывно возрастающих серий в массиве
Найти наименьшее количество строго возрастающих участков в массиве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,155
Завершенные тесты: 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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 17:00     Найдите количество ее возрастающих подпоследовательностей #3
Цитата Сообщение от Kolbusdkiy Посмотреть сообщение
подпоследовательностей
Скорее всего имеется ввиду: подпоследовательность - последовательность, которая получается вычеркиванием некоторых элементов из исходной последовательности.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
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
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,155
Завершенные тесты: 1
05.04.2014, 17:24     Найдите количество ее возрастающих подпоследовательностей #5
Цитата Сообщение от Day Посмотреть сообщение
if(A[i+1]>A[i]) amount ++;
Не пойдет, т.к. каждая пара будут считаться подпоследовательностью.
Надо отследить начало и конец каждой пп.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 17:31     Найдите количество ее возрастающих подпоследовательностей #6
zss, если есть последовательность 1 2 3 4 5. Чем 1 2 3 или 2 3 не возрастающая?
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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++ Функция переставляющая элементы положительных подпоследовательностей

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

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

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