Cas concret

[Razes]

Le A est utiliser dans la 2ème ligne du programme pour calculer le nombre maxi d'itération.

E(x) est la partie entière, la fonction doit être prise en charge par la TI89, sinon prendre une fonction équivalente.

M-B→M (pourquoi ? à chaque pas on retire B de M afin de minimiser les calculs. car plus l'indice I augmente plus le reste R diminue.

P.S.: Tu peux faire tourner le programme à la main

[zygomatique]

@zygomatique:

ta resolution n'est pas tout a fait juste :
en prenant a<b (j'ai compris l'importance de ce fait), on calcule le nombre de b max, et on demare l'algo (en admetant que m n'est pas multiple de a ou b)

le probleme c'est qu'a un moment le reste sera suppieur a a, il faut tester a chaque boucle et en rajouter 1 si necessaire ...
avec quelques ajustements, je pense pouvoir pondre un truc qui marche...

bien sur : je ne t'ai proposé que l'idée générale (et il faut ensuite entrer dans les détails)

tout le pb est de trouver l'encadrement optimal : f(u, v) < m < f(w, t)

avec f(x, y) = xa + yb

et il peut évidemment y avoir plusieurs solutions (par exemple simplement en considérant les contraintes :
utiliser le maximum de a
utiliser le maximum de b
moins de a que de b
moins de b que de a
...)

donc déjà en premier lieu c'est de majorer le nombre de tests (parce que si tu restes deux heures à savoir combien de tickets ta chérie risque de ne pas être contente )

je ne suis pas sur que l'algo de Razes convienne car il faut trouver la distance minimale de f(x, y) à m soit par valeur inférieure soit par valeur supérieure (la valeur absolue)

par contre avec ton idée de matrice on peut être sur de déterminer les meilleurs solutions

si 0 < a < b et (p - 1)a < m < pa et (q - 1)b < m < qb alors il suffit de tester tous les couples (x, y) € [0, p] x [0, q] et calculer |ax + by - m|

c'est radical mais cela fait donc (p + 1)(q + 1) tests ...

[Razes]

je ne suis pas sur que l'algo de Razes convienne car il faut trouver la distance minimale de f(x, y) à m soit par valeur inférieure soit par valeur supérieure (la valeur absolue)

par contre avec ton idée de matrice on peut être sur de déterminer les meilleurs solutions

si 0 < a < b et (p - 1)a < m < pa et (q - 1)b < m < qb alors il suffit de tester tous les couples (x, y) € [0, p] x [0, q] et calculer |ax + by - m|

Pourquoi tu dis ça zygomatique, tu as testé le programme pour émettre ce jugement?
Ce petit bout de programme balais toutes les configurations possibles, calcule le reste temporaire R et une fois il trouve un reste plus petit il le stocke dans RMINI ainsi que les quantités de A et de B qui donnent ce reste minimal.
RMINI ainsi que les quantités de A et de B sont mis à jour à chaque pas du calcul.
Si tu veux, je pourrais te l'écrire en n'importe quel langage de programmation pour que tu le teste.
P.S.: N'oublie pas ta devise: Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

@gwlegion
Si tu le veux, je peux rajouter quelques lignes de programmer et t'afficher toutes les solutions correspondantes au reste optimal.

[zygomatique]

je ne suis toujours pas sur parce qu'il me semble que tu testes uniquement par valeur inférieure avec la division euclidienne

ainsi pour une quantité I(avec les notations de ton programme) de a fixée tu calcules E(m/b)

déjà là il me semble qu'il faille calculer E[(m - Ia)/b]

ensuite plus simplement si on a la division euclidienne m - Ia = qb + r avec 0 =< r < b il faudrait regarder les deux différences

m - ia - qb = r (distance par valeur inférieure)
m - ia - (q + 1) b = b - r (distance par valeur supérieure)

et prendre la plus petite de ces deux distances pour Rmini

ce me semble-t-il ...

et au départ il faut même tester avec que des a et supérieure à m donc regarder jusqu'à k + 1

