[JAVA] DIVIDE ET IMPERA: esercizio semplice? Forse.. ma nessuno lo risolve.

[DoctorZ]

Buongiorno Dottori,

ho un quesito da porvi. Sapreste realizzare questo esercizio in Java?

Utilizzare la tecnica "Divide Et Impera" per calcolare quante volte la sequenza 'a' 'b' 'a' si ripete all'interno di un array di caratteri

Io ho provato a svolgerlo, ma in ogni caso sembra entrare in un loop.
Molti sostengono sia facile. Il problema è che nessuno riesce a svolgerlo!

[variabilepippo]

Sapreste realizzare questo esercizio in Java?

Sì, ma ti ricordo che questo è un forum con regole ben precise.

Molti sostengono sia facile. Il problema è che nessuno riesce a svolgerlo!

Non solo è facile, ma esiste molta letteratura in merito. Mostra la tua soluzione non funzionante.

[DoctorZ]

te lo posto subito.

Ne ho provate 2 versioni, le posto entrambe:

Prima versione

public class divideEtImpera {

	public static int conta (char []A, int first, int last) {
		
		int n = 0;
		int m = 0;
		int z = 0;
		
		if (first<last) {	
			
			int half = (first+last)/2;
			conta (A, first, half);
			conta (A, half+1, last);
			
			int i=0;
			
			while (i<A.length-1) {
				if (A[i]=='a' && A[i+1]=='b' && A[i+2]=='a') {
					n++;
					i++;
				}
			}
			
			//valuto il centro
			if (A[half-1]=='a' && A[half]=='b' && A[half+1]=='a')
				z++;
			else if (A[half]=='a' && A[half+1]=='b' && A[half+2]=='a')
				z++;
			
		}return n + m + z;
	}
	
	
	
	public static void main(String[] args) {
		char [] A = {'c', 'a', 'b', 'a', 'b'};
		conta(A, 0, A.length);
	}
}

E questa è la seconda:

public class divideEtImpera {

	public static int conta (char []A) {
		
		int n = 0;
		int m = 0;
		int z = 0;
		
		if (A.length > 2) {	
			
			int half = A.length/2;
			char [] left = new char [half];
			char [] right = new char [A.length - half];
			divide(A, left, right);
			conta(left);
			conta(right);
			
			int i=0;
			
			while (i<left.length) {
				if (left[i]=='a' && left[i+1]=='b' && left[i+2]=='a') {
					n=conta(left) +1;
					i++;
				}
				else n=conta (left);
			}
			
			while (i<right.length) {
				if (right[i]=='a' && right[i+1]=='b' && right[i+2]=='a') {
					m=conta(right) +1;
					i++;
				}
				else m=conta(right);
			}
			
			if (A[half-1]=='a' && A[half]=='b' && A[half+1]=='a')
				z=conta(A) +1;
			else if (A[half]=='a' && A[half+1]=='b' && A[half+2]=='a')
				z=conta(A) +1;
			else z=conta(A);
			
		}return n + m + z;
		//else non fare nulla perchè gli elementi sono due
	}
	
	
	public static void divide (char []A, char []left, char []right) {
		int i;
		for (i=0; i<left.length; i++)
			left[i] = A[i];
		for (i=0; i<right.length; i++)
			right[i] = A[left.length +1];
	}
	
	
	public static void main(String[] args) {
		char [] A = {'a', 'c', 'b', 'a', 'b', 'a', 'c', 'a', 'b', 'a'};
		conta(A);
	}
}

Credo che la prima sia megliore della seconda ma sono comunque bloccato
perchè entrambe sembrano entrare in loop

[isAlreadyInUse]

Ormai ci provano in tutti i modi per farsi fare i compitini

[DoctorZ]

Originariamente inviato da isAlreadyInUse

Ormai ci provano in tutti i modi per farsi fare i compitini

no non è un compitino

è semplicemente il vecchio esame che non ho superato a giugno
siccome nei prossimi appelli la solfa sarà più o meno la stessa, ovvero c'è l'esercizio sul metodo "divide et impera" sto cercando di capirci di più, svolgendo il testo del MIO VECCHIO ESAME NON SUPERATO.

non parlare a vanvera giusto per farti aumentare i mex

[isAlreadyInUse]

E bravo!
Adesso torna ai tuoi compitini.

[DoctorZ]

ma io sinceramente non ti capisco

