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

List and Matrices: Largest Increasing Subsequence - Неразбрано условие/пример.

Като ментор съм сигурен, че ще получа доста въпроси за последните задачи от тази лекция, затова предварително искам да изясня тази задача. Става въпрос за тази презентация: https://softuni.bg/downloads/svn/programming-basics/Jan-2016/Part-II-Programming-for-Beginners/3.%20Lists-and-Matrices.pptx

Относно задачата на слайд 34. Largest Increasing Subsequence

 

Условието и примера са следните:

Read a list of integers and find the longest increasing subsequence. If several such exist, print, the leftmost. Examples:

Input | Output
1 | 1
7 3 5 8 -1 6 7 | 3 5 6 7
1 2 3 3 4 5 | 1 2 3
1 2 3 3 4 5 5 6 7 8 | 5 6 7 8
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8   | 3 4 5 6 7 8 9

Ако разбирам правилно условието, бих казал, че изхода трябва да е такъв:

Input | Output
1 | 1
7 3 5 8 -1 6 7 | 3 5 6 7
1 2 3 3 4 5 | 1 2 3 4 5
1 2 3 3 4 5 5 6 7 8 | 1 2 3 4 5 6 7 8
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8   | 3 4 5 6 7 8 16

 

Търсим най-голямото нарастващо подмножество. Алгоритъма, който съм използвал преди, когато решавах подобна домашна, ми дава резултатите по-горе, които мисля, че са правилни за даденото условие. Разбира се, преправих го да намира най-дългото нарастващо подмножество, а не най-дългото ненамаляващо подмножество, както беше в моята домашна. Я кажете аз ли не разбирам правилно нещата, или примерите на слайда са сгрешени? Все пак мисля да докладвам за грешка в инстанцията на курса, и този доклад да не стане по моя грешка. :)

 

Edit: На последния пример трябва да е 3 4 5 6 7 8 16, а не 3 4 5 6 7 8 9 както писах първо.

0
Основи на програмирането 26/03/2016 10:57:48
nakov avatar nakov SoftUni Team Trainer 5456 Точки
Best Answer

Здравейте, оправихме грешката. Вече има вярно условие на сайта + коректни тестове в judge системата: https://judge.softuni.bg/Contests/Practice/Index/173#11.

Задачата се решава с програмна техника наречена "динамично оптимиране". Не случайно е със звездичка (само за шампиони). Подробно обяснение как се решава задачата + постъпково описано решение (лаб) има в курса по алгоритми, в темата "Dynamic Programming": https://softuni.bg/trainings/1194/algorithms-september-2015.

Успех с тази задачка. Предупреждавам, че не е много лесна.

Наков

4
Filkolev avatar Filkolev 4428 Точки

Имаше такава задача за домашно от темите Advanced Topics в подготвителното ниво преди. Там примерите бяха малко по-различни, но отново бяха грешни.

Последният ти пример е неточен, отговорът трябва да е: 3 4 5 6 7 8 16

0
sholeto avatar sholeto 93 Точки

Да, там съм го пропуснал, наистина трябва да завършва на 16 понеже се взимат най-левите елементи.

0
25/03/2016 22:26:43