algorytm przerywajacy wypisywanie powtarzajacych sie liczb

0

Witam, chcialbym zrobic program, ktory podczas wypisywania liczb naturalnych z przedzialu {1, .... , n-1}, czyli n-liczb, przerywa wypisywanie gdy liczba sie powtorzy.

Chodzi mi bardzej o ALGORYTM, a nie o program, ktory zrobil by to jak najszybciej. na razie wymyslilem kopiowanie wartosci do listy i sprawdzanie czy kolejna nowa liczba juz zostala w niej zapisana, jezeli tak to 'break'.

Z gory dziekuje za pomoc w przyspieszeniu/uproszczeniu tego co zrobilem.

W ponizszym programie dla przykladu uzywam liczb z przedzialu od 0 do 5 generowane losowo...

///

#include <iostream>
#include <time.h>
#include <list>

using namespace std;

void main()
{

	int n; //number of values
	
	list <int> m;
	list <int>::iterator mIter;

	bool flag = false; //if repeated value then TRUE


	cout << "Enter table size: ";
	cin >> n;

	int *tab = new int[n];

	tab[0] = 1; //first value in the tab[]

	srand((unsigned)time(NULL)); //seed for randomly generated values
	
	for(int i=1; i<n; i++)
		tab[i] = rand() % 5; //randomly values from 0 to 5

	cout << "\nRandomly generated table:\n" <<endl;
	
	for(i=0; i<n; i++)
		cout << tab[i] << "\t";
	
	cout << endl;

	m.clear();	
	m.push_back(tab[0]);

	for(i=1; i<n; i++)
	{	
		for (mIter = m.begin(); mIter != m.end(); mIter++)

		if(*mIter==tab[i])
		{	
			if (!flag)
				cout << "\nInterrupted at " << i+1 << " position (value: " << tab[i] << ")." << endl;
				
			flag = true;
			break;
		}
	

		if (!flag)
			m.push_back(tab[i]);
	}	



	cout << "\n\nTable after interruption: " << endl;
	
	for ( mIter = m.begin(); mIter != m.end(); mIter++)
	{
		cout << *mIter << "\t";	
	}

	
	cout << "\n\n" << endl;
	system("pause");


}	
0

Witam, chcialbym zrobic program, ktory podczas wypisywania liczb naturalnych z przedzialu {1, .... , n-1}, czyli n-liczb, przerywa wypisywanie gdy liczba sie powtorzy.

Weź się zdecyduj czy masz n-liczb na wejściu, czy n-1 wartości? Wyszukiwanie w liście to O(n), dlaczego nie zrobisz po prostu wektora/tablicy booli określającego czy dana wartość została już użyta? Liczba robi za indeks tablicy - sprawdzenie/wpisanie to O(1).

BTW, jesteś studentem informatyki?

0

Weź się zdecyduj czy masz n-liczb na wejściu, czy n-1 wartości? Wyszukiwanie w liście to O(n), dlaczego nie zrobisz po prostu wektora/tablicy booli określającego czy dana wartość została już użyta? Liczba robi za indeks tablicy - sprawdzenie/wpisanie to O(1).

Fakt, n-1 liczb mialo byc.
Tak sie zastanawiam nad Twoim pomyslem.. Czy na poczatku wszyskie wartosci w tym wektorze/tablicy booli powinny byc ustawione na false i wtedy jezeli dana wartosc wystapi to zmieniac na true? Co jezeli jedna z liczb bedzie strasznie duza? Wtedy musze stworzyc wektor ktory moze 'zjesc' cala pamiec... bo wszystko co jest przed ta wartoscia musze ustawic na false.. co wtedy... Chyba ze sie myle?

BTW, jesteś studentem informatyki?

PS Tak, jestem studentem inf.

0

Dlatego pytałem czy chodzi o przedział wartości. Znasz takie coś jak hasztablica? O(1) w amortyzowanym czasie. Tylko najpierw musiałbyś to napisać, C++ nie ma (jeszcze - tr1::unordered_map/unordered_set) takich zabawek. Zawsze pozostaje użycie std::set lub std::map, oba oparte na drzewach, złożoność logarytmiczna.

Aż chciałoby się napisać 'heloł, mamy styczeń, dobrze się na studiach bawicie?'.

0

Tak swoją drogą - o sortowaniu słyszałeś?

0

Desc dzieki za pomoc.

To co zrobilem chyba bedzie w porzadku, co o tym sadzisz?

//

