Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Équation à quatre inconnues - Plus petit résultat

Posté par
babilounet
05-07-14 à 01:22

Tout d'abbord bonjour à tous !

Je suis arrivé sur ce forum car je me creuse la tête sur un problème d'algo. J'ai à quelque chose près réussit à mettre mon problème en forme, mais ça me hante de ne pas réussir à le résoudre et mes années d'études de math sont bien loins maintenant.

Il s'agit de trouver x, y, w et z dans une équation du type :

B = A + 18x + 17y - 17w -18z

Avec A et B deux entiers positifs donnés (entre 0 et 600 disons).
Et tel que x, y, w et z soient des entiers positifs

J'aimerai trouver la solution telle que :

n = x + y + w + z

Avec n les plus petit possible.

Voilà j'espère que c'est assez clair, mais je ne sais pas pour ou commencer...

Merci de vos réponses

Posté par
verdurin
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 02:37

Bonjour,
juste une remarque pour commencer :
B-A=18(x-z)+17(y-w).
Il y a donc toujours des solutions car 17 et 18 sont premiers entre eux.
Et les solutions ne déterminent que x-z et y-w.

Posté par
babilounet
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 04:42

Salut,

Oui j'avais fais cette factorisation sur un coin de feuille mais je n'avais pas remarqué ce que ça implique.

Du coup l'équation se transforme grosso-modo en :

18a + 17b = c

avec a=(x-z) et b=(y-w)

Du coup j'ai cherché un ptit peu du côté des équation diophantienne mais je bloque toujours sur la résolution. La plupart des exemple que j'ai trouvé prennent '1' pour valeur de 'c', ce qui ne correspond pas tout à fait a mon problème :/

Posté par
weierstrass
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 08:11

Bonjour,
la résolution d'une équation diophantienne est expliquée sur wikipédia:

Et je suis sur qu'en surfant un peu tu trouveras des cours plus clairs.

Posté par
carpediem
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 14:37

salut

la question est : y a-t-il des solutions positives ?


Begin
Read a, b
n = 10000000000000000000000000000000
For x = 0 To max(a, b)
For y = 0 To max(a, b)
For z = 0 To max(a, b)
For w = 0 To max(a, b)
If 18x + 17y + b = 18z + 17w + a and x + y + z + w < n then n = x + y + z + w
Next w
Next z
Next y
Next x
Write n


REM :

1/ je majore les boucles à max (a, b) qui me semble suffisant pour avoir une solution ... à voir peut-être prendre a + b ...
2/ à toi de compléter si tu veux les valeurs de x, y, z et w qui réalisent ce minimum ...

3/ pour revenir à ma question lorsque a = b il y a bien sur la solution triviale x = y = z = w = 0 = n
4/ lorsque a et/ou b sont multiples de 17 et/ou 18 la solution est tout aussi évidente ...

....

Posté par
babilounet
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 14:51

Hello,

Merci de ta réponse weierstrass, je me suis balader sur wiki mais je n'arrive toujours pas a faire ce que je veux.

Je vais prendre un exemple concret :

1 = 35 + 18x + 17y - 17w - 18z

Ce qui nous donne en factorisant :

-34 = 18(x-z) + 17(y-w)

Et en posant X = x-z  et Y = y-w

-34 = 18X + 17Y

Jusqu'ici tout va bien. Sur le wiki on nous dis de trouver la solution particulière de ax + by = c avec c=1.

Plutôt évident ici (1;-1) étant couple solution de 18x + 17y =1

En parant de ça on déduis qu'il existe un entier k tel que 18kx + 17ky = k

Je trouve donc une solution (-34;34) à mon équation 18x + 17y = -34. Et tout couple (c;-c) résout mon équation.

Mais dans ce cas (0;-2) est également solution et je rappelle que dans mon cas il est important de trouver les solutions telles que |x| et |y| soient les plus petits possible.

Comment est-ce que je peux trouver la solution ou |x| et |y| sont le plus petit possible à chaque fois ?

