Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - problema con ricorsione
Forum - C/C++ - problema con ricorsione - Pagina 2

Pagine: [ 1 2 3 ] Precedente | Prossimo
Avatar
AldoBaldo (Member)
Expert


Messaggi: 544
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 0:45
Mercoledì, 08/01/2020
Per trattare i casi nei quali le stringhe non hanno lunghezza pari a una potenza del tre ho fatti ricorso a questo procedimento (i frammenti di codice si possono condividere).

Codice sorgente - presumibilmente C++

  1. int cantor_calcola_lunghezza_settori( int lStr, int l[] ) {
  2.     l[0] = lStr/3;  // la lunghezza del settore di sinistra
  3.     l[1] = l[0];    // la lunghezza del settore centrale
  4.     l[2] = l[0];    // la lunghezza del settore di destra
  5.    
  6.     // inizialmente, i tre settori hanno la stessa lunghezza; la loro somma, per
  7.     // via dei troncamenti determinati dall'uso di valori di tipo intero, puo'
  8.     // essere minore rispetto a quanto indicato dal parametro lStr. Per questo...
  9.  
  10.     if( 0 != l[0] ) { // ... se i settori non hanno lunghezza nulla
  11.         int r;  // r: resto
  12.  
  13.         if( (r=lStr%3) ) { // se sono state "tagliate" delle parti...
  14.             if( 1==r ) {        // se si e' "avanzato" solo un 1,
  15.                 l[1]++;         // lo aggiungiamo alla parte centrale
  16.             }
  17.             else if( 2==r ) {   // se invece l'avanzo e' 2,
  18.                 l[0]++;         // ne aggiungiamo meta' al settore di sinistra
  19.                 l[2]++;         // e meta' al settore di destra
  20.             }
  21.         }
  22.  
  23.         return 1;   // restituiamo 1 per indicare che
  24.                     // i settori hanno lunghezza valida
  25.     }
  26.  
  27.     return 0;       // restituiamo 0 per indicare che
  28.                     // i settori NON hanno lunghezza valida
  29. }



Sicuramente esistono metodi più efficaci/meno banali, però questo funziona e m'è venuto facile metterlo insieme...

Ultima modifica effettuata da AldoBaldo il 08/01/2020 alle 0:51


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
Goblin (Member)
Expert


Messaggi: 375
Iscritto: 02/02/2011

Segnala al moderatore
Postato alle 0:59
Mercoledì, 08/01/2020
però ... visto il crosspost e la risoluzione in un altro forum ...... :rofl::rofl::rofl:

Questa la mia soluzione che estrae risultati uguali a quelli di AldoBaldo, in pascal spero di non aver scritto troppe cavolate.

Codice sorgente - presumibilmente Delphi

  1. Function cantor(var str: String; posizioneInizioStringa, DimStringa: Integer): String;
  2. Var i: Integer;
  3.     nDim: Integer;
  4.     nDummy: Integer;
  5. begin
  6.   // dummy mi serve per prendere più o meno di parte centrale
  7.   // in base al resto della divisione
  8.   // ovviamente a potenza di 3 è nullo e tutto resta normale
  9.   nDummy := 0;
  10.   if (DimStringa mod 3) < 0 then  // meno di 3
  11.     nDim := 0
  12.   else if (DimStringa mod 3) = 1 then  // resto 1
  13.   begin
  14.     nDim := DimStringa DIV 3;
  15.     nDummy := 1;
  16.   end
  17.   else if (DimStringa mod 3) = 2 then  // resto 2
  18.   begin
  19.     nDim := round(DimStringa / 3);
  20.     nDummy := -1;
  21.   end
  22.   else
  23.     nDim := DimStringa DIV 3;  // divisione secca
  24.  
  25.   if nDim = 0 then
  26.     Result := str
  27.   else
  28.   begin
  29.     // prima parte
  30.     Cantor(str, posizioneInizioStringa, nDim);
  31.     // scrivo parte centrale nulla
  32.     For i := posizioneInizioStringa + nDim To posizioneInizioStringa + (nDim * 2) - 1 + nDummy do
  33.       str[i] := '.';
  34.     // terza parte
  35.     Cantor(str, posizioneInizioStringa + (nDim * 2) + nDummy, nDim);
  36.     Result := str;
  37.   end;
  38. end;
  39.  
  40. procedure TForm23.Button1Click(Sender: TObject);
  41. Var ss: String;
  42.   I: Integer;  // stringhe di test
  43.   x: Integer; // dummy per inizializzare la stringa ...
  44.   s: String;   // stringa di supporto per '0' formattazione output
  45. begin
  46.   memo1.Lines.Clear;
  47.   for I := 1 to 300 do
  48.   begin
  49. // doppio begin per inserire solo potenze di 3
  50.     begin
  51.       SetLength(ss, I);
  52.       s := '0';
  53.       for x := 1 to I do
  54.         ss[x] := '#';  // inizializzo tutto pieno ... potrei fare un fillChar ... ma ... lascio ai posteri il lavoro
  55.       // non mi ricordo più il PADL .... scusatemi faccio casareccio
  56.       if i>=10 then
  57.         s := '';
  58.       memo1.Lines.Add(s + I.ToString + ' char: ' + Cantor(ss, 1, I))
  59.     end;
  60.   end;
  61. end;


