Liczby pseudolosowe

0

Witam, pisze program który używa róznych algorytmów do sortowania tablic z liczbami. Liczby te sa generowane przez srand z zakresu który podaje użytkwownik. Algorytmy działaja bez problemu, lecz mam tylko taki mały problem, że liczby które sa losowane zawierają takze liczby ujemne, choc przedzial podawany przez uzytkownika zawiera tylko przedział liczb dodatnich.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int losowe(int nMin, int nMax)
{
	return (rand()*rand()) % nMax + nMin;
}
int i, n, p, j=2, l, t=1;
long long int T=1;
int Min, Max, m, me, N;
bool zamiana;

int* tpom = new int[N];
int* tabme = new int[N];

/* Scalanie dwoch posortowanych ciagow
tab[pocz...sr] i tab[sr+1...kon] i
wynik zapisuje w tab[pocz...kon] */
void merge(int pocz, int sr, int kon)
{

	int i,j,q;
	for (i=pocz; i<=kon; i++)
	tpom[i]=tabme[i];  // Skopiowanie danych do tablicy pomocniczej
	i=pocz; j=sr+1; q=pocz;                // Ustawienie wskaników tablic
	while (i<=sr && j<=kon) {          // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
		if (tpom[i]<tpom[j])
			tabme[q++]=tpom[i++];
		else
			tabme[q++]=tpom[j++];
	}
	while (i<=sr) tabme[q++]=tpom[i++];    // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
}

/* Procedura sortowania tab[pocz...kon] */
void mergesort(int pocz, int kon)
{
	int sr;
	if (pocz<kon) {
		sr=(pocz+kon)/2;
		mergesort(pocz, sr);    // Dzielenie lewej częci
		mergesort(sr+1, kon);  // Dzielenie prawej częci
		merge(pocz, sr, kon);  // Łšczenie częci lewej i prawej
	}
}

