Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 29.05.2016, 10:12   #1
Tavasilyok
Новичок
Джуниор
 
Регистрация: 01.02.2012
Сообщений: 2
По умолчанию ошибка в алгоритме с++

Здравствуйте, помогите, пожалуйста. Есть задача:
Есть 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

не могу найти, где ошибка в алгоритме, помогите пожалуйста
Tavasilyok вне форума Ответить с цитированием
Старый 29.05.2016, 19:55   #2
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Посмотрите здесь. Смысл изменений: векторы v1, v2 преобразуются в
в вектора Pabota1, Pabota2

Pabota1={1,3,3,3,2}
Pabota2={1,2,2,2,4,3},

где индекс вектора - это каждый час, а его значение - задействованный мотор. Т.к. время идет синхронно для 1-й и 2-й работы, то сравниваем
Pabota1[i] и Pabota1[j] поэлементно. Если Работы 1 и 2 будет конкурировать друг с другом за мотор, то выполняется та работа, у которой макс. кол-во элементов (в нашем случае Pabota2).
В следующем часе снова сравнение - если для задание нужны разные моторы - то задействуем их обоих...

Матрица Slegenie показывает как во времени работали моторы (её можно удалить).
Нет времени особо тестировать программу, но если найдешь ошибку - пиши.
У меня Visual Studio 2013 - иногда при копировании текста программы выводит ошибку - "не обнаружен конец файла". Глюк среды - лечится постепенной компиляции: сначало дирректив, потом main(), ....


Код:
#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<int> &Pabota1, vector<int> &Pabota2);


int Slegenie[2][10] = {                   // Slegenie нужно только для того. чтобыопределить как были загружены моторы во времени и задания
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },     // можно и удалить
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }};
int t = 0;



int main()
{
	setlocale(LC_ALL, "Russian");
	int ans;

	vector<Para> v1, v2;

	v1.push_back({1,1});
	v1.push_back({3,3});	
	v1.push_back({2,1});

	v2.push_back({1,1});
	v2.push_back({2,3});
	v2.push_back({4,1});
	v2.push_back({3,1});
//	v2.push_back({5,2});

	// Преобразуем v1 и v2 к виду Pabota1={1,3,3,3,2}
	//                            Pabota2={1,2,2,2,4,3}, где индекс вектора - каждый час, а значение его - задействованный мотор  

	vector<int> Pabota1, Pabota2;
	int b = 0;
	while (b<v1.size())
	{
		for (int i = 0; i < v1[b].y; i++)
			Pabota1.push_back(v1[b].x);		
		b++;
	}
	b = 0;
	while (b<v2.size())
	{
		for (int i = 0; i < v2[b].y; i++)		
			Pabota2.push_back(v2[b].x);		
		b++;
	}
	
	int i = 0;
	int j = 0;
	ans = vremia(i, j, 0, Pabota1, Pabota2);

	cout << ans << endl << endl;

	cout << "Матрица загрузки моторов" << endl;
	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cout << " "<< Slegenie[i][j];
		}	
		cout << endl;
	}
	cout << endl;

	system("pause");
	return 0;
}

int vremia(int &i, int &j, int ans, vector<int> &Pabota1, vector<int> &Pabota2)
{
	if ((i < Pabota1.size()) && (j < Pabota2.size()))
	{
		if (Pabota1[i] == Pabota2[j])
		{
			if (Pabota1.size() > Pabota2.size())
			{
				i++;
				ans++;                                                     Slegenie[0][t] = Pabota1[i-1]; t++;
				ans = vremia(i, j, ans, Pabota1, Pabota2);
			}
			else
			{
				j++;
				ans++;                                                     Slegenie[1][t] = Pabota2[j-1]; t++;
				ans = vremia(i, j, ans, Pabota1, Pabota2);
			}
		}
		else
		{
			i++;
			j++;
			ans++;                                                         Slegenie[0][t] = Pabota1[i - 1]; Slegenie[1][t] = Pabota2[j - 1]; t++;
			ans = vremia(i, j, ans, Pabota1, Pabota2);
		}
	}
	if ((i == Pabota1.size()) && (j < Pabota2.size()))
	{
		while (j < Pabota2.size())
		{
			j++;
			ans++;                                                         Slegenie[1][t] = Pabota2[j - 1]; t++;
		}
	}
	if ((i < Pabota1.size()) && (j == Pabota2.size()))
	{
		while (i < Pabota1.size())
		{
			i++;
			ans++;                                                         Slegenie[0][t] = Pabota1[i - 1]; t++;
		}
	}
	if ((i == Pabota1.size()) && (j == Pabota2.size()))
		return ans;
	return ans;
}

ura_111 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Некорректная работа, ошибка в алгоритме orandzheviyman Помощь студентам 5 07.11.2014 23:42
поиск фибоначи ошибка в алгоритме aksdaqg Помощь студентам 1 04.04.2014 11:40
Ошибка в алгоритме parkito Общие вопросы C/C++ 1 07.12.2011 04:25
Ошибка в алгоритме поиска murzilka6002 Общие вопросы C/C++ 15 24.11.2011 04:57
Ошибка в алгоритме слияние массивов ATAMAN200 Общие вопросы C/C++ 3 25.10.2010 20:37