Loading...
tiapko avatar tiapko 31 Точки

Chapter 7. Arrays - Exercise 6

Здравейте,

От няколко часа се опитвам да реша задачата, но винаги има изключение, което не съм хванал.

Може ли някой, който успешно я е решил, да ми подскаже, тъй като обяснението не успявам да разбера, а и в самия отговор(примерният) на задачата има несъответствие(според мен).

Та задачата е:

Write a program, which finds the maximal sequence of increasing elements in an array arr[n]. It is not necessary the elements to be consecutively placed. E.g.: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} -> {2, 4, 6, 8}. ( тук, най-верният отговор(от трите възможни) мисля, че трябва да е {2, 4, 5, 8}, а не този, който е даден за пример {2, 4, 6, 8}.

Упътването е:

 Задачата може да се реши с два вложени цикъла и допълнителен масив len[0..n-1]. Нека в стойността len[i] пазим дължината на най-дългата нарастваща подредица, която започва някъде в масива (не е важно къде) и завършва с елемента arr[i]. Тогава len[0]=1, a len[x] е максималната сума max(1+len[prev]), където prev<x и arr[prev]<arr[x]. Следвайки дефиницията len[0..n-1] може да се пресметне с два вложени цикъла по следния начин: първият цикъл обхожда масива последователно отляво надясно с водеща променлива x. Вторият цикъл (който е вложен в първия) обхожда масива от началото до позиция x-1 и търси елемент prev с максимална стойност на len[prev], за който arr[prev]<arr[x]. След приключване на търсенето len[x] се инициализира с 1 + най-голямата намерена стойност на len[prev]или с 1, ако такава не е намерена.
Описаният алгоритъм намира дължините на всички максимални нарастващи подредици, завършващи във всеки негов елемент. Най-голямата от тези стойности е дължината на най-дългата нарастваща подредица. Ако трябва да намерим самите елементи съставящи тази максимална нарастваща подредица, можем да започнем от елемента, в който тя завършва (нека той е на индекс x), да го отпечатаме и да търсим предходния елемент (prev). За него е в сила, че prev<x и len[x]=1+len[prev]. Така намирайки и отпечатвайки предходния елемент докато има такъв, можем да намерим елементите съставящи най-дългата нарастваща подредица в обратен ред (от последния към първия).

Та може ли някой, да ми помогне и да каже, кой е найстина правилниятт алгоритъм. Аз се опитвам да я реша спрямо този масив: int[] digitsArray = { 3, 7, 4, 4, 6, 8, 6, 9, 3, 4, 6, 9, 2, 3, 6, 1, 5, 6, 9, 1 } -> където има два верни отговора {3,4,6,8,9} и {2,3,5,6,9} и "по-верният" трябва да е вторият.

 

Тагове:
0
Programming Basics
Le0ne avatar Le0ne 16 Точки

Здравей.
Не прочетох изцяло въпроса ти, но според мен проблема тук е, че не си разбрал задачата. В задачата се иска да се напише програма намираща числова редица с възможен най-голям последен член. Поне така аз го разбирам. Затова и примера е следния: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} -> {2, 4, 6, 8}

В случая 5 не може да е член на аритметична редица(прогресия). :)

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

 

0
tiapko avatar tiapko 31 Точки

Здравей,

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

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