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

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

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

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

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

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

Найдите количество ее возрастающих подпоследовательностей
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2014, 10:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найдите количество ее возрастающих подпоследовательностей (C++):

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

Найти количество непрерывно возрастающих серий в массиве - C++
Добрый день. Уже который день мучаюсь над решением задачи: В одномерном массиве нужно найти кол - во непрерывно возрастающих серий. :mda:...

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

Даны два возрастающих массива x[k] и y[l]. Найти количество общих элементов - C++
Даны два возрастающих массива x и y. Найти количество общих элементов в этих массивах ( т. е. количество тех ...

Вывести количество возрастающих последовательностей в массиве, а также длину самой длинной из них - C++
Помогите пожалуйста! Написать программу, в которой пользователь вводит элементы целочисленного массива с клавиатуры. Необходимо...

Поиск подпоследовательностей в массиве - C++
Надо найти все подпоследовательности в массиве. Например: массив: {3,4,1,2}, подпоследовательности:...

8
zss
Модератор
Эксперт С++
6634 / 6196 / 2051
Регистрация: 18.12.2011
Сообщений: 16,157
Завершенные тесты: 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;
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 17:00 #3
Цитата Сообщение от Kolbusdkiy Посмотреть сообщение
подпоследовательностей
Скорее всего имеется ввиду: подпоследовательность - последовательность, которая получается вычеркиванием некоторых элементов из исходной последовательности.
0
Day
1159 / 964 / 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 ++;
}
0
zss
Модератор
Эксперт С++
6634 / 6196 / 2051
Регистрация: 18.12.2011
Сообщений: 16,157
Завершенные тесты: 1
05.04.2014, 17:24 #5
Цитата Сообщение от Day Посмотреть сообщение
if(A[i+1]>A[i]) amount ++;
Не пойдет, т.к. каждая пара будут считаться подпоследовательностью.
Надо отследить начало и конец каждой пп.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 17:31 #6
zss, если есть последовательность 1 2 3 4 5. Чем 1 2 3 или 2 3 не возрастающая?
0
Day
1159 / 964 / 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;
    }
}
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
05.04.2014, 18:01 #8
Цитата Сообщение от Day Посмотреть сообщение
Вот-вот. Именно это я и имел в виду.
Если будет такое значение подпоследовательности, то их будет тьма. И тогда эту задачу лучше всего решать динамикой.
0
zss
Модератор
Эксперт С++
6634 / 6196 / 2051
Регистрация: 18.12.2011
Сообщений: 16,157
Завершенные тесты: 1
05.04.2014, 21:36 #9
Цитата Сообщение от Day Посмотреть сообщение
1 2 3
Это одна подпоследовательность 1 - ее начало, 3 - ее конец
0
05.04.2014, 21:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2014, 21:36
Привет! Вот еще темы с ответами:

Функция переставляющая элементы положительных подпоследовательностей - C++
Здравствуйте, народ выручайте: Дан массив с n кол-во элементов, в котором необходимо во всех положительных последовательностях...

Создать последовательность без смежных идентичных подпоследовательностей - C++
Напишите программу создания n-символьной последовательности, состоящей из совокупности 3 символом(например, &quot;1&quot;,&quot;2&quot;,&quot;3&quot; или &quot;a&quot;,&quot;b&quot;,&quot;c&quot;), в...

Вывести начальные индексы всех непрерывных неубывающих подпоследовательностей цифр - C++
Дана последовательность целых чисел. Вывести начальные индексы всех непрерывных неубывающих подпоследовательностей цифр. помогите...

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


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

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

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