3. Exercice algobox X et Y

Exercice algobox X et Y

  • nyjo72

    Bonjour voici mon exercice sur algobox :

    Vous devez créer un programme en utilisant le logiciel Algobox pour aider une entreprise de télécommunication à déterminer l'emplacement optimal pour positionner une antenne radio sur une surface plane (par exemple, un plan cartésien), de manière à maximiser la couverture des points représentant des villes.

    *Spécifications

    1. L'utilisateur doit pouvoir saisir les coordonnées (x, y) de plusieurs points représentant des villes.

    2. Le programme devra calculer la distance entre l'emplacement de l'antenne radio (un point spécifique) et chaque point (ville). Vous pouvez utiliser la formule de la distance euclidienne pour calculer les distances sur un plan cartésien.me

    3. Pour optimiser la couverture, l'antenne radio doit être positionnée de manière à minimiser la somme des distances entre l'antenne et chaque point (ville). En d'autres termes, vous devrez trouver l'emplacement qui minimise la somme des distances.

    4. Affichez l'emplacement optimal de l'antenne radio (un point).

    Contraintes ● Vous pouvez supposer que la surface plane est un plan cartésien en deux dimensions.

    J'ai fais ça mais je bloque :
    FONCTIONS_UTILISEES
    VARIABLES
    x EST_DU_TYPE LISTE
    y EST_DU_TYPE LISTE
    i EST_DU_TYPE NOMBRE
    j EST_DU_TYPE NOMBRE
    distance EST_DU_TYPE NOMBRE
    ville EST_DU_TYPE NOMBRE
    maximum_x EST_DU_TYPE NOMBRE
    maximum_y EST_DU_TYPE NOMBRE
    k EST_DU_TYPE NOMBRE
    xgrille EST_DU_TYPE NOMBRE
    ygrille EST_DU_TYPE NOMBRE
    DEBUT_ALGORITHME
    AFFICHER "Nombre de villes ? :"
    LIRE ville
    LIRE maximum_x
    LIRE maximum_y
    POUR i ALLANT_DE 0 A ville-1
    DEBUT_POUR
    AFFICHER "Entrée la valeur x de la ville "
    LIRE x[i]
    AFFICHER "Entrée la valeur Y de la ville"
    LIRE y[j]
    FIN_POUR
    POUR i ALLANT_DE 0 A ville-1
    DEBUT_POUR
    POUR j ALLANT_DE 0 A maximum_x-1
    DEBUT_POUR
    AFFICHER* i
    AFFICHER* j
    POUR k ALLANT_DE 0 A maximum_y-1
    DEBUT_POUR
    distance PREND_LA_VALEUR sqrt(pow(x[i] - x,2) + pow(y[j] - y,2))
    AFFICHER* distance
    FIN_POUR
    FIN_POUR
    FIN_POUR
    FIN_ALGORITHME

    pouvez vous m'aider ?
    merci

  • B

    Bonjour,

    Essaie ceci.
    Ne travaille qu'avec des coordonnées positives et entières (ce qui n'est pas limitatif).

    VARIABLES
  nbreadr EST_DU_TYPE NOMBRE
  i EST_DU_TYPE NOMBRE
  j EST_DU_TYPE NOMBRE
  k EST_DU_TYPE NOMBRE
  // Liste des abscisses des villes
  absc EST_DU_TYPE LISTE   
  // Liste des ordonnées des villes
  ordo EST_DU_TYPE LISTE 
  //abscisse max des villes entrées  
  abscmax EST_DU_TYPE NOMBRE 
  //ordonnee max des villes entrées   
  ordomax EST_DU_TYPE NOMBRE   
  //abscisse min des villes entrées 
  abscmin EST_DU_TYPE NOMBRE   
  //ordonnee min des villes entrées 
  ordomin EST_DU_TYPE NOMBRE   
  // distance entre antenne et les villes (somme) 
  distance EST_DU_TYPE NOMBRE  
  // distance min entre antenne et les villes (somme)  
  dismin EST_DU_TYPE NOMBRE  
  //abscisse de l'antenne    
  abscant EST_DU_TYPE NOMBRE
  //ordonnée de l'antenne      
  ordoant EST_DU_TYPE NOMBRE    
