Не могу найти причину бесконечного цикла - PullRequest
Новая
       12

Не могу найти причину бесконечного цикла

0 голосов
/ 18 марта 2011

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

/*
some info:
"course" is a class i created
   some of the member function are:
      bool fall()           // does the class run in the fall?
      bool spring()         // does the class run in the spring?
      string name()         // name of this course
      ...                   // plenty of irrelevant stuff


"classes" is a vector of courses
"vector <vector <course> > out" has n (generally 8) elements

"vector <string> taken" records the names of the courses that have been taken

bool prereq_taken(course C, vector <string> & taken) checks if all the 
prerequisites of the course are taken

even semesters are fall and odd are spring

*/


int x = 0, semester = 0;
while ((classes.size() > 0)){
    x %= classes.size();

if (prereq_taken(classes[x], taken)){                                            // checks if all of the prerequisites in the course have already been taken

    // my test condition
    //if ((semester % 2 == 0) && classes[x].fall() && (!classes[x].spring())){

    // Ben's condtion
    if ((semester & 1)? classes[x].spring(): classes[x].fall()){

    // my retardedly long all-in-one condition
    /*if (
        (((!(semester % 2)) && classes[x].fall() && (!classes[x].spring()))    // if fall and is only fall class or
        || ((semester % 2) && (!classes[x].fall()) && classes[x].spring())     // if spring and is only spring class
        || (classes[x].fall() && classes[x].spring())                          // if any semester class

        )                                                                      // and there is class space and enough credit space
        && (((out[semester].size() + 1) < classes_per_semester) && ((credits[semester] + classes[x].credits()) < credits_per_semester))) {
    */
        taken.push_back(classes[x].name());                                      // put class name into vector of takens
        out[semester].push_back(classes[x]);                                     // put class into final output
        classes.erase(classes.begin() + x);                                      // remove from class list
    }
    else
        x++;

 }
    else
        x++;                                                                         // else go to next class

    if ((out[semester].size() + 1) > classes_per_semester)
        semester++;
}

Я пытаюсь выполнить все данные (и выполнить цикл) до тех пор, пока все курсы не будут правильно размещены

по какой-то причине, когда я добавлю оператор if сзвезды вокруг него, цикл продолжается вечно.однако без него и else (но с внутренним содержимым, все еще находящимся в коде) код завершится.Зачем?Является ли C ++ логическая математика чем-то отличным от Python (что имеет значение для этого кода)?

Если я неясен каким-либо образом, пожалуйста, скажите, что уточнить

Ответы [ 3 ]

2 голосов
/ 18 марта 2011

Как вы думаете, что это делает? 

if ((x == classes.size()))
    x %= classes.size();

Назначение такое же, как: 

   x = x % classes.size();

Но вы только что узнали x == classes.size() так 

   x = classes.size() % classes.size();

А для любого N, N%N равен нулю, что означает 

if ((x == classes.size()))
    x = 0;

Это то, что вы хотите?

Рассматриваемый if способен работать только с классами, предлагаемыми только осенью. Возможно, вы хотели: 

if ((semester & 1)? classes[x].spring(): classes[x].fall()) { ... }

Может быть, это будет работать? 

int x = 0, semester = 0, scheduled = 0;
vector<string> completed;
while ((classes.size() > 0)) {
    if (classes.size() == x) {
        x = 0;
        cout << "Checked all classes and scheduled " << scheduled << endl;
        if (0 == scheduled) {
            ++semester;
            completed = taken;
        }
        scheduled = 0;
    }

    if (prereq_taken(classes[x], completed)) {
        if ((semester & 1)? classes[x].spring(): classes[x].fall()) {
            if (credits[semester] + classes[x].credits() <= credits_per_semester) {
                taken.push_back(classes[x].name());
                out[semester].push_back(classes[x]);
                credits[semester] += classes[x].credits();
                cout << classes[x].name() << " will be taken in semester " << semester << " for " << classes[x].credits() << " credits" << endl;
                classes.erase(classes.begin() + x);
                scheduled++;
            }
            else {
               cout << classes[x].name() << " can't be taken in semester " << semester << " : overload on credits" << endl;
               x++;
            }
        }
        else {
            cout << classes[x].name() << " can't be taken in semester " << semester << " : not offered" << endl;
            x++;
        }    
     }
     else {
        cout << classes[x].name() << " can't be taken in semester " << semester << " : not offered" << endl;
        x++;                                                                         // 
     }

     if (out[semester].size() >= classes_per_semester || credits[semester] >= credits_per_semester) {
        cout << "Full load reached for semester " << semester << endl;
        semester++;
        completed = taken;
     }
}
2 голосов
/ 18 марта 2011

Я думаю, проблема в том, что вы никогда не сможете выполнить требования для всех курсов.Звездный код 

if ((semester % 2 == 0) && classes[x].fall() && (!classes[x].spring())){

позволяет проходить только осенние курсы.Если требуемый курс доступен только весной, ваш код попытается назначить курсы более чем без возможности добавления новых курсов из-за пропущенных требований.

Теперь давайте предположим, что вы исправили if и разрешитетребования курса должны быть выполнены.Вы все равно зависите от правильности данных (то есть от циклических зависимостей курса).Я предлагаю почитать о топологической сортировке , если вы с ней уже не знакомы.Простой (хотя и неэффективный) способ справиться с возможностью бесконечных циклов заключается в использовании наблюдения, что на каждом шаге по всему списку курсов должен был быть удален хотя бы один курс из списка.Таким образом, вы могли бы написать что-то вроде: 

int x = 0, semester = 0, prev_size = classes.size();
while ((classes.size() > 0)){
    if (x == classes.size()){
        x = 0;
        if( classes.size() == prev_size ) { // no courses removed in the last cycle
            // signal error
            break;
        }
        else
            prev_size = classes.size();
    }
    ...
}
1 голос
/ 18 марта 2011

& само по себе является побитовым и. Вы хотите &&. Эта часть внутри оператора if, вероятно, никогда не достигается, поэтому размер не изменяется.

...