[gwlegion]

pour afficher tout les couples nA et nB ayant un reste optimal, il faudrais calculer tout les couples entre 0 et le nombre max.

du coup, on se rapprocherais de mon idee de matrice, puis de tri des resultats pas ordre croissant jusqu'a M...

d'ailleur, maintenant que j'y pense, on doit pouvoir se faire un document libreoffice qui fais ca

[Razes]

pour afficher tout les couples nA et nB ayant un reste optimal, il faudrais calculer tout les couples entre 0 et le nombre max.

du coup, on se rapprocherais de mon idee de matrice, puis de tri des resultats pas ordre croissant jusqu'a M...

d'ailleur, maintenant que j'y pense, on doit pouvoir se faire un document libreoffice qui fais ca

C'est pour cela que je t'ai demandé dès le départ, est ce que tu cherche une solution ou toutes les solutions et tu m'as répondu "une solution".

[zygomatique]

on suppose b < a

Code: Tout sélectionner

Read a, b, m
k = E(m/a)
ri = m - ka
rs = (k + 1)m - a
(u, v) = (k, 0)
(x, y) = (k + 1, 0)
For i = 0 To k
     j = E[(m - ia)/b]
     rit = m - ia - jb
     rst = ia + (j + 1)b - m
     If rit < ri
          (u, v) = (i, j)
          ri = rit
     If rst < rs
          (x, y) = (i, j + 1)
          rs = rst
If ri < rs Then Write (u, v) Else Write (x, y)

si le couple (u, v) est affiché alors m - ua - vb est minimal
si le couple (x, y) est affiché alors xa + yb - m est minimal

comme l'algo de Razes en gros on ne traite que "la diagonale" de la matrice de toutes les solutions possibles (grace à la division euclidienne on va au plus près de m au lieu de tester tous les couples (i, j) de la matrices avec i variant de 0 à E(m/a) + 1 et j variant de E(m/b) + 1)

ri : reste inférieure de m - ia - jb
rs : reste supérieur de ia + (j + 1)b - m

rit et rst : t = temporaire (calculé pour le couple (i, j) en cours dans la boucle) et compares aux meilleurs trouvés jusque là (soit ri et rs)

[gwlegion]

serait il possible d'envisager un resolution geometrique.
on sait que le resultat se situe sur une diagonale allat de Amax a Bmax sur un triangle rectangle.
quelque chose du genre Bmax-(X*B+X*A)
du coup, on doit pouvoir determiner a quel point cette diagonale prends exactement la valeur M.
les meilleures solutions doivent pas etre loin de ce point

[Razes]

Bonour gwlegion ,

Voici le programme adapté sur VBA EXCEL, je l'ai testé ça marche impeccablement.

Code: Tout sélectionner

Sub CalculerSomme()
    A = ActiveWorkbook.Sheets("Feuil1").Cells(2, 2).Value
    B = ActiveWorkbook.Sheets("Feuil1").Cells(3, 2).Value
    M = ActiveWorkbook.Sheets("Feuil1").Cells(4, 2).Value
    If (M <= A) Or (M <= B) Then
        MsgBox "Le montant est inférieur au tarif"
        Exit Sub
    End If
    If A < B Then
        INVERSER = True 'Indicateur d'intervertion de A et B
        C = A
        A = B
        B = C
    End If
   
    K = Int(M / A)  'Nombre maxi de A
    R = M           'Initialisation Reste, Temporaire
    i = 0           'Quantité; de; A, Temporaire“
    j = 0           'Quantité; de; B, Temporaire; “
    QA = 0          'Quantité; de; A, stocké“
    QB = 0          'Quantité; de; B, stocké“
    RMINI = M       'Initialisation Reste minimum, stocké”
    Do While i <= K
              j = Int(M / B)
              R = M - j * B
              If R < RMINI Then
                   QA = i
                   QB = j
                   RMINI = R
              End If
              i = i + 1
              M = M - A
    Loop
    If INVERSER Then
        Cells(8, 1) = QB
        Cells(8, 2) = QA
    Else
        Cells(8, 1) = QA
        Cells(8, 2) = QB
    End If
    Cells(8, 3) = RMINI
