Zadanie z MAIN

Mam takie zadanko http://main.edu.pl/en/user.phtml?op=showtask&task=prze&con=PAS. Mój kod działa tylko przy niektórych przedziałach i nie wiem czemu

 #include <iostream>

using namespace std;

const int N = 1000;


void generuj(int tab[], int poczatek, int koniec)
{
	
	int dlugosc = koniec - poczatek;

	for (int i = 0; i < dlugosc + 1; i++)
	{
		tab[i] = poczatek + i;
		cout << tab[i] << "  ";
	}
	cout << endl;
}

int main()
{
	int tablica[N];
	int poczatek, koniec,liczbaPrzedzialow;
	int sumaLacznych = -1, pomocKoniec = 100000, pomocPoczatek = -1000000;
	
	

	cout << "Ile ma byc przedzialow: " << endl;
	cin >> liczbaPrzedzialow;

	for (int i = 0; i < liczbaPrzedzialow; i++)
	{
		cout << "Podaj poczatek i koniec: " << endl;
		cin >> poczatek >> koniec;
		generuj(tablica, poczatek, koniec);
		if (koniec <= pomocKoniec)
		{
			pomocKoniec = koniec;
			sumaLacznych += 1;
		}
		if (poczatek >= pomocPoczatek)
		{
			pomocPoczatek = poczatek;
			sumaLacznych += 1;
		}
	}

	cout << "Suma lacznych przedzialow to : " <<sumaLacznych;
	system("pause");
}

Po pierwsze ten kod nie będzie przechodził żadnego testu, bo

cout << "Ile ma byc przedzialow: " << endl;
cout << "Podaj poczatek i koniec: " << endl;
cout << "Suma lacznych przedzialow to : " <<sumaLacznych;
system("pause");

Po drugie

int dlugosc = koniec - poczatek;
for (int i = 0; i < dlugosc + 1; i++)

zdajesz sobie sprawę, że dlugosc jest rzędu 10⁹? Iterowanie po tym 5000 razy (bo tyle może być przedziałów) na pewno sprawi, że program nie przejdzie czasowo niektórych testów.

Na algorytm nie patrzę, bo go nie rozumiem :D

Chyba trzeba jednak opracować jakiś czytelniejszy kod :)

A jak wygląda sam algorytm żeby sprawdzić czy przedziały są łączne ?

Troche czytelniej.

#include <iostream>

using namespace std;


const int N = 1000;
int main()
{
	int liczbaTablic;
	int poczatki[N], konce[N],suma=1;
	cout << "Ile tablic: " << endl;
	cin >> liczbaTablic;
	cout << "Podaj poczatki " << liczbaTablic << " przedzialow" << endl;
	for (int i = 0; i < liczbaTablic; i++)
	{
		cin >> poczatki[i];
	}
	cout << "Podaj konce " << liczbaTablic << " przedzialow" << endl;
	for (int i = 0; i < liczbaTablic; i++)
	{
		cin >> konce[i];
	}

	
	for (int i = 0; i < liczbaTablic; i++)
	{
		if (poczatki[i] <= konce[i-1]) suma += 1;		
	}
	cout << "suma przedzialow lacznych : " << suma;
	system("pause");
} 

A gdzie sortowanie? I co tu robi zmienna globalna?

Jak mam to posortować? Oddzielnie tablice z początkami i oddzielnie z końcami ? Nie zmieni to zakresu przedziałów? A zmienna globalna w tym miejscu to efekt zajęć na studiach :) tak na wykładach mamy

Pewnie że zmieni. Na początku radziłbym skorzystać z dobrodziejstw programowania obiektowego. Co do zmiennej globalnej - no to źle na wykładach macie. Wykładowca za takie coś powinien w dziąsło dostać.

No to jeszcze trochę nauki przede mną :) a na tym poziomie zaawansowania nie da rady ruszyć?

Nie potrafisz stworzyć struktury z dwiema zmiennymi reprezentującymi początek i koniec przedziału i wpisywać do tej struktury?

void sorting(int x[], int y[], int n)
{
    for(int i = 0; i < n; i++)
      for(int j = i + 1; j < n; j++) {
         if (x[i] > x[j]) {
             int tmp = x[i];
             x[i] = x[j];
             x[j] = tmp;
             tmp=y[i];
             y[j] = y[i];
             y[i] = tmp;
         }
      }
}

Struktura stworzona ale jak to posortowac. Pisze ze argument typu mojej struktury jest niekompatybilny z typem int

#include<iostream>

using namespace std;

void sortuj(int tab[], int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = n - 1; j >= 1; j--)
		{
			if (tab[j]<tab[j - 1])
			{
				int bufor;
				bufor = tab[j - 1];
				tab[j - 1] = tab[j];
				tab[j] = bufor;
			}
		}
	}
}

