Loading...
Boyanandreev avatar Boyanandreev 3 Точки

Problem 3 - Merge Trains

Здравейте,

Бих искал да помоля за насоки за задача 3 от STL linear containers и по точно за принтирането на влаковете.

Събирам ги в стек от символи и при мен на VS Studio  минава, но в Judge получавам компилационна грешка.

Явно подхода ми е грешен.

Тагове:
0
C++ Fundamentals
galin_kostadinov avatar galin_kostadinov 166 Точки

Привет!

Обикновено "Compile time error" се получава ако кода ти не може да се компилира, т.е. не може да се създаде изпълним файл, ако изпуснеш ";" ако не си направил някой ипорт "#include <>", ако не си дефинирал някоя фукнция по нагоре в кода, от този ред, в който я извикваш да я използаш. Ако не си направил нещо по стандарт, както ако използаш масив с нефиксирана дължина преди компилацията, а я четеш от конзолата след компилация... Това са някои от нещата, които се сещам, но за да ти кажа със сигурност трябва да видя какво си написал.

Ако грешката е "Run time error" тогава вече ако кода е компилиран нещо логита вътрре не е наред - безкраен цикъл(infinite loop), Null Pointer Exception - т.е. ако се достъпва елемет, който е извън масива, или в случая стека...

За принтирането:

while (!train.empty()) {
    std::cout << train.top() << " ";
    train.pop();
}

Докато стека не ти е празен, за да не получиш " Null Pointer Exception", принтираш. Можа да ко направиш и с train.size() > 0.

Ако използваш опашка:

while (!AB_sequence.empty()) {
    std::cout << AB_sequence.front();
    AB_sequence.pop();
}

Разликата е, че вместо .top() използваш .front()

Поздрави!

1
10/10/2019 09:55:48
spasimira25 avatar spasimira25 25 Точки

Да не отварям нова тема. Та ето моя работещ код, по който имам въпроси.

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include<stack>
#include <queue>
//using namespace std;
std::vector<int> readFunction(std::string passedString){
    std::vector<int> rail;
    std::stringstream iss( passedString );
    int number;
    while ( iss >> number )  {rail.push_back(number);}
    return rail;
}

int main(){

std::vector<int> railA;
std::vector<int> railB;
std::string input;

    getline (std::cin, input);
    railA=readFunction(input);
    getline (std::cin, input);
    railB=readFunction(input);


std::priority_queue<int> Result;
std::vector<char> TrainChar;

    for ( int i : railA) {Result.push(i);}
    for ( int i : railB) {Result.push(i);}
// на следващите 4 реда (до края на while)  се чувствам като маймуна с автомат...
    while (!Result.empty()){
        if ( std::find (railA.begin(), railA.end(), Result.top()) != railA.end() ) {TrainChar.push_back('A');}
        else {TrainChar.push_back('B');}
        Result.pop();
        }
// демек до тук
    for(int n=TrainChar.size()-1; n>=0 ; n--){std::cout<<TrainChar[n];}    std::cout<<std::endl;
    std::vector<int> train (railA.size()+railB.size());
    merge(railA.begin(), railA.end(), railB.begin(), railB.end(), train.begin());
    sort(train.begin(), train.end(),std::greater<int>());
    for(auto n: train){std::cout<<n<<" ";}
}

 

Въпросните неразбираеми редове признавам,  съм ги "преписал"/ модифицирал итн. Та защо в последствие трябва да ги вадя тия вагони, за да имам достъп до тях. Има ли друг начин? Това е едното нещо, което не разбирам. Другото което не разбирам е следното: priority_queue откъде почва да ги вади. Явно при инсърта няма FirstIn или LastIn, тъй като те се наместват, според приоритета - разбъркано. Но пък при махане на елемент, кой елемент маха? Последния или първия? Малко ми беше налучкване - докато наместя АБАБАББ... итн във вектора, пък после и наопъки го пуснах да се печата. Та в общи линии идеята ми е има ли ли вариант при който да използвам функционалноста на priority_queue като първо отпечатам буквите, а после вагоните. Без да създавам нов вектор, и без да мърджвам + сортирам втори път векторите. Може би евентуално дали има начин да вадя елемента и да го записвам в нов вектор. После да си печатам двата вектора в един единствен цикъл. Демек да намаля последните 5 реда на 3.
Поздрави, Тошо.
ПП предварително цъквам по една точка. Нека има. :) Хубав ден.

1
10/10/2019 16:40:47
Filipbg avatar Filipbg 26 Точки

Аз пък да си призная изобщо не я разбрах тази задача. Останалите имаха логика, но тази ме потресе. Ще се опитам да се уча от твоя код. Например това readFunction не помня да сме го взимали на лекция. Както и merge. За sort до колкото знам сортира по големина променливите.

0
galin_kostadinov avatar galin_kostadinov 166 Точки

Привет!

1. Какво е priority_queue:

http://www.cplusplus.com/reference/queue/priority_queue/

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

След като си напълниш дадената опашка, може вместо да правиш накрая merge, sort... да си я запаш в още една друга приоритетна опашка(ако искаш може да си ги прехвъриш в друга структура, като обикновен вектор):

std::priority_queue<int> print = Result; - това тук копира Result.

2. http://www.cplusplus.com/reference/algorithm/find/

std::find(railA.begin(), railA.end(), Result.top())

- това ти обхожда последователно railA, като търси дали дадения елемент Result.top(), т.е. първият ти елемент в опашката се съдържа в дадения векор railA, ако не се съдържа, ти връша railA.end(), т.е. итератор след последия елемент.

Ако не ти е върнал railA.end()  т.е. резултата ти е различен от !=railA.end()

std::find(railA.begin(), railA.end(), Result.top()) != railA.end()

то записваш, че дадения елемент ти е от влак 'A'. Иначе е от влак 'B'. И след това махаш този елемент от опашката:

Result.pop(); - на следваща итерация ще сравняваш с другия най-голям.

3. Принтираш наобратно

std::vector<char> TrainChar

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

4. Принтираш си запазената опашка:

while (!print.empty()) {
    std::cout << print.top() << " ";
    print.pop();
}

Задачата може да се реши и без приоритатна опашка, просто ще имаш повече проверки(railcarA.top() < railcarB.top()), аз съм използвал:

std::stack<int> railcarA;
std::stack<int> railcarB;
std::stack<int> train;
std::queue<char> AB_sequence;

Поздрави!

 

1
10/10/2019 14:34:06
spasimira25 avatar spasimira25 25 Точки

Галине, мерси за разясненията. Особено за 1 и 2 поизнясниха ми се нещата за файнд и приоритетната опашка (името и малко ме подвежда). При опашка трябва да излиза първия елемент на опашката, а той с (поп) излиза последния(ако добре съм разбрал). Та малко да конкретизирам. Тъй като вадим най-горния елемент, как евентуално да сменя приоритета наопъки, че после да не печатам наобратно вектора с чаровете, който правя. Всъщност ако сменя приоритета може изобщо да не правя вектора с чаровете. Докато го пишех, пък се сетих, че някак си буквите и цифрите са ми на обратно, та ни така - ни иначе...

Нищо де, още веднъж мерси.

Филипбг. Тази функиция не сме я взимали, защото аз съм си измислил името :)  Просто при два еднотипни входа, използвам 1 изнесена функция и  си я викам два пъти, за да си направя двата вектора. за релса1 и 2.
Иначе ако беше останало в мейн-а щеше да е двойно като количество, а и така може да се призползва и в други програми за н- на брой инт вектори. (или друг тип с модифициране).

Поздрави. Тошо.


 

1
10/10/2019 17:10:18
j.petrov_90 avatar j.petrov_90 373 Точки

std::priority_queue<> e така наречената структура от данни "heap" или на български - пирамида. Ако ви се чете повече информация ето едно линкче:
https://en.wikipedia.org/wiki/Heap_(data_structure)

Пирамидата обаче сама по себе си е трудна за работа, затова в C++ стандарта са решили да я "скрият" зад опашка.
Защото така или иначе в една опашка можеш:
- да достъпваш само първия елемент 
- да insert-ваш елемент
Т.е. API-а е еднакъв и за queue и за priority_queue а вече функциите са реализирани отдолу по различен начин.

Поздрави

1
spasimira25 avatar spasimira25 25 Точки

Подведе ме наименованиоето, че е от тип heap , което автоматично преведох като "пирамида" или "купчина".  През цялото време си мислех, че ако е пирамида/купчина няма как поп да вади най-долния елемент. Всичко ми беше с налучкване с опит-грешка.  Като видях дървоводната структура (в уйкипедия) ми се изясни как поп-ва всъщност "най-долния" елемент. 
Освен това ме обърква и :
https://en.cppreference.com/w/cpp/container/stack  ---------------------------------------  pop    removes the top element
https://en.cppreference.com/w/cpp/container/priority_queue  ---------------------------  pop    removes the top element
https://en.cppreference.com/w/cpp/container/queue  --------------------------------------- pop     removes the first element

За всеки случай си компилирах нещата от тук: https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/

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