IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Invariant de boucle


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    mars 2012
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2012
    Messages : 6
    Points : 2
    Points
    2
    Par défaut Invariant de boucle
    Bonjour,
    Voilà le code:

    ******************************************************
    # ‘jour’ est initialement la date en jours écoulés depuis le 01/01/2005
    annee = 2005

    while jour > 365:
    if EstAnneeBissextile(annee):
    if jour > 366:
    jour = jour - 366
    annee = annee + 1
    else:
    jour = jour - 365
    annee = annee + 1
    print "Aujourd’hui nous sommes le", jour, "ieme jour de l’année", annee
    ******************************************************

    Cette algo converti un nombre de jour depuis le 1er janvier 2005 en le n-ieme jour d'une année.
    On dispose d'une fonction nbBissextile(x) qui calcule le nombre d'années bissextile en 2005 et x (exclu), cete fonction est censé aider pour l'invariant de boucle...
    Mon problème est de trouver l'invariant de boucle, en théorie ça avait l'air simple mais maintenant que je dois le faire, plus tant que ça^^.

    On nous demande aussi de corriger l'algo si nécessaire, il me semble avoir trouver un problème si jour=366 et que l'année est bissextile, ce que j'ai corrigé comme cela:
    while (jour>365 and (not EstAnneeBissextile(annee)) or (jour>366 and EstAnneeBissextile(annee))

    Merci d'avance!

  2. #2
    Candidat au Club
    Profil pro
    Inscrit en
    mars 2012
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2012
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    Bon j'ai peut être une réponse:
    soit x et y les valeurs initiales respectivement de jour et annee, on a
    x=(annee-y)*365+jour+nbBissextile(annee)
    Et je travaille à la preuve de correction...

    EDITreuve de correction
    Soit jour' et annee' les nouvelles valeurs en sortie de jour et annee,
    jour'= jour - 365 (-1 si annee est bissextile)
    annee'=annee+1

    En remplaçant les nouvelles valeurs dans l'invariant:
    x=(annee+1-y)*365 + jour - 365 (-1 si annee est bissextile) +nbbissextile(annee+1) = (annee-y)*365 + jour + nbbissextile(annee)

    car si annee est bissextile on a
    nbBissextile(annee) + 1 = nbBissextile(annee+1) et on retranche 1 au total si l'année est bissextile...
    Je suis un peu en terre inconnue donc si ça parait correcte ou incorrecte à quelqu'un...
    Merci

Discussions similaires

  1. Invariant de boucle entrée/sortie
    Par martin999999 dans le forum Caml
    Réponses: 9
    Dernier message: 24/09/2012, 00h07
  2. Invariant de boucle
    Par larchicha dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 17/11/2011, 12h02
  3. Calcul d'un invariant de boucle
    Par caroline-bx1 dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 21/10/2011, 14h03
  4. Preuve de correction d'une boucle par invariant : correction d'un exercice
    Par Titom78 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 05/08/2011, 16h08
  5. Réponses: 2
    Dernier message: 29/05/2002, 20h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo