[PYTANIE] Znajdź ciąg znaków spełniających warunek

[Pr0sikor]

Siemka. Mam do zrobienia zadanie i jak na razie idzie spoko ale nie wiem jak zrobić, żeby z podanych przez program n losowych danych a albo b (np. abababbbbabababbaaa) wypisało mi jaki jest najdłuższy ciąg który by spełniał warunek. Oto kawałek treści zadania :

Podaj ile znaków zawiera najdłuższy ciąg znaków losowo wpisanych przez program gdzie zn={a, b} który by spełniał podane założenie:

Ilość a nie może być mniejsza bądź równa ilości b...

 

Moje wypociny

 

#include <iostream>
#include <conio.h>
#include <ctime>


using namespace std;

int main()
{

int n;

    srand(time(NULL));
   
    
    cout<<"Podaj ilosc znakow..."<<endl;
    cin>>n;
    
    for(int i=0; i<n; i++)
    {
            if(rand()%2 == 0)
            {
             cout << "a";
            }
            else
            {
             cout << "b";
            }
    }    
    getch();
}

 

[Xau]

Chyba chodzi o coś takiego:

(na podstawie tego co już masz)

#include <iostream>
#include <conio.h>
#include <ctime>

using namespace std;

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

    cout << "Podaj ilosc znakow..." << endl;
    cin >> n;

    int ca = 0, cb = 0, cx = 0;
    
    for (int i = 0; i < n; i++)
    {
        if (rand() % 2 == 0)
        {
            cout << "a";
            ++ca;
        }
        else
        {
            cout << "b";
            ++cb;
        }
        if (cb > ca)
            cx = i+1;
    }
    cout<<'\n'<<cx;
    getch();
}
 

ale nie jestem pewien, bo dla mnie to polecenie jest trochę niejasne.

I pozbądź się biblioteki conio, bo nie jest tu do niczego potrzebna.

[Pr0sikor]

To jest treść tego zadania :

 

 

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 1000), oznaczającą

liczbę znaków. Kolejny wiersz zawiera napis złożony z n liter a1a2 . . . an (ai ∈ {a, b}). Jeśli ai = a, to i-tym

znakiem w rzędzie jest a, w przeciwnym przypadku jest to b.

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą liczbie owoców w najdłuższym spójnym fragmencie rzędu, który spełnia wymagania. Jeśli warunki nie mogą zostać spełnione, prawidłowym wynikiem jest 0.

 

Niestety jeszcze jest jeden warunek że musi być spełnione jeżeli by było wczytywane od lewej do prawej i od prawej do lewej w tym jeżeli w chociaż jednym warunek nie jest spełniony szuka innego ciągu...
Wysypałem się na tej części i nie wiem jak się do tego w ogóle zabrać... :/

[hax]

strasznie zagmatwane...
nie wiem czy dobrze zrozumiałem że masz np ciąg abbaaaaabbbaaaa i ma ci zwracać jaki jest najdłuższy ciąg który spełnia warunek ilość 'a'>ilość 'b'?

czyli w tym przypadku cały ciąg

[Pr0sikor]

Tak o to mi chodzi ale już dosyć długo nie spałem i mam problem z wyrażeniem się
Ale musi jeszcze spełnić warunek dla sprawdzania tego od prawej do lewej i od lewej do prawej. a ten ciąg znaków wypisałem jako przykład tak na ślepo.
Teraz próbuję coś wykombinować ale nie idzie :/

[hax]

hmmm.
dynamiczna tablica tab do której wpisujesz ciąg znaków

zmienne typu int z wartością początkową 0, które będą zwracały indeksy początku i końca w tablicy dla maksymalnego ciągu spełniającego warunek

i zmienna max która będzie mówić ile liter mamy w najdłuższym ciągu

dwie pętle zagnieżdżone
które przechodzą od tab[0] do tab[rozmiar] następnie od tab[1] do tab[rozmiar] itd.

no i sprawdzasz warunek

