Šta je novo?
Od:
Filteri

Pomoc oko programa u C

T

TheRevolucija

Cenjen
Učlanjen(a)
08.05.2011
Poruke
169
Poena
169
Pozdrav!
Treba da ispisem mali programcic u C-u koji radi sledece:

ucitava niz, a zatim trazi duzinu najduzeg podniza koji se sastoji od nula i ispisuje pocetnu i krajnju poziciju tog podniza.

Npr, niz je 1 2 0 0 3 0 4 0 0 0 0 8
dakle, duzina najduzeg podniza 0 jeste 4, a pocetna i krajnja pozicija su 8 i 11.

Ovde imam delic koda
Kod: 
duz = 0;
		d = 0;
		for(j=1;j<db;j++) {
			if (b[j-1]==0) {d++; kraj=j; if(d>duz)duz=d;}
			else if(b[j]!=0)d=0;
		}

Ideja je sledeca:
petlja for prolazi kroz niz, ako je tekuci element jednak nuli, duzina niza se uvecava za 1, a promenljiva kraj oznacava da je taj element poslednji. Ako je tekuca duzina veca od duzine, duzina dobija vr tekuce duzine. Zatim se proverava da li je naredni element razlicit od nule. Ako jeste, dolazimo do toga da tekucu duzinu resetujemo na nulu.

Ovo je kostur, za koji sam svestan da ne radi... Medjutim, kako sam pocetnik, i vec sat i po se mlatim sa ovim, trenutno nisam u stanju da smislim logicne ispravke za kod, te bih molio za pomoc.
 
Preporučio bih ti da prvo napišeš jednostavno i direktno rešenje. Zamisliš kako bi ti rešio taj problem koristeći papir i olovku, pa onda taj algoritam pretočiš u kod. Naravno, mnogo bolje je ako možeš da zamisliš kako bi CPU najefikasnije rešio taj problem. :)

Znači prvo napišeš nešto ovako:

Kod: 
void FindLargestSubArray_001(int *sourceArray, const int arraySize, int *p_startPos, int *p_endPos)
{
	int currentSubSize = 0, recordedSubSize = 0;
	int currentStartPos = -1, recordedStartPos = -1;
	int subStarted = 0;
	int i;
	int endIndex = arraySize - 1;

	for(i=0; i <= endIndex; i++)
	{
		//first element found
		if( (subStarted == 0) && (sourceArray[i] == 0) )
		{
			subStarted = 1;
			currentStartPos = i;
			currentSubSize = 0;
		}

		//subArray is in progress
		if( (subStarted == 1) && (sourceArray[i] == 0) )
			currentSubSize++;

		//subArray ended
		if( (subStarted == 1) && ((sourceArray[i] != 0) || (i == endIndex)) )
		{
			subStarted = 0;
			
			if( currentSubSize > recordedSubSize )
			{
				recordedSubSize = currentSubSize;
				recordedStartPos = currentStartPos;
			}
		}

	}

	
	*p_startPos = recordedStartPos;
	*p_endPos   = recordedStartPos + recordedSubSize - 1;

	return;
}


Onda možeš da probaš da napraviš neku drugačiju varijaciju:

Kod: 
void FindLargestSubArray_002(int *sourceArray, const int arraySize, int *p_startPos, int *p_endPos)
{
	int currentSubSize = 0, recordedSubSize = 0;
	int currentStartPos = -1, recordedStartPos = -1;
	int i;
	int endIndex = arraySize - 1;

	for(i=0; i <= endIndex; i++)
	{
		if( sourceArray[i] == 0 )
		{
			if(currentSubSize == 0)
				currentStartPos = i;
			currentSubSize++;
		}
		
		if ( (sourceArray[i] != 0) || (i == endIndex) )
		{
			if(currentSubSize > recordedSubSize)
			{
				recordedSubSize = currentSubSize;
				recordedStartPos = currentStartPos;

				currentSubSize = 0;
			}
		}

	}

	
	*p_startPos = recordedStartPos;
	*p_endPos   = recordedStartPos + recordedSubSize - 1;

	return;
}
 
Poslednja izmena:
Hvala veliko!
Nesto slicno sam pokusavao, ali uvek zakucam kod tih "granicnih slucajeva", tj ako je nula na kraju, kako pravilno da implementiram for petlju.

Kod: 
if ( (sourceArray[i] != 0) || (i == endIndex) )
.
I nikako ovog da se setim.

Jos jednom, hvala veliko!
 
Zato ti kažem, prvo smisli kako bi rešio problem.

Na prvom primeru:

Pri iteraciji kroz niz imaš tri relevantna slučaja: naišao si na početak podniza, podniz je već počeo i naišao si na sledeći element, podniz se završio.

Sada definišeš uslov za svaki slučaj:
početak podniza - podniz nije u toku i trenutni element niza je 0;
naišao si na sledeći element koji pripada podnizu - podniz je u toku i trenutni element je 0;
podniz se završio - trenutni element nije 0 ili si stigao do kraja niza.

Onda na osnovu toga napišeš kod.
 
Poslednja izmena:
Opet imam jedno pitanjce.
Treba da pronadjem najvecu sumu elemenata svih dijagonala matrice.

Tj, imam prvaougaonu matricu, i treba da nadjem sve sume po svim dijagonalama i da nadjem najvecu od tih suma.

Problem je da smislim nacin da prodjem kroz dijagonale koje nisu glavna i sporedna (jer nije u pitanju kvadratna matrica)
 