il codice è Delphi Pascal, il click del bottone aggiunge i risultati in un memo, è molto spartano e buttato giù in qualche minuto .. scusate eventuali errori
G.


Ibis redibis non morieris in bello
PM Quote
Avatar
AldoBaldo (Member)
Expert


Messaggi: 544
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 18:28
Mercoledì, 08/01/2020
A mala pena leggiucchio il pascal un po' alla mia maniera, però da quel che intuisco hai usato un sistema diverso da quello che ho usato io. Mi vien voglia di tentare una "traduzione" letterale in C. Anzi, lo faccio (e mi ci divertirò pure)!


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
AldoBaldo (Member)
Expert


Messaggi: 544
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 20:59
Mercoledì, 08/01/2020
La "traduzione" l'ho fatta, ma mi dà risultati diversi da quelli che mi sarei aspettato, con raggruppamenti di '#' e '.' diversi da quelli della mia soluzione.

Ho visto che tu hai inizializzato la stringa con tutti '#', per poi andare a modificare gli '#' con '.' dove hai ritenuto necessario. Io ho preferito una strada diversa: non ho inizializzato per niente la stringa iniziale, e poi ho usato una funzione con questo prototipo:

int cantor( char str[], int lStr, char chrEst, char chrInt );

Ho passato cioè negli ultimi due parametri il carattere "esterno" (che nel nostro caso è '#') e il carattere "interno" (che nel nostro caso è '.'). E' poi cantor() a decidere quale dei due usare in ogni parte della stringa della quale vengono passati l'indirizzo e la lunghezza. Ad ogni chiamata ricorsiva, ovviamente, vengono passati indirizzi e lunghezze diverse, corrispondenti alle varie "porzioni" della stringa da trattare. La funzione che ho ideato non è interessata a sapere a che livello di "profondità" si trova, semplicemente tratta la "sua" stringa come se fosse l'unica, continuando a chiamare nuovi cantor() fino a che la lunghezza della stringa da trattare è 0 (a quel punto ritorna, chiudendo il ciclo delle ricorsioni).


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
Goblin (Member)
Expert


Messaggi: 375
Iscritto: 02/02/2011

Segnala al moderatore
Postato alle 21:59
Mercoledì, 08/01/2020
Facciamo il giochino inverso, credo di masticare il "C" al tuo livello di pascal ... dunque metti la tua soluzione e io la converto in pascal ... vediamo quello che esce :)
Nell'immagine a sx il mio a dx il tuo.

EDIT: come ho scritto, ho buttato giù il codice in 5/10 minuti, forse non è molto ottimizzato e molto basilare, ma al momento funzionava, e non sono stato tanto x il sottile, ma sono veramente curioso di vedere la tua versione


