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

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

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

Определение длины подпоследовательности - C++

19.10.2009, 09:28. Просмотров 665. Ответов 4
Метки нет (Все метки)

Вот такое задание у меня: составить программу для определения длины самой длинной неубывающей подпоследовательности в последовательности чисел. Причём в качестве подпоследовательности брать лишь подряд расположенные элементы. Последовательность вводится из текстового файла.
Вывести длину найденной подпоследовательности и саму подпоследовательность как на экран, так и в текстовый файл.

Подкиньте идеи, код, часть кода... всё, что можете.

В C++ шарю слабо.

С уважением.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2009, 09:28     Определение длины подпоследовательности
Посмотрите здесь:

C++ Стандартное определение длины строки в С++
Определение длины файла в С C++
определение длины слова с номером n в строке s C++
C++ Определение длины заранее неопределенной строки
C++ Работа с классами(определение длины вектора)
C++ Определение длины одномерного массива
C++ Определение количества слов четной длины в строке
C++ Определение длины строки
Определение площади и длины радиуса круга C++
C++ Определение длины массива в C++ в функции
Неверное определение длины строки C++
Определение длины файла для fstream C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mamedovvms
2916 / 837 / 93
Регистрация: 30.04.2009
Сообщений: 2,624
19.10.2009, 09:52     Определение длины подпоследовательности #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int max=0;
int k=0;
int kon;
for (int i=1;i<n;i++)
{ if (a[i]<=a[i-1]) k++;
  else
     {
       if (k>max){max=k;kon=i-1}
     }
   
}
 
for (int i=0;i<max;i++)
 cout<<a[kon-i]<<" ";
Alladin
0 / 0 / 0
Регистрация: 12.05.2009
Сообщений: 33
19.10.2009, 10:10  [ТС]     Определение длины подпоследовательности #3
mamedovvms, спасибо, а... что есть что?
Rififi
2336 / 1051 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
19.10.2009, 10:16     Определение длины подпоследовательности #4
В демонстрационной версии - с выводом только на экран: ((:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <functional>
#include <iostream>
#include <locale>
#include <iostream>
#include <iterator>
 
/*
    составить программу для определения длины самой длинной
        неубывающей подпоследовательности в последовательности чисел
*/
 
template <typename T>
void find(const T* arr, const size_t N)
{
    typedef typename std::allocator<T>::const_pointer iterator;
 
    iterator curr = &arr[0], next, found = arr + N;
    size_t max_seq = 0;
 
    for(; (next = std::adjacent_find(curr, arr+N, std::greater<T>())) != arr+N; std::advance(curr = next, 1))
    {
        const size_t curr_length = std::distance(curr, next) + 1;
        if (curr_length > max_seq)
        { max_seq = curr_length; found = curr; }
        std::advance(curr = next, 1);
    }
 
    const size_t last_length = std::distance(curr, next);
    if (last_length > max_seq)
    { max_seq = last_length; found = curr; }
 
    std::cout << "самая длинная неубывающая последовательность:" << std::endl;
    std::copy(found, found + max_seq, std::ostream_iterator<T>(std::cout, " "));
}
 
int main()
{
    setlocale(LC_ALL, "");
    int arr[] = {1,2,3,0,1,-1,7,6,5,4,1,1,1,1};
    const size_t N = sizeof(arr) / sizeof(arr[0]);
    find(arr, N);
 
    return (0);
}
проверка: http://codepad.org/P1Xaxysl
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
19.10.2009, 10:32     Определение длины подпоследовательности #5
здесь можешь ещё посмотреть
Yandex
Объявления
19.10.2009, 10:32     Определение длины подпоследовательности
Ответ Создать тему
Опции темы

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