Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Ricerca personalizzata

Quanti alberi binari propri si possono formare con n nodi?

Linguaggi e sistemi

Moderatore: Foto UtentePaolino

0
voti

[1] Quanti alberi binari propri si possono formare con n nodi?

Messaggioda Foto UtentePatras » 8 set 2017, 18:22

Ciao a tutti conoscete per caso qualche formula o forse vi viene in mente qualche idea matematica per trovare il numero di alberi binari propri diversi strutturalmente che si possono costruire con n nodi?
Per albero proprio intendo albero binario i cui nodi hanno due soli figli (a parte le foglie che non ce li hanno).

L'ho messo in informatica perché ho scritto un algoritmo ricorsivo (java) che lo risolve ma non so se è giusto perché ho perso un'ora a farlo facendo varie correzioni con questo magari rendendolo efficiente solo per i primi casi che sono riuscito a verificare a mano sul foglio. (n=3, n=5, n=7, n=9) però per esempio per n=9 non andava e ho dovuto fare una correzione. Per n>9 ormai non ho voglia di verificare a mano.
Se volete verificarlo guardando il codice è dura spiegarvelo ma sicuramente le sue prestazioni temporali fanno pellagra. Si basa sul fatto che togliendo ogni volta 2*k nodi da uno dei sottoalberi rimango con 2*k+1 nodi dall'altro sottoalbero e le combinazioni che si creano a loro volta se moltiplicate e sommate mi danno il risultato totale. Siccome tanti casi i ripetono per simmetria li moltiplico per 2. Quelli invece in cui l'albero (o sottalbero preso) sono "bilanciati" cioè stesso numeri di nodi, mi sono accorto che non conviene moltiplicarli per 2 perché non si ripetono. Insomma se qualcuno riesce a verificarlo per numeri più grandi di 9 o conosce qualche formula mi aiuta molto:

Codice: Seleziona tutto
public static int getQ(int n)
{
   if(n<=3)
      return 1;
   int s=0, r=0;
   for(int i=1; 2*i<=(n+1)/2; i++)
   {
      r = getQ(n-2*i)*getQ(2*i-1);
        if(2*i-1 != n-2*i)
         r *= 2;
         s+=r;
   }
   return s;
}
Avatar utente
Foto UtentePatras
20 4
New entry
New entry
 
Messaggi: 52
Iscritto il: 24 mag 2017, 14:27

0
voti

[2] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtenteIlGuru » 8 set 2017, 18:54

Tiro a indovinare:
floor( ( n - 1 ) / 2 )
\Gamma\nu\tilde{\omega}\theta\i\ \sigma\epsilon\alpha\upsilon\tau\acute{o}\nu
Avatar utente
Foto UtenteIlGuru
2.985 7 12
Master
Master
 
Messaggi: 990
Iscritto il: 31 lug 2015, 22:32

0
voti

[3] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtentePatras » 8 set 2017, 19:10

Non credo proprio. Quello che hai messo mi sembra il numero di foglie.
Forse per chi è bravo con la combinatoria magari dando un'occhiata anche ai miei risultati sperimentali... ma comunque vada mi basta anche una conferma se il codice potrebbe andare... o se mi offriste i vostri risultati per n=11, n=13... magari sapete come metterci di meno...

Miei risultati che verificano anche il programma
n=3 ovviamente 1
n=5 -> 2
n=7 -> 5
n=9 -> 14
Avatar utente
Foto UtentePatras
20 4
New entry
New entry
 
Messaggi: 52
Iscritto il: 24 mag 2017, 14:27

0
voti

[4] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtenteIlGuru » 8 set 2017, 19:12

Allora non ho capito la definizione di albero proprio
\Gamma\nu\tilde{\omega}\theta\i\ \sigma\epsilon\alpha\upsilon\tau\acute{o}\nu
Avatar utente
Foto UtenteIlGuru
2.985 7 12
Master
Master
 
Messaggi: 990
Iscritto il: 31 lug 2015, 22:32

5
voti

[5] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtentePietroBaima » 8 set 2017, 19:40

Se ho fatto i conti giusti per n=11 mi viene 42 e per n=13 mi viene 132.
Ti torna?
Non ho guardato il tuo programma.
Generatore codice per articoli:
nomi
emoticon
citazioni
formule latex
Avatar utente
Foto UtentePietroBaima
65,9k 6 12 13
G.Master EY
G.Master EY
 
Messaggi: 7600
Iscritto il: 12 ago 2012, 0:20
Località: Londra

0
voti

[6] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtentePatras » 8 set 2017, 21:00

PietroBaima ha scritto: n=11 mi viene 42, e per n=13 mi viene 132

WOW! I conti tornano! Grazie mille come hai fatto? moltiplicando i casi più semplici?
Avatar utente
Foto UtentePatras
20 4
New entry
New entry
 
Messaggi: 52
Iscritto il: 24 mag 2017, 14:27

4
voti

[7] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto Utentewruggeri » 8 set 2017, 22:02

Il numero di alberi propri con N nodi (foglie escluse) è il N-esimo numero di Catalan, Foto UtentePatras...

https://it.wikipedia.org/wiki/Numero_di_Catalan
Si, nei limiti delle mie capacità ti rispondo... ma per favore, impara l'italiano!
Se non conosci un argomento, non parlarne.
Gli unici fatti scientifici sono quelli accertati dagli studi. Il resto è opinione.
GATTINI A TORINO
Avatar utente
Foto Utentewruggeri
2.368 1 5 13
Expert EY
Expert EY
 
Messaggi: 447
Iscritto il: 25 nov 2016, 17:46

4
voti

[8] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtentePietroBaima » 8 set 2017, 22:04

perché ho fatto un plot della tua sequenza e l'ho sovrapposta a e^x/x.

Più o meno ci siamo asintoticamente, quindi ho pensato che la tua successione fosse una dismutazione semplice.

Untitled-1.jpg
Untitled-1.jpg (8.18 KiB) Osservato 157 volte


Però non ci siamo localmente, all'inizio, dove la crescita è più lenta.

poiché n! \approx n^n \text{e}^{-n} \sqrt{x} per Stirling il problema è l'n^n.

Devo trovare quindi una successione che stia nel mezzo, tipo un set di Mandelbrot o di Catalan.

Molto subdolamente e trassando alla grande le ho provate entrambe e Catalan verifica la tua sequenza :mrgreen:

C[n]=\frac{(2n)!}{n!(n+1)!}

Codice: Seleziona tutto
f[n_] = (2 n)!/(n! (n + 1)!);
Table[f[n], {n, 1, 6}]

Out[1]= {1, 2, 5, 14, 42, 132}


Così hai anche la formula.

Eh, era bello quando mi potevo occupare di queste cose tranquillamente, senza altri grattacapi per la testa...

EDIT: Foto Utentewruggeri conosce la teoria degli alberi binari meglio! Sorry per la sovrapposizione :oops:
Generatore codice per articoli:
nomi
emoticon
citazioni
formule latex
Avatar utente
Foto UtentePietroBaima
65,9k 6 12 13
G.Master EY
G.Master EY
 
Messaggi: 7600
Iscritto il: 12 ago 2012, 0:20
Località: Londra

1
voti

[9] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto Utentewruggeri » 8 set 2017, 22:12

Conoscere la teoria degli alberi binari meglio di un fisico-matematico-genioassoluto? Ma assolutamente no :mrgreen:
In realtà, c'è il trucco: pochi giorni fa ho finito di leggere questo, dove la correlazione tra numeri di Catalan ed alberi binari propri è citata esplicitamente un bel po' di volte :ok:
Si, nei limiti delle mie capacità ti rispondo... ma per favore, impara l'italiano!
Se non conosci un argomento, non parlarne.
Gli unici fatti scientifici sono quelli accertati dagli studi. Il resto è opinione.
GATTINI A TORINO
Avatar utente
Foto Utentewruggeri
2.368 1 5 13
Expert EY
Expert EY
 
Messaggi: 447
Iscritto il: 25 nov 2016, 17:46

0
voti

[10] Re: Quanti alberi binari propri si possono formare con n nod

Messaggioda Foto UtentePatras » 8 set 2017, 22:20

infatti mi veniva il dubbio di metterla nella sezione di matematica perché mi sembrava più opportuno però d'altra parte avevo scritto il programma :D Sta di fatto che mi sono accorto di aver svolto sempre oggi un altro problema con un algoritmo completamente diverso dietro al quale però c'era questo numero di Catalan (problema delle parentesi)... è questo il bello dell'informatica, a volte puoi saltare la matematica

Comunque volevo ringraziarvi per le risposte :ok:
Avatar utente
Foto UtentePatras
20 4
New entry
New entry
 
Messaggi: 52
Iscritto il: 24 mag 2017, 14:27

Prossimo

Torna a PC e informatica

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti