Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > помогите, пожалуйста найти ошибку

Автор: Тавасилек 28.5.2016, 17:43

Здравствуйте, помогите, пожалуйста. Есть задача: Есть N станков и 2 работы. Каждая работа состоит из Si этапов. Этап характеризуется парой (n, t) чисел, где n — номер станка, а t — продолжительность этапа. Для каждой работы порядок этапов строго задан. Любой этап можно приостановить в любой момент и позже продолжить с того же момента. В каждый момент времени любая работа может выполняться только на одном станке и любой станок может выполнять только одну работу. Необходимо составить такое расписание, чтобы все работы были выполнены за минимальное время. Формат входного файла В первой строке содержится единственное число N. В следующих двух строках на первом месте записано число Si, а за ним — Si пар (n, t) через пробел. И мое решение: Код #include <iostream> #include <fstream> #include <vector> using namespace std; struct Para {     int x;     int y;     Para(int t=0,int s=0):x(t),y(s) {} }; int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2); int main() {     ifstream fin("input.txt");     int n,a1,a2,b,c,i,j;     fin >> n;     vector<Para> v1,v2;     ofstream fout("output.txt");     int ans = 0;     Para r1,r2;     fin >> a1;     for(j=0;j<a1;j++) {         fin >> b;         fin >> c;         Para q(b,c);         v1.push_back(q);     }     fin >> a2;     for(j=0;j<a2;j++) {         fin >> b;         fin >> c;         Para q(b,c);         v2.push_back(q);     }     i=0;     j=0;     ans = vremia(i,j,ans,v1,v2);     fout << ans;     fout.close();     fin.close();     return 0; } int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2) {     int b,c;     Para r1,r2;     if(i<v1.size()) {         r1 = v1[i];         b = 1;     }     else {         b = 0;     }     if(j<v2.size()) {         r2 = v2[j];         c = 1;     }     else {         c = 0;     }     if((b==0)&&(c==0)) { }     else {         if(b==0) {             while(j<v2.size()) {                 r2 = v2[j];                 ans += r2.y;                 j++;             }         }         else {             if(c==0) {                 while(i<v1.size()) {                     r1 = v1[i];                     ans += r1.y;                     i++;                 }             }             else {                 if(r1.x!=r2.x) {                     if(r1.y<r2.y) {                         ans += r1.y;                         v2[j].y = r2.y - r1.y;                         i++;                         ans = vremia(i,j,ans,v1,v2);                     }                     else {                         if(r1.y>r2.y) {                             ans += r2.y;                             v1[i].y = r1.y - r2.y;                             j++;                             ans = vremia(i,j,ans,v1,v2);                         }                         else {                             if(r1.y==r2.y) {                                 //ans += r1.y;                                 i++;                                 j++;                                 ans = vremia(i,j,ans,v1,v2);                             }                         }                     }                 }                 else {                     int k = i+1;                     b = vremia(k,j,ans,v1,v2) + r1.y;                     int l = j+1;                     c = vremia(i,l,ans,v1,v2) + r2.y;                     if(b<=c) {                         ans = b;                     }                     else {                         ans = c;                     }                 }             }         }     }     return ans; } Суть в том, что на некоторых входных данных выдает неправильный ответ( Хотя и редко). Например при входе: 4 3 1 1 3 3 2 1 4 1 1 2 3 4 1 3 1 выдает ответ 5, хотя мин время работы 6 не могу найти, где ошибка в алгоритме, помогите пожалуйста

Автор: Tieswar 29.5.2016, 14:33

У меня на этот ввод выдаёт 3. Вы бы добавили комментариев к коду. Чтобы хотя бы общие черты логики были видны сразу, без погружения в код.

Автор: Tieswar 29.5.2016, 15:01

Немного подредактировал ваш код. Код #include <iostream> #include <fstream> #include <vector> using namespace std; struct Para {     int x;     int y;     Para(int t=0,int s=0):x(t),y(s) {} }; int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2); int main(int argc, char **argv) {     int n, // число станков         a1,// число пар для первой работы         a2,// число пар для второй работы         b, c, i, j;     // Считываем входящие данные     ifstream fin("/home/timur/res/texts/input.txt");     fin >> n;     vector<Para> v1,v2;     int ans = 0;     Para r1,r2;     // считываем количество пар и добавляем их к первой работе     fin >> a1;     for(j = 0; j < a1; j++)     {         fin >> b;         fin >> c;         Para q(b,c);         v1.push_back(q);     }     // считываем количество пар и добавляем их ко второй работе     fin >> a2;     for(j = 0 ; j < a2; j++)     {         fin >> b;         fin >> c;         Para q(b,c);         v2.push_back(q);     }     i=0;     j=0;     // подсчитываем минимальное время работы     ans = vremia(i,j,ans,v1,v2);     // Записываем результаты, закрываем файлы, выходим     ofstream fout("/home/timur/res/texts/output.txt");     fout << ans;     fout.close();     fin.close();     return 0; }// main() int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2) {     int b,c;     Para r1,r2;     if(i<v1.size()){         r1 = v1[i];         b = 1;     }else{         b = 0;     }//if else     if(j<v2.size()){         r2 = v2[j];         c = 1;     }else{         c = 0;     }//if else     if((b==0)&&(c==0)){         cerr << "b == 0 and c == 0\n";     }else{         if(b==0){             while(j<v2.size()){                 r2 = v2[j];                 ans += r2.y;                 j++;             }//while         }else{             if(c==0){                 while(i<v1.size()){                     r1 = v1[i];                     ans += r1.y;                     i++;                 }//while             }else{                 if(r1.x!=r2.x){                     if(r1.y<r2.y){                         ans += r1.y;                         v2[j].y = r2.y - r1.y;                         i++;                         ans = vremia(i,j,ans,v1,v2);                     }else{                         if(r1.y>r2.y){                             ans += r2.y;                             v1[i].y = r1.y - r2.y;                             j++;                             ans = vremia(i,j,ans,v1,v2);                         }else{                             if(r1.y==r2.y){                                 //ans += r1.y;                                 i++;                                 j++;                                 ans = vremia(i,j,ans,v1,v2);                             }//if                         }//if else                     }//if else                 }else{                     int k = i+1;                     b = vremia(k,j,ans,v1,v2) + r1.y;                     int l = j+1;                     c = vremia(i,l,ans,v1,v2) + r2.y;                     if(b<=c){                         ans = b;                     }else{                         ans = c;                     }//if else                 }//if else             }//if else         }//if else     }//if else     return ans; } Похоже, просто всегда срабатывает условие в функции рассчёта времени  Код     if((b==0)&&(c==0)){         cerr << "b == 0 and c == 0\n";

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)