Private joke entre matheux, dommage...

Si j'ai bien compris ton algo est juste un truc dans ce genre ?

for (int i = 1; i <= n/2; i++) {
    if (i * i == n) {
       return i;
    }
 }

Je serais bien curieux de savoir comment tu peux avoir -1 comme résultat. C'est ce que tu renvoies si tu n'as pas trouvé la racine ? Dans ce cas beaucoup d'autres nombres auraient "-1" comme racine (les entiers non carrés parfaits).

Je n'aurais pas deviné sans ton commentaire !

Si les experts de la finance font de telles optimisations, tu m'étonne qu'ils foutent autant le bordel à la bourse.

En supposant qu'on retourne -1 si y'a un soucis :

 for (int i = 0; i * i < n; i++);
 
 if (i * i == n)
     return i;
 else
     return -1;
 

Qui dit mieux ?

Tu n'as pas tout compris : il s'agit de foutre le bordel dans la Finance, la détruire par ses outils pour aboutir à une optimisation de la société. Fichtrement astucieux ...

Ton code ne devrait pas fonctionner (ou alors retournera toujours −1) car i n'est déclarée que dans la boucle, qui ne fait qu'une ligne.

Pour moi CTLPB, 0*0=0n et sqrt(0)=0 et 1*1=1 et sqrt(1)=1, donc l'algo while (i*i<=n) suffit largement, ça n'a aucun intérêt de les traiter à part...

Seulement quand c'est le responsable qui paie.
Oh wait ...

Arrêtez-moi si je me trompe, mais il me semble que l'auteur a dit que c'est ce qui était fait au début : une boucle de 0 à n, que le professeur a jugé pas optimisé.

Je ne vois pas du tout l'intérêt de mettre n/2 comme borne sup. L'algo aura exactement la même complexité et s'arrêtera pour n>2 bien avant n/2. Il n'y a donc aucune optimisation en faisant ce changement. Un méthode par dichotomie accélérerait déjà un peu. Bref, c'est pas un pebkac, juste un enseignant nul en math (ce qui au passage est très courant en finance...).

C'est quoi ce délire ? Il est déjà passé ce PEBKAC !

Et même en corrigeant cette erreur sur la boucle, il ne fonctionnerait que pour les carrés parfaits.

Je me faisais la même réflexion...

lien ?

Pour les carrés parfaits c'est normal, il demande seulement 'les racines entières'... La valaur -1 veut simplement dire que la racine n'est pas entière. C'est un des premiers exos qu'on m'a fait faire quand j'ai appris le C(++) :p

Par contre effectivement faut déclarer i avant :)

La racine carrée entière, c'est la partie entière de la racine carré :
RacEnt(0)=0
RacEnt(1)=1
RacEnt(2)=1
RacEnt(3)=1
RacEnt(4)=2
RacEnt(5)=2
RacEnt(6)=2
RacEnt(7)=2
RacEnt(8)=2
RacEnt(9)=3
etc.

les racines carrées de 0 et de 1 valent respectivement « -1 »
C'est moi ou il manque quelque chose ? Ou alors c'est le mot respectivement qui ne fallait pas utiliser ?

Che confirme, petit sacripan! On utilise « respectivement » lorsqu'il y a plusieurs valeurs à mettre en miroir. juu, mAn, vous recevrez respectivement zéro et un coup de fouet pour vos actes.

/me tend une sucette et un drapeau «Grammar macht frei» à juu pour sa contribution.

Et on met un espace avant et après un point d'exclamation... Mais c'est vrai que ce n'est pas de la grammaire...

Sauf que là tu ne retournes rien pour les valeurs de n < 2, il faut au moins rajouter un return -1 après la boucle pour obtenir l'algo donné en correction par l'enseignant. (sinon ça ne passera même pas la compilation)


Après je te laisse le tester toi même avec des valeurs de n à 0 et à 1. ;)

Je pense que l'ago devait etre

for (int i = 0; i == n; i++) { //autant aller jusqu'à 'n', ca évite de calculer le n/2, et on s'arrêtera en route de toute facon Sauf si on ne fait pas de retour.
if (i * i > n) { //afin de prendre en compte les resultats non entier
return i-1; //On enleve 1 car on arrondit à l'inférieur
}
}
(Par contre, je trouve 0 pour 1, et non -1.)

Si quelqu'un avait déjà posté le même, mea culpa !

Au temps pour moi, j'aurai du mettre un « chacune ».

Baisse son pantalon pour recevoir les coups de fouet de Grammar Nazi

Bon, je vais essayer de donner les algos

Première position que ma chérie a réalisée pour son TD :
Fonction fRac(entier positif n)
Début
Pour( i de 0 à n )
si( i * i = n )
Retourne i
fsi
FPour
Retourne -1 // Donc pas de racine carrée entière trouvée
Fin

Le prof refuse, « ce n'est pas optimisé » il n'est pas nécessaire de parcourir jusqu'à n... ce qui n'est pas faux.
Pas grand chose à modifier donc :
Fonction fRac(entier positif n)
Début
Si( n = 0 )
Retourne 0
Sinon si( n = 1 )
Retourne 1
Fsi
Pour( i de 2 à n/2 )
si( i * i = n )
Retourne i
fsi
FPour
Retourne -1 // Donc pas de racine carrée entière trouvée
Fin

Refus de l'enseignant qui trouve ça « trop compliqué » O_ô, barre la première partie et remplace « i de 2 » par « i de 1 » dans la boucle...

Alors ensuite, y a peut-être bien plus optimisé que la boucle (comme l'usage d'une puissance 1/2 ?), mais il ne faut pas oublier qu'il s'agissait d'un tout premier court d'algorithmie. Ça commence mal hein ?

Je suis certain de l'avoir déjà lue il y a quelques semaines, mais impossible de la retrouver après la demande de Vinm.
@SuperClem : au secours !

@Tharkun Un petit tour sur Wikipédia confirme ce que tu dis. :)

N'ayant pas son énoncé sous les yeux, je l'ai peut-être mal retranscrit en choisissant un mauvais terme et là honte à moi. Ce que je me souviens à coup sûr c'est que seuls des entiers étaient impliqués d'après la signature de la fonction.

Si c'est bien ce que l'énoncé demandait, honte à nous trois : l'enseignant, ma chérie et moi même. ;)
Au moins j'en sors avec une nouvelle connaissance.

Je sais pas pourquoi tout le monde veut aller à N/2, si vous voulez optimiser, faites:

i = 0
while(true)
tmpVar = i*i
si( tmpVar = n )
Retourne i
//Aucune chance de trouver n si on est déjà au dessus
Sinon si( tmpVar>n )
Retourne -1
fsi
//Faut incrémenter, sinon, ça sert à rien
i++
FWhile
Fin

Certains reprocheront le while true, vous pouvez l'enlever avec un seul return à la fin et un boolean pour stopper la boucle... Le tmpVar n'est là que pour faire l'opération du ii une fois, vous pouvez l'enlever si vous souhaitez faire plus de calcul et le remplacer par ii partout.

Vous pouvez faire plus optimisé si vous voulez, mais ça sera sans doute beaucoup plus complexe.

Ben c'est comme le tout premier algo proposé, écrit avec un Faire Tant que au lieu d'un Pour. ^^;

Après niveau gain si on va seulement jusqu'à n/2, on vire la moitié des tests (inutiles de surcroit) ce qui n'est dans l'absolu pas négligeable... mais dans les deux cas on considère que c'est du o(n) si ma mémoire est bonne (les cours de complexité commencent à se faire vieux).

Edit : D'ailleurs j'aurai pu virer encore un test vu que n entier positif :
Si (n < 2) retourne n
Pour i de 2 à n/2 ...

Enfin bon c'est du chipotage là.

Merci pour le drapeau, je vais demander à Clem de me l'échanger contre une belle médaille !

Relis l'algo, il va sortir quand i*i est au dessus de N

Du coup, au lieu d'avoir d'aller jusqu'à N/2, ça va que jusqu'à racine(N) +1
De plus, t'as pas à te soucier du test de 0 et 1 vu qu'il va correctement les gérer.

Exemple: avec 101, ça va aller jusqu'à 11 et pas jusqu'à 50 :)

Mais oui, c'est du chipotage.

Ah oui exact !

Ne pas faire deux choses en même temps
Ne pas faire deux choses en même temps
Ne pas faire deux choses en même temps

Là on passe donc dans du o(n^1/2) ce qui est en effet bien mieux !!
Quand je dis que mes propres souvenirs de cours de complexité commencent à dater...

Non le chipotage c'était pour mon instruction de plus. ;)

Oui, dans ce que j'ai écrit, seul des entiers sont impliqués aussi.
L'algo reste simple (vite fait, en VBA) :

Function RacEnt(n As Integer)
Dim i As Integer
i = 0
While i * i <= n
i = i + 1
Wend
RacEnt = i - 1
End Function

Oui, mais je ne vais pas non plus comment optimiser plus.

J'ai du mal à comprendre l'intérêt des premiers tests (n == 0, n == 1). L'algo marche très bien pour ces 2 valeurs, il suffit de s'assurer que la boucle va assez loin (n/2 est OK pour n=0, pour que ça marche avec n=1 il suffit de mettre n/2+1, ce qui dans le cas général n'est pas pire que n/2).

Donc, pour faire plaisir au prof qui veut absolument un n/2 (ce qui est stupide vu que d'une part la boucle s'arrête bien avant dans tous les cas et d'autre part en terme de complexité, n/2 et n c'est pareil... et qu'en plus Roudoudou montre qu'on peut trivialement avoir du n^1/2 !) :

for (int i = 0; i < n/2+1 /* ou n'importe quelle borne >= n/2+1... */ ; ++i) {
if (i*i == n) return i;
// pour du n^1/2, ajouter "else if (i*i > n) return -1;"
}
return -1;

En typographie on dit UNE espace

Groumpf, évidemment il suffit que je ré-écrive le pseudo-code en C pour me planter, c'est bien sûr :

for (int i = 0; i <= n/2+1; ++i)

que je voulais dire (et non pas <, sinon 1 foire encore)...

Même si c'est moins performant que la solution de Roudoudou, car niveau temps d'exécution c'est la même chose que mon algo (n/2 exécutions de la boucle au max), ça marche et vire en effet le test séparé de 0 et de 1. Moins de lignes pour la même chose.

Après ça ne change pas le fait que la solution de l'enseignant reste fausse : for (int i=1; i<=n/2; i++) :(

@Tharkun La solution de Mufman plus bas est je pense probablement la meilleure pour cet exercice. ;)

En fait, faudrait avoir le vrai énoncé. Car on veut vraiment la racine carrée entière, on s'arrêtera de toutes façons dès qu'on l'a trouvée, quelque soit la condition de fin de boucle, on s'arrêtera en moyenne au bout de n^1/2 itérations (c'est-à-dire racinecarrée(n) )
Si on cherche à savoir si n est un carré parfait, il faut effectivement faire comme il a fait pour sortir dès que i*i > n

i == n ? Euh... comment dire... Tu ne rentre même pas dans la boucle, sauf pour n valant 0.