Софтуерно Инженерство
Loading...
+ Нов въпрос
ivajlotokiew avatar ivajlotokiew 2 Точки

Въпрос относно намирането на най-дълга поредица от нарастващи елементи в целочислен масив

Здравейте,

Опитвам се да намеря решение на следния проблем. Даден ни е целочислен масив, примерно: 

 int[] matrix = { 1, 2, 3, 1, 5, 17, 22, 8, 1, 33 };

Искам да намеря най-дългата поредица от нарастващи елементи и да я запиша примерно в друг масив. В случая тя е: 1, 5, 17, 22.

 Опитах няколко начина, но без успех. Ще се радвам ако някой успее да помогне. 

Поздрави.

Тагове:
dggeorgiev avatar dggeorgiev 14 Точки

Здравей,

Ето

 една възможна реализация на задачата:

ModEdit: Забранено е цитирането на над 15 реда код във форума.

Обхождаш масива и проверяваш до кога ще имаш нарастваща редица. Когато получим условието за край на редицата записваме дължината на нарастващата редица и започваме да броим отново. Ако намерим друга редица с по-голяма дължина - запазваме нея като най-дълга и започваме да броим отново. Просто е.

Поздрави

Edit: Поправих грешка в логиката

0
19/08/2015 17:55:51
ivajlotokiew avatar ivajlotokiew 2 Точки

Здравей,

Благодаря ти за отговора, обаче немога да разбера конректно написаното в while цикъла: 

while (counter < matrix.Length-1)

Когато копирам кода ти в VS и ми дава доста грешки, именно на тези места където се съдържа: <

 

0
djc_bg2015 avatar djc_bg2015 922 Точки

Това е от форума, ескейпва > < и други подобни

&lt; (less than) <

&gt; (greater than) >

1
ivajlotokiew avatar ivajlotokiew 2 Точки

Здравей, 

Благодаря ти за пояснението. Оправих го кода. Обаче когато задам следните стойности в масива: {1, 8, 3, 17, 22, 33}, вместо да ми изкара като отговор: 3, 17, 22, 33, ми изкарва: 1 и 8. 

0
dim4o avatar dim4o 289 Точки

Ще се опитам да ти дам пример как може да стане с масива, който ти си предложил.

1. Правиш си един масив int[] help = new help[N], където N = matrix.Length

2. В help си пазиш дължини, като help[i] (0<=i<N) ще ти е равно на дължината на максималната подредица, завършваща matrix[i]. Как се определе точно ще пиша по-долу.

Направо почвам с конкретния пример.

  • help[0] = 1 очевидно защото най-дългата редица завършваща в matrix[0] e с дължина 1
  • help[1] = 2 - за да го намериш трябва към help[0] да прибавиш 1
  • help[2] = 3 = help[2] + 1
  • help[3] = 1, защото няма такова число k, за което matrix[k] < matrix[3], т.е. това може да е само начало на подредица, а не край
  • help[4] = 4 = help[2] + 1, защото help[2] е най-голямата стойност измежду help[0], help[1], help[2], help[3], за която при това matrix[4] > matrix[2], т.е. намираме, че оттук вече можем да продължим най-дългата подредица. 
  • help[5] = 5 = help[4] + 1, защото help[4] е най-голямо измежду всички help[index] за index < 5 и  matrix[5] > matrix[4]
  • help[6] = 6 = hel[5] + 1,...
  • help[7] = 5 = help[4] + 1, защото help[5] e най-голямото измежду всички help[index] за index < 7 и  matrix[7] > matrix[4]
  • help[8] = 1...
  • help[9] = 7 = help[6] + 1, защото help[6] e най-голямото измежду всички help[index] за index < 9 и  matrix[9] > matrix[6]

Имаш help = {1, 2, 3, 1, 4, 5, 6, 5, 1, 7}

Сега за питаш: Кое е най голямото? - help[9] = 7 => matrix[9] = 33

Откъде е получено 7. От някое с 1 по-малко и по-напред, т.е. 6 => help[6] = 6 и matrix[6] = 22

6 идва пък от 5 => help[5] = 5 и matrix[5] = 17

...

Така получаваш числата в обратен ред. Остава само да ги обърнеш: 1, 2, 3, 5, 17, 22, 33

За времето дето пиша това вече щях да съм написал кода, но според мен така ще ти е по-полезно.

2