0 / 0 / 0
Регистрация: 06.04.2016
Сообщений: 55
1

Дан вектор произвольной длины. Вывести самую длинную неубывающую последовательность.

08.09.2016, 09:18. Показов 1663. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дан вектор произвольной длины,вывести самую длинную неубывающию последовательность?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.09.2016, 09:18
Ответы с готовыми решениями:

Дан вектор произвольной длины, вывести самую длинную неубывающую последовательность
Дан вектор произвольной длины,вывести самую длинную неубывающию последовательность?

Дан массив из N вещественных чисел. Найти самую длинную неубывающую последовательность подряд идущих элементов массива
Задача: Дан массив из N вещественных чисел. Найти самую длинную неубывающую последовательность...

Найти самую длинную неубывающую последовательность
Дан список из n целых чисел a1, a2,..., a. Найти самую длинную неубывающую последовательность...

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

14
.NET C#,ASP.NET MVC
Эксперт .NET
593 / 504 / 225
Регистрация: 16.10.2010
Сообщений: 1,902
08.09.2016, 09:26 2
Цитата Сообщение от konderson97 Посмотреть сообщение
Дан вектор произвольной длины,вывести самую длинную неубывающию последовательность?
А что не получается?
0
184 / 183 / 96
Регистрация: 30.04.2016
Сообщений: 478
08.09.2016, 10:14 3
Цитата Сообщение от konderson97 Посмотреть сообщение
Дан вектор произвольной длины,вывести самую длинную неубывающию последовательность?

Не по теме:

Да, можете вывести

2
.NET C#,ASP.NET MVC
Эксперт .NET
593 / 504 / 225
Регистрация: 16.10.2010
Сообщений: 1,902
08.09.2016, 10:39 4
Цитата Сообщение от golubyatnikovtv Посмотреть сообщение
Да, можете вывести

Не по теме:


Согласен, вывести можно

0
0 / 0 / 0
Регистрация: 06.04.2016
Сообщений: 55
08.09.2016, 14:45  [ТС] 5
Не понятно как это все реализовать в коде
0
746 / 487 / 187
Регистрация: 30.12.2012
Сообщений: 1,278
Записей в блоге: 2
08.09.2016, 14:56 6
konderson97, а как это реализовать на листочке бумаги вы представляете?
0
0 / 0 / 0
Регистрация: 06.04.2016
Сообщений: 55
08.09.2016, 15:14  [ТС] 7
Чесно говоря нет. Прошу помочь и объяснить
0
746 / 487 / 187
Регистрация: 30.12.2012
Сообщений: 1,278
Записей в блоге: 2
08.09.2016, 16:14 8
konderson97, я предлагаю так:
Алгоритм близок по реализации к поиску максимума в массиве A
1) Объявляем max = A[0].
2) Пробегаем по массиву. Если встречаем элемент A[i], больший max, то в max записываем A[i].

В этой задаче я предлагаю завести две тройки: (li, ri, delta) - индексы левого и правого элементов в неубывающей последовательности и (li_max, ri_max, delta_max) - индексы левого и правого элементов в самой длинной из найденных неубывающих подпоследовательностей.
1) Объявляем li = ri = delta = 0; li_max = ri_max = delta_max = 0;
2) Пробегаем по массиву. Пока элементы неубывают (A[i+1] >= A[i]), "тянем" ri за собой.
Если условие нарушено, то считаем delta = ri - li и проверяем, длиннее ли этот промежуток максимального delta_max;
Если длиннее, то сохраняем тройку (li, ri, delta) в тройку (li_max, ri_max, delta_max), сбрасываем по нулям первую тройку и продолжаем бежать по массиву.
3) выводим элементы массива от A[li_max] до A[ri_max] включительно.
0
1321 / 983 / 267
Регистрация: 17.05.2012
Сообщений: 2,687
08.09.2016, 18:02 9
konderson97, Не уверен, что правильно. Но если быстро, то можно накидать так.
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
using System.Collections.Generic;
 
