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
 

0
Programming Basics
annsta avatar annsta 305 Точки

Търси се 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 305 Точки

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

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 95 Точки

Много сложна задача за 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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.