Moraš rešenje da potražiš u matematici. ;)

Ako znaš da je kod kvadratne matrice i=j za glavnu dijagonalu, a kod pomoćne dijagonale i+j=n+1, lako ćeš da dođeš do if uslova koji određuje te elemente.

E sad, nađi sam elemente ostalih dijagonala. :)

Kod matrica moraš da imaš duplu for petlju. Recimo, u C# :

Kod: 
for (int i = 0; i < M; i++)
{
	for (int j = 0; j < N; j++)
	{
		if (i == j)
		{
			// nešto se izvršava
		}
		else if (i + j == N - 1)
		{
			// nešto se izvršava
		}
	}
}

Verovatno ima elegantnijih rešenja ali ovo mi je prvo palo na pamet.
 
Poslednja izmena:
Sale KG je napisao(la):
Moraš rešenje da potražiš u matematici. ;)

Ako znaš da je kod kvadratne matrice i=j za glavnu dijagonalu, a kod pomoćne dijagonale i+j=n+1, lako ćeš da dođeš do if uslova koji određuje te elemente.

E sad, nađi sam elemente ostalih dijagonala. :)

Kod matrica moraš da imaš duplu for petlju. Recimo, u C# :

Kod: 
for (int i = 0; i < M; i++)
{
	for (int j = 0; j < N; j++)
	{
		if (i == j)
		{
			// nešto se izvršava
		}
		else if (i + j == N - 1)
		{
			// nešto se izvršava
		}
	}
}

Verovatno ima elegantnijih rešenja ali ovo mi je prvo palo na pamet.
Kliknite za proširenje...

Koliko vidim, ovo se odnosi na kvadratnu matricu.

Ali ako imam matricu oblika

1 2 3 4 5
6 7 8 9 10

dijagonale bi bile elementi 1-7; 2-8; 3-9; 4-10; ili 5-9; itd... te ne znam kako da sa dva for-a obuhvatim takve dijagonale.
 
Pa napisao sam ti primer a ti ga razradi i potraži rešenje u matematici. Ne znam ni ja napamet. Dao sam ti primer kako bi to moglo da se uradi za glavnu i pomoćnu dijagonalu, nisam razumeo da želiš sve "na tacni".

Ajda malo razmisli sam pa ako ne ide ti se javi opet. ;)

EDIT: Sa for petljama obuhvataš celu matricu a ne dijagonale. One ti "vrte" sve članove matrice a sa if uslovom ispituješ koji je element pravi. Kapiraš sad?

EDIT 2: Evo šta kaže Google na upit: "elementi na dijagonalama matrice"

http://arhiva.elitesecurity.org/t375486-elementi-matrice-koji-pripadaju-istoj-dijagonali

Mrzi me da gledam sve ovo, mislim da ti odgovara primer, ali ne verujem da si se potrudio sam da pronađeš rešenje.
 
Poslednja izmena:
Kreni redom kroz elemente prvog reda, od svakog kreni dijagonalno po obe dijagonale i izračunaj sume.
 
Sale KG je napisao(la):
Kod matrica moraš da imaš duplu for petlju. Recimo, u C# :
Kliknite za proširenje...

ne mora dupla petlja, matrice su podskup nizova zato sto imaju konacan (samim tim i prebrojiv) broj elemenata. tj. mozes da je prodjes u jednoj petlji, samo je vise smaranja (meni bar).

meni to deluje kao klasican divide & conquer problem, ali nemam sad vremena da razradjujem. nadjes najmanju dimenziju (ako je 5x3 onda 3), i samo trazis obe dijagonale za sve tri 3x3 matrice koje se nalaze unutar te 5x3.
 
Evo mene opet :)

Zanima me sledece:
treba da unesem string, ciju duzinu ne znam unapred. Memorija treba da se alocira dinamicki.

ja sam to uradio na sledeci nacin:

dodelio sam jedan bajt memorije (za znak '\0'), a zatim svaki put kada ucitam novi karakter sa getchar() (dok god je getchar()!='\n') uvecam brojac duzine za jedan i alociram (d+1)*sizeof(char) preko realloc. Medjutim, uvek mi izbacuje duzi string nego sto to zapravo jeste. Npr unesem test, kad stavim printf("%s", string), izbaci test=2222 itd.

Ako neko moze da pogleda kod, i pomogne da pronadjem gde je greska
Kod: 
void main() {
	char *niz;
	char c;
	int d=1,i=0;

	niz=(char*)malloc(sizeof(char));
	while ( (c=getchar()) != '\n')
	{
		d++;
		niz = (char*)realloc (niz, d);
		niz[i]=c;
		i++;
	}
 
Moras na kraju da na poslednje mesto stavis '\0' da bi ti to bio string.
 
Odlična strategija, postavljanje istog pitanja na više foruma, ali to ipak ne garantuje brži odgovor jer ima dosta istih ljudi na različitim forumima. :)

Elem, najlakše je koristiti funkciju koja ti čita ceo string sa ulaza.

fgets(char* buffer, int legth, FILE* stream);
Kod: 
//Alociraš memoriju, recimo 200 bajtova
char* buffer = malloc(200)
//i pozoveš
fgets(buffer, 200, stdin);
Pročitaće najviše 199 char-ova iz stdin-a (jer terminiše string sa nulom), ako naiđe na newline karakter pročitaće do njega i ubaciti ga na kraj stringa.
 
Poslednja izmena:
Morate se prijaviti ili registrovati da odgovorite ovde.
Nazad
Vrh Dno