View Full Version : [JAVA] DIVIDE ET IMPERA: esercizio semplice? Forse.. ma nessuno lo risolve.
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! :D
variabilepippo
28-11-2007, 15:29
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.
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
28-11-2007, 15:54
Ormai ci provano in tutti i modi per farsi fare i compitini
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 :p
isAlreadyInUse
28-11-2007, 16:08
E bravo!
Adesso torna ai tuoi compitini.
ma io sinceramente non ti capisco :mbe:
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
28-11-2007, 16:24
Dai miei post letti in giro ti sembro alle prime armi?
E quali sarebbero di grazia?
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
l'ultima "a" di una sequenza può essere contata come la prima di un'altra?
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
28-11-2007, 19:42
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.
...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...
...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
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
28-11-2007, 23:41
Nel senso che se non entra nell'if va in un loop infinito.
perchè non provi a usare il debugger?
Ti ringrazio per il post Ally, ma non è divide et impera
...cosa si intende per divide et impera?...
...ciao...
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 ?
perchè non provi a usare il debugger?
devo imparare ad utilizzarlo in Eclipse non ho mai provato
...cosa si intende per divide et impera?...
...ciao...
E' un tipo di algoritmo che suddivide un problema in sottoproblemi.
Può essere di ricerca, di ordinamento..
devo imparare ad utilizzarlo in Eclipse non ho mai provato
tutto quello che devi fare è piazzare un paio di breakpoint e lanciare il programma in modalità debug. da solo ti chiederà di passare alla visuale debug.. oppure impostala manualmente (al posto della visuale "java" in alto a destra).
un'altra possibilità è quella di stampare a schermo i risultati intermedi dell'algoritmo o il valore di alcune variabili significative, ma io ti consiglio di usare il debug.
wingman87
29-11-2007, 12:17
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 ?
Allora, il pezzo di codice a cui mi riferisco è questo:
while (i<A.length-1) {
if (A[i]=='a' && A[i+1]=='b' && A[i+2]=='a') {
n++;
i++;
}
}
La condizione del ciclo è "i<A.length-1" ma la lunghezza di A non cambierà mai, l'unica cosa che può cambiare è i giusto? Ma se i lo modifichi solo se entri nell'if, basta che non entri una volta e i non cambierà mai più e quindi la condizione di ciclo resterà sempre vera (e quindi resterai nel ciclo per sempre).
Ti ringrazio per il post Ally, ma non è divide et impera
se è per questo non era manco Java
...cosa si intende per divide et impera?...
...ciao...
http://en.wikipedia.org/wiki/Divide_et_impera
edit - scusate, ho beccato la prima cosa su wikipedia senza manco leggere :sbonk: :rotfl: :rotfl:
edit2 - ecco, questo va decisamente meglio :D :D :D
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
posto che è un'idiozia risolvere questo esercizio con un algoritmo divide et impera, questa è la mia soluzione:
public class DivideEtImpera
{
private String content;
public DivideEtImpera(String content)
{
this.content = content;
}
private int divideEtImpera(int startOffset, int endOffset)
{
if (endOffset > startOffset)
{
int halfSpan = (endOffset - startOffset) / 2;
return divideEtImpera(startOffset, startOffset + halfSpan) + divideEtImpera(startOffset + halfSpan + 1, endOffset);
}
else
{
String test = new String(content.toCharArray(), startOffset, 3);
if (test.equals("aba"))
{
return 1;
}
else
{
return 0;
}
}
}
public int count()
{
return divideEtImpera(0, content.length() - 3);
}
}
public class Test1
{
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
DivideEtImpera divideEtImpera = new DivideEtImpera(reader.readLine());
System.out.println(divideEtImpera.count());
}
}
sono d'accordo che è una cosa insensata risolvere questo tipo di esercizio con un divide et impera, ma purtroppo questo vogliono.
ho dato un'occhiata veloce, ma ti dico già che hai fatto lo stesso errore che avevo fatto io al vecchio appello, ovvero "aba" è una stringa, non una sequenza di caratteri.
L'array che la funzione prende in input è di caratteri, non di stringhe.
non esiste un carattere 'aba'
l'impostazione del programma però non sembra male.
Devo provare a darci un'occhiata.
Ma l'hai già testato?
AnonimoVeneziano
29-11-2007, 16:01
Una domanda.
Le stringhe si possono sovrapporre?
Tipo :
abababa quante sottostringhe "aba" sono? Se si possono sovrapporre sono 3 stringhe, se non si possono sovrapporre è essenzialmente la prima e l'ultima.
Ciao
ho dato un'occhiata veloce, ma ti dico già che hai fatto lo stesso errore che avevo fatto io al vecchio appello, ovvero "aba" è una stringa, non una sequenza di caratteri. adesso si mettono pure a fare pignolerie sui dettagli implementativi? vogliono un algoritmo secondo il paradigma divide et impera, quello ho scritto. se volevano che l'implementazione dell'algoritmo utilizzasse un array di caratteri {'a', 'b', 'a'} anziché direttamente una stringa "aba" allora 1) dovevano scriverlo nel testo dell'esercizio, e 2) è una stronzata.
L'array che la funzione prende in input è di caratteri, non di stringhe.
non esiste un carattere 'aba' il programma che ho scritto:
1) non ha funzioni
2) i metodi che ha non ricevono come parametri ne' stringhe ne' array di caratteri
3) l'input lo prende dalla console, e per fare questo il sistema più naturale in Java (esemplificato anche nella documentazione della Sun) è utilizzare un oggetto String letto tramite BufferedReader ed InputStreamReader
4) non ha array di stringhe, fatta eccezione per gli argomenti del main che se ci fai caso vengono bellamente ignorati.
Ma l'hai già testato? molto sommariamente.
ommioddio che leggo... :asd:
sono andato a riguardarmi il testo dell'esercizio ed effettivamente richiede proprio l'uso di un array di caratteri :|
in tal caso mi correggo:
adesso si mettono pure a fare pignolerie sui dettagli implementativi? vogliono un algoritmo secondo il paradigma divide et impera, quello ho scritto. se volevano che l'implementazione dell'algoritmo utilizzasse un array di caratteri {'a', 'b', 'a'} anziché direttamente una stringa "aba" allora 1) dovevano scriverlo nel testo dell'esercizio, e 2) è una stronzata. rimane solamente il punto 2 :asd:
voilà, poche banalissime correzioni:
public class DivideEtImpera
{
private char[] content;
public DivideEtImpera(String content)
{
this.content = content.toCharArray();
}
private int divideEtImpera(int startOffset, int endOffset)
{
if (endOffset > startOffset)
{
int halfSpan = (endOffset - startOffset) / 2;
return divideEtImpera(startOffset, startOffset + halfSpan) + divideEtImpera(startOffset + halfSpan + 1, endOffset);
}
else
{
String test = new String(content, startOffset, 3);
if (test.equals("aba"))
{
return 1;
}
else
{
return 0;
}
}
}
public int count()
{
return divideEtImpera(0, content.length - 3);
}
}
mi spiace ma li ho fregati :rolleyes:
Maverick18
29-11-2007, 16:52
Non riesco davvero a capire il senso di questo esercizio. il divideEtImpera in questo caso è inutile, a meno che non si voglia dividere il programma in due metodi, uno che ricava le sottostringhe di 3 caratteri ed un altro metodo che confronta i tre caratteri. Davvero non ha senso, comunque se è come l'ho interpretato io, l'esercizio è fattibile in pochi minuti.
Una domanda.
Le stringhe si possono sovrapporre?
Tipo :
abababa quante sottostringhe "aba" sono? Se si possono sovrapporre sono 3 stringhe, se non si possono sovrapporre è essenzialmente la prima e l'ultima.
Ciao
Non è specificato nell'esercizio, a mio avviso a rigor di logica possono sovrapporsi. Ma miraccomando, non sono stringhe, sono caratteri
ommioddio che leggo... :asd:
sono andato a riguardarmi il testo dell'esercizio ed effettivamente richiede proprio l'uso di un array di caratteri :|
in tal caso mi correggo:
rimane solamente il punto 2 :asd:
come non quotare ;)
Non riesco davvero a capire il senso di questo esercizio. il divideEtImpera in questo caso è inutile, a meno che non si voglia dividere il programma in due metodi, uno che ricava le sottostringhe di 3 caratteri ed un altro metodo che confronta i tre caratteri. Davvero non ha senso
Maverick purtroppo non c'è un senso, ma questo è quanto richiesto dall'esercizio
Avrebbe senso se utilizzassi un metodo divide et impera per l'ordinamento, come ad esempio il merge sort, potrebbe avere un senso
ma per la ricerca.. mha
comunque se è come l'ho interpretato io, l'esercizio è fattibile in pochi minuti.
bhe.. va bhe lasciamo stare :p
voilà, poche banalissime correzioni:
...
...
....
mi spiace ma li ho fregati :rolleyes:
Allora, guarda qua, è il tuo codice, riassemblato.
Da due errori, evidenzio il codice che genera l'errore in grassetto.
In fondo ti scrivo cosa dice il compilatore.
import java.io.*;
import java.util.*;
public class Mio_DivideEtImperaChar {
private char[] content;
public DivideEtImpera(String content)
{
this.content = content.toCharArray();
}
private int divideEtImpera(int startOffset, int endOffset) {
if (endOffset > startOffset)
{
int halfSpan = (endOffset - startOffset) / 2;
return divideEtImpera(startOffset, startOffset + halfSpan) + divideEtImpera(startOffset + halfSpan + 1, endOffset);
}
else
{
String test = new String(content, startOffset, 3);
if (test.equals("aba"))
return 1;
else
return 0;
}
}
public int count()
{
return divideEtImpera(0, content.length - 3);
}
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
DivideEtImpera divideEtImpera = new DivideEtImpera(reader.readLine());
System.out.println(divideEtImpera.count());
}
}
primo grassetto: Return type for the method is missing;
i 2 grassetti nel main: DivideEtImpera cannot be resolved to a type;
franksisca
29-11-2007, 17:45
Allora, guarda qua, è il tuo codice, riassemblato.
Da due errori, evidenzio il codice che genera l'errore in grassetto.
In fondo ti scrivo cosa dice il compilatore.
public class Mio_DivideEtImperaChar {
private class DivideEtImpera{
//cut
}
}
primo grassetto: Return type for the method is missing;
i 2 grassetti nel main: DivideEtImpera cannot be resolved to a type;
mancvava la dichiarazione della classe....
Avevi ragione ;)
rimane ancora un errore però. Riposto tutto:
import java.io.*;
public class Mio_DivideEtImperaChar {
private class DivideEtImpera {
private char[] content;
public DivideEtImpera(String content) {
this.content = content.toCharArray();
}
private int divideEtImpera(int startOffset, int endOffset) {
if (endOffset > startOffset) {
int halfSpan = (endOffset - startOffset) / 2;
return divideEtImpera(startOffset, startOffset + halfSpan) + divideEtImpera(startOffset + halfSpan + 1, endOffset);
}
else {
String test = new String(content, startOffset, 3);
if (test.equals("aba"))
return 1;
else
return 0;
}
}
public int count() {
return divideEtImpera(0, content.length - 3);
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
DivideEtImpera divideEtImpera = new DivideEtImpera(reader.readLine());
System.out.println(divideEtImpera.count());
}
}
l'errore è il seguente (faccio prima a fare uno screenshoot che a scriverlo!)
http://img516.imageshack.us/img516/4012/immaginefs6.jpg
primo grassetto: Return type for the method is missing; furbo... hai rinominato la classe senza rinominare il costruttore :rolleyes:
i 2 grassetti nel main: DivideEtImpera cannot be resolved to a type; embe', una volta che hai rinominato la classe...
piuttosto, visto che (mi pare che) usi Eclipse, anziché rinominare a muzzo usa gli strumenti di refactoring.
mindwings
29-11-2007, 19:56
furbo... hai rinominato la classe senza rinominare il costruttore :rolleyes:
embe', una volta che hai rinominato la classe...
piuttosto, visto che (mi pare che) usi Eclipse, anziché rinominare a muzzo usa gli strumenti di refactoring.
:D
non ti pare di essere un pò cattivello ciao :flower:
http://en.wikipedia.org/wiki/Divide_et_impera
edit - scusate, ho beccato la prima cosa su wikipedia senza manco leggere :sbonk: :rotfl: :rotfl:
edit2 - ecco, questo va decisamente meglio :D :D :D
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
...grazie...interessante...non ho colto pero' il vantaggio in questo caso specifico...con altri approcci si risolve con tre righe reali di codice...
...ciao...
hai provato a disegnare un automa e ad aiutarti?
nn è facile scriverlo sul comp, ma è:
stato 0: ci resto fin quando trovo b
esco se trovo a e passo allo
stato 1: ci resto fin quando ho a
esco se trovo b e passo allo
stato 2: qui è critico: se trovo a ho trovato la stringa ed incremento il contatore, ritornando allo stato 0
se trovo b devo ripartire da capo
se riesco a fore una foto ti allego il disegnino...
questa è informatica teorica, per la cronaca!
furbo... hai rinominato la classe senza rinominare il costruttore :rolleyes:
embe', una volta che hai rinominato la classe...
piuttosto, visto che (mi pare che) usi Eclipse, anziché rinominare a muzzo usa gli strumenti di refactoring.
allora, (abbi ancora un po' di pazienza :) ), l'ho rimessa come era
con il nome originale, ma da 3 errori, te li scrivo sotto.
import java.io.*;
public class DivideEtImpera {
private class DivideEtImpera {
private char[] content;
public DivideEtImpera(String content) {
this.content = content.toCharArray();
}
private int divideEtImpera(int startOffset, int endOffset) {
if (endOffset > startOffset) {
int halfSpan = (endOffset - startOffset) / 2;
return divideEtImpera(startOffset, startOffset + halfSpan) + divideEtImpera(startOffset + halfSpan + 1, endOffset);
}
else {
String test = new String(content, startOffset, 3);
if (test.equals("aba"))
return 1;
else
return 0;
}
}
public int count() {
return divideEtImpera(0, content.length - 3);
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
DivideEtImpera divideEtImpera = new DivideEtImpera(reader.readLine());
System.out.println(divideEtImpera.count());
}
}
Nested type DivideEtImpera hides an enclosing type;
The constructor DivideEtImpera(String) is undefined;
The method count() is undefined for the type DivideEtImpera
hai provato a disegnare un automa e ad aiutarti?
nn è facile scriverlo sul comp, ma è:
stato 0: ci resto fin quando trovo b
esco se trovo a e passo allo
stato 1: ci resto fin quando ho a
esco se trovo b e passo allo
stato 2: qui è critico: se trovo a ho trovato la stringa ed incremento il contatore, ritornando allo stato 0
se trovo b devo ripartire da capo
se riesco a fore una foto ti allego il disegnino...
questa è informatica teorica, per la cronaca!
dici a me yashi?
dici a me yashi?
eh... tu hai aperto il post si?
ti ho posto una soluzione indipendente dal codice, se capisci come funziona l'automa il codice è automatico...
questo per aiutarti quando sei seduto a fare l'esame....
o forse meglio lasciar perdere, che ti potresti confondere di +!
...il secondo errore deve essere dato perchè hai fatto un po' di casotto nel dichiarare la classe...
...non prendere male le mie parole...ma esistono un paio di regole base semplici semplici per lavorare in java...assimila bene queste e poi non avrai problemi...
...ciao...
AnonimoVeneziano
29-11-2007, 20:31
Prova con queste due classi :
Istruzioni :
1- Crea un nuovo progetto in eclipse
2- Crea un nuovo package chiamato "dei"
3- Crea due nuovi file all'interno del package "dei" . Uno si chiamerà "Dividieimpera.java" l'altro "Main.java" .
4- Cancella COMPLETAMENTE il contenuto dei due file e incollaci, in ordine, questi due listati :
Dividieimpera.java
package dei;
/**
*
* @author Maggioni Marcello
*/
public class Dividieimpera {
char[] stringa;
public Dividieimpera(char[] array) {
this.stringa = array;
}
public int getABANum() {
return realCount(0, stringa.length);
}
private int realCount(int index1, int index2) {
int length = (index2 - index1)/2;
if(index1 != index2)
return realCount(index1, index1+length) + realCount(index1 + length + 1, index2);
else if ( index1 <= stringa.length - 3 && stringa[index1] == 'a'
&& stringa[index1+1] == 'b' && stringa[index1+2] == 'a')
return 1;
return 0;
}
}
Main.java
package dei;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
*
* @author Maggioni Marcello
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
String input = null;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
input = br.readLine();
Dividieimpera dei = new Dividieimpera(input.toCharArray());
System.out.println("Il numero di sottostringhe è: " + dei.getABANum());
}
}
5- Salva ed esegui
Fammi sapere se funziona
Ciao
o forse meglio lasciar perdere, che ti potresti confondere di +!
ma quale lasciar perdere
li sto studiando anch'io in "linguaggi di programmazione I" gli automi a stati finiti deterministici/e non
vai tranquillo che i consigli sono sempre ben accetti ;)
Nested type DivideEtImpera hides an enclosing type;
The constructor DivideEtImpera(String) is undefined;
The method count() is undefined for the type DivideEtImpera il primo errore mi sembra chiarissimo, no? rinomina la classe esterna e vedrai che li risolvi tutti. non usare gli strumenti di refactoring di Eclipse, non vorrei che rinominasse anche la chiamata al costruttore nel main.
vuoi sapere perchè il tuo programma va in loop?
while (i<A.length-1) {
if (A[i]=='a' && A[i+1]=='b' && A[i+2]=='a') {
n++;
i++;
}
}
ha tutta l'aria di essere un while(true)
ps. mi sono deciso a usare il debug al posto tuo :D
EDIT: avevo incollato il codice sbagliato
Prova con queste due classi :
Istruzioni :
1- Crea un nuovo progetto in eclipse
2- Crea un nuovo package chiamato "dei"
3- Crea due nuovi file all'interno del package "dei" . Uno si chiamerà "Dividieimpera.java" l'altro "Main.java" .
4- Cancella COMPLETAMENTE il contenuto dei due file e incollaci, in ordine, questi due listati :
Dividieimpera.java
package dei;
/**
*
* @author Maggioni Marcello
*/
public class Dividieimpera {
char[] stringa;
public Dividieimpera(char[] array) {
this.stringa = array;
}
public int getABANum() {
return realCount(0, stringa.length);
}
private int realCount(int index1, int index2) {
int length = (index2 - index1)/2;
if(index1 != index2)
return realCount(index1, index1+length) + realCount(index1 + length + 1, index2);
else if ( index1 <= stringa.length - 3 && stringa[index1] == 'a'
&& stringa[index1+1] == 'b' && stringa[index1+2] == 'a')
return 1;
return 0;
}
}
Main.java
package dei;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
*
* @author Maggioni Marcello
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
String input = null;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
input = br.readLine();
Dividieimpera dei = new Dividieimpera(input.toCharArray());
System.out.println("Il numero di sottostringhe è: " + dei.getABANum());
}
}
5- Salva ed esegui
Fammi sapere se funziona
Ciao
Perfetto, funziona. :read:
Ho qualche dubbio però, ti elenco un paio di questions:
1. Perchè hai creato il package dei? E' solo una questione di migliore leggibilità del codice essendo scritto su due file? Nel senso, se avessi scritto il main e la classe DivideEtImpera in un unico file sarebbe stato uguale no?
2. Giusto per sapere: perchè utilizzare un costruttore...
char[] stringa;
public Dividieimpera(char[] array) {
this.stringa = array;
}
...invece di un metodo?
public static int divideEtImpera(char[] array) {
...
...
...
3. Perchè?
public int getABANum() {
return realCount(0, stringa.length);
}
4. Perchè -3? Cioè, ho capito che corrisponde alla numero di caratteri che compongono la sequenza "aba", ma sto provando a capire il perchè dirglielo
if(index1 != index2)
return realCount(index1, index1+length) + realCount(index1 + length + 1, index2);
else if ( index1 <= stringa.length - 3 && stringa[index1] == 'a'
&& stringa[index1+1] == 'b' && stringa[index1+2] == 'a')
return 1;
comunque le classi hanno nomi maiuscoli per convenzione -_-
AnonimoVeneziano
29-11-2007, 21:08
Perfetto, funziona. :read:
Ho qualche dubbio però, ti elenco un paio di questions:
1. Perchè hai creato il package dei? E' solo una questione di migliore leggibilità del codice essendo scritto su due file? Nel senso, se avessi scritto il main e la classe DivideEtImpera in un unico file sarebbe stato uguale no?
Perchè è sconsigliato l'uso del package di default nelle applicazioni Java. Anche se in una applicazione di esempio del genere è abbastanza irrilevante è meglio farlo sempre per abituarsi bene subito.
2. Giusto per sapere: perchè utilizzare un costruttore...
char[] stringa;
public Dividieimpera(char[] array) {
this.stringa = array;
}
...invece di un metodo?
public static int divideEtImpera(char[] array) {
...
...
...
Visto che di mezzo c'erano gli array era necessario mandare anche i due indici di inizio e fine dell'array ad ogni chiamata di funzione "dividiEtImpera()" facendola diventare qualcosa tipo "int divideEtImpera(char[], int, int)" , meno leggibile da parte dell'utilizzatore finale, a mio parere, rispetto alla soluzione con la classe a parte. Inoltre si separa la parte che esegue il lavoro dal main principale , il che è cosa buona
3. Perchè?
public int getABANum() {
return realCount(0, stringa.length);
}
Così si nasconde all'utente la funzione "realCount()" (che è più complicata, accetta 2 parametri ... etc) e gli si fornisce invece una funzione più semplice che non usa parametri in ingresso.
4. Perchè -3? Cioè, ho capito che corrisponde alla numero di caratteri che compongono la sequenza "aba", ma sto provando a capire il perchè dirglielo
if(index1 != index2)
return realCount(index1, index1+length) + realCount(index1 + length + 1, index2);
else if ( index1 <= stringa.length - 3 && stringa[index1] == 'a'
&& stringa[index1+1] == 'b' && stringa[index1+2] == 'a')
return 1;
Perchè se index1 è > di stringa.length - 3 come minimo stringa[index+2] lancia un ArrayOutOfBoundException che terminerebbe il programma. Per evitare ciò è necessario fare un controllo. Inoltre non ci potrebbe essere una substring "aba" in quel caso , perchè non ci sarebbero abbastanza lettere per comporla.
Ciao
ma quale lasciar perdere
li sto studiando anch'io in "linguaggi di programmazione I" gli automi a stati finiti deterministici/e non
vai tranquillo che i consigli sono sempre ben accetti ;)
allora per essere chiarA e tranquillA, se ti ti disegni l'automa, poni due variabili int=0 e case=o
implementi lo switch sul case e passi fra uno stato e l'altro.
quando riconosci una stringa, se la a finale può essere la a iniziale, vai sul case=1
altrimenti riparti dal case=0
qui hai l'immagine dell'automa...
http://www.sendspace.com/file/x7320n
^TiGeRShArK^
29-11-2007, 22:26
hai provato a disegnare un automa e ad aiutarti?
nn è facile scriverlo sul comp, ma è:
stato 0: ci resto fin quando trovo b
esco se trovo a e passo allo
stato 1: ci resto fin quando ho a
esco se trovo b e passo allo
stato 2: qui è critico: se trovo a ho trovato la stringa ed incremento il contatore, ritornando allo stato 0
se trovo b devo ripartire da capo
se riesco a fore una foto ti allego il disegnino...
questa è informatica teorica, per la cronaca!
:rotfl:
è vero che fa male informatica teorica :asd:
cmq pure io la prima cosa che avevo pensato era un'automa a stati finiti dato che è fatto apposta per parsare le stringhe appartenenti a grammatiche regolari :p
..Però in questo modo non sfrutti il divide et impera mi sa :fagiano:
P.S. addata su MSN...
se vedi un indirizzo strano sò io.. non mi bloccare :fagiano:
P.S. addata su MSN...
se vedi un indirizzo strano sò io.. non mi bloccare :fagiano: sto provolone :fagiano:
guarda che c'ha 28 anni c'ha :asd:
sto provolone :fagiano:
guarda che c'ha 28 anni c'ha :asd:
per TiGeRShArK questo ed altro...
per TiGeRShArK questo ed altro... cioè? gli presenti la tua amica 40enne? :|
:D
allora per essere chiarA e tranquillA, se ti ti disegni l'automa, poni due variabili int=0 e case=o
implementi lo switch sul case e passi fra uno stato e l'altro.
quando riconosci una stringa, se la a finale può essere la a iniziale, vai sul case=1
altrimenti riparti dal case=0
qui hai l'immagine dell'automa...
http://www.sendspace.com/file/x7320n
ehm.. non avevo notato che sei "chiarA e tranquillA" yashi :D
grazie per la foto.. ;)
però come diceva quel provolone di tiger, non usa il divide et impera
ehm.. non avevo notato che sei "chiarA e tranquillA" yashi :D
grazie per la foto.. ;)
però come diceva quel provolone di tiger, non usa il divide et impera
forse nn lo ricordo io ...
ma procede per passi...
cerca a
cerca ab
cerca aba
boh....
cmq il provolone è una carissima persona....:ciapet:
edito: non voglio insistere ma concettualmente penso che gli automi rispettino le caratteristiche del "procedere a piccoli passi" tipiche del divide et impera
^TiGeRShArK^
30-11-2007, 10:09
cmq il provolone è una carissima persona....:ciapet:
Infatti :O
:D
^TiGeRShArK^
30-11-2007, 10:16
cioè? gli presenti la tua amica 40enne? :|
:D
:mbe:
...ne ho anche troppe di amiche 34enni... :mbe:
a cuccia :O
:asd:
Visto che di mezzo c'erano gli array era necessario mandare anche i due indici di inizio e fine dell'array ad ogni chiamata di funzione "dividiEtImpera()" facendola diventare qualcosa tipo "int divideEtImpera(char[], int, int)" , meno leggibile da parte dell'utilizzatore finale, a mio parere, rispetto alla soluzione con la classe a parte. Inoltre si separa la parte che esegue il lavoro dal main principale , il che è cosa buona
... code ...
Così si nasconde all'utente la funzione "realCount()" (che è più complicata, accetta 2 parametri ... etc) e gli si fornisce invece una funzione più semplice che non usa parametri in ingresso.
... code ...
Perchè se index1 è > di stringa.length - 3 come minimo stringa[index+2] lancia un ArrayOutOfBoundException che terminerebbe il programma. Per evitare ciò è necessario fare un controllo. Inoltre non ci potrebbe essere una substring "aba" in quel caso , perchè non ci sarebbero abbastanza lettere per comporla.
Ciao
Ho provato a modificarlo un attimo il tuo codice, ma guisto per fare un prova.
Volevo chiederti un paio di cose, ti evidenzio in grassetto il punto in cui ho un dubbio.
public class DividiEtImpera {
char[] stringa;
public DividiEtImpera(char[] array) {
this.stringa = array;
}
public int getABANum() {
return realCount(0, stringa.length);
}
private int realCount(int left, int right) {
int half = (left + right)/2;
if(left != right)
return realCount(left, half) + realCount(half + 1, right);
else if ( left <= stringa.length - 3 && stringa[left] == 'a'
&& stringa[left+1] == 'b' && stringa[left+2] == 'a')
return 1;
return 0;
}
public static void main(String[] args) throws IOException {
char [] A = {'a', 'c', 'e', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'b', 'a', 'c'};
DivideEtImpera(A);
System.out.println("Il numero di sottostringhe è: " + dei.getABANum());
}
}
1) Il punto evidenziato in grassetto: è possibile farlo come l'ho scritto io? Nel senso, dovrebbe essere sufficiente passargli i due indici in questo modo, invece che sommarli tra loro come avevi scritto tu. Può essere?
2) Può andar bene passargli l'array (nel main) come ho scritto invece che farlo inserire come input dall'utente?
PS: grazie per l'aiuto
AnonimoVeneziano
30-11-2007, 11:56
Ho provato a modificarlo un attimo il tuo codice, ma guisto per fare un prova.
Volevo chiederti un paio di cose, ti evidenzio in grassetto il punto in cui ho un dubbio.
public class DividiEtImpera {
char[] stringa;
public DividiEtImpera(char[] array) {
this.stringa = array;
}
public int getABANum() {
return realCount(0, stringa.length);
}
private int realCount(int left, int right) {
int half = (left + right)/2;
if(left != right)
return realCount(left, half) + realCount(half + 1, right);
else if ( left <= stringa.length - 3 && stringa[left] == 'a'
&& stringa[left+1] == 'b' && stringa[left+2] == 'a')
return 1;
return 0;
}
public static void main(String[] args) throws IOException {
char [] A = {'a', 'c', 'e', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'b', 'a', 'c'};
DivideEtImpera(A);
System.out.println("Il numero di sottostringhe è: " + dei.getABANum());
}
}
1) Il punto evidenziato in grassetto: è possibile farlo come l'ho scritto io? Nel senso, dovrebbe essere sufficiente passargli i due indici in questo modo, invece che sommarli tra loro come avevi scritto tu. Può essere?
Mi sembra corretto e anche più leggibile come l'hai proposto tu. Non l'ho testato, fallo tu come prova del 9 ;)
2) Può andar bene passargli l'array (nel main) come ho scritto invece che farlo inserire come input dall'utente?
PS: grazie per l'aiuto
Certamente, non ha importanza come glielo passi, basta che gliene passi uno
Ciao
Perfetto AnonimoVeneziano, gentilissimo.
L'ho modificato a mano a lavoro ma non ho potuto testarlo.
Proverò Domenica sera appena torno a casa.
Grazie ancora delle dritte!
^TiGeRShArK^
30-11-2007, 13:32
un consiglio veloce veloce per evitarti rotture di balle :D
anzichè scrivere:
char [] A = {'a', 'c', 'e', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'b', 'a', 'c'};
potresti scrivere:
char [] A = "aceabababcbabac".toCharArray();
mi sa che ci metti di meno :p
Ueilà! Bella questa!
Proverò anche questo appena sarò tornato a casa.
Sai cos'è Tiger.. è che non sai mai se convenzioni come questa sono ben accette dai docenti, vuoi perchè non le si sono fatte come argomento a lezione, vuoi perchè al docente non piace, o quant'altro.
Certo che però è comoda ! ;)
è codice Java valido; se i tuoi professori ti hanno insegnato Java (e non un suo sottoinsieme) allora non devono fare storie, altrimenti le loro storie le scrivevano nella traccia dell'esercizio.
concordo, ma più volte mi è capitato di sentirne di tutti i colori a tal proposito, mai personalmente per fortuna
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.