int main ()
{
	//int m;
	int algorytm;

	cout << "Ktorego sortowania chcesz uzyc?:" << endl;
	cout << endl;
	cout << "  1. Sortowanie przez wstawianie"<< endl;
	cout << "  2. Sortowanie babelkowe" << endl;
	cout << "  3. Sortowanie przez scalanie" <<endl;
	cout << endl;
	cout << "Twoj wybor to: " ;
	cin >> algorytm;

	cout << endl;
	cout << endl;
	if (algorytm==1)
	{
		int opcja;
		cout << endl;
		cout << "  1. Liczby podawane przez uzytkownika z klawiatury." << endl;
		cout << "  2. Liczby losowane przez system." << endl;
		cout << endl;
		cout << "Twoj wybor to: " ;
		cin >> opcja;
		switch(opcja)
		{
		case 1:
			cout << "1.  LICZBY PODAWANE Z KLAWIATURY" << endl;
			cout << endl;

			int *a;
			cout << "  Rozmiar tablicy a[n] (n=?):   ";
			cin >> n;
			a = new int[n];
			n=n+1;
			cout << endl;
			//////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////Uzupełnianie tablicy - podawanie liczb z klawiatury//////////////////////
			//////////////////////////////////////////////////////////////////////////////////////////////////////////////
			for (l=1; l<n; l++)
			{
				cout<<"    a[" <<l<< "] =   ";       //
				cin >> a[l];
			}
			////////////////////////////////////////////////////////////////////////////////////////////////
			////////////////////////////////////// Sortowanie///////////////////////////////////////////////
			////////////////////////////////////////////////////////////////////////////////////////////////
			for (j=2; j<n; j++)
			{
				p=a[j];
				i=j-1;
				while ((i>0) && (a[i]>p))
				{
					a[i+1]=a[i];
					i=i-1;
					t=t+1;
				}
				t=t+1;
				a[i+1]=p;
			}

			cout << endl;
			//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////// Wynik po sortowaniu///////////////////////////////////////////////
			/////////////////////////////////////////////////////////////////////////////////////////////////////////////////

			cout << "  Po sortowaniu liczb podanych z klawiatury:" << endl;
			cout << endl;

			for (l=1; l<n; l++)
			{
				cout << "    a[" << l << "] =   ";
				cout << a[l] << endl;
			}

			cout << endl;
			cout << "  Ilosc porownan:    " << t << endl;
			cout << endl;

			n=n-1;
			{float iloraz;
			iloraz = (float)t / (float)(n*n);
			cout << "  Iloraz t/(n*n):   " <<iloraz << endl;}

			cout << endl;
			cout << endl;
			cout << endl;
			break;



			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////PSEUDOLOSOWE///////////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////
		case 2:
			cout << "2.  LICZBY PSEUDOLOSOWE" << endl;
			cout << endl;

			srand ( static_cast < unsigned int >(time(NULL))); // zainicjowanie generatora liczb pseudolosowych aktualnym czasem z kompa

			cout << "  Wybierz przedzial dla liczb losowych:   " << endl;
			cout << endl;

			cout << "    Min: ";
			cin >> Min;
			cout << "    Max: ";
			cin >> Max;

			cout << endl;

			int *b;
			cout << "  Rozmiar tablicy b[m] (m=?):   ";
			cin >> m;
			b = new int[m];
			m=m+1;

			cout << endl;

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////UZUPEŁNIENIE TABLICY///////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			for (l=1; l<m; l++)
			{
				cout << "    b[" << l << "] =   ";
				b[l]=losowe(Min,Max);
				cout << b[l] << endl;
			}

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////SORTOWANIE///////////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			for (j=2; j<m; j++)
			{
				p=b[j];
				i=j-1;
				while ((i>0) && (b[i]>p))
				{
					b[i+1]=b[i];
					i=i-1;
					T=T+1;
				}
				T=T+1;
				b[i+1]=p;
			}

			cout << endl;

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////WYNIK PO SORTOWANIU////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			cout << "  Po sortowaniu liczb pseudolosowych:" << endl;
			cout << endl;

			for (l=1; l<m; l++)
			{
				cout << "    b[" << l << "] =   ";
				cout << b[l] << endl;
			}

			cout << endl;
			cout << "  Ilosc porownan:    " << T << endl;
			cout << endl;

			m=m-1;
			{float Iloraz;
			Iloraz = (float)T / (float) (m*m);
			cout << "  Iloraz T/(m^2):   " <<Iloraz << endl;}
			break;


		default:

			cout << "Nie ma takiej opcji." << endl;
			break;
		}
	}


	/////////////////////////////////////////////////////////////////////////////////////////
	////////////////////////////////////// BUBBLE SORT//////////////////////////////////////
	///////////////////////////////////////////////////////////////////////////////////////
	else if(algorytm==2)
	{
		int opcja2;
		cout << endl;
		cout << "  1. Liczby podawane przez uzytkownika z klawiatury." << endl;
		cout << "  2. Liczby losowane przez system." << endl;
		cout << endl;
		cout << "Twoj wybor to: " ;
		cin >> opcja2;
		switch(opcja2)
		{
		case 1:
			cout << "1.  LICZBY PODAWANE Z KLAWIATURY" << endl;
			cout << endl;

			int *tab;

			cout << "  Rozmiar tablicy a[n] (n=?):   ";
			cin >> n;
			tab = new int[n];
			n=n+1;
			cout << endl;

			// Uzupełnianie tablicy - podawanie liczb z klawiatury

			for (l=1; l<n; l++)
			{
				cout<<"    a[" <<l<< "] =   ";       //
				cin >> tab[l];
			}

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////SORTOWANIE///////////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			// Czy zamieniono w ostatnim obrocie? Jeli nie, to tablica jest posortowana.

			do {
				zamiana = false;
				for (int l = 1; l<n-1;l++)
				{
					if (tab[l] > tab[l+1])
					{
						swap(tab[l], tab[l+1]);
						zamiana = true;
					}t=t+1;
				}

			} while (zamiana);

			cout << endl;

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////WYNIK PO SORTOWANIU////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			cout << "  Po sortowaniu liczb podanych z klawiatury:" << endl;
			cout << endl;


			for(l=1;l<n;l++)
				cout<<tab[l]<<endl;

			cout << endl;
			cout << "  Ilosc porownan:    " << t << endl;
			cout << endl;

			n=n-1;
			{float iloraz;
			iloraz = (float)t / (float)(n*n);
			cout << "  Iloraz t/(n*n):   " <<iloraz << endl;}

			cout << endl;
			cout << endl;
			cout << endl;
			break;

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////PSEUDOLOSOWE///////////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

		case 2:
			cout << "2.  LICZBY PSEUDOLOSOWE" << endl;
			cout << endl;

			srand ( static_cast < unsigned int >(time(NULL))); // zainicjowanie generatora liczb pseudolosowych aktualnym czasem z kompa

			cout << "  Wybierz przedzial dla liczb losowych:   " << endl;
			cout << endl;

			cout << "    Min: ";
			cin >> Min;
			cout << "    Max: ";
			cin >> Max;

			cout << endl;

			int *b;
			cout << "  Rozmiar tablicy b[m] (m=?):   ";
			cin >> m;
			b = new int[m];
			m=m+1;

			cout << endl;
			//////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////// Uzupełnianie teblicy liczbami pseudolosowymi/////////////////////////
			////////////////////////////////////////////////////////////////////////////////////////////////////////
			for (l=1; l<m; l++)
			{
				cout << "    b[" << l << "] =   ";
				b[l]=losowe(Min,Max);
				cout << b[l] << endl;
			}
			////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////Sortowanie////////////////////////////////////////////////
			//////////////////////////////////////////////////////////////////////////////////////////////////
			do {
				zamiana = false;
				for (int l = 1; l<m-1;l++)
				{
					if (b[l] > b[l+1])
					{
						swap(b[l], b[l+1]);
						zamiana = true;
					}T=T+1;
				}

			} while (zamiana);

			cout << endl;
			//////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////// Wynik po sortowaniu///////////////////////////////////////////
			//////////////////////////////////////////////////////////////////////////////////////////////////
			cout << "  Po sortowaniu liczb pseudolosowych:" << endl;
			cout << endl;

			for (l=1; l<m; l++)
			{
				cout << "    b[" << l << "] =   ";
				cout << b[l] << endl;
			}

			cout << endl;
			cout << "  Ilosc porownan:    " << T << endl;
			cout << endl;

			m=m-1;
			{float Iloraz;
			Iloraz = (float)T / (float) (m*m);
			cout << "  Iloraz T/(m^2):   " <<Iloraz << endl;}
			break;


		default:

			cout << "Nie ma takiej opcji." << endl;
			break;

		}
	}
	//////////////////////////////////////////////////////////////////////////////////
	//////////////////////////////////////MERGE SORT//////////////////////////////////
	//////////////////////////////////////////////////////////////////////////////////
	else if(algorytm==3)
	{
		int opcja3;
		cout << endl;
		cout<<"Wybrales sortowanie przez scalanie"<<endl;
		cout << "  1. Liczby podawane przez uzytkownika z klawiatury." << endl;
		cout << "  2. Liczby losowane przez system." << endl;
		cout << endl;
		cout << "Twoj wybor to: " ;
		cin >> opcja3;
		switch(opcja3)
		{
		case 1:
			cout << "1.  LICZBY PODAWANE Z KLAWIATURY" << endl;
			cout << endl;

			int *tab;

			cout << "  Rozmiar tablicy a[n] (n=?):   ";
			cin >> n;
			tab = new int[n];
			n=n+1;
			cout << endl;

			// Uzupełnianie tablicy - podawanie liczb z klawiatury

			for (l=1; l<n; l++)
			{
				cout<<"    a[" <<l<< "] =   ";       //
				cin >> tab[l];
			}

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////SORTOWANIE/////////////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			// Czy zamieniono w ostatnim obrocie? Jeli nie, to tablica jest posortowana.

			do {
				zamiana = false;
				for (int l = 1; l<n-1;l++)
				{
					if (tab[l] > tab[l+1])
					{
						swap(tab[l], tab[l+1]);
						zamiana = true;
					}t=t+1;
				}

			} while (zamiana);

			cout << endl;

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////WYNIK PO SORTOWANIU////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

			cout << "  Po sortowaniu liczb podanych z klawiatury:" << endl;
			cout << endl;


			for(l=1;l<n;l++)
				cout<<tab[l]<<endl;

			cout << endl;
			cout << "  Ilosc porownan:    " << t << endl;
			cout << endl;

			n=n-1;
			{float iloraz;
			iloraz = (float)t / (float)(n*n);
			cout << "  Iloraz t/(n*n):   " <<iloraz << endl;}

			cout << endl;
			cout << endl;
			cout << endl;
			break;

			/////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////////PSEUDOLOSOWE///////////////////////////////////////////////
			///////////////////////////////////////////////////////////////////////////////////////////////////////

		case 2:
			cout << "2.  LICZBY PSEUDOLOSOWE" << endl;
			cout << endl;

			srand ( static_cast < unsigned int >(time(NULL))); // zainicjowanie generatora liczb pseudolosowych aktualnym czasem z kompa

			cout << "  Wybierz przedzial dla liczb losowych:   " << endl;
			cout << endl;

			cout << "    Min: ";
			cin >> Min;
			cout << "    Max: ";
			cin >> Max;

			cout << endl;

			//int *tabme;
			cout << "  Rozmiar tablicy tabme[me] (me=?):   ";
			cin >> me;
			tabme = new int[me];
			me=me+1;

			cout << endl;
			//////////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////// Uzupełnianie teblicy liczbami pseudolosowymi/////////////////////////
			////////////////////////////////////////////////////////////////////////////////////////////////////////
			for (l=1; l<me; l++)
			{
				cout << "    tab[" << l << "] =   ";
				tabme[l]=losowe(Min,Max);
				cout << tabme[l] << endl;
			}
			////////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////////////Sortowanie////////////////////////////////////////////////
			//////////////////////////////////////////////////////////////////////////////////////////////////
			mergesort(0,me-1);



			cout << endl;
			//////////////////////////////////////////////////////////////////////////////////////////////////
			/////////////////////////////////// Wynik po sortowaniu///////////////////////////////////////////
			//////////////////////////////////////////////////////////////////////////////////////////////////
			cout << "  Po sortowaniu liczb pseudolosowych:" << endl;
			cout << endl;

			for (l=1; l<me; l++)
			{
				cout << "    tab[" << l << "] =   ";
				cout << tabme[l] << endl;
			}

			cout << endl;
			cout << "  Ilosc porownan:    " << T << endl;
			cout << endl;

			m=m-1;
			{float Iloraz;
			Iloraz = (float)T / (float) (m*m);
			cout << "  Iloraz T/(m^2):   " <<Iloraz << endl;}
			break;


			/*default:

			cout << "Nie ma takiej opcji." << endl;
			break;*/

		}
	}

	return 0;
}
0

Zapomnialem dodac ze program jest pisany w code::blocks pod linuxem, natomiast ten sam kod na win7 w visual studio 2010 nie losuje liczb ujemnych... lecz tylko dodatnie

0

Po pierwsze nie powinieneś tyle przerw ("enterów"), czyni to twój kod nieczytelny.

Jak masz za duży monitor, i to Ci przeszkadza, to zwiększ czcionkę w edytorze. rand()*rand() doprowadza do przepełnienia inta, przez co mogą Ci powstać liczby ujemne (lub wyjść demony z nosa, przepełnienie liczb signed jest zgodnie ze standardem niezdefiniowane). Operacja modulo (%) w wielu językach (choć poza np. Pythonem) gdy liczba z lewej strony jest ujemna daje wynik ujemny.

Rand() w visual studio ma mniejszy zakres, przez co nie obserwujesz przepełnienia (zgodnie z MSDN 215-1). Na linuksie najczęściej RAND_MAX==INT_MAX, czyli 231-1.

Pomysł z rand()rand() jest poroniony. Zakładając, że nie ma przepełnienia oraz rand() jest kompletnie losowy, to powiedzmy, że chcesz wybrać tą metodą losową liczbę w zakresie od jednego do sześciu (po drobnych poprawkach do tej metody). (ab)%c jest równe ((a%c)*(b%c))%c, więc stosując taką operację na tym przykładzie otrzymujemy, że wynikiem każdego z elementów tych działań (a%c i b%c, czyli rand()%6) jest z równym prawdopodobieństwem liczba z zakresu od 0 do 5. Rozpisując wyniki wszystkich możliwości w tabeli (z wykonaniem od razu modulo) otrzymujemy:

-       0       1       2       3       4       5
        |       |       |       |       |       |
0  -    0       0       0       0       0       0

1  -    0       1       2       3       4       5

2  -    0       2       4       0       2       4

3  -    0       3       0       3       0       3

4  -    0       4       2       0       4       2

5  -    0       5       4       3       2       1

Wszystkich elementów w tej tabeli jest 36, zer jest 15, więc szansa na wynik będący zerem jest równa 15/36. Czyli tak zrobiona funkcja dla zakresu 1-6 w prawie połowie przypadków zwróci 1, co jest zupełnie bez sensu.

BTW chyba się wreszcie zmuszę do napisania artykułu o liczbach pseudolosowych. To był trochę mój konik, a większość postów ich dotyczących powoduje, że powoli staję się psychopatą.

0 
int i, n, p, j=2, l, t=1;
long long int T=1;
int Min, Max, m, me, N;
bool zamiana;
int* tpom = new int[N];
Szczerze mówiąc nie mam zamiaru nawet próbować czytać kodu. Jest go za dużo, jest nieczytelny i nie jest za ciekawy,, ale po pierwszym fragmencie powiedz mi ile elementow będzie miała tablica tpom ??

1 użytkowników online, w tym zalogowanych: 0, gości: 1