[C#] Arrays - 18 задача.


10

 

Условие на задачата:
* Write a program that reads an array of integers and removes from it a minimal number of elements in such way that the remaining array is sorted in increasing order. Print the remaining sorted array. Example:
 {6, 1, 4, 3, 0, 3, 6, 4, 5} -> {1, 3, 3, 4, 5}
 
Идея за решение:

I. Заделяме 2 масива с дължина равна на масива, който ще обхождаме:

1-ви масив ще съхванява всички дължини. С други думи всеки елемент от него ще съхранява текущата дължина на най-голяма подредица за него.
2-ри масив ще съхранява индекса на неговия поделемент.

II. Проверяваме всеки елемент с неговите предшественици, за да намерим какви числа са по-малки от него и кое от тях е с най-много предшественици.

III. Взимаме най-голямата дължина и съставяме нов масив, в които ще съхраним нашия резултат.

IV. Отпечатваме резултата.

Моето решение:
http://pastebin.com/McbFpvzb

EDIT:

Поправена и изправна по препоръките на колегата valentinvs.
 




Отговори



0
Леле тая задача я мъча от мноого време.Не искам да гледам решението ти защото искам сам да го намеря.

от iwitass (3695 точки)


8

Аз я реших тази задача по по-различен начин с код на Грей:

http://pastebin.com/xDCnWPL2

Разяснение:

Изхождам от факта, че ако искаме да премахнем най-малко елементи от масива, то това е същото като да намерим този сортиран подмасив, който съдържа най-много елементи спрямо всички останали сортирани подмасиви.

Затова взимам всички възможни подмасиви от зададения ни и го проверявам дали е сортиран. Ако е сортиран, запомням му дължината в една променлива. И така следващия сортиран масив, ак ое по-къс от предишния, го пропускам. Накрая извеждам като резултат най-дългия сортиран подмасив от всички.

1. Декларирам си два метода, единия проверява дали даден масив е сортиран и връща стойности true i false (isSorted), другия просто принтира даден масив (PrintList).

2. Декларирам входа (hardcoded за улеснение) и изхода като два отделни интеджер листа.

3. Използвам алгоритъма за обхождане на всички subsets от дадед set, вслучая подмасиви от масив. Детайлно е обяснен тук:

Subset Sums

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

4. Проверявам дали дължината е по-голяма от предишната дължина, която съм намерил и заедно с това проверявам дали текущия подмасив е сортиран. Ако това е вярно, запаметявам го в листа, който използвам за изход.

5. Принтирам резултата.

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


от ivaylo.kenov (30760 точки)


0
Би ли драснал малко обяснение , защото и без коментари малко трудно го разчитам? :)

от kirov (4821 точки)

0
Готов си. :)

от ivaylo.kenov (30760 точки)


6

Ето и моето решение: source.

Подобно на 16 задача.

Има и по-ефективни алгоритми на задачата Longest increasing subsequence. Решение от колегите от минали години: http://pastebin.com/G8xagrvK.


от jasssonpet (6814 точки)


0
Много сгъчкваш решенията и правиш нещата, за които е казано, че не е добра практика (например нямаш скоби за for и if).

от ScorpS (1542 точки)

0
Свикнал съм да пиша на езици, където for > if > function не е на 7 реда, а на 1.

от jasssonpet (6814 точки)


3

Това е моето решение: http://pastebin.com/QsL8wAeT

И аз използвам Subset Sums, като съм вкарал и 1 допълнително условие следващото число да е по-голямо или равно на предходното. Ако това е изпълнено го добавям към един List и увеличавам брояча с едно.

След като свърша с тази комбинация проверявам дали тя е по-дълга от предходната и ако е ми става основна.

И накрая принтирам List-а, в който си държа основната комбинация.


от ScorpS (1542 точки)


0
Браво за решението колега. Признавам си, че и аз я мъчех ли мъчех по този начин, но нещо все не ми се получаваше. След като видях твоя код видях две грешки които съм допускал-едната от който беше, че не си чистих листа преди пак да го запълня.

от Svetli (280 точки)

0
Не мога да разбера как изчислявате че възможните комбинации са толкова( int length = (2 << array.Length - 1) - 1)? това по някаква формула ли е или? :)

от Pavla (145 точки)



1
Ето и моето решение. Има коментари в самия код:
http://pastebin.com/kGZedUzr

от psabinski (129 точки)


0
Ето http://pastebin.com/uM6xTPjc - само че принтирам останалите числа в обратен ред, който го дразни да си ги тикне в масив отзад-напред :)

от spareva (1375 точки)


0

Тази я направих с динамино оптимиране. Тоест по същият начин като Георги.

Решение


от nikola76 (1250 точки)


1
Аз реших да опитам с List, но не съм съвсем убедена, че работи винаги коректно. Ще се радвам на мнения:
http://pastebin.com/Gk1tdsRN

от anonymous (0 точки)


0
desssssy, не проверяваш всички възможни подмножества по този начин. Тъй като стартирайки от първия елемент и увеличавайки всеки път стартовия индекс с единица, проверяваш само първото подмножество, което отговаря на условието да е във възходящ ред. Примерно, ако имаш масив 1 3 2 2 2 2, ще ти изведе 1 3 като решение, тъй като 3-ката отговаря на условието ти да е по-голяма от предишния елемент.
Обиколи всички подмножества и така намери най-дългото, което е във възходящ ред.

от kdikov (3407 точки)

0
Благодаря, че се отзова! Прав си, а освен това при примера в задачата: {6, 1, 4, 3, 0, 3, 6, 4, 5} изкарва само 1, 3, 6... хайде втората 3ка не е трудно да я направя да се показва, но сега мозъкът ми не може да измисли как точно да проверя най-дългото възможно подмножество и както е в случая, да пропусне 6 и да продължи с 4 и 5... Може би утре ще ми хрумне нещо, но сега блокирах направо. ... искаш да кажеш да правя проверка от индекс 0 до края на листа и за всеки индекс да проверявам дали както следващия, така и всички след него са по-големи...

от anonymous (0 точки)



0

Longest sorted subset

Използвам метода от предишната задача, който ми връща подмножествата с фиксирана дължина.

Извиквам го стартирайки от най-дългите подмножества и намалявам дължината с единица до намиране на сортирано подмножество, тъй като няма смисъл да проверявам първо малките подмножества, при положение, че може да има сортирано подмножество с max - 1 елемента например, което да обезсмисли всички останали проверки.


от kdikov (3407 точки)


2

При вход:

1,2,1,1,1

Изходът от програмата трябва да е: {1, 2}

Все пак търсим коя е най-голямата нарастваща редица

Проверих на всички кода и се оказа,че само "anonymous" (предполгам, че е премахнат студент от системата) няма проблеми, останалите си оправете решенията.

Поздрави ^^


от valentinvs (1327 точки)


0
Тъкмо се зарадвах, че съм си решила задачата и видях твоя пост. Отне ми още 2 часа да я донатъманя. Но сега мисля, че работи и за твоя пример:)Благодаря! http://pastebin.com/ttxDqn3i

от marieta (210 точки)

0
Колега, търсим редица подредена във възходящ ред. Т.е. не е ясно дали 1,1,1 също не е верен отговор.

от loloto (1073 точки)