struct przedzial
{
	int poczatek, koniec;	
};
int main()
{
	const int N = 1000;
	int liczbaTablic;
	int suma=1;
	przedzial przedzialy[N];

	cout << "Ile tablic: " << endl;
	cin >> liczbaTablic;

	cout << "Podaj poczatki " << liczbaTablic << " przedzialow" << endl;
	for (int i = 0; i < liczbaTablic; i++)
	{
		cin >> przedzialy[i].poczatek;
	}
	
	cout << "Podaj konce " << liczbaTablic << " przedzialow" << endl;
	for (int i = 0; i < liczbaTablic; i++)
	{
		cin >> przedzialy[i].koniec;
	}

	
	sortuj(przedzialy, liczbaTablic);	
	
	
}
 

tak wiem w funkcji sortuj powinien byc argument inny. Co nie zmienia faktu ze i tak nie chce sie to posortować :)

No i fajnie. Nie kopiuj bezmyślnie czyjegoś kodu. Mówie teraz o tej bzdurnej funkcji sortuj kolegi @withelm
Do sortowania użyj tej funkcji
http://en.cppreference.com/w/cpp/algorithm/sort
z podanym trzecim argumentem. Tym argumentem jest wspomniany w podlinkowanej dokumentacji Compare comp, czyli funkcja, której argumentami są dwie zmienne typu przedzial. Funkcja ma zwracać true, kiedy pierwszy argument jest mniejszy od drugiego, w przeciwnym wypadku false.

Mógłbyś pokazać na przykładzie jak użyć tej funkcji z trzema argumentami ?

sort(przedzialy, przedzialy + liczbaTablic, funkcja_porownujaca);
Chyba, że nie rozumiesz też implementacji funkcja_porownujaca.

No niestety :)

bool funkcja_porownujaca (przedzial a, przedzial b) {
  if (a.poczatek < b.poczatek)
    return true;
  else
    return false;
}

W najprostszej możliwej wersji wygląda to tak.

1. Zapoznaj się z inkrementacją bo nie rozumiesz: http://4programmers.net/Forum/1101404
2. Twoje sortowanie ma koszt O(N²) da się zmniejszyć do O(N log(N))

I w jaki sposób za pomocą tej funkcji mam zliczyć ilość nachodzących na siebie przedziałów. Przepraszam za głupie pytania ale naprawdę muszę to zrozumieć :) Jeżeli można to wytłumaczcie ta funkcje porównujacą jak najprostszymi słowami

#include<iostream>
#include<algorithm>

using namespace std;

bool funkcja_porownujaca(przedzial a, przedzial b) {
	if (a.poczatek < b.poczatek)
		return true;
	else
		return false;
}
struct przedzial
{
	int poczatek, koniec;
};
int main()
{
	const int N = 1000;
	int liczbaTablic;
	int suma = 1;
	przedzial przedzialy[N];

	cout << "Ile tablic: " << endl;
	cin >> liczbaTablic;

	cout << "Podaj poczatki " << liczbaTablic << " przedzialow" << endl;
	for (int i = 0; i < liczbaTablic; i++)
	{
		cin >> przedzialy[i].poczatek;
	}

	cout << "Podaj konce " << liczbaTablic << " przedzialow" << endl;
	for (int i = 0; i < liczbaTablic; i++)
	{
		cin >> przedzialy[i].koniec;
	}

	sort(przedzialy, przedzialy + liczbaTablic,funkcja_porownujaca);


	system("pause");
}
 

wywala ten kod

Dlaczego podkreśla to sortowanie ? Pokazuje miedzy innym błąd " no instance of overloaded function "sort" matches the argument list"

Bo gdy definiujesz tę funkcję struktura przedzial jeszcze nie istnieje, więc kompilator nie wie co to jest.

A wiec nie wystarczy ze na poczatku deklaruje tablice typu przedział a potem wczytuje sobie z petli poczatki i konce ? Wiec jak temu zaradzić?

mariusz326 napisał(a):

A wiec nie wystarczy ze na poczatku deklaruje tablice typu przedział a potem wczytuje sobie z petli poczatki i konce?
Chodzi o to, że definicja struct przedzial musi być przed funkcją porównującą.

#include <iostream>
#include <algorithm>
using namespace std;

struct Range
{
	int start, finish;	
};

bool compareRange(const Range& left, const Range& right)
{
	if (left.start == right.start)
		return left.finish < right.finish;
	return left.start < right.start;
}

int main() 
{
	Range test[] = { {2, 3}, {-1, 4}, {4, 8}, {2, 5}, {1, 8} };
	sort(begin(test), end(test), compareRange);
	for (const auto& i : test)
		cout << "[" << i.start << "," << i.finish << "]\n";
	
	return 0;
}