#include <iostream>
#include <time.h>
#include <map>

using namespace std;

void main()
{

	int n; //number of values
	int i; //for loops..

	map <int, bool> m;
	map <int, bool>::iterator mIter;// = m.begin();
	typedef pair <int, bool> mPair;


	cout << "Enter table size: ";
	cin >> n;

	int *tab = new int[n];

	tab[0] = 1;					//ONE is the first value in the table
	m.insert(mPair(1, true));	//therefore FIRST value in boolTab	is true 

	/*cout << "TAB: " << endl;
	for(i=1; i<n; i++)
	{	
		cout << tab[i] << " - ";
	}

	cout << "\nMAP before:" << endl;
	for ( mIter = m.begin(); mIter != m.end(); mIter++)
	{
		cout << mIter->second << " - ";	
	}*/
	
	srand((unsigned)time(NULL)); //seed for randomly generated values
	
	
	cout << "\nRandomly generated table: \n" << endl;
	cout << tab[0] << " - ";

	for(i=1; i<n; i++)
	{	
		int randVal = rand() % 20; //randomly values from 0 to 20
		mIter = m.find(randVal);
		if (mIter->second == true)
		{
			cout << "\nInterrupted at: " << i+1 << " position (repeated value: " << randVal << ")." << endl;
			break;
		}
			
		tab[i] = randVal;
		cout << tab[i] << " - ";
		m.insert(mPair(randVal,true));
	}

	/*cout << "\nMAP after:" << endl;
	for ( mIter = m.begin(); mIter != m.end(); mIter++)
	{
		cout << mIter->second << " - ";	
	}*/

	cout << endl;

	system("pause");


}	
</cpp>
0

Źle nie jest ale ja użyłbym raczej set - map generalnie lekko marnuje pamięć, szczególnie użyte w ten sposób.

To kilka uwag:

  • niepotrzebnie ten iterator do elementu mapy tworzysz;
  • możesz uprościć dostęp do mapy poprzez operator[]:
                mIter = m.find(randVal);
                if (mIter->second == true)

możesz zastąpić po prostu:

                if (m[randVal])
  • generalnie to samo z insert, można to zastąpić:
                m[randVal] = true;
  • generalnie to ta tablica jest Ci zbędna...
  • ...szczególnie, że jej nie zwalniasz.

Z nudów naklepałem coś takiego:

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

int main() 
{
     srand(unsigned(time(NULL)));

     unsigned n = 0;
     cout << "wtf?!";
     cin  >> n;

     cout << "omg! ";

     set <unsigned> used;
     for (unsigned i = 0; i < n; i++) {

          unsigned rn = rand() % 69;

          if (used.count(rn) == 0) {
               cout << rn << " ";

               used.insert(rn);
          } else {
               cout << "\nInterrupted at "  << i
                    << " position (value: " << rn
                    << ")";

               break;
          }
     }
     cout << endl;
}
0

Możesz do tego podejść z innej strony. Ponieważ podajesz ilość liczb, możesz stworzyć tablicę dynamiczną o rozmiarze n liczb. Przedstawiam kod z losowym wybieraniem liczb. Podaj np n=111.

#include<iostream>
#include <time.h>
using namespace std;
int *tab,n,pp;
int main()
{  
 	time_t t;  
 srand((unsigned) time(&t));
 cout<<"podaj ilosc liczb  ";
 cin>>n;
 tab=new int[n]; 
 cout<<"wylosowane liczby "<<endl;
  	for(int i=0;i<n;i++)
	{  
    pp=rand()%n;
    if(tab[pp]==0){tab[pp]=pp;cout<<pp<<" ";}
    else
    {        
      cout<<endl<<endl<<"liczba "<<pp<<" juz wystapila,przerywam"<<endl<<endl;
      break;  
    }  
   }

 delete []tab;
    system("pause");
 }
0

Problem w tym, że z wątku raczej nie wynika jak duże te liczby będą - przeczytaj uważnie, dlatego się czepiałem. Zresztą takie rozwiązanie w pierwszym poście zaproponowałem. W sumie chaotyczny ten wątek jak cholera, ciężko z człowieka wyciągnąć jaka jest dokładnie treść zadania.

0

Jezeli chodzi o to zadanie to niestety nie jestem w stanie skonkretyzowac problemu super-dokladnie. Chodzilo mi mniej wiecej o odpowiedz jak powinno sie do tego zabrac... Pomogliscie, takze, dzieki za zaangazowanie!

Pozdrawiam.

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