End Sub


Copie feuille Excel:

Calcul Tickets.jpg (23.67 Kio) Vu 348 fois

Il suffit de rentrer les valeurs de dans les cellules B2; B3; B4
et démarrer la routine et le tour est joué.

[zygomatique]

tu ne réponds pas à mon interrogation dans le cas où on peut donner des tickets correspondant à une somme supérieure

je suis d'accord que cet algo marche pour trouver la différence minime "par valeur inférieure" c'est à dire la meilleure solution pa + qb < m et m - (pa + qb) = ri (reste inférieur) est minimal

mais à nouveau il ne me semble pas voir le cas de la meilleure solution m < pa + qb et pa + qb - m = rs (reste supérieur) est minimal

ainsi si je ne fais pas d'erreur avec les mêmes valeurs

A = 22
B = 27

et M = 3330 que répond-il ?


mais peut-être me trompé-je ....

[Razes]

144A+6B=3330

[zygomatique]

ok bon et si on ne prend pas a et b premiers entre eux (ce qui est le cas des tickets il me semble)

du genre :

a = 10
b = 5

[gwlegion]

a=8.65
b=5.3
m=17.2

la reponse attendue serait 2a soit 17.3 ... apres tout on est pas a 10 cent pres

[Razes]

3B
Tu as le programme, tu peux le tester directement. Seulement dans ton dernier cas, il faut passer en centimes pour te débarrasser des virgules.

[chan79]

salut
on peut bidouiller pour avoir toutes les solutions (à vérifier)

[zygomatique]

voila ton exemple montre exactement ce que je demande à Razes ...

il donne toutes les sommes "par valeur supérieure" et qui conduisent à un écart minimal (identique)

on vois bien que toute combinaison linéaire pa + qb < 3329,5 conduit à un écart plus important

je ne suis pas sur (mais comme je l'ai dit peut-être que je me trompe dans la lecture de son algo) que celui de Razes réalise cela

sauf erreur mon algo le fait et vu sa construction il donne la solution avec le coefficient de A (si A > B) le plus grand possible (puisqu'il balaie toutes les valeurs de 0 à E(m/a))

[chan79]

correction; je n'avais pas affiché toutes les solutions...

[zygomatique]

ha on aurait aussi bien par valeur inférieure que par valeur supérieure ?

enfin un exemple n'est pas une preuve ...

en tout cas voila un bel exercice :

a et b deux entiers non nuls donnés

m un entier

E = {ua + vb < m}
F = {xa + yb > m}

question : pour tout m a-ton m - max E = min F - m ?

[Razes]

bonjour.

voici mon probleme du moment

soit un couple ayant tout les deux des tickets restaurants ( A et B) de valeurs differents
Il me faut determiner combien je dois donner de A et de B pour approcher au plus pret le montant a payer.

apres, je compte en faire un programme... mais ca je me debrouillerais.

Bonsoir,
Je ne comprends pas ce que vous voulez trouver, je pense que l'énoncé est clair "on vous tends un billet de 100euros pour avoir des tickets restaurants" et qu'il fallait trouver les quantités de A et de B qui rentrent dans le budget.

Si j'ai bien compris, ce que vous êtes en train de faire, c'est de faire un calcul par excès quitte à dépasser le budget et demander au client de rallonger plus de sous parce qu'on a décidé cela lors de la programmation (et si le client ne l'a pas).

Ce qui m’intéresse de savoir, c'est quoi le critère choisi? C'est quoi la valeur de la précision choisie (j'ai cru lire 10 cents).

[chan79]

a et b deux entiers non nuls donnés

m un entier

E = {ua + vb < m}
F = {xa + yb > m}

question : pour tout m a-ton m - max E = min F - m ?

essayer avec:
a=11
b=21
m=125