Question algorithmique

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Felwin
Messages: 2
Enregistré le: 07 Jan 2017, 00:51

Question algorithmique

par Felwin » 07 Jan 2017, 01:12

Bonjour,
Je suis développeur et malheureusement pas assez bon en math pour résoudre ce petit problème, j'en appelle donc a votre aide.
Je vais essayer de le formuler de la manière la plus rigoureuse possible mais mes années de mathématiques remontent a loin donc j’espère que vous serez indulgent.
Code: Tout sélectionner
x et y des entiers naturels positif,
on a la relation suivante : ax²+bx+c <= y < a(x+1)²+b(x+1)+c
pour y donné, comment trouver x ?

Un calcul mathématique direct serait merveilleux, mais je ne suis pas certain que cela soit possible, je doit implémenter cette solution dans un algorithme, dans ce cadre la solution avec le moins d’itérations serait la meilleure.
Mon algorithme actuel est :
Code: Tout sélectionner
x = 0
tant que ax²+bx+c <= y faire
x = x+1
fin de faire
resultat: x -1

J'ai l'intuition que l'on peut faire beaucoup mieux.

En espérant que vous puissiez m'aider, ou qu'au moins ce petit problème vous aura plut.

PS : pour vous donner un contexte il s'agit de savoir, en fonction de l’expérience gagné par le joueur, quel est son niveau ^^



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Question algorithmique

par fatal_error » 07 Jan 2017, 02:04

sans plus de connaissance sur a,b et c, faut se taper les disjonctions de cas
le but c'est de résoudre les deux inéquations séparément puis de prendre l'intersection des deux intervalles (respectifs) solution.

On peux procéder ainsi:
1) une fonction f(a,b,c,y) qui résoud ax^2+bx+c<=y et qui te retourne un array d'intervalle
2) on bidouille pour la deuxieme inégalité
3) une fonction inter(u,v) où u et v sont des array d'intervalle et te retourne un array d'intervalle intersection

1)
Code: Tout sélectionner
function f(a,b,c,y)
    d = c-y
    //ax^2+bx+d<=0
    si a == 0
        //un petit effort à fournir
        return

    //le trinome est du signe de a à l exterieur des racines
    calcul de x1,x2, x1<x2 les racines de ax^2+bx+d, tu devrais tenter ta chance au lycée, ils connaissent pas mal delta.
    si a > 0
        retourner [[x1,x2]] //partie entre les racines vu qu'on veut <=0
    retourner [ [-Infty, x1], [x2, Infty] ]


2) pour résoudre la deuxieme inéquation il suffit de développer...
ax^2+2ax+1+bx+b+c = ax^2+(2a+b)x+1+b+c
idem on a le triple (a, 2a+b, 1+b+c)
puis comme on veut (a, 2a+b, 1+b+c)>=y (et non inférieur) on multiplie par -1
(-a, -2a-b, -1-b-c)<=-y
et on peut donc appeler f


3)
Code: Tout sélectionner
//suppose les intervalles "ordonnés" au sein de u, ainsi qu'au sein de v
function inter(u,v)
    intersection = [];
    pour chaque intervalle i_u de u
        pour chaque intervalle i_v de v
            //on regarde si ya une intersection
            //ya pas 50k intervalles...yen a 4 donc -à priori- ca va
            //ca revient à considérer
            // l_u-----r_u
            //     l_v-----r_v
            // intersection!
            si l_u <= l_v et r_u <=r_v
                intersection.push([l_v, r_u])
            sinon si l_v<=l_u et ... mystere mystere
                ...
            fsi
        fpour
    fpour
    //note: ne gère pas le cas [a,b]U[b,c] qui devrait être réduit en [a,c]
    //mon petit doigt me dit que ca se produit pas, mais bon l'intuition...
    return intersection

si tu veux x>0 tu peux de fait appeler inter([0, infty], inter(u,v))
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Question algorithmique

par Ben314 » 07 Jan 2017, 03:02

Salut,
En fait, c'est assez simple :
.
Pour qu'il y ait des solutions, il faut s'annule donc que le discriminant soit positif ou nul, sinon c'est foutu (en supposant que pour que ce soit effectivement un polynôme du second degré).
Si le polynôme admet deux racine et et deux cas se présentent :

- Si alors le polynôme est négatif ou nul sur et l'entier que tu cherche est le plus grand entier de cet intervalle qui, s'il existe, est évidement la partie entière de .
L'éventuelle solution est donc , mais il faut vérifier que (ou bien que ) car il est possible que l'intervalle soit trop petit pour contenir un entier.

- Si alors le polynôme est strictement positif sur et l'entier cherché est le plus petit entier de cet intervalle qui, s'il existe, est égal à .
Donc l'éventuelle solution est de nouveau comme dans le premier cas, mais cette fois, il faut vérifier que (ou bien que ) car si est trop petit pourrait ne pas être dedans.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Felwin
Messages: 2
Enregistré le: 07 Jan 2017, 00:51

Re: Question algorithmique

par Felwin » 09 Jan 2017, 00:04

Ben314 a écrit:L'éventuelle solution est donc , mais il faut vérifier que (ou bien que ) car il est possible que l'intervalle soit trop petit pour contenir un entier.


C'est bien ça ! Merci beaucoup !

Effectivement j'aurais du donner plus d'informations sur a, b et c, dans mon cas a et b sont positif et c négatif, ce qui fait que la formule est exploitable sans soucis.

Je passe d'un algorithme avec une complexité en O(n) a une complexité en O(1), c'est un gain énorme !
Encore merci !

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 13 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite