Loading...
NonaG avatar NonaG 111 Точки

Задача 8. Поредица от нарастващи елементи от Sample Coding 101 Exam - Jan 2016

Условието на задачата е:

Дадена е редица от n числа: a1, a2, …, an. Да се пресметне дължината на най-дългата нарастваща поредица от последователни елементи в редицата от числа.

Вход

Входните данни се четат от конзолата. На първия ред стои цяло число n (0n1000). На следващите n реда стоят n цели числа в интервала [-10001000]: a1, a2, …, an.

Изход

На конзолата трябва да се отпечата едно число – дължината на най-дългата нарастваща редица.

Примерен вход и изход

вход

изход

 

вход

изход

 

вход

изход

 

вход

изход

3

5

2

4

2

4

2

8

7

6

2

4

1

2

4

4

3

4

5

6

7

8

4

Тестване на решението: https://judge.softuni.bg/Contests/Practice/Index/157#7

Стигнах до 66 точки, моето решение: http://pastebin.com/ELayqDmR

Всъщност, вярвам, че и сама ще си оправя програмата, ако видя принципно каква е правилната идея. Така че ако може да предложите Ваши решения. В този форум вече има веднъж отворена тема за тази задача, но е решена с масиви /или по-скоро е ползвана думата "array", пък дали са масиви.../.Ако имате решение само с материала от Programming Basics, бих се радвала да го видя.

Тагове:
0
Programming Basics 15/12/2016 20:27:54
ThePSXHive avatar ThePSXHive 436 Точки
Best Answer

Аз много рядко ползвам C# (само когато задачата в Judge-a е "оптимизирана" за него, което определено е вярно за немалка част от задачите), затова ще копирам решението си на C, и ще предоставя няколко обяснения. Прочее, Наков много добре обясни решението в едно от видеата в YouTube, но точно този клип в момента не го намирам.

 

#include <stdio.h>


int main()
{
    unsigned int n, length = 0, max_length = 1;

    int current, previous = 1000;

    scanf("%u", &n);

    if (n <= 1)
        printf("%u", n);

    else
    {
        while (n)
        {
            scanf("%d", &current);

            if (previous < current)
            {
                length++;
            }

            else
            {
                length = 1;
            }

            if (max_length < length)
                max_length = length;


            previous = current;

            --n;
        }

        printf("%u", max_length);
        printf("%c", '\n');
    }

    return 0;
}

 

Идеята в случая е, че трябва да знаеш стойността на предишния въведен елемент в поредицата от числа, както и дължината на текущата въведена редица. Първото се осъществява чрез променливата previous, която отначало не притежава стойност, защото преди първия въведен елемент, редицата е празна, и съответно не е възможно да има някаква стойност. Затова е необходимо първата проверка с тази променлива да бъде "неуспешна", защото стойността на текущия (нововъведен) елемент ще бъде присвоена на previous едва след първата итерация на цикъла. Това може да се осъществи по различни начини, като например инициализиране с гранична стойност, като 1000, защото по задание, това е максималната стойност, която може да бъде въведена. Тогава проверката няма да бъде истинна, защото стойността на current не може да бъде 1001, но и не може да бъде 1000, без това да доведе до оценяването на if-a като неистинен. След това присвояваш стойността на текущия елемент (current) на previous.

 

Дори и когато въведената редица съдържа само един елемент, стойността на максималната нарастваща редица не е нула, защото минималната стойност на редицата - щом съществува - е единица. От друга страна, аз лично предпочитам подобни гранични случаи да бъдат dealt with в началото на изпълнението на програмата, което обяснява и тази проверка за единица.

 

Ако стойността на предишният елемент е по-малка от стойността на текущият елемент, увеличаваме броячът length. Тази променлива служи за сравнение на досега намерената дължина, която отговаря на условието в задачата, с тази която има най-голяма стойност. Мисли за нея като за променливата с която намираш елемент с най-голяма стойност в един масив; най-напред започваш с първия елемент, и ако в последствие установиш, че в редицата от елементи има елемент с по-голяма стойност, присвояваш стойността му на променливата, която съдържа максималният елемент. Това е и ролята на max_length в задачата.

 

Ако дотук въведената редица съдържа елементи с нарастващи стойности, чудесно - просто инкрементираме length. Ако ли пък установим, че стойността на предишният елемент е по-голяма от стойността на текущия елемент (случаят с примерната редица [2 3 5 3 4]), присвояваме на length единица, защото е необходимо броенето да започне отначало. Забележи, че на този етап максималната стойност (max_length) ще бъде 3, и вече ще сме открили това, което желаем. Ако стойността на текущият елемент е равна на стойността на предишния елемент (в примерната редица [2 3 4 4]), то отново започваме да броим, но max_length и в този случай ще съдържа правилния резултат.

 

Понеже всички тези операции се реализират само с едно преминаване през колекцията, и разполагаме с две проверки if, сложността е линейна.

0
NonaG avatar NonaG 111 Точки

Аз използвам същата идея, два брояча, първоначално присвоявам крайна стойност на previous / -1000/.

Благодаря, утре ще я почна по-смело, значи съм на прав път. Тази задача ми е най-трудната от всички качени задачи за изпити по Основи на програмирането /без Old Exams, там не знам какво се случва/.

 

 

 

0
NonaG avatar NonaG 111 Точки

Има някакъв проблем с таблицата, но се появява след като публикувам поста. Затова пак:

вход: 3 5 2 4

изход: 2

вход: 4 2 8 7 6

изход: 2

вход: 4 1 2 4 4

изход: 3

вход: 4 5 6 7 8

изход: 4

Входът е на отделни редове.

0
ambiorix avatar ambiorix 640 Точки

Здравей. Твоето решение ми изглежда малко усложнено и не разбирам за какво е втората условна конструкция.

Ето моето решение което е доста описателно мисля, защото променливите имат доста ясни имена и трябва да схванеш идеята: https://github.com/gaydov/Softuni-Programming-Basics/blob/master/Exams/Sample-Coding-101-Exam-Jan-2016/IncreasingElements/IncreasingElements.cs

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