Премини към съдържанието

Архивирана тема

Темата е твърде стара и е архивирана. Не можете да добавяте нови отговори в нея, но винаги можете да публикувате нова тема, в която да продължи дискусията. Регистрирайте се или влезте във вашия профил за да публикувате нова тема.

snaksa

Забързване на алгоритъм

Препоръчан отговор


Здравейте! Тези дни реших да реша някои от задачите, които се се паднали на националните олимпиади по програмиране. Проблемът ми е, че за повечето успявам да измисля алгоритъм, но не достатъчно оптимален. Твърде наивен. Например днес се мъча с ето тази задача, която е за 12 клас:
 

Задача A2. САМОТНА ПЕЙКА

Пейката в метрото има n места, номерирани с числата от 1 до n. В началото пейката е празна – всичките n места са свободни. Последователно, един по един, през входа на метрото влизат пътници. Всеки влязъл човек сяда в центъра на първата максимална последователност от свободни места. В случай, че максималната последователност от свободни места съдържа четен брой места, човекът сяда на мястото с по-малък номер измежду двете централни места на последователността.

Например, ако пейката има n = 6 места, първият човек сяда на място с номер 3, защото има единствена максимална последователност от свободни места – от 1 до 6, която съдържа четен брой места, и 3 е мястото с по-малък номер измежду двете централни места (3 и 4) на тази последователност. За втория човек има две последователности от свободни места – от място 1 до място 2 и от място 4 до място 6. Последователността от място 4 до място 6 е максимална, съдържаща 3 места, и вторият човек сяда в центъра  – място 5. Третият човек сяда на място с номер 1 – „централното” за последователността от свободни места от първо до второ, четвъртият човек – на място 2, петият – на място 4 и шестият – на място 6.

Напишете програма bench, която определя мястото, на което сяда определен човек, и кой човек сяда на предварително зададено място.

Вход

От стандартният вход се въвежда един ред с три цели чиста: n i p, разделени с интервал, където:

  • n е общият брой места на пейката;
  • i е номер на човек, влязъл в метрото (първият влязъл има номер 1);
  • p представлява номер на място от пейката.

 Изход

Програмата трябва да извежда на стандартния изход един ред с две цели числа q и j, разделени с интервал, за които е изпълнено, че:

  • i-тият човек, влязъл в метрото сяда на място с номер q и
  • j-тият човек, влязъл в метрото сяда на място с номер p.

Ограничения

1 ≤ i, pn ≤ 1016

В 20% от тестовете е изпълнено n ≤ 10000.

В други 30% от тестовете, n = 2k-1, където k>0 е цяло число.

Пример 1   Пример 2

Вход   Вход

6 1 5   10 2 6

Изход   Изход

3 2                                                 8 5

 

 

Накратко имам една пейка в метрото. Всеки нов пътник сяда точно в средата на най-дългото място от свободни седалки. И така докато всички седалки бъдат запълнени. Трябва да намеря мястото, на което ще седнe даден пореден пътник и кой поред пътник ще седне на дадено място.

 

Алгоритъма, който аз успях да напиша е твърде елементарен. При всяко влизане на нов пътник аз обхождам масива с n седалки и търся най-дългата свободна редица. След това маркирам средната седалка на тази редица като използвана и така се получават две отделни редици. Но този метод е твърде бавен. Както пише в условието n може да бъде до 10^16, а аз не мога да направя толкова голям масив. А и да успея ще ми трябва доста време за да го обходя.

Чуда се дали знаете за някаква техника, която да ми помогне. Може би трябва да се използва някаква формула? И също ще се радвам, ако можете да ми кажете как да започна да измислям добри алгоритми.. Ако можете да ми препоръчате някаква книга, която да развива мисленето на човека или нещо подобно? Защото няма как да стана добър програмист без да прочета нещо от някъде нали :D В книгите от които учих C++ бяха дадени само основни примери и задачи, но не и по-трудни проблеми като този. :)

Поздрави!

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Чуда се дали знаете за някаква техника, която да ми помогне. Може би трябва да се използва някаква формула? И също ще се радвам, ако можете да ми кажете как да започна да измислям добри алгоритми.. Ако можете да ми препоръчате някаква книга, която да развива мисленето на човека или нещо подобно? Защото няма как да стана добър програмист без да прочета нещо от някъде нали :D В книгите от които учих C++ бяха дадени само основни примери и задачи, но не и по-трудни проблеми като този. :)

