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
Programming Basics 26/03/2016 10:57:48
nakov avatar nakov SoftUni Team Trainer 5295 Точки
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 4482 Точки

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

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

0
sholeto avatar sholeto 93 Точки

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

0
25/03/2016 22:26:43
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.