PDA

Visualizza la versione completa : [C] Funzione ricorsiva per l'unione di stringhe


Deidan
27-01-2011, 17:47
Salve a tutti avrei un piccolo problema. In pratica mi è stato chiesto di realizzare una funzione ricorsiva la quale ha in input due stringhe, che rappresentano due insiemi A e B di caratteri, e restituisce in output una terza stringa che contiene l'unione degli insiemi A e B, per esempio se stringa1 = "afr" e stringa2 = “abdr” allora stringa3 = “abdfr” . Non ho molta pratica con la ricorsione e quindi non so bene come implementarla. Ci sarebbe qualcuno che può aiutarmi? Grazie mille in anticipo. :ciauz:

Laikius91
27-01-2011, 17:49
Non ci è permesso aiutarti in toto.. :)

Prova a ragionare su un foglio di carta su come realizzare la funzione:

analizzi la stringa più corta;

1) se è terminata ritorni una stringa risultato non modificata;
2) se non è terminata e il primo carattere è presente nell'altra stringa, copi il carattere nella stringa risultato;
3) se no riduci la ricerca incrementando la stringa che stai analizzando!


;)

Deidan
28-01-2011, 13:20
Io avevo pensato a questa soluzione, solo che non so come implementarla ricorsivamente:

1) Confronto ciascun elemento della stringa più lunga con tutti gli elementi della stringa più corta. Se trovo l'elemento interrompo la ricerca e lo copio nella stringa risultato. Altrimenti continuo la ricerca e se non trovo nessun elemento della stringa corta corrispondente all'elemento della stringa lunga che sto analizzando, allora lo copio nella stringa risultato.

2) Una volta completata la stringa lunga, passo alla stringa corta e confronto ciascun elemento della corta con tutti gli elementi della stringa risultato. Se trovo l'elemento della corta nella stringa risultato allora non copio nulla, altrimenti copio il carattere della stringa corta nella stringa risultato.

Laikius91
28-01-2011, 13:56
Scusami, mi sa che avevo letto troppo in fretta la consegna :zizi:

Il tuo ragionamento è giusto comunque, devi solo capire come renderlo ricorsivo, ricordati che occorre sempre una condizione di terminazione, ossia un caso banale al quale ricondurti con le altre istruzioni ;)

Magari prova a buttare giù qualcosa e posta il risultato! :)

Laikius91
28-01-2011, 16:43
Originariamente inviato da Deidan
Salve a tutti avrei un piccolo problema. In pratica mi è stato chiesto di realizzare una funzione ricorsiva la quale ha in input due stringhe, che rappresentano due insiemi A e B di caratteri, e restituisce in output una terza stringa che contiene l'unione degli insiemi A e B, per esempio se stringa1 = "afr" e stringa2 = “abdr” allora stringa3 = “abdfr” . Non ho molta pratica con la ricorsione e quindi non so bene come implementarla. Ci sarebbe qualcuno che può aiutarmi? Grazie mille in anticipo. :ciauz:



Piccolo chiarimento, le stringhe passate alla funzione sono ordinate? O è una coincidenza che nel tuo esempio sia cosi?

Deidan
28-01-2011, 17:27
No è una coincidenza dell'esempio, non serve che siano ordinate

Laikius91
28-01-2011, 21:49
Ok perfetto... Ma c'è un po' di ambiguità nella richiesta, cioè è un unione particolare... Mi spiego meglio:
dall'esempio sembra che nella stringa risultato debbano esserci i caratteri contenuti nelle due stringhe passate NON ripetuti; se una delle due stringhe al suo interno ha delle ripetizioni queste vanno ignorate?

Ad esempio: se vengono passate le stringhe "aghkja" e "aaabbb", la stringa risultato deve essere "abghkj"?

Deidan
28-01-2011, 23:04
Le stringhe rappresentano degli insiemi di caratteri, quindi si suppone che non ci siano elementi ripetuti.

ramy89
29-01-2011, 02:01
La mia idea è di usare una variabile statica che rappresenta la stringa che alla fine andrà restituita,questa stringa all' inizio sarà vuota,poi man mano che scandisci le stringhe se ne trovi uno nuovo lo allochi,fai il controllo carattere per carattere,alla fine del controllo se la stringa non è finita (guardi se c'è il terminatore) passi alla stessa funzione il carattere successivo.Poi se e solo se entrambe le due stringhe sono finite ritorni l' array di char,statico e che viene allocato di un carattere in più solo se il carattere non è già presente.
Spero che è chiaro,prova a farla semmai se è sbagliata ci diamo un' occhiata.

Laikius91
29-01-2011, 09:23
Originariamente inviato da ramy89
La mia idea è di usare una variabile statica che rappresenta la stringa che alla fine andrà restituita,questa stringa all' inizio sarà vuota,poi man mano che scandisci le stringhe se ne trovi uno nuovo lo allochi,fai il controllo carattere per carattere,alla fine del controllo se la stringa non è finita (guardi se c'è il terminatore) passi alla stessa funzione il carattere successivo.Poi se e solo se entrambe le due stringhe sono finite ritorni l' array di char,statico e che viene allocato di un carattere in più solo se il carattere non è già presente.
Spero che è chiaro,prova a farla semmai se è sbagliata ci diamo un' occhiata.


Interessante sai?
Per comodità, la stringa risultato si potrebbe già allocare della somma delle lunghezze delle altre due (ossia il caso peggiore in cui le due stinghe contegano caratteri tutti diversi)...
Il problema è stabilire i casi banali di terminazione dell'algoritmo... Cioè, se una delle due stringhe termina prima dell'altra come bisogna comportarsi?

Loading