DEBUT_ALGORITHME
  AFFICHER "Entrez le nombre de villes :"
  LIRE nbreadr
  POUR i ALLANT_DE 1 A nbreadr
    DEBUT_POUR
    AFFICHER "Entrer abscisse (entier naturel) de la ville"
    AFFICHER i
    AFFICHER " : "
    LIRE absc[i]
    AFFICHER "Entrer ordonnee (entier naturel) de la ville"
    AFFICHER i
    AFFICHER " : "
    LIRE ordo[i]
    FIN_POUR
  abscmax PREND_LA_VALEUR absc[1]
  abscmin PREND_LA_VALEUR absc[1]
  ordomax PREND_LA_VALEUR ordo[1]
  ordomin PREND_LA_VALEUR ordo[1]
  POUR i ALLANT_DE 1 A nbreadr
    DEBUT_POUR
    SI (abscmax < absc[i]) ALORS
      DEBUT_SI
      abscmax PREND_LA_VALEUR absc[i]
      FIN_SI
    SI (abscmin > absc[i]) ALORS
      DEBUT_SI
      abscmin PREND_LA_VALEUR absc[i]
      FIN_SI
    SI (ordomax < ordo[i]) ALORS
      DEBUT_SI
      ordomax PREND_LA_VALEUR ordo[i]
      FIN_SI
    SI (ordomin > ordo[i]) ALORS
      DEBUT_SI
      ordomin PREND_LA_VALEUR ordo[i]
      FIN_SI
    FIN_POUR
  dismin PREND_LA_VALEUR nbreadr*sqrt((abscmax - abscmin)*(abscmax - abscmin) + (ordomax - ordomin)*(ordomax - ordomin))
  POUR i ALLANT_DE abscmin A abscmax
    DEBUT_POUR
    POUR j ALLANT_DE ordomin A ordomax
      DEBUT_POUR
      distance PREND_LA_VALEUR 0
      POUR k ALLANT_DE 1 A nbreadr
        DEBUT_POUR
        distance PREND_LA_VALEUR distance + sqrt((absc[k]-i)*(absc[k]-i) + (ordo[k]-j)*(ordo[k]-j))
        FIN_POUR
      SI (dismin > distance) ALORS
        DEBUT_SI
        dismin PREND_LA_VALEUR distance
        abscant PREND_LA_VALEUR i
        ordoant PREND_LA_VALEUR j        
        FIN_SI
      FIN_POUR
    FIN_POUR
  AFFICHER* "Résultats :"
  AFFICHER "distance minimum :"
  AFFICHER* dismin
  AFFICHER "abscisse antenne :"
  AFFICHER* abscant
  AFFICHER "ordonnee antenne :"
  AFFICHER* ordoant
FIN_ALGORITHME
  • nyjo72

    C'est presque ça mais par contre, si je fais 10-10 pour la 1ère ville et 1-1 pour la seconde , il devrait mettre 5.5
    or ce n'est pas le cas
    une idée ?

    B 1 réponse
  • B

    @nyjo72 a dit dans Exercice algobox X et Y :

    C'est presque ça mais par contre, si je fais 10-10 pour la 1ère ville et 1-1 pour la seconde , il devrait mettre 5.5
    or ce n'est pas le cas
    une idée ?

    Et bien non.
    Si le problème est de minimiser la somme des distances entre l'antenne et les villes.

    Si il n'y a que 2 villes (B et C), l'antenne A peut se trouver n'importe où sur le segment [BC], on aura la même valeur pour |AB| + |AC|
    Donc l'antenne peut être n'importe où sur le le segment [AB] ... le programme désigne donc un point pour l'antenne n'importe ou sur [BC]

  • nyjo72

    Je crois que je me suis mal exprimé , l'exercice qu'on nous à donner je dois afficher le point minimal optimal entre les deux villes ou plus selon ce que l'utilisateur met
    En tous cas merci

  • B

    Bonjour,

    Cela reste évident.

    On teste le nombre de villes entrés ...
    Si c'est 2, alors la position de l'antenne est au milieu:
    Abscisse de l'antenne = (abscisse ville 1 + abscisse ville 2)/2
    et
    Ordonnée de l'antenne = (ordonnée ville 1 + ordonnée ville 2)/2

    Si c'est plus que 2 ... on laisse tourner le programme écrit avant.

  • B

    Voila le programme avec la modification implémentée.

    VARIABLES
  nbreadr EST_DU_TYPE NOMBRE
  i EST_DU_TYPE NOMBRE
  j EST_DU_TYPE NOMBRE
  k EST_DU_TYPE NOMBRE
  // Liste des abscisses des villes
  absc EST_DU_TYPE LISTE   
  // Liste des ordonnées des villes
  ordo EST_DU_TYPE LISTE 
  //abscisse max des villes entrées  
  abscmax EST_DU_TYPE NOMBRE 
  //ordonnee max des villes entrées   
  ordomax EST_DU_TYPE NOMBRE   
  //abscisse min des villes entrées 
  abscmin EST_DU_TYPE NOMBRE   
  //ordonnee min des villes entrées 
  ordomin EST_DU_TYPE NOMBRE   
  // distance entre antenne et les villes (somme) 
  distance EST_DU_TYPE NOMBRE  
  // distance min entre antenne et les villes (somme)  
  dismin EST_DU_TYPE NOMBRE  
  //abscisse de l'antenne    
  abscant EST_DU_TYPE NOMBRE
  //ordonnée de l'antenne      
  ordoant EST_DU_TYPE NOMBRE    
