Loading...

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

LoshaPanda avatar LoshaPanda 10 Точки

Mergre Trains{3}

Христос воскресе !

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

Тагове:
0
C++ Fundamentals
MartinBG avatar MartinBG 4803 Точки
Best Answer

Задачата може да се реши по много начини, но предвид лекцията към която е, се предполага, че в решението трябва да се използват само линейни контейнери и да няма собствени класове.

Най-точно към това условие ще се придържа решение със stack.

Решения с priority_queue и/или vector са по-прости, но се бяга от идеята на задачата.

 

Примерен алгоритъм със stack:

- четем двата влака ('A' и 'B'), всеки в собствен stack<int>

- в while(докато има вагони в някой от влаковете) цикъл вземаме този с най-малък номер и го добавяме в нов stack<int>, като принтираме 'A' или 'B' в зависимост от това, от кой влак сме взели вагона ("AABABAB")

- вадим вагоните от сумарния стек и го принтираме на конзолата (11 5 4 3 2 1)

 

Алтернативно, в т.2 вместо да се принтират влаковете директно, може да се добавят в queue<char>, от който да бъдат изведени и изпринтирани след приключване на цикъла.

0
19/04/2020 19:28:54
LoshaPanda avatar LoshaPanda 10 Точки

Извинявам се , MartinBG !

Това ми е кода : https://sourceb.in/c2f663c8f2, но не можах да го принтирам в обратен ред ( принтирах буквите както трябва, но не и числата ). Ще се радвам ако ми помогнете ! Също така ако нещо не ви харесва или можете да съкратите ви моля да ме информирате !

0
20/04/2020 17:26:44
MartinBG avatar MartinBG 4803 Точки

Бих ви препоръчал да ползвате по-съвременни източници при ученето на езика (напр. парсването на входните данни е доста архаично като подход).

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

  • само влак А има оставащи вагони -> A
  • само влак B има оставащи вагони -> B
  • трябва а вземем вагон от влак А -> А
  • трябва да вземем вагон от влак B -> B

За принтиране на елементите от стека, трябва да ги извадим един по един, тъй като стека не поддържа итератори и няма как да се завърти във for цикъл. Ето един начин:

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

 

Това е преправеното решение на задачата (100/100): 

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <algorithm>
#include <iterator>

using Train = std::stack<int>;

Train parseTrain(const std::string& trainString) {
  Train train{ };
  std::istringstream iss{ trainString };
  std::istream_iterator<int> start{ iss }, eof{ };
  std::for_each(start, eof, [&train](const int index) { train.push(index); });
  return train;
}

int main() {
  std::string trainString;

  std::getline(std::cin, trainString);
  Train trainA{ parseTrain(trainString) };

  std::getline(std::cin, trainString);
  Train trainB{ parseTrain(trainString) };

  Train mergedTrain{ };

  while (!trainA.empty() || !trainB.empty()) {
    if (trainA.empty()) {
      std::cout << 'B';
      mergedTrain.push(trainB.top());
      trainB.pop();
    } else if (trainB.empty()) {
      std::cout << 'A';
      mergedTrain.push(trainA.top());
      trainA.pop();
    } else if (trainA.top() < trainB.top()) {
      std::cout << 'A';
      mergedTrain.push(trainA.top());
      trainA.pop();
    } else {
      std::cout << 'B';
      mergedTrain.push(trainB.top());
      trainB.pop();
    }
  }

  std::cout << std::endl;

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

 

0
LoshaPanda avatar LoshaPanda 10 Точки

Извинявам се отново за притеснението, но в алгоритъма който сте написали виждам много непознати функции, символи и т.н. Възможно ли е да проверите този код : https://sourceb.in/03cb2fff2d ( Същия като предния , но с първата ви добавена част - while loop-а ) ? Джъдж ми дава 33/100 , като единия тест е със закаснение, а другите с грешен отговор.

0
MartinBG avatar MartinBG 4803 Точки

Ето примерни входни данни, с които решението не работи:

3 2
77 33 23 1

Резултат:

BAABAB
23 3 23 3 2 1 

 

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

0
LoshaPanda avatar LoshaPanda 10 Точки

MartinBG, благодаря Ви за помощта ! 

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