Мога да добавя още едно нещо към препоръките на soundtracker, които са много добри. И това е, че добър, във каквото и да е, се става със знания и опит. Ако целта са ти алгоритми и задачи, освен четенето на теория, бих ти препоръчал да си намериш решени задачи и много хубаво да ги разбереш, да осмислиш мотивите за избор на решението и самата му реализация. Да го кажа по такъв начин: ако знаеш решенията на 50 различни проблема, като дойде 51ият, в най-лошия случай ще знаеш 50 възможни начина, които директно да отхвърлиш. Но по-вероятно е, поне нещо от тях да те насочи към решението.

Относно задачата.

Мисля, че и двамата имате една и съща солидна грешка в подхода. При положение, че имате директно и еднозначно дефинирана редица и то само от 2 числа - големината на пейката и номера на човека или съответно седалката, вие реално знаете, къде е той. Няма нужда да го търсите, независимо с колко сложен или ефективен метод. Е, може би не е толкова очевидно, но... Не мисля да решавам задачата, само ще продължа подсказката от условието.

вземаме 30те % в които n = 2k -1,  Това не е случайна стойност. Всъщност това е best-case на задачата. Тоест:

  • проверката дали число е от вида 2k -1 е елементарна
  • първият седнал ще раздели пейката на две равни половини и то забележете как:
  • всяка половина ще е (2k -1 - 1) / 2 = (2k - 2) / 2 = 2k-1 - 1 - т.е число от същия вид.
  • тоест първият човек ще я раздели на 2, първите 3ма на 4, първите 7 на 8 и т.н равни части. Не е ли прекрасно?
  • намираме колко е броят на хората, които ще разделят пейката по такъв начин преди да седне нашия човек: това е най-голямата стойност 2m -1 < i, Може с побитови операции или логаритъм с основа 2 - избирате си.
  • към момента след сядане на 2m -1вия човек, на пейката има 2m празни места, всяко от по (n - 2m -1) / 2m седалки.
  • Е те са еднакви, значи просто всеки следващ ще сяда в средата на първата свободна, по ред.
  • значи нашия човек ще седне в средата на (i - 2m -1) % 2m -тото празно място (% -  остатък от деленето).
  • Това дотук се разписва в формула на 1 ред.

От мен толкова. :)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

За да продължа обаче по-нататък с помощта, трябва да ми отговорите на следните въпроси:

1) Знаете ли какво са Binary Tree и Heap ? Можете ли да боравите с тях и знаете ли как ?

2) Знаете ли какво е Balanced Tree и каква е идеята, заложено в него ?

3) Знаете ли какво е B-Tree - какво представлява и с какво се различава от горното ?

4) Знаете ли какво представлява алгоритъма Alpha-Beta Pruning ? Той ще е необходим за оптимизирането на работата на алгоритъма Ви.

Мерси за предложените алгоритми. 1) и 2) знам какво представляват, но за 3) и 4) не мога да кажа същото. Ще ги разгледам по-подробно :)

 

 

Други, които мога да дам като пример са тези две:

Основи на алгоритмите

Алгоритми на С

За съжаление втората книга не мога да я намеря в наличност. Първата съм я разглеждал и аз, но ми се стори, че по-голямата част от кода е на Pascal и може би малко по-трудно ще осмисля съдържанието. Може би някоя книга, която използва C/C++, C# или Java ще е по-добър избор :)

 

 

@flare, мерси много за предложената формула. Ще се опитам да я реализирам. А откъде мога да намеря решени задачи? Може би можете да ми препоръчате някоя книга или сайт?  :)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Коментар-допълнение в телеграфен стил:

 

Първата книга е много добра и не отстъпва на чуждестранните такива. Третата я има на английски, ако ви устройва -- Algorithms in C. Акцентира повече върху имплементацията, отколкото върху теорията и анализа. Introduction to Algorithms  е класическа.

 

Освен това, курсовете на Масачузетския институт може да са от полза: http://ocw.mit.edu


Сподели този отговор


Линк към този отговор
Сподели в други сайтове

@flare, мерси много за предложената формула. Ще се опитам да я реализирам.

Че тя е реализирана. По скоро помисли, как да я разшириш за случаите, когато n != 2k -1...

 

А откъде мога да намеря решени задачи?