jeżeli się zgadza to zapisujesz w zmiennej max ilość znaków które spełniają warunek i zmieniasz indeksy

i jeszcze dałbym warunek jeżeli max>(rozmiar-i) to kończymy bo już nie znajdzie dłuższego, gdzie i to licznik pierwszej pętli

[Kubusiasty]

a to nie jest przypadkiem zadanie z OI ? :P

[Pr0sikor]

Po wygooglowaniu o co chodzi z OI stwierdzam że nie zadanie to dał mi nauczyciel bo w tydzień nauki wyszedłem ponad program nauczania a do konkursów jak na razie nie planuje się zgłaszać bo rok temu kolega który można powiedzieć, że pracuje jako programista i nie przeszedł etapu :/

Ty bierzesz udział ?

[IeMaster]

na OI jest że z dwóch stron nie może być mniejsza ilosć pomarańczy a tu wersja easy tylko z jednej strony

[Pr0sikor]

LOL żeby nie było że ja zrobie zadanie a ta gnida je wrzuci bo mi dał coś takiego :

Napisz program który dla wpisanej ilości losowy wyświetlanych wartości a lub b wyliczy największy ciąg znaków spełniający warunek : a>b dla wczytywanych wartości od prawej do lewej i od lewej do prawej.

[Kubusiasty]

"gnida" jest raczej za stara ,OI jest dla licealistow max :P Ale jak zrobisz to zadanie ,to co ci szkodzi wrzucenie tego na OI ? Powodzenia

[Vesim]

#include <string>

int main()
{
	char test[] = "aaaaaaaabbbbbbbbbbaaaaa";

	int max_a = 0;
	int start_a = 0;

	int max_b = 0;
	int start_b = 0;

	bool a = false;
	for(int i = 0; i < strlen(test); i++){
		if(!a && test[i] == 'a'){
			start_a = i;
			a = true;
		}else if(a && test[i] == 'b'){
			start_b = i;
			a = false;
		}else if(i - start_a > max_a && a){
			max_a = i - start_a;
		}else if(i - start_b > max_b && !a){
			max_b = i - start_b;
		}
	}
	max_a++;
	max_b++;
	printf("string:%s\nmax_a: %d\nmax_b: %d", test, max_a, max_;
	getchar();
	return 0;
}

Coś w tym stylu?

[REPREDATOR]

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

 
using namespace std;

int main()
{
	string lan;
	string napis;
	string maxt;
	
	
	int n,i,j,k,w,iA=0,iB=0,max=0;
	
	srand((unsigned)time(NULL));
	
	n=rand() % 1000 + 1; 

  	for(i=0;i<n;i++) lan+=char(65+rand()%2);
	

	    cout<<" Wygenerowano losowy lancuch o dlugosci "<<n<<" znakow :\n - "<<lan<<"\n";


 
for(i=0;i<n;i++)
    for(j=i+1;j<=n;j++)
    {
		napis=lan.substr(i,j-i); 
		  
	for (unsigned w=0;w<=napis.length()-1;++w)
 		{
			if (napis[w]==65) ++iA;
				else iB++;
		}

	if(iA>iB)
		{	//wyswietlanie , nie polecam jak lancuch ma skladac sie z 1000 znakow ... ,') 
			//for(k = 0; k < i; k++)cout<<" ";
			//cout<<lan.substr(i,j-i)<<"\n";
       			 
       		if(lan.substr(i,j-i).length()>max)
       			{
					max=lan.substr(i,j-i).length();
					maxt=lan.substr(i,j-i);
				}
		}
			
	iA=0;
	iB=0;				
    }

  cout<<"\n\n Najdluzszy lancuch spelniajacy warunek (ilosc znakow 'A'>'B') : \n - sklada sie z "<<max<<" znakow\n - "<<maxt;



  return 0;
}



 //http://ideone.com/N1dXCe

Takie cus ?

 

Od lewej do prawej czy na odwrot to w tym wypadku bedzie to samo , wiec nie trzeba sie tym martwic ;]