[BOOK] Домашно Arrays - задача 6


0

Напишете програма, която намира максималната подредица от нарастващи елементи в масив arr[n]. Елементите може и да не са последователни. Пример: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} -> {2, 4, 6, 8}.


Някой може ли да я реши? И по възможност реализирайки упътването, което е: 
 

Задачата може да се реши с два вложени цикъла и допълнителен
масив len[0..n-1]. Нека в стойността len[i] пазим дължината на
най-дългата нарастваща подредица, която започва някъде в масива
(не е важно къде) и завършва с елемента arr[i]. Тогава len[0]=1, a
len[x] е максималната сума max(1 + len[prev]), където prev < x и
arr[prev] < arr[x]. Следвайки дефиницията len[0..n-1] може да се пресметне с два вложени цикъла по следния начин: първият цикъл обхожда масива последователно отляво надясно с водеща променлива x. Вторият цикъл (който е вложен в първия) обхожда масива от началото до позиция x-1 и търси елемент prev с максимална стойност на len[prev], за който arr[prev] < arr[x]. След приключване на търсенето len[x] се инициализира с 1 + най-голямата намерена стойност на len[prev] или с 1, ако такава не е намерена.
Описаният алгоритъм намира дължините на всички максимални нарастващи подредици, завършващи във всеки негов елемент. Най-голямата от тези стойности е дължината на най-дългата нарастваща подредица. Ако трябва да намерим самите елементи съставящи тази максимална нарастваща подредица, можем да започнем от елемента, в който тя завършва (нека той е на индекс x), да го отпечатаме и да търсим предходния елемент (prev). За него е в сила, че prev < x и len[x] = 1+len[prev]. Така намирайки и отпечатвайки предходния елемент докато има такъв, можем да намерим елементите съставящи най-дългата нарастваща подредица в обратен ред (от последния към първия).

 




Отговори



2

Здравей,

Опитах се да напиша решение максимално близо до това, което е показано в упътването. Надявам се решението да е правилно и разбираемо.

Алгоритъмът всъщност търси по-малки числа назад в масива и изчислява дължината на редица с въпросните по-малки елементи. Например ако имаме масива: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4}

Когато сме на елемента 5ия елемент - '4': Търсисм назад виждаме елемента '2'. С него може да бъде образувана последователност: 4 -> 2;  В последствие, при елемент 7 виждаме че може да бъде образувана последователност с елементите 6 или 4 или 2, но тъй като в масива с дължинете, пише че с елемент 4 вече е образувана една последователност, а именно (4 - > 2). То 7 ще се комбинира с нея и ще имаме 7 -> 4 -> 2. И в масива за дължините ще запишем че за съответния елемент '7' имаме редица с дължина  2 + дължината на редицата с '4', тоест 2 + 1 = 3.

А ето и решението на задачата: http://pastebin.com/F3xCs3Rw

И направих и още едно решение, чиито код е доста неприятен. Него направих с цел да се опитам да онагледя на конзолата как работи алгоритъма: http://pastebin.com/9gzX2tAm

Надявам се да съм помогнал с разрешаването на проблема, решението не ми се вижда сложно, но да обясня защо това решение работи така доста ме затруднява.

 


от kalimar (125 точки)


0
Здравейте колега, при множеството { 9, 6, 2, 7, 4, 7, 5, 6, 7, 8, 4 } би трябвало да изведе 2 -> 4 -> 5 -> 6 -> 7 -> 8, но всъщност извежда 2 -> 4 - > 5 -> 6.
Програмата всъщност го намира (9: number: 8 - lenght: 6 sequence: 8 7 6 5 4 2), но не извежда правилната редица.
При { 1, 2, 3, 4, 5, 6, 7 } извежда { 2, 3, 4, 5, 6, 7 }
При втората програма, при множеството { 9, 6, 2, 5, 4, 7 } би трябвало да намери {2, 4, 7} и {2, 5, 7}, но намира само {2, 4, 7}.

от martin.nikolov (4535 точки)

0
Здравейте, в действителност имаше грешка при функцията за изписване на максималната последователност, мисля че я поправих. Относно последния пример програмата не показва всички последователности заради проверката: len[i] + 1 > len[x] Направих така че да показва дори и тези последователности които не са по-дълги от вече намерените. Линковете в оригиналният отговор са подменени може да тествате решенията там. Благодаря за обратната връзка!

от kalimar (125 точки)


1

http://pastebin.com/pxb5YJSP Ето моя варянт. Пълним едни масив, сортираме го. И почваме да печатим отзад напред до въвведената граница.