Google.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

  • Разглеждащи това в момента   0 потребители

    Няма регистрирани потребители разглеждащи тази страница.

  • Горещи теми в момента

  • Подобни теми

    • от m.dimitrov98
      Здравейте, имам ето това задание:
      Големи числа се наричат цели положителни числа с К цифри. Големите цели числа могат да се представят с помощта на линеен едносвързан списък, всеки елемент на който съдържа точно една цифра от числото. Дадени са две големи цели числа N1 и N2 (до 100 цифри). Да се напишат програмни фрагменти за :
                a. Представяне на числата чрез списъци;
                b. Сумиране на две големи цели числа.
      Бях го направил с две функции create1 и create2 и две променливи N1 и N2, но професорката иска да е само един и колкото числа искам да въведа толкова пъти да извикам един и същ create. Опитах по този начин но при започване на въвеждането на второто число програмата блокира. Бих бил благодарен ако някой помогне.
      Ето и до къде съм стигнал.
       
       
      #include <iostream> using namespace std; struct chislo{ int N; chislo* next; }; typedef chislo* Point; Point Head; void Create(Point &Head) { Point Last, P; Last=NULL; int brc=0; int br=0; cout<<"Колко цифри ще е числото?: "; cin>>br; while (brc != br) { P = new chislo; brc++; cout << brc <<" цифра на числото: "; cin >> P->N; P->next=NULL; if (Head == NULL) Head = P; else Last->next = P; Last = P; } } void Traverse(Point P){ cout<<"Числото е:"; while (P !=NULL) { cout<<P->N; P = P->next; } cout<<endl; } int main() { system("chcp 1251"); Point Head = NULL; Create(Head); Create(Head); Traverse(Head); Traverse(Head); }  
    • от Georgi Kirchev
      Здравейте , дадоха ми да правя курсова задача по Визуално програмиране , но не мога да я направя , а имам срок до четвъртък - 10.01.2019 
      програмираме със Visual Studio 2010/13 на MFC Standart , Single Document 
      Ще съм изключително благодарен , ако някой успее да ми помогне. 

      Условието е следното: 
      Да се състави еднодокументно приложение с архитектура документ - изглед.
       - Добавете бутон който трябва да активира функцията , както и елемента Hello от менюто 
       - Добавете контекстно-ориентирано меню към програмата , което използва падащо меню Help като скрито

      Във файл да се съхраняват и четат данни, които да се въвеждат чрез диалогова кутия , която се вика чрез 
       - ляв бутон на мишката.
       - опция от менюто .
       - клавишни ускорители.
       - бутон от инструменталната лента.
      В диалоговата кутия да има:
       - текстово поле за въвеждане на текст.
       - рамка със списък за шрифтове.
       - групова рамка.
       - бутон за приключване.

      Предварително благодаря , ако някой се захване да ми окаже помощ. 
       
    • от lullabies
      Съставете програма с меню за избор на функция за:
      a)       Въвеждане от клавиатурата в масив и файл /чрез допълване/ данните за К  вложители в банка /К<=50/: име BLV USD EURO. Извеждане текущото съдържание на масива /файла/ на екран
      b)      Извеждане на справки за
      -          Вложител по въведено име /със запитване на нова справка – диалогова процедура/
      -          Всичко вложители с обща сума на влогове /в лева/ над зададена и според текущите курсове на валутата
      c)       Пренареждане на данните за вложители във възходящ ред според влоговете в USB /или  EURO или BLV – по избор/ и извеждането им на екрана
      Главната функция main – с меню за избор на функция задължително да се използва. Използване на главни променливи или функции с предаване на параметри – по избор.
    • от Alexandar Jelev
      Здравейте, искам  да попитам някой може ли да ми помогне за курсовата задача, ще му бъда изключително благодарен? :)
      Задачата е следната:
      Съставете програма с функции за:
      а) Въвеждане от клавиатура във файл и в масив ( чрез добавяне) данни за автобусни превози ( до 35 ) - Автогара Варна: маршрут, дата (1 до 31), номер на автобуса, фамилия на водача, брой пътници, цена на съответните билети, обща сума на билетите - през месец юли. Извеждане текущото съдържание на масива (файла) на екран;
      б) Извеждане на екран справка за всички превози през избран ден от месеца ( със запитване за нова справка);
      в) Извеждане на екран номерата на автобусите и общата сума на билетите от превозите, извършени с тях, подредени в низходящ ред по сумата.
                   Главна функция main() -с меню  за избор на функции и проврка за състоянието на данните.  Използване на функции с предаване на параметри.
       
    • от Plamy Gerova
      Здравейте, може ли помощ за курсовата ми задача?
      съставете програма с функции за:
      а) въвеждане от клавиатурата във файл и в масив( чрез добавяне) данни за морски пътувания (до 25)- Морска гара Варна: маршрут, кораб-име, име на капитан, цени на билетите- I,II класа, брой пасажери в съответната класа, обща сума на продадените билети- през избран месец от годината.Извеждане текущото съдържание на масива(файла) на екрана.
      б) извеждане на екран данните за превозите на кораб по въведено от клавиатурата име на кораб(със запитване за справка)
      в) извеждане на екран данните за морско пътуване с най- голяма обща сума на продадени билети.
      Главна функция main()- с меня за избор на функции и проверка за състоянието та данните.Използване на локални променливи и функции с предаване на параметри. 
       
  • Дарение

×

Информация

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