namespace ConsoleTrain
{
    class Programm
    {
       public static void Main()
        {   
            // Размер списка
            int size = 10;
            // Список случайных элементов
            List<int> listRandom = new List<int>();
            // Список с максимальной  неубывающию последовательность 
            List<int> listMax = new List<int>();
          
            // Заполняем список случайными числами
            Random random = new Random();
            for (int i = 0; i < size; i++)
               listRandom.Add(random.Next(100));
 
            Show(listRandom, size, "Начальный список: ");
 
            listMax = new List<int>(NonDecreasingSequence(listRandom, size));
 
            Show(listMax, listMax.Count, "Cамая длинная неубывающию последовательность: ");
 
            Console.ReadKey();
        }
       /// <summary>
       /// Метод показывающий последовательность.
       /// </summary>
       /// <param name="list">Список для отображения.</param>
       /// <param name="size">Размер списка для отображения.</param>
       /// <param name="text">Текст перед отображением.</param>
       public static void Show(List<int> listShow, int size, string text)
       {
           Console.Write(text + " ");
 
           for (int i = 0; i < listShow.Count; i++)
               Console.Write(listShow[i] + " ");
 
           Console.WriteLine();
       }
       /// <summary>
       /// Метод вычисляющий самую длинную неубывающую последовательность.
       /// </summary>
       /// <param name="listRandom">Список в котором ищем самую длинную неубывающую последовательность.</param>
       /// <param name="size">Размер списка.</param>
       /// <returns></returns>
       public static List<int> NonDecreasingSequence(List<int> listRandom, int size)
       {
           // Список с максимальной последовательностью.
           List<int> listMax = new List<int>();
           // Текущий список для сравнения.
           List<int> listCurrent = new List<int>();
 
           for(int i = 0; i < size ; i++)
           {
               // Последний элемент в списке сравнивать не надо, выход из цикла. 
               if (i == size - 1)
                   break;
 
               // Сравниваем текущий элемент с тем который стоит впереди него.
               if(listRandom[i] <= listRandom[i+1])
               {
                   // Если список пустой, необходимо добавить текущий элемент.
                   if (listCurrent.Count == 0)
                       listCurrent.Add(listRandom[i]);
 
                   // Добавляем в список впереди стоящий.
                   listCurrent.Add(listRandom[i+1]);
               }
               else
               {   
                   // Сравниваем размеры текущего и максмиального списков.
                   if (listCurrent.Count > listMax.Count)
                       listMax = new List<int>(listCurrent);
 
                   // Очищаем текущий
                   listCurrent.Clear();
               }
           }
 
           return listMax;
       }
    }
}
0
0 / 0 / 0
Регистрация: 06.04.2016
Сообщений: 55
09.09.2016, 09:00  [ТС] 10
Спасибо
0
58 / 57 / 15
Регистрация: 15.09.2012
Сообщений: 557
09.09.2016, 13:22 11
Есть немного короче решение
C#
1
2
 int max = inputlist[0];
 var outList = inputlist.TakeWhile(x => { bool result = x >= max; max = x; return result; }).ToList();
0
184 / 183 / 96
Регистрация: 30.04.2016
Сообщений: 478
09.09.2016, 13:44 12
ASDFD12, Ваше решение не работает.

C#
1
2
3
4
5
var inputlist = new[] {6, 4, 1, 2, 5, 2, 3, 3};
            var max = inputlist[0];
            var outList = inputlist.TakeWhile(x => { bool result = x >= max; max = x; return result; }).ToList();
            // outList = [6]
            // а должно быть [2, 3, 3]
0
58 / 57 / 15
Регистрация: 15.09.2012
Сообщений: 557
09.09.2016, 13:51 13
ясно, не так задачу понял
0
184 / 183 / 96
Регистрация: 30.04.2016
Сообщений: 478
09.09.2016, 13:55 14
ASDFD12, а я в замечании ошибку допустил)

В примере две неубывающие последовательности одинаковой длины: [1, 2, 5] и [2, 3, 3]. В задаче не сказано как поступать в таком случае, поэтому обе последовательности могут считаться верным ответом.
0
269 / 253 / 186
Регистрация: 28.10.2015
Сообщений: 723
11.09.2016, 18:19 15
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
using System;
using System.Linq;
using System.Collections.Generic;
 
class Program
{
    public static void Main()
    {
        List<int> lst = new List<int> {6, 4, 1, 2, 5, 2, 3, 3};
        int max = 0;
        List<int> seq = new List<int>();
        foreach (int i in lst)
        {
            if (seq.Count == 0 || i >= seq.Last())
            {
                seq.Add(i);
                max = Math.Max(max, seq.Count);
            }
            else
            {
                seq.Clear();
            }
        }
        Console.WriteLine(max);
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.09.2016, 18:19
Помогаю со студенческими работами здесь

Найти самую длинную неубывающую последовательность подряд идущих элементов массива
Передо мной стоит задача: Дан массив из N вещественных чисел. Найти самую длинную неубывающую...

В произвольной последовательности чисел найти самую длинную последовательность, упорядоченную по возрастанию
В произвольной последовательности чисел, заданной в виде одномерного массива, найти самую длинную...

Цикл: Найти самую длинную неубывающую цепочку чисел
В цикле с клавиатуры вводится 15 целых чисел. Необходимо найти самую длинную неубывающую цепочку...

Найти и вывести самую длинную цепочку из слов одинаковой длины
Кто знает Ассемблер помогите очень прошу. №2 Задано текст, слова в котором разделены пробелами и...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru