Софтуерно Инженерство
Loading...
+ Нов въпрос
Boyanandreev avatar Boyanandreev 3 Точки

Problem 3 - Merge Trains

Здравейте,

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

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

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

Тагове:
0
C++ Fundamentals
dmartinov avatar dmartinov 33 Точки

Не съм сигурен какви насоки точно да ти дам. Мога да ти кажа моята концепция - чета входа, след което го ползвам istringstream, за да вкарвам елементите в два вектора (trackA и trackB). После правя priority_queue и го пълня с for цикъл обхождайки елементите на векторите. След това започвам да вадя елемент по елемент от priority_queue-то и си ги добавям в един стринг. В зависимост от това дали става въпрос за елемент от trackA или trackB, push-вам в един стак A или Б. Като приключи тоя цикъл принтирам на конзолата елемента от стака, попвам го и така докато не го изпразня. Накрая принтирам на конзолата стринга който съм екстрактнал от priority_queue-то и с това задачата приключва

1
galin_kostadinov avatar galin_kostadinov 131 Точки

Привет!

Обикновено "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 6 Точки

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

0
galin_kostadinov avatar galin_kostadinov 131 Точки

Привет!

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