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

[List] - Homework - Largest Increasing Subsequence

Здравейте, колеги!
Имам въпрос относно задачата от List & Matrices - Homework: * Largest Increasing Subsequence
С условие: Read a list of integers and find the longest increasing subsequence. If several such exist, print, the leftmost.
В Judge-a е на адрес: https://judge.softuni.bg/Contests/Practice/Index/173#11
Кодът, който съм написал е следният: http://pastebin.com/Lx4sJdjz
Дава ми само 70 точки.
Заложил съм и тестовите примери.
Усъмни ме нещо в единият от дадените примери (в слайд 34)
Examples:
Input: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8
Output: 3 4 5 6 7 8 16

По каква логика, последното число от поредицата в изходът е 16 а не 9 ?
Не трябва ли последното число да бъде 9?
Съответно изходната редица: Output: 3 4 5 6 7 8 9
 

annsta avatar annsta 311 Точки

Търси се leftmost поредица. 16 е по-наляво от 9, няма противоречие.

2
VladoGenov avatar VladoGenov 45 Точки

leftmost-поредицата не е ли при намиране на 2 или повече поредици с еднаква дължина, да се вземе най-лявата поредица, а не число от поредицата?
Така, както беше в подобното условие на задача: Max Sequence of Equal Elements (слайд 31)
(If several such exist, print the leftmost.)
Абсолютно същата е и последната част от условие и в тази задача?!
(If several such exist, print, the leftmost.)

0
annsta avatar annsta 311 Точки

Същото е. В случая дължината е еднаква и разликата е само в последния елемент. По-лявата редица е тази е по-ляв последен елемент.

1
VladoGenov avatar VladoGenov 45 Точки

Т.е. за поредици според условието се считат и следните:
Output: 3 4 5 6 7 8 16
и
Output
: 3 4 5 6 7 8 9
а не само тази:
Output: 3 4 5 6 7 8 9

При вход: Input: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8

0
GeorgiGG avatar GeorgiGG 6 Точки

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

Дали някой може да се сети защо.

Ето кода -  http://pastebin.com/yCd6dh6Z

както е даден в Уикипедия никога според мен няма да влезе в while цикъла.

мерси ако някой се сети как да сработи този код

0
20/04/2016 18:06:48
VladoGenov avatar VladoGenov 45 Точки

То във while влиза с една корекция в условието: (low <= high) - добавяне на "=".
В твоят код е: while (low < high)
а според кода в Wiki e while (low <= high)
Но  винаги е по-трудно да "нагласиш" нещо готово и неработещо, отколкото да направиш алгоритъм на чисто.
Моят код, работи (по-горе в линка), като вади всички редици, чиито следващи членове обаче се различават с най-малката възможна разлика.
Скоро ще работя по тази задача, за да я довърша според оригиналното условие и ако още имаш нужда, ще публикувам кода!

0
GeorgiGG avatar GeorgiGG 6 Точки

То още в началото low е 1 a high е 0. Дори и с равно не влиза - явно е неработещо решението.

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

 

-1
netherblood avatar netherblood 94 Точки

Много сложна задача за Programming Fundamentals. Тя се учи в курса по алгоритми и по-специфично Dynamic Programming лекцията. Решава се по много хитър начин, ето го моят код:
http://pastebin.com/WAjFAUez

Ако искаш да разбереш как става, ето линкче към подробно обяснение.
https://www.youtube.com/watch?v=N-AlTemCnMc&t=24m55s

6
AleksanderKostadinov avatar AleksanderKostadinov 12 Точки

Много трудна задача наистина. И аз изкарвах по седемдесет точки на нея и понеже не я разбирам даже и дебъгара не помогна.

Благодаря ти брат.

Срам ме да си призная, но почти цялото ти решение копнах.:(

 

1
sevdalin avatar sevdalin 38 Точки

Здравейте, тъй като тази тема е точно за задачата по-която имам въпрос. Може ли да ви помоля да погледнете моето решение, аз доста се измъчих и заради 1-2 ситуации, се наложи да преправям кода, по не много умен начин, но все пак накрая ми работи с примерите от задачата. Опитах се да намеря задачата в Judge системата ама май вече я няма.

 

Задача код: цък

0
09/02/2017 10:33:20