Bienvenue sur  ! | Les sites de JeuxOnLine... |
Bienvenue sur ! | Les sites de JeuxOnLine... |
Archives des forums MMO/MMORPG > Forums divers > La Taverne > PB :C++ Algorithme Recurrence terminale 2eme ordre
PB :C++ Algorithme Recurrence terminale 2eme ordre
Par Shury le 24/11/2002 à 22:42:58 (#2635624)
Bon, déja, je sais pas trop si c le bon forum pour, mais, sait on jamais, voila :
J'ai un probleme, je cherche a faire la fonction qui permet de calculer
U(n)=2*U(n-1)+U(n-2)-n avec U(0)=1 et U(1)=1
D'apres la prof, l'algorithme serait int U(int n,int v,int w){ // La fonction U
if(n==0){return w;} // En cas n =0
else { if(n==1){return v;} // En cas n = 1
else {return U(n-1,2*v+w-n,v);} // Sinon, on refait un tour
}
}
int main(){
int n;
cout<>n;
cout<<"Le résultat est "<<U(n,1,1)<<" "; // Affiche le résultat
system("pause");
}
Le probleme, c'est que je trouve pas le meme resultat, avec le calcul a la main :
Je trouve a la main U(2)=1 U(3)=0 et U(4)=-3 ainsi que U(5)=-11
Alors que d'apres l'ordi U(2)=1 U(3)=-1 U(4)=-11 et U(5)=-47
Donc, je crois que j'ai un probleme niveau algorithme, c'est surment le U(n-1,2*v+w-n,v) , je me demande où est l'erreur
Donc, si quelqu'un peut m'aider, ca serait gentil :)
Par Blasteguaine le 24/11/2002 à 22:47:06 (#2635659)
* trop fatigué pour le faire, peut être demain mais quelqu'un aura sûrement répondu avant *
Par Shury le 24/11/2002 à 22:50:09 (#2635689)
Et oui, tu as la boucle , la récurence non terminale, et la récurence terminale :)
Quand à demain, j'ai un partiel de programmation, comment ca je m'y prend trop tard? :)
Par Blasteguaine le 24/11/2002 à 22:54:00 (#2635724)
Amuse toi bien demain :monstre:
Par Kathandro le 24/11/2002 à 22:55:16 (#2635737)
Et la boucle c'est : else {return U(n-1,2*v+w-n,v);}
(pour le principe, bah euh, c'est simple, mais là, je vais pas être clair si j'explique)
Euh question bête: il te sert à quoi ton dernier else?? Parce que si n=o, il return le premier résultat, et il continue pas, si n=1, il return le second résultat et il s'arrête donc, ton dernier else, c'est pas optionnel??
Par Guillaume le 24/11/2002 à 23:03:03 (#2635802)
Par Shury le 24/11/2002 à 23:05:45 (#2635828)
Fib(i)=fib(i-1)+fib(i-2)
en récursif non terminal, il met :
int fib(int n){
if (n==0) return 1;
else {if (n==1) return 1;
else return (fib(n-1) + fib(n-2));
}
mais bon, je cherche a le faire en récursif terminal :rolleyes:
Par Shury le 24/11/2002 à 23:09:19 (#2635855)
le dernier else, calcul si n est != a 0 ou a 1
Guil :
Merci pour m'avoir jeté un vent :)
Ps : Nan, désolé si je flood :(
Par Kathandro le 24/11/2002 à 23:13:21 (#2635884)
Provient du message de Shury
Kat :
le dernier else, calcul si n est != a 0 ou a 1
Ce que je veux dire, ce que t'es pas obligé de marqué else, ça alourdi l'algo... :)
if(n==0)
return w; // En cas n =0
else {
if(n==1)
return v;} // En cas n = 1
return U(n-1,2*v+w-n,v);}
Ca fonctionne aussi bien ;)
Par contre, la fonction de Fibo, connait pas, désolé...
[edit pour monsieur du dessous: c'est vrai, t'as pas tort :)]
Par Anduric le 24/11/2002 à 23:20:05 (#2635926)
Provient du message de Kathandro
Ce que je veux dire, ce que t'es pas obligé de marqué else, ça alourdi l'algo... :)
if(n==0)
return w; // En cas n =0
else {
if(n==1)
return v;} // En cas n = 1
return U(n-1,2*v+w-n,v);}
Ca fonctionne aussi bien ;)
Par contre, la fonction de Fibo, connait pas, désolé...
Autant prolonger le raisonnement en terminant de virer les else :
if (n==0) return w;
if (n==1) return v;
return U(n-1,2*v+w-n,v);
Par Masklinn le 24/11/2002 à 23:27:43 (#2635975)
le plus simple est de mettre "return (2*u(n-1,1,1)+u(n-2,1,1)-n);" mais je suis pas sur que ce soit le genre d'algos que tu es cense utiliser
avec ca en tout cas les resultats sont corrects
Par Shury le 24/11/2002 à 23:34:19 (#2636012)
par contre, si j'ai bien compris avec U(n-1,2*v+w-n,v)
la valeur v prend u(n-1) et la valeur w prend la valeur de v d'auparavant ( pas celui qui est modifié )
Par Anduric le 24/11/2002 à 23:34:30 (#2636016)
Provient du message de Masklinn
le plus simple est de mettre "return (2*u(n-1,1,1)+u(n-2,1,1)-n);" mais je suis pas sur que ce soit le genre d'algos que tu es cense utiliser
avec ca les résultats sont corrects
C'est une récursivité non terminale. Les résultats sont correctes, mais en O(n²). Avec la récursivité terminale, les résultats sont en O(n).
Le principe théorique de la récursivité terminale est d'arriver à la chaîne d'appel suivante
f(n, u_1, u_0) appelle f(n-1, u_2, u_1) qui appelle f(n-2, u_3, u_2) etc ... qui appelle f(1, u_n, u_n-1), et quand on est là, il suffit de renvoyer u_n, qui est le résultat qu'on cherche.
Bon, le truc c'est que ça rend la programmation un peu plus délicate au niveau algorithmique.
Et ce soir je dois être un peu éteint, car je vois pas où est la faute dans le prog.
Par Shury le 24/11/2002 à 23:39:19 (#2636047)
if (n==0) n'a jamais lieu, car quand n==1, ca s'arrete imédiatement, ca calcul donc un petit bout...
Par Anduric le 24/11/2002 à 23:43:08 (#2636066)
Provient du message de Shury
je crois avoir compris l'erreur
if (n==0) n'a jamais lieu, car quand n==1, ca s'arrete imédiatement, ca calcul donc un petit bout...
Je doute que ça change grand chose... le test ==0 sert uniquement à éviter de planter ton algo quand on lui fournit U(0, 1, 1)
Par Anduric le 24/11/2002 à 23:51:19 (#2636137)
Tu as U(k, 1, 1) [= U(k, u_1, u_0)], mais quand tu itères, tu devrais avoir U(k-1, u_2, u_1), et ça n'est pas le cas.
A ce moment là de ton calcul, la valeur que tu calcule n'est pas u_2, mais la valeur qu'aurais u_k si u_k-1 et u_k-2 valait u_2 et u_1.
Il faut donc que tu ajoutes un quatrième paramètre à ton algorithme, mettons k, et que tu fasse l'appel suivant :
return U(n-1, 2*v + w - (k- n +2), v, k)
Voilà voilà.
Par Sans Coeur le 24/11/2002 à 23:53:35 (#2636152)
parlez moi pas de maths :(
ljd, pas matheux du tout.
Par Shury le 25/11/2002 à 0:01:09 (#2636213)
Par Shury le 25/11/2002 à 0:04:18 (#2636233)
bon bon, merci pour votre aide, j'ai appris plein de truc :)
Par Anduric le 25/11/2002 à 0:09:35 (#2636257)
U(10, u_1, u_0) = U(9, 2u_1 + u_0 - 10, u_1)
Dans la récursivité dans le calcul de u_n, tu es censé avoir en permanence l'appel U(k, u_n-k+1, u_n-k), avec k<=n. C'est l'invariant qui te permet de conclure que quand k=1, alors le second paramètre de l'appel est bien u_k.
Et tu vois que le second argument dans ta formule n'utilise pas la bonne valeur de n (ce problème vient du fait que le premier argument va de n à 1 au lieu d'aller de 1 à n, ce que corrige mon 4eme paramètre)
Re: PB :C++ Algorithme Recurrence terminale 2eme ordre
Par LoneCat le 25/11/2002 à 14:49:24 (#2639707)
Provient du message de Shury
Bonsoir
Bon, déja, je sais pas trop si c le bon forum pour, mais, sait on jamais, voila :
J'ai un probleme, je cherche a faire la fonction qui permet de calculer
U(n)=2*U(n-1)+U(n-2)-n avec U(0)=1 et U(1)=1
D'apres la prof, l'algorithme serait int U(int n,int v,int w){ // La fonction U
if(n==0){return w;} // En cas n =0
else { if(n==1){return v;} // En cas n = 1
else {return U(n-1,2*v+w-n,v);} // Sinon, on refait un tour
}
}
int main(){
int n;
cout<>n;
cout<<"Le résultat est "<<U(n,1,1)<<" "; // Affiche le résultat
system("pause");
}
Le probleme, c'est que je trouve pas le meme resultat, avec le calcul a la main :
Je trouve a la main U(2)=1 U(3)=0 et U(4)=-3 ainsi que U(5)=-11
Alors que d'apres l'ordi U(2)=1 U(3)=-1 U(4)=-11 et U(5)=-47
Donc, je crois que j'ai un probleme niveau algorithme, c'est surment le U(n-1,2*v+w-n,v) , je me demande où est l'erreur
Donc, si quelqu'un peut m'aider, ca serait gentil :)
C'est sympa ton truc, Anduric a trouvé le bug.
Me demande bêtement si tu ne peux pas faire ça (je ne connais pas assez le C++ pour savoir si ça passerait):int U(int n){ // La fonction U
if(n==0){return 1;} // En cas n =0
if(n==1){return 1;} // En cas n = 1
return (2*U(n-1)+U(n-2)-n); // Sinon, on refait un tour
}
int main(){
int n;
cout<>n;
cout<<"Le résultat est "<<U(n)<<" "; // Affiche le résultat
system("pause");
}
Ca me semblerait quand même beaucoup plus simple (enfin, si le C++ supporte autant de récursivité).
Ciao,
LoneCat
Par Shury le 25/11/2002 à 14:58:07 (#2639765)
j'explique la différence :
avec une récurence terminale on a :
return U(x,y,z)
avec une récurence nont terminale , on a :
return 2+x+U(x,y,z) par exemple
La différence? C'est que dans le premier, on fait pas d'opération de return, dans le second si...
Sinon, pour ceux que ca interesse, j'en ai pas eu du tout besoin lors du partiel, et de plus, je l'ai un peu foiré ( d'ailleur, 80% l'ont surment foiré ), j'aurai surment 5% de réussite ...
Par LoneCat le 25/11/2002 à 15:09:32 (#2639832)
Provient du message de Shury
Lonecat, ce que tu as écrit , c la récurence non terminale
j'explique la différence :
avec une récurence terminale on a :
return U(x,y,z)
avec une récurence nont terminale , on a :
return 2+x+U(x,y,z) par exemple
La différence? C'est que dans le premier, on fait pas d'opération de return, dans le second si...
Sinon, pour ceux que ca interesse, j'en ai pas eu du tout besoin lors du partiel, et de plus, je l'ai un peu foiré ( d'ailleur, 80% l'ont surment foiré ), j'aurai surment 5% de réussite ...
J'ai pas complètement compris, mais je vais chercher pour voir si ce que j'ai plus ou moins compris est exact :)
J'ai trouvé une définition très claire ICI. J'ajoute que je serais assez curieux de voir à quoi ressemblait ton partiel :)
Ciao,
LoneCat
Par Felomes le 25/11/2002 à 15:49:50 (#2640133)
--
Canivo, chieur.
Par Shury le 25/11/2002 à 16:30:27 (#2640445)
en gros, dans le 1er exo, il fallait inverser les elements d'un tableau ( c'est a dire, le 1er terme, se positionne au dernier terme, et vice verca ect ect ), bien sur, il faut le faire en récursive
--> c une fonction a faire ( 2 points )
dans le 2eme, tu a un tableau rempli d'entier, on te donne 2 bornes ( a et b ), et de T[a] a T[b} , il doit retourner la valeur minimun, on te demande comment faire pour qu'il retourne l'indice auquel T soit le min entre T[a] et T, tout ca en récursif
--> c une autre fonction a faire ( 4 points )
dans le 3eme, il fallait trier un tableau , du plus petit au plus grand , en suposant que la fonction de l'exo 2 fonctionne... Bien sur, ici, pas de boucle, juste la récurence... ( 4 points )
Dans l'exo 4, tu as U(n)=3*U(n-1)+2*n avec U(0)=0; il faut faire la fonction en récursive non terminale ( fastoche ), terminale ( là, j'ai merdé ), et itérative ( qui doit reprendre la terminale , mais of course j'ai merdé, sorry ):rolleyes:
-> 2 points
Dans l'exo 5, il fallait faire une fonctionne pour vérifier si 2 chaines étaient des anagrammes ou non....
-> 6 points
dans l'exo 6.... Tu as un tableau, rempli de positif, négatif, et de 0, il faut que dans les premieres termes de tableau ( de 0 a n ) on a que des positifs, de n à x que des nuls et de x à fin du tableau, que des négatifs...
-> 6 points
Le tout est noté 24 points, mais avec tout ca, je pense meme pas que j'ai eu 5 points :rolleyes:
Ca m'apprendra a avoir trop eu confiance en moi !
Ah oui, sinon, on a eu droit qu'a 2 heures...
Par Lwevin Myan le 25/11/2002 à 21:04:15 (#2642932)
Provient du message de Shury
Lonecat, ce que tu as écrit , c la récurence non terminale
j'explique la différence :
avec une récurence terminale on a :
return U(x,y,z)
avec une récurence nont terminale , on a :
return 2+x+U(x,y,z) par exemple
La différence? C'est que dans le premier, on fait pas d'opération de return, dans le second si...
Sinon, pour ceux que ca interesse, j'en ai pas eu du tout besoin lors du partiel, et de plus, je l'ai un peu foiré ( d'ailleur, 80% l'ont surment foiré ), j'aurai surment 5% de réussite ...
La vraie différence ne réside pas là.
Dans le cas d'une récursivité non terminale, on fait plusieurs fois le même calcul.
Un exemple sera sûrement plus parlant (j'ai pris Fibonacci qui est plus simple, et plus court à écrire, mais ça se retrouve dans toute suite, évidemment).
Soit la version récursive non terminale :
int fibn( int n )
{
if( 0 == n )
return 1;
if( 1 == n )
return 1;
return ( fibn( n - 1 ) + fibn( n - 2 ) );
}
fibn( 4 ) = fibn( 3 ) + fibn( 2 )
fibn( 4 ) = fibn( 2 ) + fibn( 1 ) + fibn( 1 ) + fibn( 0 )
fibn( 4 ) = fibn( 1 ) + fibn( 0 ) + 1 + 1 + 1
fibn( 4 ) = 1 + 1 + 1 + 1 +1
fibn( 4 ) = 5
Soit 8 appels à fibn (complexité polynomiale).
Version récursive terminale :
int fibr( int n, int u, int v )
{
if( 0 == n )
return u + v;
return fibr( n - 1, u + v, u );
}
(Avec l'équivalent fibn( i ) = fibr( i, 1, 1 )
fibr( 4, 1, 1 ) = fibr( 3, 2, 1 )
fibr( 4, 1, 1 ) = fibr( 2, 3, 2 )
fibr( 4, 1, 1 ) = fibr( 1, 5, 3 )
fibr( 4, 1, 1 ) = 8
Soit 3 appels (complexité linéaire).
Quelques remarques, au passage :
- Nommage correct des variables, ça aide ;)
- Pas besoin de c++ pour ça... Le C génère du code aussi rapide (pour cet algo), tout en prenant 10 fois moins d'espace disque.
- Le mieux pour apprendre la récursivité est de faire un peu de lisp (l'idéal) ou ses dérivés (Caml, Scheme, etc.)
- Les if imbriqués sont à proscrire : Complexité McCabe accrue, et en plus, tu vas t'amuser quand ton if{} / else{} fera un ou deux écrans, et en plus, c'est illisible. Ca sert à rien de faire des tests si la fonction a de toute façon fini son travail.
A vue de nez, je dirais aussi qu'une variable statique est préférable à passer un 4e paramètre qui alourdit la pile inutilement.
*va regarder le partiel d'algo*
Par Kathandro le 25/11/2002 à 21:53:50 (#2643316)
Provient du message de Lwevin Myan
A vue de nez, je dirais aussi qu'une variable statique est préférable à passer un 4e paramètre qui alourdit la pile inutilement.
*va regarder le partiel d'algo*
Sinon tu passes les variables par référence (particularité bien pratique du C++)... Pour les algos, le c++ c'est moyen quand même malgré tout...
Et puis le int main qui renvoie rien à la fin, normalement, ça plante :p... (façon simple de finir le main: return (0); )
Par Lwevin Myan le 25/11/2002 à 22:46:12 (#2643648)
S'il y en a que ça intéresse, je posterais mes réponses demain, histoire de laisser réfléchir.
D'ailleurs, j'aimerais bien voir les possibilités pour la réponse 5, on va dire que je n'ai pas utilisé une méthode très catholique ;)
Petite précision, je l'ai fait en C.
Par Poulet Findus le 25/11/2002 à 23:30:48 (#2644055)
Par Tynril le 25/11/2002 à 23:45:37 (#2644152)
Terminale 10 PRINT "HELLO WORLD"
20 END
DUT 1ère année program HELLO(input, output)
begin
writeln('HELLO WORLD')
end.
DUT 2ème année (defun HELLO
(print
(cons 'HELLO (list 'WORLD))
)
)
Fraîchement sorti de l'école
#include
void main(void)
{
char *message[] = {"HELLO ", "WORLD"};
int i;
for(i = 0; i < 2; ++i)
printf("%s", message);
printf("\n");
}
Professionnel très expérimenté
#include
#include
class string
{
private:
int size;
char *ptr;
public:
string() : size(0), ptr(new char('\0')) {}
string(const string &s) : size(s.size)
{
ptr = new char[size + 1];
strcpy(ptr, s.ptr);
}
~string()
{
delete [] ptr;
}
friend ostream &operator <<(ostream &, const string
string &operator=(const char *);
};
ostream &operator<<(ostream &stream, const string &s)
{
return(stream << s.ptr);
}
string &string::operator=(const char *chrs)
{
if (this != &chrs)
{
delete [] ptr;
size = strlen(chrs);
ptr = new char[size + 1];
strcpy(ptr, chrs);
}
return(*this);
}
int main()
{
string str;
str = "HELLO WORLD";
cout << str <Release();
// Tell OLE we are going away.
CoUninitialize();
return(0); }
extern CLSID CLSID_CHello;
extern UUID LIBID_CHelloLib;
CLSID CLSID_CHello = { /* 2573F891-CFEE-101A-9A9F-00AA00342820 */
0x2573F891,
0xCFEE,
0x101A,
{ 0x9A, 0x9F, 0x00, 0xAA, 0x00, 0x34, 0x28, 0x20 }
};
UUID LIBID_CHelloLib = { /* 2573F890-CFEE-101A-9A9F-00AA00342820 */
0x2573F890,
0xCFEE,
0x101A,
{ 0x9A, 0x9F, 0x00, 0xAA, 0x00, 0x34, 0x28, 0x20 }
};
#include
#include
#include
#include
#include
#include "pshlo.h"
#include "shlo.hxx"
#include "clsid.h"
int _cdecl main(
int argc,
char * argv[]
) {
HRESULT hRslt;
IHello *pHello;
ULONG ulCnt;
IMoniker * pmk;
WCHAR wcsT[_MAX_PATH];
WCHAR wcsPath[2 * _MAX_PATH];
// get object path
wcsPath[0] = '\0';
wcsT[0] = '\0';
if( argc > 1) {
mbstowcs(wcsPath, argv[1], strlen(argv[1]) + 1);
wcsupr(wcsPath);
}
else {
fprintf(stderr, "Object path must be specified\n");
return(1);
}
// get print string
if(argc > 2)
mbstowcs(wcsT, argv[2], strlen(argv[2]) + 1);
else
wcscpy(wcsT, L"Hello World");
printf("Linking to object %ws\n", wcsPath);
printf("Text String %ws\n", wcsT);
// Initialize the OLE libraries
hRslt = CoInitializeEx(NULL, COINIT_MULTITHREADED);
if(SUCCEEDED(hRslt)) {
hRslt = CreateFileMoniker(wcsPath,
if(SUCCEEDED(hRslt))
hRslt = BindMoniker(pmk, 0, IID_IHello, (void **)
if(SUCCEEDED(hRslt)) {
// print a string out
pHello->PrintSz(wcsT);
Sleep(2000);
ulCnt = pHello->Release();
}
else
printf("Failure to connect, status: %lx", hRslt);
// Tell OLE we are going away.
CoUninitialize();
}
return(0);
}
Administrateur Système
#include
main()
{
char *tmp;
int i=0;
/* on y va bourin */
tmp=(char *)malloc(1024*sizeof(char));
while (tmp="HELLO WORLD"[i++]);
/* Ooopps y'a une infusion ! */
i=(int)tmp[8];
tmp[8]=tmp[9];
tmp[9]=(char)i;
printf("%s\n",tmp);
}
Apprenti Hacker
#!/usr/local/bin/perl
$msg="HELLO, WORLD.\n";
if ($#ARGV >= 0) {
while(defined($arg=shift(@ARGV))) {
$outfilename = $arg;
open(FILE, ">" . $outfilename) || die "Can't write $arg: $!\n";
print (FILE $msg);
close(FILE) || die "Can't close $arg: $!\n";
}
} else {
print ($msg);
}
1;
Hacker expérimenté
#include
#define S "HELLO, WORLD\n"
main(){exit(printf(S) == strlen(S) ? 0 : 1);}
Hacker très expérimenté % cc -o a.out ~/src/misc/bv/bv.c
% a.out
Gourou des Hackers % cat
HELLO, WORLD.
^D
Directeur junior 10 PRINT "HELLO WORLD"
20 END
Directeur mail -s "HELLO, WORLD." bob@b12
Henri, pourrais-tu m'écrire un programme qui écrit "HELLO, WORLD." À l'écran?
J'en ai besoin pour demain.
^D
Directeur sénior % zmail Jean
J'ai besoin d'un programme "HELLO, WORLD." Pour cette après-midi.
Président Directeur Général % letter
:ange:
letter: Command not found.
% mail
To: ^X ^F ^C
% help mail
help: Command not found.
% damn!
!: Event unrecognized
% logout
Par Anduric le 26/11/2002 à 1:28:17 (#2644662)
Provient du message de Kathandro
Sinon tu passes les variables par référence (particularité bien pratique du C++)... Pour les algos, le c++ c'est moyen quand même malgré tout...
Et puis le int main qui renvoie rien à la fin, normalement, ça plante :p... (façon simple de finir le main: return (0); )
Passer les variables par références ça change pas, pour l'occupation de la pile. Au lieu d'empiler la valeur, j'empile l'adresse de la valeur sur le Heap.
Sinon, je suis pas d'accord : le c++ est l'un des langages les plus rapides (moins que le C pur et l'assembleur, certes, mais aussi nettement plus flexible)
Par Anduric le 26/11/2002 à 2:15:43 (#2644836)
Je pars de tableau d'entier, mais on peut changer les types, j'ai juste la flemme de faire les templates, il est tard.
Provient du message de Shury
bon, alors pour ceux que ca interesse :
en gros, dans le 1er exo, il fallait inverser les elements d'un tableau ( c'est a dire, le 1er terme, se positionne au dernier terme, et vice verca ect ect ), bien sur, il faut le faire en récursive
tableau de départ: int _tab[_size]
void swap(int *_tab, int _size)
{
if (_size==1) return;
int _tampon = _tab[0];
_tab[0] = _tab[_size-1];
_tab[_size-1] = _tampon;
swap(_tab+1, _size-2);
}
O(n), je pense que c'est relativement optimal.
A posteriori, mon arithmétique des pointeurs est pas très claire (si ça se trouve, j'en ai profité pour me tromper, ce qui ne m'étonnerait pas du tout)
dans le 2eme, tu a un tableau rempli d'entier, on te donne 2 bornes ( a et b ), et de T[a] a T[b} , il doit retourner la valeur minimun, on te demande comment faire pour qu'il retourne l'indice auquel T soit le min entre T[a] et T, tout ca en récursif
--> c une autre fonction a faire ( 4 points )
int min(int *tab, int a, int b)
{
if (a==b) return a;
if (a==b-1) return (tab[a]<tab)?a:b;
int val1 = min(tab, a, (a+b)/2);
int val2 = min(tab, (a+b)/2 + 1, b);
return (tab[val1]<tab[val2])?val1:val2;
}
O(n). Sans hypothèse sur le tableau, difficile de faire mieux...
dans le 3eme, il fallait trier un tableau , du plus petit au plus grand , en suposant que la fonction de l'exo 2 fonctionne... Bien sur, ici, pas de boucle, juste la récurence... ( 4 points )
void trie(int *tab, int n)
{
if (n 2 points
Là c'est le truc dont on parle depuis le début du thread (en faisant gaffe au 2*n). J'ai la flemme.
Dans l'exo 5, il fallait faire une fonctionne pour vérifier si 2 chaines étaient des anagrammes ou non....
-> 6 points
Il faut faire du récursif ici ?
Si c'est pas nécessaire : méthode bourrin, on profite de savoir qu'on manipule des lettres pour optimiser la vitesse de calcul. Tri par dénombrement.
bool compare (char *ch1, char *ch2, int taille)
// si les chaines ont pas la même taille, c'est trivial et je le fais pas ici
{
int _alphabet[26] (on me voit venir, là, non ? :D)
int j=0;
while (j<26)
_alphabet[j++] =0;
for (int i=0; i<taille; i++) {
_alphabet[ch1[ i ]-'a']++; // gras : je profite de la table ascii et de la contingence des lettres
_alphabet[ch2[ i ]-'a']--;
}
bool egal = true;
j = 0;
while (j 6 points
Pas très clair... si y a que ça... bah c'est pareil que l'exo 3 (sauf qu'on trie dans l'autre sens). Je suppose donc qu'il y a une subtilité ?
Edit : une coquille dans le 1)
Par Lwevin Myan le 26/11/2002 à 21:27:11 (#2651233)
1.
int pwInverser( void* rpwEntree, int iMini, int iMaxi )
{
void* pwElement;
/* >= pour prévoir le cas d'un nombre impair d'éléments */
if( iMini >= iMaxi )
{
/* OK */
return 0;
}
else
{
if( 0 != pwInverser( rpwEntree, iMini + 1, iMaxi + 1 ) )
{
return 1;
}
pwEntree = rpwEntree[ iMaxi ];
rpwEntree[ iMaxi ] = rpwEntree[ iMini ];
rpwEntree[ iMini ] = pwEntree;
return 0;
}
}
2.
int iMin( int rtiTab[], int riBorneMin, int riBorneMax )
{
static int viMinTmp = 0;
if( riBorneMin == riBorneMax )
{
return riBorneMin;
}
viMinTmp = iMin( rtiTab, riBorneMin + 1, riBorneMax );
if( rtiTab[ viMinTmp ] > rtiTab[ riBorneMin ] )
{
return riBorneMin;
}
return viMinTmp;
}
3.
int iTrier( int rtiTab[], int riMini, int riNbElements )
{
static int viMini = 0;
static int viValMin = 0;
viMini = iMin( rtiTab, riMini, riNbElements );
viValMin = rtiTab[ viMini ];
rtiTab[ viMini ] = rtiTab[ 0 ];
rtiTab[ 0 ] = viValMin;
}
Non terminal et terminal déjà fait au dessus, à la fonction près.
Itératif :
4.
int UIteratif( int n )
{
int i = 1;
/* En fait, viSomme doit prendre la valeur U0 */
int viSomme = 0;
while( i <= n )
{
viSomme += 3 * viSomme + 2 * i;
i--;
}
}
5.
int iAnagramme( const char* const rpcChaine1, char* rpcChaine2, int riLongueurChaine2 )
{
/* Pour la clarté, mais pas indispensable */
char* p = rpcChaine2;
int i = 0;
if( 0 == strlen( riLongueurChaine1 )
{
return 0;
}
if( 0 != iAnagramme( rpcChaine1 + 1, rpcChaine2, riLongueurChaine2) )
{
/* Raté */
return 1;
}
/* Jusqu'ici, tout va bien... */
/* Vérification que le caractère courant de rpcChaine1 se trouve dans Chaine2 */
while( i < viLongueurChaine2 && rpcChaine1[ 0 ] != *(p + i) )
{
i++;
}
if( rpcChaine1[ 0 ] != *( p + i ) )
{
return 1;
}
/* Trouvé, il faut le supprimer pour ne pas le resélectionner plus tard */
*( p + i ) = '\0';
return 0;
}
6.
int iTri2( int rtiTab[], int riIndice, int* riBorneNul, int* riBorneNegatif )
{
static viMinTmp = 0;
if( 0 == riIndice )
{
/* OK */
*riBorneNul = 0;
*riBorneNegatif = 0;
return 0;
}
if( 0 != iTri2( rtiTab, riIndice - 1, riBorneNul, riBorneNegatif ) )
{
return 1;
}
if( rtiTab[ riIndice ] 0 */
/* 2 opérations à faire, le décalage des nombres < 0, et nuls*/
viMinTmp = rtiTab[ Indice ];
rtiTab[ riIndice ] = rtiTab[ *riBorneNegatif ];
rtiTab[ *riBorneNegatif ] = rtiTab[ *riBorneNul ];
rtiTab[ *riBorneNul ] = viMinTmp;
/* Incrémentation des deux compteurs */
*riBorneNegatif++;
*riBorneNul++;
}
}
A priori, ca n'appelle pas de code particulier, mais bon, au besoin...
Aucun code n'a été seulement compilé, donc un peu d'indulgence (m'étonnerait bien que je me sois pas planté, ne serait-ce que sur un indice)
Par TM'sC le 26/11/2002 à 21:30:32 (#2651263)
Par LeBaronDeLaNuit le 26/11/2002 à 22:00:55 (#2651536)
Par Anduric le 26/11/2002 à 22:06:40 (#2651585)
Ca rend le code moins lisible :D
Par Shury le 26/11/2002 à 22:21:10 (#2651711)
Vous etes des bourrins !!! :D
Ceci dit, quand j'ai montré ca a une copine qui maitrise un peu le c++ algo, elle a haluciné :D
vous etes des bourrins de codes je vous dis :D
Ceci dit, ca me fait déprimer, car je me demande si un jour, j'arriverai a faire comme vous :(
Par Anduric le 26/11/2002 à 22:44:37 (#2651896)
Perso, c'est un peu mon boulot (cela dit, en relisant ce que j'ai pondu, y a quand même des trucs qui me satisfont pas, mais à 2h du mat et 45mn, je vais pas faire le difficile ;) )
Tiens, à ce propos... C'est quel niveau, ce partiel ?
Par Lwevin Myan le 26/11/2002 à 23:19:17 (#2652133)
Provient du message de Shury
Vous etes des bourrins !!! :D
?
Ceci dit, quand j'ai montré ca a une copine qui maitrise un peu le c++ algo, elle a haluciné :D
Houlà, c++ et algo, ça va pas ensemble ;)
Honnêtement, le C peut donner un très bon niveau technique (il est à mon sens le meilleur compromis entre langage de bas et haut niveau), mais donne de très mauvaises manières de coder, parce qu'il est extrêmement facile de faire tourner quelque chose en C alors qu'en fait, le programme est buggé / pas optimisé.
Et c'est encore pire en C++ (qui est à mon avis un très mauvais langage, dire que je code avec en ce moment :()
Alors qu'avec des langages fonctionnels (comme Lisp), pour que ton programme tourne, tu dois en général t'accrocher (la manière de penser n'est pas intuitive pour 99,99% des gens), mais tu apprends deux choses fondamentales :
1) Penser à ce que tu dois faire avec de taper. Les langages fonctionnels tolèrent peu l'à peu près. Si ton algo est mauvais, tu as tout à recommencer. En C, tu peux le plus souvent trouver une bidouille (désastreuse pour les perfs et la clarté du code).
2) Penser comme la machine. Je ne sais plus où j'avais lu ça, mais il parait que debugger un source est une activité détestée des programmeurs (avec les tests, mais ça, ça se comprend ;) ). J'imagine qu'en fait, c'est surtout parce que le débuggage demande un esprit particulièrement analytique : il faut voir le code en regardant ce qu'il fait, pas en regardant ce que tu voudrais qu'il fasse. C'est à mon sens la plus importante des choses à savoir faire pour un informaticien, mais une poignée en est réellement capable.
(Par contre, programmation récursive immaintenable, donc proscrit au boulot :( A part un ou deux codes, j'avais rien fait de récursif depuis quelques années, ca rafraichit ;) )
Par Khorram le 27/11/2002 à 0:14:00 (#2652544)
:monstre: :rasta: :aide: :hardos: :confus: :doute:
Par Llewellen le 27/11/2002 à 11:40:20 (#2654745)
On en fait pour améliorer son algorithmique.
On ne l'utilise pas, parce que c'est un cauchemar à débugguer.
D'autre part, débugguer est en général relativement simple quand le code a été correctement écrit (ie : pas de variable globable entre autre) et qu'on a des outils qui permettent de faire du pas à pas.
Je vous garanti que débugguer un code embarqué quand la seule source d'info, on la reçoit parce qu'on a détourné les informations en sortie (j'en ai bavé pour débugguer le code embarqué d'une carte cryptographique qui ne disposait pas de debuggueur intégré)
Par contre, en ce moment, je bosse avec une autre carte crypto disposant d'un debuggueur embarqué, et c'est d'une simplicite :D (bon, faut juste rebooter le PC à chaque fois que y'a une erreur mémoire qui se produit en interne, on peut encore mieux faire :p)
JOL Archives 1.0.1
@ JOL / JeuxOnLine