Goblin ha allegato un file: Schermata 2020-01-08 alle 21.58.53.png (82656 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Goblin il 08/01/2020 alle 22:10


Ibis redibis non morieris in bello
PM Quote
Avatar
AldoBaldo (Member)
Expert


Messaggi: 544
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 22:09
Mercoledì, 08/01/2020
Ah! Guardando l'immagine mi risulta OVVIO che ho "cannato" la traduzione... e di brutto! :)

Comunque sia, sperando di non far inquietare i moderatori, vediamo cosa succede quando la traduzione la tenti TU! :heehee:

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int cantor_calcola_lunghezza_settori( int lStr, int l[] ) {
  5.     l[0] = lStr/3;
  6.     l[1] = l[0];
  7.     l[2] = l[0];
  8.  
  9.     if( 0 != l[0] ) {
  10.         int r;
  11.  
  12.         if( (r=lStr%3) ) {
  13.             if( 1==r ) {
  14.                 l[1]++;
  15.             }
  16.             else if( 2==r ) {
  17.                 l[0]++;
  18.                 l[2]++;
  19.             }
  20.         }
  21.  
  22.         return 1;
  23.     }
  24.  
  25.     return 0;
  26. }
  27.  
  28. int cantor( char str[], int lStr, char chrEst, char chrInt ) {
  29.     int i, l[3];
  30.  
  31.     if( cantor_calcola_lunghezza_settori(lStr,l) ) {
  32.         int e = cantor( str, l[0], chrEst, chrInt );
  33.         for( i=0; i<l[1]; ++i ) (str+l[0])[i] = chrInt;
  34.         e += cantor( str+l[0]+l[1], l[2], chrEst, chrInt );
  35.         return 2 == e;
  36.     }
  37.     else {
  38.         for( i=0; i<lStr; ++i )
  39.             str[i] = chrEst;
  40.         return 0;
  41.     }
  42. }
  43.  
  44. int main() {
  45.     char *s = NULL;
  46.     unsigned int l;
  47.  
  48.     do {
  49.         printf( "Quanti caratteri deve avere la tua stringa? " );
  50.         scanf( "%u", &l );
  51.         while( '\n' != getchar() );
  52.  
  53.         if( (s=calloc(l+1,sizeof(*s))) ) {
  54.             cantor( s, l, '#', '.' );
  55.             printf( "\n%s\n\n", s );
  56.             free( s ); s = NULL;
  57.         } else puts( "\nErrore: memoria non allocata.\n" );
  58.     } while( 0 != l );
  59.  
  60.     return 0;
  61. }



ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
Goblin (Member)
Expert


Messaggi: 375
Iscritto: 02/02/2011

Segnala al moderatore
Postato alle 22:17
Mercoledì, 08/01/2020
Testo quotato

Postato originariamente da AldoBaldo:

Ah! Guardando l'immagine mi risulta OVVIO che ho "cannato" la traduzione... e di brutto! :)

Comunque sia, sperando di non far inquietare i moderatori, vediamo cosa succede quando la traduzione la tenti TU! :heehee:




Credo che ormai sia diventato un giochino tra di noi, ho visto la soluzione che hanno dato nell'altro forum
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #define N 27
  3.  
  4. void cantor(char[], int, int);
  5.  
  6. int main() {
  7.     char v[N+1];
  8.     int i;
  9.     for(i = 0; i<N; i++){
  10.         v[i] = 'a';
  11.     }
  12.     v[i] = '\0';
  13.     cantor(v, 0, N-1);
  14.     printf("%s\n", v);
  15.    
  16.     return 0;
  17. }
  18.  
  19. void cantor(char str[], int posInStr, int posFinStr){
  20.     int a = (posFinStr+1-posInStr)/3;
  21.     int i;
  22.     if((posFinStr - posInStr) >= 2){
  23.         for(i=posInStr; i < posInStr + a; i++){
  24.             str[i] = '#';
  25.         }
  26.         for(i = posInStr + a; i < posInStr + 2*a; i++){
  27.             str[i] = '.';
  28.         }
  29.         for(i = posInStr + 2*a; i < posFinStr+1; i++){
  30.             str[i] = '#';
  31.         }
  32.         cantor(str, posInStr, posInStr+a-1);
  33.         cantor(str, posInStr+2*a, posFinStr);
  34.     }
  35. }



e.....
EDIT: :rofl::rofl::rofl::rofl:  meno male che non hai postato prima la tua soluzione.... credo che se come soluzione avesse portato la tua nemmeno il prof l'avrebbe capita, hai usato una tecnica veramente avanzata, e peccato che non ci lavori con il codice .... il mondo software sarebbe migliore, i miei complimenti ... spero di essere all'altezza della traduzione pascal

Ultima modifica effettuata da Goblin il 08/01/2020 alle 22:31


Ibis redibis non morieris in bello
PM Quote
Avatar
AldoBaldo (Member)
Expert


Messaggi: 544
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 22:44
Mercoledì, 08/01/2020
Non ti seguo, scusa. Quella che hai inviato per ultima è la versione in C del tuo programma in Pascal? Perché se è così la mia "traduzione" non era sbagliata di brutto, era UNA TRAGEDIA! :)
E' proprio vero che in queste cose l'intuito è meglio dimenticarselo...


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Pagine: [ 1 2 3 ] Precedente | Prossimo