ma almeno tu sai che cos'è un compitino?
come diavolo posso fare un compitino e postare qui sul forum????

non è un compitino il mio e sia chiaro!

Io a giugno ho sostenuto l'esame e non l'ho superato.
Nell'esame c'era questo esercizio e ora me lo sto svolgendo a casa e sto cercando di capirci qualcosa chiedendo qui sul forum perchè non trovo l'errore.

Poi se non vuoi aiutarmi pazienza, anche perchè dai tuoi post letti in giro mi sembra tu sia alle prime armi, ma non mi riguarda.

Ma questo che ti piaccia o no NON è un compitino e non potrebbe nemmeno esserlo.

Spero di essere stato chiaro.

[isAlreadyInUse]

Dai miei post letti in giro ti sembro alle prime armi?
E quali sarebbero di grazia?

[DoctorZ]

Nessuno può darmi una mano con il mio esercizio?
E' come se entrasse in loop, anzi quasi certamente entra in loop perchè aprendo il task manager ho la CPU inchiodata al 100%

ma non credo la tecnica usata sia errata, solo c'è qualcosa che non va ma non riesco proprio capire in che punto

[Furla]

l'ultima "a" di una sequenza può essere contata come la prima di un'altra?

[DoctorZ]

Originariamente inviato da Furla

l'ultima "a" di una sequenza può essere contata come la prima di un'altra?

mmh.. nell'esercizio non è specificato, quindi suppongo di si.
Anzi, a rigor di logica sono quasi certo di si.

[wingman87]

Ho dato solo uno sguardo veloce, nel primo mi sembra che la condizione del ciclo while viene mutata solo quando entri nell'if, credo sia quello il problema. Nel secondo ho visto che fai una cosa simile ma non so se è proprio lo stesso problema.

[ally]

...la prima non sembra male...

...ti posto la mia soluzione...

public static void abreyu(Stringhe[] arrayDiStringhe){

intero trovati = 0;

for(intero = 0;intero<arrayDiStringhe.lunghezza()-3;intero = intero + 1)
se(arrayDiStringhe[intero].èUguale("a") e arrayDiStringhe[intero+1].èUguale("b") e arrayDiStringhe[intero+2].èUguale("a"))
trovati = trovati+1;

}

...mh...sono le otto perdonate se ho scritto stupidaggini...

...ciao...

[DoctorZ]

Originariamente inviato da ally

...la prima non sembra male...

...ti posto la mia soluzione...

public static void abreyu(Stringhe[] arrayDiStringhe){

intero trovati = 0;

for(intero = 0;intero<arrayDiStringhe.lunghezza()-3;intero = intero + 1)
se(arrayDiStringhe[intero].èUguale("a") e arrayDiStringhe[intero+1].èUguale("b") e arrayDiStringhe[intero+2].èUguale("a"))
trovati = trovati+1;

}

...mh...sono le otto perdonate se ho scritto stupidaggini...

...ciao...

Ti ringrazio per il post Ally, ma non è divide et impera

[DoctorZ]

Originariamente inviato da wingman87

Ho dato solo uno sguardo veloce, nel primo mi sembra che la condizione del ciclo while viene mutata solo quando entri nell'if, credo sia quello il problema. Nel secondo ho visto che fai una cosa simile ma non so se è proprio lo stesso problema.

mmh.. in che senso?

[wingman87]

Nel senso che se non entra nell'if va in un loop infinito.

[k0nt3]

perchè non provi a usare il debugger?

[ally]

Originariamente inviato da DoctorZ

Ti ringrazio per il post Ally, ma non è divide et impera

...cosa si intende per divide et impera?...

...ciao...

[DoctorZ]

Originariamente inviato da wingman87

Nel senso che se non entra nell'if va in un loop infinito.

mmh, si ho capito cosa intendi.
Però, non capisco perchè debba andare in loop se non entra nell'IF.
Nel senso, se nell'IF non ci entra, il programma smette, interrompre, perchè non trova più istruzioni.

Cioè giusto per capire, dici di metterci un

[code]
...
...

else {
fai qualcos'altro..
}

...
...

se intendi questo, cosa potrei fargli fare? il programma deve interrompere in quel punto..

un return 0 ?

[DoctorZ]

Originariamente inviato da k0nt3

perchè non provi a usare il debugger?

devo imparare ad utilizzarlo in Eclipse non ho mai provato