Решавам задача 8 от последното домашно "C# за напреднали" и нещо в примерите не ми е съвсем ясно:
|
Input |
Output |
|
1 1 1 2 2 2 |
1 1 1 |
Според мен 1 1 1 2 2 2 си е цялото ненамаляваща редица и трябва да бъде отпечатано цялото. Аз ли не разбирам условието или примерът не е точен?
Благодаря предварително!
И според мен примерът е неточен. Не е логично просто да отпечатва 1 1 1, защото условието е да създадем longest non-decreasing subsequence, а не longest non-decreasing subsequence of equal elements или нещо подобно...
Това не е единственият грешен пример. Последният отпечатва 3 4 5 6 7 8 9, а би трябвало да бъде 3 4 5 6 7 8 16, защото по условие: In case of several longest non-decreasing sequences, print the leftmost of them.
В крайна сметка, кодът може да се коригира да отпечатва това което ни искат с няколко прости условни конструкции, но няма смисъл от това според мен.
Тук тотално зациклих. Единственото, което ми хрумва, е да се проверят всички възможни редици, да се отсеят намаляващите от тях, после най-дългите и да се види коя стои най в ляво. Това може да стане чрез вложени цикли. Само че проблемът е, че не знаем колко елемента са в групата. Съответно стигам до извода, че начинът това да стане, е рекурсия. Което ми звучи твърде сложно. Досега не съм го правил.
тръгнах да чистя всяко число, което е по-малко от предходното. Но не дава точен отговор. Понякога трябва да се изчистят първите числа и редицата става по-дълга. Някакви идеи как да се реши по-просто?
Аз си послужих с рекурсия, за да реша задачата. Логиката, която измислих е доста проста.
Преминавам през всички възможни комбинации, като ги въвеждам в поредица (array) и просто проверявам дали дадена комбинация е ненамаляваща (чрез цикъл и if).
След това сравнявам текущата поредица и поредицата, която ще съдържа Longest non-decreasing subsequence. На принципа на намирането на максималното или минималното число в редица (също така наричан методът на мехурчето), първоначалната стойност на крайната ми поредица е 0 и всеки път проверявам текущата комбинация дали е с по-голяма дължина и ако е, тя присвоява елементите ѝ.
Общо взето, най-сложното от всичко е да разбереш как работи рекурсията. Може да изгледаш някои видеа от Телерик, в които Наков обяснява това или просто да прочетеш съответната глава от книгата Fundamentals of programming with C#.
Source code: ЛИНК
Това бе последната задача, която ми беше останала от домашните. Доста време загубих с грешните примери.
Примерното решение ми помогна. Благодаря!
Според мен, по логиката на дадените примери когато има еднакви цифри редицата ( output ) трябва да съдържа най-много повтарящите се цифри или най-малката от повтарящите се, в останалите случаи се извежда наи-дългата не-намаляваща се редица. Не съм сигурен и аз може и да греша.
Решението на тази задача е елементарно, стига да измислиш как да го направиш. На мен след проба грешка и много бели косми ми светна лампичката на 3-тия ден. Промених си цялостната концепция за решението и ми отне около 5 минути да напиша кода.
Тъй като точно тази вечер не ми е да правя акаунти в нета, пък и смятам, че така ще е по-полезно за вас, ще ви дам указания какви стъпки се следват:
1. Правите си лист с парснатите числа(може и масив)
2. Правите си нов лист(задължително) и му слагате стойностите на първия лист.
3. Сортирате го (втория).
4. Правите един цикъл да обхожда от 0 до дължината на листа (и двата са с еднаква дължина)
5. За всеки i-ти елемент, който е по-голям в първата матрица от съответстващия във втората му слагате стойност null. (Слагам null-ове, защото ако ги трия директно и ми се размества номерацията в листовете. Жокер - list<int?> = new list<int?> Може и да има по-добър начин...)
6. Триете всички null-ове в първата матрица.
7. Може да ви останат няколко стойности, които са намаляващи (но няма пикови). Елиминирате ги с още един for-loop и принтирате крайния резултат.
ПС: Да, примерите на някои места са грешни. Решена по този начин задачата дава правилни отговори (не като в примерите). Ползвайте дебъгера! Много помага.
Благодаря за решението много помогна, въпреки че вси още не мога да разбера дадените примери иначе по твоя начин се получи :)
Радвам се, че съм от полза. Обаче открих един малък проблем в задачата си: Не е много ефективна при намиране на по-лявата най-дълга серия. Например ако и напишем 1 1 1 3 3 3 2 2 2, тя ще отговори 1 1 1 2 2 2, а трябва да отговори 1 1 1 3 3 3. За съжаление, нямам време и оставям на вас да измислите ефективен метод за осъвършенстване на решението ми. Стискам палци! Като ми дойде музата, ще дам и свое предложение.
Да и на четвъртия пример отговорът трябва да е 1 1 1 3 3 3, а не 2 2 2 2 според това как аз разбирам условието. Така или иначе не ми е съвсем ясно какво искат от нас, но ще скалъпя някакво решение.
Малка грешка имаш - трябва да е 1 1 1 2 2 2 2, защото е 7 знака (с 1 повече)