DEBUT_ALGORITHME
  AFFICHER "Entrez le nombre de villes :"
  LIRE nbreadr
  POUR i ALLANT_DE 1 A nbreadr
    DEBUT_POUR
    AFFICHER "Entrer abscisse (entier naturel) de la ville"
    AFFICHER i
    AFFICHER " : "
    LIRE absc[i]
    AFFICHER "Entrer ordonnee (entier naturel) de la ville"
    AFFICHER i
    AFFICHER " : "
    LIRE ordo[i]
    FIN_POUR
  abscmax PREND_LA_VALEUR absc[1]
  abscmin PREND_LA_VALEUR absc[1]
  ordomax PREND_LA_VALEUR ordo[1]
  ordomin PREND_LA_VALEUR ordo[1]

  SI (nbreadr == 2) ALORS
  	DEBUT_SI
  	  abscant PREND_LA_VALEUR (absc[1]+absc[2])/2
      ordoant PREND_LA_VALEUR (ordo[1]+ordo[2])/2
      dismin PREND_LA_VALEUR sqrt((absc[1] - absc[2])*(absc[1] - absc[2]) + (ordo[1] - ordo[2])*(ordo[1] - ordo[2]))
    FIN_SI    
  SINON
      	DEBUT_SINON
    POUR i ALLANT_DE 1 A nbreadr
    DEBUT_POUR
    SI (abscmax < absc[i]) ALORS
      DEBUT_SI
      abscmax PREND_LA_VALEUR absc[i]
      FIN_SI
    SI (abscmin > absc[i]) ALORS
      DEBUT_SI
      abscmin PREND_LA_VALEUR absc[i]
      FIN_SI
    SI (ordomax < ordo[i]) ALORS
      DEBUT_SI
      ordomax PREND_LA_VALEUR ordo[i]
      FIN_SI
    SI (ordomin > ordo[i]) ALORS
      DEBUT_SI
      ordomin PREND_LA_VALEUR ordo[i]
      FIN_SI
    FIN_POUR
  dismin PREND_LA_VALEUR nbreadr*sqrt((abscmax - abscmin)*(abscmax - abscmin) + (ordomax - ordomin)*(ordomax - ordomin))
  POUR i ALLANT_DE abscmin A abscmax
    DEBUT_POUR
    POUR j ALLANT_DE ordomin A ordomax
      DEBUT_POUR
      distance PREND_LA_VALEUR 0
      POUR k ALLANT_DE 1 A nbreadr
        DEBUT_POUR
        distance PREND_LA_VALEUR distance + sqrt((absc[k]-i)*(absc[k]-i) + (ordo[k]-j)*(ordo[k]-j))
        FIN_POUR
      SI (dismin > distance) ALORS
        DEBUT_SI
        dismin PREND_LA_VALEUR distance
        abscant PREND_LA_VALEUR i
        ordoant PREND_LA_VALEUR j        
        FIN_SI
      FIN_POUR
    FIN_POUR
  FIN_SINON
  AFFICHER* "Résultats :"
  AFFICHER "distance minimum :"
  AFFICHER* dismin
  AFFICHER "abscisse antenne :"
  AFFICHER* abscant
  AFFICHER "ordonnee antenne :"
  AFFICHER* ordoant
FIN_ALGORITHME
Se connecter pour répondre