Zadanie z MAIN

M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

Kopiuj
 #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");
}
withelm
Lol przecież na fb w komentarzach masz napisane jak to zrobić :D PS. Świat jest mały (:
twonek
akurat to, że jest gdzieś rozwiązanie nie znaczy, że powinien z niego korzystać
withelm
"Szkic rozwiązania przedziałów: 1. Sortujesz przedziały<a,b> po a 2. Po kolei idziesz i patrzysz czy przedział ity ma część wspólną z przedziałem i+1 jak nie ma to wynik + 1"
twonek
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 2 lata
  • Postów:2500
0

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

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

Po drugie

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

zdajesz sobie sprawę, że dlugosc jest rzędu 109? 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

M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

Chyba trzeba jednak opracować jakiś czytelniejszy kod :)

M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

withelm
Masz przedziały <a,b> i <c,d>. Wiesz, że a < b i c <d i a < c. To kiedy przedziały <a,b> i <c,d> nachodzą na siebie? Jak tego nie widzisz to rozrysuj sobie.
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

Troche czytelniej.

Kopiuj
#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");
} 
edytowany 1x, ostatnio: mariusz326
pingwindyktator
  • Rejestracja:ponad 12 lat
  • Ostatnio:2 miesiące
  • Lokalizacja:Kraków
  • Postów:1055
0

A gdzie sortowanie? I co tu robi zmienna globalna?


do not code, write prose
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

edytowany 1x, ostatnio: mariusz326
pingwindyktator
  • Rejestracja:ponad 12 lat
  • Ostatnio:2 miesiące
  • Lokalizacja:Kraków
  • Postów:1055
0

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ć.


do not code, write prose
edytowany 1x, ostatnio: pingwindyktator
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

pingwindyktator
  • Rejestracja:ponad 12 lat
  • Ostatnio:2 miesiące
  • Lokalizacja:Kraków
  • Postów:1055
0

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


do not code, write prose
withelm
  • Rejestracja:około 15 lat
  • Ostatnio:około 9 lat
0
Kopiuj
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;
         }
      }
}
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0
Kopiuj
#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);	
	
	
}
 
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

edytowany 1x, ostatnio: mariusz326
pingwindyktator
  • Rejestracja:ponad 12 lat
  • Ostatnio:2 miesiące
  • Lokalizacja:Kraków
  • Postów:1055
0

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.


do not code, write prose
edytowany 1x, ostatnio: pingwindyktator
withelm
Zauważ, ze n jest do <=5k czyli wydajnościowo pyknie :P
pingwindyktator
no offence, po prostu sugeruje wyrabiać dobre praktyki programowania od samego początku.
withelm
Oki tylko zauważ, że to nie Ty będziesz się tłumaczył przed wykładowcą w niedzielę z tego programu :P
pingwindyktator
Przecież to jest proste.
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

pingwindyktator
  • Rejestracja:ponad 12 lat
  • Ostatnio:2 miesiące
  • Lokalizacja:Kraków
  • Postów:1055
0

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


do not code, write prose
edytowany 1x, ostatnio: pingwindyktator
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

No niestety :)

pingwindyktator
  • Rejestracja:ponad 12 lat
  • Ostatnio:2 miesiące
  • Lokalizacja:Kraków
  • Postów:1055
0
Kopiuj
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.


do not code, write prose
edytowany 1x, ostatnio: pingwindyktator
_13th_Dragon
  • Rejestracja:prawie 20 lat
  • Ostatnio:14 dni
0
  1. Zapoznaj się z inkrementacją bo nie rozumiesz: http://4programmers.net/Forum/1101404
  2. Twoje sortowanie ma koszt O(N2) da się zmniejszyć do O(N log(N))

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon
Zobacz pozostałe 5 komentarzy
pingwindyktator
Chyba się nie rozumiemy.
_13th_Dragon
Może podam dane: 11 0 3 3 6 6 9 9 12 12 20 0 4 4 7 7 10 10 12 0 8 8 12 - nadał uważasz że da rady 0(n) ?
pingwindyktator
Okej, mea cupla, da się jedynie przy ogromnej pamięci zrobić to liniowo.
withelm
Jakiś hint jak zrobić to liniowo?
pingwindyktator
W tym zadaniu jest to bezcelowe i niewykonalne. Musielibyśmy przyjąć założenia o dużo mniejszym rozmiarze przedziałów.
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

Kopiuj
#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

edytowany 2x, ostatnio: mariusz326
pingwindyktator
Ta funkcja wyłącznie sortuje przedziały ze względu na ich początki.
M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

edytowany 1x, ostatnio: mariusz326
twonek
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 2 lata
  • Postów:2500
1

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

M3
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 8 lat
  • Postów:23
0

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

twonek
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 2 lata
  • Postów:2500
1
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ą.

Kopiuj
#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;
}
pingwindyktator
Szczere powodzenia w tłumaczeniu tego kodu, ja się już poddaje ;D

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.