Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Сезон 2001 - 2002
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2000 - 2001
Задача 1 - БАНКА - Анализ

          Не случайно големият швейцарски информатик Никлаус Вирт постави за заглавие на книгата си формулата “Алгоритми + структури данни = програми”. За създаването на качествена програма, изборът на подходящи структури от данни е не по-малко важен от избора на добър алгоритъм. Затова и тази година първата задача в Конкурса трябваше да провери умението на участниците да си служат с сложни структури от данни за да получават ефективни решения.  
          Преди да се спрем по същество на задачата да обърнем внимание на един терминологичен нюанс. Заедно с понятието структура от данни е добре да се разглежда и понятието абстрактен тип . Първото от тях използваме, когато искаме да подчертаем начина по които данните са организирани (структурирани) в паметта на компютъра, а второто – когато не се интересуваме от реалното разположение на данните в паметта, а по-скоро от важни за прилагания алгоритъм абстрактни (математически) свойства на данните и най-вече операциите, които ще трябва да извършваме с тях.
           Като пример да разгледаме абстрактния тип приоритетна опашка, който ще ни е необходим за решаването на задачата и няколко различни начина да представим този абстрактен тип в конкретни структури от данни. Приоритетната опашка е съвкупност от елементи O1,O2,…,On от някакъв тип, като за всеки елемент Oi е зададена числова характеристика Pi, която наричаме приоритет. Различните елементи имат различни приоритети (така е в задачата, но в общия случай това не е толкова важно). Колкото по-голямо е числото Pi, толкова по-висок е приоритетът на Oi. За приоритетната опашка съществени са операциите добавяне на нов елемент със зададен приоритет и премахване на елемента с най-висок приоритет .  
           Най-простият начин за представяне на приоритетна опашка е, да се използва достатъчно голям масив Q за съхраняване на елементите й и цяла променлива M показваща техния брой в момента. Текущо намиращите се в приоритетната опашка елементи се съхраняват в първите М елемента на Q. С такава структура на данните операцията добавяне се извършва със сложност О(1)– новият елемент се поставя на първото свободно място в масива и съдържанието на брояча М се увеличава с 1. За премахването на елемента с най-висок приоритет, обаче ще са необходими O(M) операции – едно преглеждане на елементите за да се определи този с най-висок приоритет и още едно за да се премахне този елемент и следващите го в масива да преминат една позиция напред, за да се съхрани правилността на представянето.
           Разбира се, че към структурата може да се добави допълнителното изискване текущо намиращите се в Q елементи да са подредени в намаляващ ред на приоритетите си. Това изобщо не подобрява нещата. За да се “вмъкне” новият елемент на подходящото място в сортираната последователност са необходими O(M) операции. Вярно е, че сега елементът с най-висок приоритет е в първия елемент на масива, но след премахването му всички останали елементи трябва да преминат с една позиция напред, за да се съхрани правилността на представянето. Следователно в този случай и добавянето и премахването ще се реализират със сложност O(M).
          Тази неприятност може да се избегне ако наличните в опашката елементи не се държат в първите М елемента на масива, а могат да са в кои да е М последователни елементи на Q, включително последните X и първите М-X. В този случай, вместо броя М, в структурата от данни се използват два индекса S и Е за началото и края на опашката. При това за премахване на елемента с най-висок приоритет е достатъчно само да се увеличи S с единица и така тази операция вече ще се изпълнява със сложност О(1). Разбира се, че увеличаването на двата индекса с единица винаги става по модул броя на елементите на Q, за да се постигне “плавно преминаване” на опашката през края на масива.
          Както се вижда, със сортиране или без сортиране на елементите, ако едната от операциите на приоритетната опашка реализирахме със сложност О(1), то другата реализирахме със сложност О(M). За алгоритми които изискват статистически приблизително равен брой от двете операции с приоритетната опашка (както е в разглежданата задача) сложността на алгоритъма ще бъде О(M).
          Известна техника за подобряване на бързодействието на алгоритми, използващи две “противоположни” операции е да се реализира всяка от тези операции със сложност по-голяма от O(1), но по-малка от O(M). За приоритетна опашка това може да стане като се използва структурата от данни пирамида . С използване на тази структура и двете операции на приоритетната опашка се реализират със сложност O(logM) и така алгоритъм, използващи тези две операции приблизително равен брой пъти, ще има същата сложност. (Подробности, свързани със същността и реализацията на структурата пирамида, може да намерите в практически всяка книга по алгоритми.)
          За решението на разглежданата задача е необходим още един абстрактен тип, който да наречем сортиран цикличен списък от приоритетни опашки. За всеки клон, от който има необработени заявки, списъкът съдържа по една приоритетна опашка. Приоритетните опашки в списъка, да означим броя им в определен момент с N, са подредени по номерата на клоновете, като списъкът е циклически свързан – след опашката на клона с най-висок за момента номер следва опашката на клона с най-нисък за момента номер. Естествени операции за този абстрактен тип са: добавянето на нова опашка – когато се появи заявка от клон, за който в момента няма необслужена заявка, премахване на опашка – когато за съответния клон не е останала необслужена заявка и намиране на следваща опашка – когато трябва да се определи поредната заявка, която ще бъде обслужена.
           При обичайната реализация на списъка – динамичен двойно-свързан циклически списък -  операциите премахване и намиране на следваща опашка се реализират със сложност О(1), но операцията добавяне ще изисква О(N) стъпки за да се намери мястото на новата опашка в сортирания списък.  Операцията добавяне може да се реализира много по-бързо, ако можем бързо да намираме елемента от списъка пред (или след) който трябва да вмъкнем новата приоритетна опашка. За целта може да се използват различни подходи. Например, с балансирано по височина дърво за двоично търсене, можем да намерим съответния елемент от списъка с O(logN) операции.
          В някои езици (например С) се предлагат готови реализации на споменатите абстрактни типове. Най-използвана е библиотеката STL, в която приоритетната опашка е реализирана както е описано по-горе с пирамида, а вместо двойно-свързан списък успешно се използва абстрактния тип множество. Разбира се, това съвсем не е познатата ни от Pascal структура, а доста сложно имплементиран абстрактен тип, включващ много бърза операция за намиране на следващ елемент.

Анализи на решения изпратени от участници:

Очаквайте скоро!

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.