Funzinale IMO

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Dopo un po\' di tempo sono tornato (stremato da un anno di uni...), della serie anche gli idioti ogni tanto sono in ferie...
 
 Allora, una funzionale dalle IMO
 
 F: NxN --> N
 
 F(0, a) = a+1 per ogni a in N
 F(a+1, 0) = F(a, 1) per ogni a in N
 F(a+1, b+1) = F(a, F(a+1, b)) per ogni a, b in N
 
 calcolare F(4, 1981)
 
 L\'ho risolta, ma volevo vedere se la risolve in maniera più elegante...
 (P.S. a me ricorda tanto la funzione di Ackermann... - complessità computazionale alle stelle).

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

F(4,n)=2^(2^(...(2^16)...)) -3 dove i 2 nella \" exponential tower\" sono n (compresa la base, e escluso il 16 finale) va bene come risposta??
 
 <IMG SRC="images/forum/icons/icon_eek.gif">

JackSparrow · Messaggio da **JackSparrow** » 01 gen 1970, 01:33

Anche a me esce lo stesso risultato, applicando successivamente le uguaglianze a partire da F(1, k). Risulta infatti F(1, k) = k + 2, F(2, k) = 2k + 3, F(3, k) = 2^(k + 3) - 3 e F(4, k) quello che ha scritto talpuz.
 
 Ciao. [ Questo Messaggio è stato Modificato da: JackSparrow il 06-08-2004 20:35 ]

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

L\'avete risolto come l\'ho risolto io, con formule di ricorrenza tenedo fissa la prima variabile...
 ...non è un po\' deludente come risultato per un esercizio di una gara IMO (quella del 1981..penso...)?

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-08-07 09:14, Catraga wrote:
 L\'avete risolto come l\'ho risolto io, con formule di ricorrenza tenedo fissa la prima variabile...
 ...non è un po\' deludente come risultato per un esercizio di una gara IMO (quella del 1981..penso...)?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 E\' un po\' deludente se consideri che era il problema 6. Ma conta che negli anni \'80 i problemi erano ancora mooolto facili, se paragonati a quelli attuali. In ogni caso, non penso che nel 1981 qualche studente del liceo conoscesse la funzione di Ackermann.

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-08-07 09:14, Catraga wrote:
 L\'avete risolto come l\'ho risolto io, con formule di ricorrenza tenedo fissa la prima variabile...
 ...non è un po\' deludente come risultato per un esercizio di una gara IMO (quella del 1981..penso...)?
 
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 già...
 
 cmq la vedo difficile risolverla in modo diverso, visto il numerazzo che viene fuori <IMG SRC="images/forum/icons/icon_eek.gif">