1. Ce site utilise des "témoins de connexion" (cookies) conformes aux textes de l'Union Européenne. Continuer à naviguer sur nos pages vaut acceptation de notre règlement en la matière. En savoir plus.

Défis de programmation

Discussion dans 'Programmation' démarrée par Spiikesan, 18 Juin 2017.

  1. Spiikesan
    Offline

    Spiikesan Développeur Membre de l'équipe Développeur backend

    Inscrit depuis le :
    6 Mars 2017
    Messages :
    37
    "J'aime" reçus :
    10
    Points de Trophée :
    8
    Sexe :
    Masculin
    Travail/Loisirs :
    Informatique, développement
    Lieu de résidence :
    Bordeaux
    Bonjour !

    Sur le modèle de Clyese, je vais faire ici non pas des exercices mais des défis de programmation !
    Je m'excuse d'avance si vous n'aimez pas le C, mais étant mon langage de prédilection, je ne proposerais sûrement que des défis en C.
    Vous pouvez en proposer du langage que vous désirez cependant (sauf brainfuck... quoique ;)) en suivant ce modèle :

    Basé sur le modèle d'exercices de Clyese
    Nom : Nom du défi

    Langage : Langage de programmation (C/C++/C#/python/PHP/etc...)
    Difficulté : [1-10] (A vous de définir)
    Temps estimé/imparti : Une difficulté en plus ! Et oui, c'est un défie ;) (optionnel)

    Instructions :

    // Les instructions...

    Correction : (spoiler) (optionnel => Vous pouvez proposer des défis que vous ne savez pas forcément faire vous même. Mais il faut tout de même proposer des choses possibles qui ne nécessite pas d'équipe par exemple)

    Je vais commencer avec un défi pas trop compliqué pour ne pas vous dégoûter dès le début !

    Nom : Multiplication entière à précision "infinie"

    Langage : C
    Difficulté : [3]
    (Un simple algorithme, c'est vraiment pas très long, mais intéressant de tenter de gérer les nombres "infinis"...)
    Temps estimé : 1 à 2 heures

    Instructions :


    Vous devrez créer un programme qui prend en paramètre deux nombres sous forme de chaînes de caractères.
    Vous afficherez sur la sortie standard le résultat de la multiplication de ces deux nombres.

    Les nombres sont entiers et positifs. Les seuls caractères acceptés sont les chiffres de 0 à 9.
    Les nombres peuvent être composés d'un nombre "infini" de caractères. La limite étant votre mémoire vive...

    Le programme doit être capable d'effectuer la multiplication de deux nombres de 5000 caractères en moins d'une seconde.
    Si vous êtes sur linux, ce script vous aidera à tester votre programme :

    Code:
    echo "usage : ${0} <file_num_1> <file_num_2> <file_num_result>"
    echo "if result is 1, your num is correct"
    echo `cat ${1}` "*" `cat ${2}` "==" `cat ${3}` | bc
    Il prend trois fichiers en entrée (le 1 et le 2 peuvent être le même, le 3 est le résultat que vous voulez vérifier)

    Correction :
    Voilà ce que je vous propose :
    Code:
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    /* Multiplie deux nombres représentés par des chaines de caractères */
    char        *multiplication(const char *a, const char *b)
    {
      char        *result; /* Contiendra le résultat */
      ssize_t    lenght_x; /* Longueur de la chaine a */
      ssize_t    lenght_y; /* Longueur de la chaine b */
      ssize_t    x; /* Curseur de la chaine a */
      ssize_t    y; /* Curseur de la chaine b */
      ssize_t    tmp; /* Valeur tampon */
      ssize_t    c /* Curseur de la chaine result*/;
    
      if (!a || !b)
        return NULL;
      lenght_x = strlen(a);
      lenght_y = strlen(b);
      result = calloc(lenght_x + lenght_y + 1, sizeof(char)); /* On crée la chaine résultat. La taille sera au plus de la longueur de lenght_x + lenght_y donc on y ajoute 1 pour le \0 (fin de chaine) */
      for (tmp = 0, c = (lenght_x + lenght_y - 2); c >= 0 ; --c) { /* On initialise tmp et c, et on boucle en décrémentant c jusqu'a ce qu'il atteigne -1 (car >= 0) */
        for (y = (c > (lenght_y - 1) ? (lenght_y - 1) : c), x = (c > (lenght_y - 1) ? c - (lenght_y - 1): 0); y >= 0 && x < (lenght_x); ++x, --y) /* On initialise y et x en faisant attention de ne pas sortir de la chaine */
          tmp += (a[x] - '0') * (b[y] - '0'); /* Ici c'est la multiplication à proprement parler */
        result[c] = (tmp % 10) + '0'; /* Ici on récupère le résultat, qui est la tranche inférieur à 10 */
        tmp /= 10; /* Le résultat étant récupéré, on ne garde que la tranche supérieure à 10 */
      }
      /*
      * Si la variable temporaire contiens une valeur, ça veux dire que la multiplication prend la taille maximale de la chaine.
      * On décale donc toute la chaine d'un cran vers la droite et on insert le dernier résultat.
      * Cela est fait pour ne pas avoir de '0' devant le nombre.
      */
      if (tmp != 0) {
        memmove(result + 1, result, strlen(result));
        result[0] = tmp + '0';
      }
      return (result);
    }
    
    int main(int ac, char **av)
    {
      char    *result;
    
      if (ac != 3)
        return (1);
      result = multiplication(av[1], av[2]);
      printf("%s\n", result);
      free(result);
      return (0);
    }
    
    Voici le résultat du test :

    Le nombre fait 11200 caractères. Le résultat en fait 22400.

    $ time ./libtcc.exe `cat big_11200` `cat big_11200` > res
    real 0m0.450s
    user 0m0.000s
    sys 0m0.030s

    $ ./script_test_bc big_11200 big_11200 res
    1

    On est loin des 1 secondes autorisés pour 5000 caractères ! ;)

    Je proposerai d'autres défis par la suite, bien plus compliqué, histoire de se remuer les méninges !

    Bon courage
     
    • Like Like x 1
  2. Servius Tullius
    Offline

    Servius Tullius Administrateur Membre de l'équipe Administrateur Graphiste

    Inscrit depuis le :
    18 Octobre 2015
    Messages :
    546
    "J'aime" reçus :
    97
    Points de Trophée :
    43
    Sexe :
    Masculin
    Lieu de résidence :
    France
    Page d'accueil :
    Salut,
    Cet exercice n'est pas mal du tout ! Quand j'aurai du temps, j'essayerai de le faire ;)
     

Partager cette page

Utilisateurs qui regardent actuellement cette discussion : 0 membre(s) et 0 visiteur(s)