[aide][Java] Fermé

Question

Bonjour
j'ai un exercise a faire et vraiment je l'ai trouve tres difficile si vous pouvez m'aider ça serait un tres grand plaisir de votre part..
c'est sur le langage java.
le probleme est le suivant:
1.la fonction de Ackrmann est définie par:
A(0,n)=n+1
A(m+1,0)=A(m,1)
A(m+1,n+1)=A(m,A(m+1,n))
a) qu'est ce que cette fonction calcul ?
b) simuler quelque valeur a la main
c) implémenter la fonction. calculer quelque valeur.
2. Ecrivez une fonction récursive pour inverser une chaine de caractere : "hello" -> "olleh"

merci bien de me repondre le plus proche possible.

franky* · Answer

Salut,
Les forums de CCM n'ont pas pour vocation de faire les exercices des autres... Donc tu n'auras pas de vraie réponse ici : si tu dois faire cet exercice, c'est que ça te sera utile, ne serait-ce que pour avoir un bon entraînement.

Mais bon, vu le problème, on peut bien faire un petit effort ;-)

Pour Ackerman, si tu n'as pas trouvé à quoi elle sert, c'est que tu n'as pas cherché... sur internet ! C'est tout à fait trouvable ! (c'est un histoire de puissance, mais je ne t'en dis pas plus. Tu peux ajouter le mot clé "complexité", ça t'aidera)
b) Tu peux facilement calculer les 2 premières valeurs, mais ne vas pas plus loin : c'est inutile !
c) Si tu n'arrive pas à implémenter la fonction, dis-nous où tu coince. Sinon, n'essaie surtout pas de dépasser A(4) ! C'est pas faisable avec un ordinateur personnel ! Simplement parce que c'est une fonction extrêmement complexe...

A+

mouna · Answer

merci bien de m'avoir repondre
tu as raison j'ai pas bcp cherche... le probleme c'est que mon bagage en java est insuffisant pour resoudre l'exercice.et le prof nous a donne de faire cette exercice et il est note..
si vous pouvez m'envoyer l'exercice complet ca serait vraiment un trs grand plaisir...stp

franky* · Answer

Salut,
Pour être tout à fait franc, je ne suis pas du tout programmeur (même si je bosse dans l'informatique), donc je ne risque pas de répondre mieux que toi à la partie programmation !

Par contre, pour les questions a et b, il n'y a pas besoin de programmer !!! Et pour la question c, l'algorithme est donné en entier par la définition de la fonction.

Pour ce qui est de la question 2, l'algo est très simple :
fonction inverser :
lire chaine
si chaine = "" alors retourner chaine
sinon (chaine = tête + queue
retourner (inverser(queue) + lettre) )
fin

Tu devrais quand même réussir à coder ça !

Sinon, je viens de jeter un coup d'oeil sur internet, et c'est effectivement pas aussi facile à trouver que ça, Ackermann, quand on ne sait pas exactement ce qu'on cherche... Donc je te l'explique en gros.
Si tu définis une suite d'opérateurs binaires récursivement de la façon suivante :
( s(a) est le successeur de a, donc a + 1)

addition
a + 0 = a
a + s(b) = s(a + b)

multiplication
a * 0 = 0
a * s(b) = a + (a * b) addition définie avant

puissance
a^0 = 1
a^s(b) = a * a^b multiplication définie avant

puissance degré 2
a^^0 = 1
a^^s(b) = a ^ (a^^b) puissance définie avant

etc.

Tu tends vers une fonction très compliquée (puisque les fonctions sont de plus en plus compliquées à chaque étape) à l'infini, et cette fonction peut être exprimée par la fonction d'Ackermann : si on appelle c le degré de la fonction (1 pour l'addition, 3 pour la puissance), on peut se passer de la variable a, et ne conserver que les variables b et c, qui sont les seules à intervenir dans la complexité. On exprimera ça A(b,c) ou A (c,b), je ne sais plus. On se rend bien compte que la fonction d'Ackermann croît TRES vite !

Tu peux calculer :
A(0,0)=1
A(0,1)=2
A(0,2)=3
...
A(1,0)=A(0,1)=2
A(1,1)=A(0,A(1,0))=A(0,2)=3
A(2,2)=A(1,A(1,A(2,0)))=A(1,A(1,A(1,1)))
=A(1,A(0,A(0,A(1,1))))=A(1,5)=A(0,A(1,4))=... et c'est pas fini !!!

Avec ça, t'as tout pour finir...

mnr · Answer

bonjour... j'espère pouvoir vous aider...

1. cette fonction calcule, pour deux indices i et j, la valeur (i+j+1) c'est-à-dire la somme incrémentée de 1.

2. vous pouvez simuler tout seul...

3. une implémentation, bon on est juste amateur...

import java.io.*;
import java.lang.*;

public class a{

public static void main(String s[]){

int i, j;

for(i=0; i<10; i++)
for(j=0; j<10; j++)
System.out.println("a( "+i+", "+ j+")="+v(i, j));
}

public int v(int i, int j){

if(i == 0) return j+1;

if (j == 0) return v(i-1, 1);

return v(i-1, v(i, j-1));
}

}

c'est ce que je propose, bon courage...

4. l'inverse d'une chaîne str de type String est la l'ajout (+) du dernier caractère de cette chaîne à l'inverse du reste de la chaîne. Ce caractère doit se mettre en premier...

inverse("") = "";
inverse(s) = s.last()+inverse(s.subString(s.size()-2));

vous devez trouver des méthodes dans ce sens dans la classe String, elles retournent des String...

Voilà... c'est ce que je peux, j'espère que ça ira... bon courage, à plus...

franky* · Answer

Salut mnr,

c'est sympa d'aider, mais tu aurais du lire ce que j'avais écrit : je t'assure que la fonction ne calcule pas la somme incrémentée de 1, mais une fonction bien plus complexe que ça !

Résultat, le code que tu as donné est surement juste, sauf qu'aucune machine n'est capable de le calculer !!!
Tout simplement parce que les meilleurs calculateurs sont limités, je crois, à Ack(6,6)...

A+

franky* · Answer

Re, mnr,

En fait, cette fonction est vraiment vicieuse :
Tu as l'impression d'avoir des relations entres les valeurs, mais on peut démontrer (je te passe la théorie, j'ai bossé là-dessus cette année, c'est horrible !) qu'il est IMPOSSIBLE de calculer une valeur de la fonction plus rapidement qu'en suivant tous les calculs de la définition. Autrement dit, si on te donne les n premières valeurs, il n'existe qu'une seule façon de calculer la suivante !

Si ça t'amuse, je peux te donner des auteurs qui traitent de ça, mais il faut avoir un bon bagage scientifique avant (c'était l'un des cours les plus durs de mon DEA en intelligence artificielle !).

A+ sur les forums,
François

[aide][Java]

6 réponses

Discussions similaires