Posté par
babilounet
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 15:02

Merci carpediem, j'écrivais en même temps que tu postais o/

Merci pour le bout d'algo.

Je me sers de cet algo pour trouver un chemin entre deux cases sur une grille un peu spéciale. Il y a forcement toujours une solution avec x, y, w et z positif.

Le cas A=B ne se présente jamais et comme tous les cas doivent être automatisé, même les solutions évidentes doivent être calculés.

Je vais tester ça, merci pour ta réponse

Posté par
weierstrass
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 15:26

babilounet,
les couples solutions sont de la forme (-34+17k,34-17k)

Pour trouver le meilleur couple, je pense qu'il doit y avoir une formule...

au pire, il suffit d'essayer pour certain k, je pense intuitivement que le couple recherché doit être situé entre le couple (a,b) ou |a| est minimal, et celui ou |b| est minimal, ou en tout cas pas loin, ça restreint le champ de recherche...

Posté par
babilounet
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 15:43

C'est bon j'arrive à faire à peu près ce que je veux, il y a encore des optimisation à faire mais la base est la grâce à vous.

Merci bien les amis, bonne fin de journée et bonnes vacances pour ceux qui en ont ! \o/

Posté par
weierstrass
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 16:05

Les couples solutions sont de la forme (a+dk,b-dk)
considérons la somme |a+dk|+|b-dk|

si a+dk positif et b-dk positif:
|a+dk|+|b-dk| = a+b

si a+dk négatif et b-dk négatif:
|a+dk|+|b-dk| = -(a+b)

si a+dk positif et b-dk négatif:
|a+dk|+|b-dk| = a-b+2dk

si a+dk négatif et b-dk positif:
|a+dk|+|b-dk| = b-a-2k


si a+dk et b-dk sont de signes différent, on cherche a-b+2dk et b-a-2dk proches de 0
on obtient k = E((b-a)/2d) ou k = E((b-a)/2d)+1

Le minimum sera donc soit |a+b|, soit |a-b+2dk|, avec k tel que a+dk et b-dk soient de signes différent.

En espérant ne pas dire de bêtises

A vérifier...

Posté par
carpediem
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 17:47

pour revenir à une solution plus théorique :

18(x - z) + 17(y - w) = b - a <=> 18u + 17v = b - a

or 18.1 + 17(-1) = 1 donc 18(b - a + 17k) + 17(a - b - 18k) = b - a

donc

u = b - a + 17k et v = a - b - 18k

donc

x - z = b - a + 17k
y - w = a - b - 18k

mais ensuite ....

Posté par
weierstrass
re : Équation à quatre inconnues - Plus petit résultat 05-07-14 à 20:48

Je viens de me rendre compte que je me suis effectivement trompé...
Dans l'hypothèse où a et b sont premiers entre eux (mais facilement généralisable...)
Les couples solutions sont de la forme (a+xk,b-yk)

a+xk positif, b-yk positif:
|a+xk|+|b-yk| = a + b + k(x-y)
cette expression sera minimale pour k = E((a+b)/(y-x)) ou k = E((a+b)/(y-x)) 1


a+xk positif, b-yk négatif:
|a+xk|+|b-yk| = a - b + k(x+y)
Cette expression sera minimale pour k = E((b-a)/(x+y)) ou k = E((b-a)/(x+y)) 1


a+xk négatif, b-yk positif:
|a+xk|+|b-yk| = b - a -k(x+y)
Cette expression sera minimale pour k = E((b-a)/(x+y)) ou k = E((b-a)/(x+y)) 1

a+xk négatif, b-yk négatif:
|a+xk|+|b-yk| = -(a+b) + k(y-x)
Cette expression sera minimale pour k = E((a+b)/(y-x)) ou k = E((a+b)/(y-x)) 1


Conclusion:
Il suffira de tester les valeurs E((b-a)/(x+y)), E((b-a)/(x+y)) 1, E((b-a)/(x+y)), E((b-a)/(x+y)) 1



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !