Forums des Zéros

18 janvier 2010 à 13:32:50

Citation : HightTam

Aurez vous des idées peut-être ?

Il y a plusieurs pistes

Prendre garde à ne pas calculer plusieurs fois la mème chose(9 99 999 999999)
Voir que 1002 12 102 120 21 2001 2010 210 2100 ont la même somme.

Avec une première amélioration, j'ai

version de base :
N = 1000000000, S = 27 -> 14033305 trouves en 97.40 s
version avec une (petite) amelioration :
N = 1000000000, S = 27 -> 14033305 trouves en 49.40 s

Process returned 0 (0x0)   execution time : 146.828 s
Press any key to continue.

En éspèrant que ce soit juste.

Il y a moyen de faire bien mieux!

Zeste de Savoir, le site qui en a dans le citron !

18 janvier 2010 à 17:54:30

Pour ma part j'ai :

92538 -> 27
1459784612340012340123478942651012315647894561230123456789 -> 228
entre 0 et 1000000000 , il y a 14033305 nombre dont la somme est 27

Process returned 0 (0x0)   execution time : 61.904 s
Press any key to continue.

Voici mon code:

#include <stdio.h>

int zSommeChiffres(int n)
{
int y=0;

    while(n!=0){

    y+=n%10;

    n/=10;

    }

  return y;
}

int zSommeChiffresChar(char *chaine)
{
int y=0,i=0,z=0;

   do{

        y++;

    }while(chaine[y]!= '\0');


while(i< y){

z+=chaine[i]-'0';

i++;

}

return z;

}

int zSommeChiffresEgale(int n,int n1)
{
  int i;
  int y=0;
  for (i=0;i<=n;i++)
    {
      if (zSommeChiffres(i)==n1)
        {
          y++;
        }
    }
  return y;
}

Pour la fonction int zSommeChiffresChar(char *chaine); J'ai presque réussie a la faire, seulement au lieu de z+=chaine[i]-'0'; (ligne 31)J'avais mit z+=chaine[i]; j'ai finalement décidé de regarder la solution mais je comprend pas pourquoi ça marche seulement si on ajoute -'0'?

darkipod

18 janvier 2010 à 20:13:17

bonjour,
voici ma contribution de débutant

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int zSommeChiffres(int n)
{
    int somme=0;
    int i;
    do
    {
        i= n % 10;   // pour isoler les unités
        n= (n-i) /10; // pour avoir le chiffre des dizaines et qu'il devienne le nouveau chiffre des unites
        somme = somme+i;//pour aditionner la somme des chiffres
    }
    while (i!=0); // on arrete quand on a plus d'unites
    return somme;//retour du resultat
}

int zSommeChiffresChar(char *src)
{
    int somme =0;
    int i;
    for (i=0;i<strlen(src);i++)
    {
        somme = somme + src[i]-'0';// nombre = code ascii - code ascii de 0
    }

    return somme;
}

int main(void)
{
    int n1 = 92538;
    char *n2 ="92538";
    printf("%d -> %d\n", n1 , zSommeChiffres(n1));
    printf("%s -> %d\n", n2 , zSommeChiffresChar(n2));


    return 0;
}

et une version sans utiliser string.h :

#include <stdio.h>
#include <stdlib.h>
/*#include <string.h> j'en ai plus besoin*/

int zSommeChiffres(int n)
{
    int somme=0;
    int i;
    do
    {
        i= n % 10;   // pour isoler les unités
        n= (n-i) /10; // pour avoir le chiffre des dizaines et qu'il devienne le nouveau chiffre des unites
        somme = somme+i;//pour aditionner la somme des chiffres
    }
    while (i!=0); // on arrete quand on a plus d'unites
    return somme;//retour du resultat
}

int zSommeChiffresChar(char *src)
{
    int somme =0;
    for ( ; *src ; src++)
    {
       somme = somme + *src -'0';// nombre = code ascii - code ascii de 0
    }

    return somme;
}



int main(void)
{
    int n1 = 92538;
    char *n2 ="92538";
    printf("%d -> %d\n", n1 , zSommeChiffres(n1));
    printf("%s -> %d\n", n2 , zSommeChiffresChar(n2));

    return 0;
}

18 janvier 2010 à 20:22:25

sympa les commantaires

et le résultat?

Bad_Wolf

18 janvier 2010 à 20:56:01

Salut à tous.

Citation : GurneyH

Il y a moyen de faire bien mieux!

Effectivement, à condition d'aimer un peu les maths

.

Voici les résultats que j'obtiens :

$ time ./simple
N = 1000000000, S = 27 -> 14033305

real        1m46.448s
user        1m45.175s
sys        0m0.292s

$ time ./better
N = 1000000000, S = 27 -> 14033305

real        0m0.442s
user        0m0.375s
sys        0m0.003s

Voici les sources. Je donne l'implémentation naïve (on teste tous les entiers entre 1 et n) à titre de comparaison avec l'implémentation rapide.

Implémentation naïve :

naive.h:

#ifndef __H__NAIVE
#define __H__NAIVE

int zSommeChiffres(int n);

/* Calcule le nombre d'entiers entre 0 et range dont la somme des chiffres
 * vaut sum.
 */
int count_with_given_sum (int range, int sum);

#endif

naive.c:

#include "naive.h"


int zSommeChiffres(int n)
{
    int result = 0;

    while (n != 0) {
        result += n%10;
        n /= 10;
    }
    
    return result;
}

int count_with_given_sum (int range, int sum)
{
    int i;
    int result = 0;

    for (i = 0; i < range; i++) {
        if (zSommeChiffres(i) == sum) {
            result++;
        }
    }

    return result;
}

Implémentation rapide :

partitions.h:

#ifndef __H__PARTITIONS
#define __H__PARTITIONS

/* Calcule le nombre d'entiers entre 0 et range dont la somme des chiffres
 * vaut sum. (Version rapide.)
 */
int count_with_given_sum_better (const char *range, int sum);

#endif

partitions.c:

#include <string.h>

#include "partitions.h"

int count_with_given_sum_better (const char *range, int sum)
{
    return p(sum, range);
}

/* Calcule le nombre de partitions de s en k termes (a_1, ..., a_k), où k est
 * le nombre de chiffres de n, où les entier a_i sont compris entre 0 et 9,
 * et où l'entier a_k...a_1 (i.e. celui dont les chifres sont les a_i) est <= n.
 */     
int p(int s, const char *n)
{
    int leading_digit = *n - '0';
    int i;
    int sum = 0;
    int k = strlen(n);

    if (*n == '\0') {
        return 0;
    }

    for (i = 0; i < leading_digit; i++) {
        sum += q(s - i, k - 1);
    };

    return sum + p(s - leading_digit, n + 1);
}

/* Calcule le nombre de partitions de s en k termes (a_1, ..., a_k), où les
 * a_i sont compris entre 0 et 9. */
int q(int s, int k)
{
    int sum = 0;
    int i;

    if (s < 0) {
        return 0;
    }

    if (s == 0) {
       return 1;
    }

    if (k == 1) {
        if (s <= 9) {
            return 1;
        } else {
            return 0;
        }
    }

    for (i = 0; i <= 9; i++) {
        sum += q(s - i, k - 1);
    }

    return sum;
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "naive.h"
#include "partitions.h"

int main (void)
{
    int s = 27;
    int n = 1000000000;
    char *n_str = malloc(20 * sizeof(char));
    strcpy(n_str, "1000000000");

    /* La méthode naive */
    printf("N = %d, S = %d -> %d\n", n, s, count_with_given_sum(n, s));

    /* La méthode rapide */
    printf("N = %s, S = %d -> %d\n", 
            n_str, s, count_with_given_sum_better(n_str, s));

    free(n_str);

    return 0;
}

Les commentaires indiquent ce que sont <math>\(p(s,n)\)</math> et <math>\(q(s,k)\)</math>.
Si on aborde le problème sous un angle mathématique (à savoir compter des partitions d'un entier), l'aspect algorithmique est mort : l'implémentation est simplement la traduction en C des formules suivantes :

Si <math>\(b_1,...,b_k\)</math> sont les chiffres de <math>\(n\)</math>, alors
<math>\(p(s,n) = \sum_{j=0}^{b_k-1}q(s-j,k-1) + p(s-b_k, n-10^kb_k)\)</math>
et
<math>\(q(s,k) = \sum_{j=0}^9 q(s-j, k-1).\)</math>

Si le pourquoi du comment on obtient ces formules intéresse quelqu'un, je pourrai rajouter une explication.

Edit: En fait, je dis que l'aspect algorithmique est mort, mais c'est faux. Le calcul de <math>\(q(s,k)\)</math> a l'air exponentiel en <math>\(k\)</math> (à vue de pif). J'ai l'impression qu'on calcule cinquante fois les mêmes valeurs, et qu'on devrait donc pouvoir faire mieux en stockant les valeurs déjà calculée dans un tableau. M'enfin si y'a quelqu'un plus à l'aise que moi sur les question de complexité qui peut vérifier ce que je dis, je suis preneur, ça me paraît bizarre qu'un truc exponentiel en <math>\(j\)</math> (donc linéaire en <math>\(n\)</math>) tourne si vite...

Pouet_forever

18 janvier 2010 à 21:24:30

J'ai bien une solution mais j'arrive pas à la mettre en place :'(

Ca fait 2 jours que je suis dessus et ça n'aboutit pas

Le but est en fait de calculer tous les nombres sans doublons. Donc on part de 0 jusqu'à 9 (arbitraire mais dans l'algo c'est plus simple à mettre en oeuvre

) et on incrémentes à chaque fois. Pour chaque nombre on calcule le nombre de combinaisons. Mais il faut enlever le nombre de permutations qui n'en sont pas vraiment (111 = 1 et pas 3!).

Au final ça donne un truc comme ça :

00 01 02 03 04 05 06 07 08 09 11 12 13 ... 19 22 23 ... 29 33 34 ... 35 36 .. 39 44 ... ... 89 99

En faisant comme ça on est sûr de ne calculer aucun doublon, mais il faut arriver à gérer les 'exceptions' (111, 222, etc.), ce que je n'arrive pas à faire :'(

Bad_Wolf

18 janvier 2010 à 21:34:43

Pouet_forever : c'est exactement ce que j'ai essayé de faire au début, mais c'est un cauchemard !

Incrémenter de façon à pas avoir de doublons, ça va, mais j'ai pas réussi à calculer le nombre de combinaisons convenables sans tester toutes les permutations possibles des chiffres, ce qui diminue un peu beaucoup l'intérêt d'éviter les doublons :-°

.

J'ai l'impression que la formule qui donne le nombre de combinaisons est plus difficile à obtenir que celle qui donne directement la solution... C'est un peu con !

Pouet_forever

18 janvier 2010 à 21:40:09

Citation : Bad_Wolf

c'est un cauchemard !

Moi ce que j'ai fait c'est un tableau de 10 cases, qui correspondent au nombre de doublons qu'il y a. Ensuite on calcule la factorielle de chaque case et on la soustrait au résultat final, sauf si c'est un nombre 'unique' genre 11111 33333. Mais bon, je sais pas si je suis sur la voie et à vrai dire, ça commence à m'énerver :lol:

Je vais essayer de mettre en pratique ta formule

18 janvier 2010 à 22:53:04

z+=chaine[i]-'0'; si quelqu'un a le temps j'aimerai bien avoir quelque explication je répète si sa dérange pas

Pouet_forever

18 janvier 2010 à 23:32:34

Je mets en secret :

En fait on calcule selon le caractère ASCII. Une chaîne de caractère c'est '0' '1' etc. Ces lettres ont des valeurs. Par exemple '0' à la valeur 48, '1' = 49 etc. Donc pour avoir le 0 1 2 etc. il suffit de retrancher à la valeur ASCII la valeur de '0'. On aurait pu mettre aussi bien - 48 mais c'est moins compréhensible

18 janvier 2010 à 23:32:38

Citation : Bad_Wolf

Implémentation rapide :

partitions.h:

#ifndef __H__PARTITIONS
#define __H__PARTITIONS

/* Calcule le nombre d'entiers entre 0 et range dont la somme des chiffres
 * vaut sum. (Version rapide.)
 */
int count_with_given_sum_better (const char *range, int sum);

#endif

partitions.c:

#include <string.h>

#include "partitions.h"

int count_with_given_sum_better (const char *range, int sum)
{
    return p(sum, range);
}

/* Calcule le nombre de partitions de s en k termes (a_1, ..., a_k), où k est
 * le nombre de chiffres de n, où les entier a_i sont compris entre 0 et 9,
 * et où l'entier a_k...a_1 (i.e. celui dont les chifres sont les a_i) est <= n.
 */     
int p(int s, const char *n)
{
    int leading_digit = *n - '0';
    int i;
    int sum = 0;
    int k = strlen(n);

    if (*n == '\0') {
        return 0;
    }

    for (i = 0; i < leading_digit; i++) {
        sum += q(s - i, k - 1);
    };

    return sum + p(s - leading_digit, n + 1);
}

/* Calcule le nombre de partitions de s en k termes (a_1, ..., a_k), où les
 * a_i sont compris entre 0 et 9. */
int q(int s, int k)
{
    int sum = 0;
    int i;

    if (s < 0) {
        return 0;
    }

    if (s == 0) {
       return 1;
    }

    if (k == 1) {
        if (s <= 9) {
            return 1;
        } else {
            return 0;
        }
    }

    for (i = 0; i <= 9; i++) {
        sum += q(s - i, k - 1);
    }

    return sum;
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "naive.h"
#include "partitions.h"

int main (void)
{
    int s = 27;
    int n = 1000000000;
    char *n_str = malloc(20 * sizeof(char));
    strcpy(n_str, "1000000000");

    /* La méthode naive */
    printf("N = %d, S = %d -> %d\n", n, s, count_with_given_sum(n, s));

    /* La méthode rapide */
    printf("N = %s, S = %d -> %d\n", 
            n_str, s, count_with_given_sum_better(n_str, s));

    free(n_str);

    return 0;
}

Ton algorithme est compliqué, ton code est peu accessible aux débutants (cf. le titre du fil) et pas si rapide.

Sur mon PC :

candide@candide-desktop:~$ c99opt sommeChiffres_candide.c 
candide@candide-desktop:~$ time ./x
410820025

real        0m0.004s
user        0m0.000s
sys        0m0.000s
candide@candide-desktop:~$ c99opt badWolf.c
candide@candide-desktop:~$ time ./x
N = 10000000000, S = 42 -> 410820025

real        0m16.463s
user        0m16.157s
sys        0m0.100s
candide@candide-desktop:~$

19 janvier 2010 à 4:35:44

Citation : candide

Ton algorithme est compliqué, ton code est peu accessible aux débutants (cf. le titre du fil) et pas si rapide.

Hum, ça n'empêche qu'il faut que tout le monde puisse trouver un intérêt...

Citation : Bad_Wolf

Si le pourquoi du comment on obtient ces formules intéresse quelqu'un, je pourrai rajouter une explication.

C'est toujours intéressant, ne te prives pas! :). Ou un lien, si tu as, à la limite.

@zoom751: ça semble bon.
J'ai eu du mal, à comprendre ton raisonnement pour la fonction zSommeChiffresChar! Tu commence par chercher le nombre de caractères avec une variable y, (qui te sers de somme dans tes autres fonctions)... Toute cette étape est inutile!
A mon avis, tu devrais essayer de refaire cette fonction.

Une remarque, ton code est mal indenté, et les noms de variable (i, y, z...), n'aident pas à la lecture du code. C'est une bonne habitude que de nommer ses variables.

Ton code indenté, et avec des noms de variables plus explicites.

/* zoom751 */
#include <stdio.h>

int zSommeChiffres(int n)
{
    int somme = 0;

    while (n != 0)
    {
        somme += n % 10;
        n /= 10;
    }
    return somme;
}

int zSommeChiffresChar(char *chaine)
{
    /* Longueur de la chaîne */
    int lenChaine = 0;
    int somme = 0;
    /* Indice du caractère courant */
    int i = 0;

    do
    {
        lenChaine++;
    }
    while (chaine[lenChaine] != '\0');

    while (i < lenChaine)
    {
        somme += chaine[i] - '0';
        i++;
    }

    return somme;

}

int zSommeChiffresEgale(int n, int s)
{
    int somme = 0;
    int i;
    for (i = 0; i <= n; i++)
    {
        if (zSommeChiffres(i) == s)
        {
            somme++;
        }
    }
    return somme;
}

int main(void)
{
    printf("%d\n", zSommeChiffres(92538));
    printf("%d\n", zSommeChiffresChar("1459784612340012340123478942651"
                                        "012315647894561230123456789"));

    printf("%d", zSommeChiffresEgale(1000000000, 27));

    return 0;
}

Zeste de Savoir, le site qui en a dans le citron !

darkipod

19 janvier 2010 à 5:43:06

Voici pour ma part ma solution naive terminée :

#include <stdio.h>


int zSommeChiffres(int n)
{
    int somme=0;
    int i;
    do
    {
        i= n % 10;   // pour isoler les unités
        n= n /10; // pour avoir le chiffre des dizaines et qu'il devienne le nouveau chiffre des unites
        somme = somme+i;//pour aditionner la somme des chiffres
    }
    while (i!=0); // on arrete quand on a plus d'unites
    return somme;//retour du resultat
}

int zSommeChiffresChar(char *src)
{
    int somme =0;
    for ( ; *src ; src++)//j'utilise le pointeur de chaine
    {
        somme = somme + *src -'0';// nombre = code ascii - code ascii de 0
    }

    return somme;
}

int zPareil(long n, int valeur)
{
    long i;
    int resultat = 0;
    for (i = 0; i <= n; i++)
    {
        if (zSommeChiffres(i)== valeur)
        {
            resultat++;
        }
    }
    return resultat;
}


    int main(void)
    {
        int n1 = 92538;
        char *n2 ="92538";
        long n3 = 100000000;
        int n4 =27;
        printf("%d -> %d\n", n1 , zSommeChiffres(n1));
        printf("%s -> %d\n", n2 , zSommeChiffresChar(n2));
        printf ("trouve %d dans les %ld nombres : %d fois\n",n4,n3,zPareil(n3,n4));

        return 0;
    }

et le resultat :

92538 -> 27
92538 -> 27
trouve 27 dans les 100000000 nombres : 1542546 fois

Process returned 0 (0x0)   execution time : 10.828 s
Press any key to continue.

juste par curiosite ,les formules Bad_Wolf, tu les as trouvés ou?

19 janvier 2010 à 6:37:51

@darkipod:
Lorsque tu fais

i= n % 10;
n= (n-i) /10;

Exemple, n = 96
i = 96 % 10 = 6
n = (96 - 6) / 10 = 9
Ca marche...
Maintenant si tu te contente de

i = n % 10;
n /= 10; /* n = n / 10*/

Toujours avec n = 96
i = 96 % 10 = 6 (ça ne change pas :-°

)
n = 96 / 10 = ?... 9 également
On travaille sur des entiers, il ne faut pas oublier.
Dans tous les cas, pour tout n
n % 10 -> chiffre droit du nombre(reste) divisé par 10
n / 10 -> partie gauche du nombre(quotient) divisé par 10.

Zeste de Savoir, le site qui en a dans le citron !

19 janvier 2010 à 8:10:22

Citation : GurneyH

Citation : candide

Ton algorithme est compliqué, ton code est peu accessible aux débutants (cf. le titre du fil) et pas si rapide.

Hum, ça n'empêche qu'il faut que tout le monde puisse trouver un intérêt...

La contribution de Bad_Wolf n'est pas sans intérêt mais je trouve son code inutilement compliqué (plusieurs fichiers, utilisation de const) et alourdit la tache du débutant.

Voici mon code (simple programmation dynamique) qui est plus simple et beaucoup plus efficace :

#include <stdio.h>

#define NB_MAX_CHIFFRES 20
#define VAL_MAX_CHIFFRES NB_MAX_CHIFFRES*9
#define INT long long int

INT s(int nb_ch, int somme)
{
  INT t[NB_MAX_CHIFFRES + 1][VAL_MAX_CHIFFRES + 1] = { {0} };
  int v, k, i, j;

  for (v = 0; v < 10; v++)
    t[1][v] = 1;
  for (k = 2; k <= nb_ch; k++)
    for (v = 0; v <= somme; v++)
      {
        j = v;
        for (i = 0; j >= 0 && i < 10; i++, j--)
          t[k][v] += t[k - 1][j];
      }
  return t[nb_ch][somme];
}

int main(void)
{
  int nb_ch = 18;
  int somme = 42;

  printf("%lld\n", s(nb_ch, somme));
  return 0;
}

Bad_Wolf

19 janvier 2010 à 11:30:46

Citation : candide

ton code est peu accessible aux débutants (cf. le titre du fil)

C'est vrai. Sans parler de l'algorithme (qui n'est pas très compliqué, c'est la formule qui se cache derrière qui l'est), je n'ai pas pensé au problème que peut poser la présence de plusieurs fichiers, du const, etc.

Citation : candide

et pas si rapide.

Également vrai. J'aurais du le tester pour de plus grandes valeurs de s, le programme se comporte mal lorsque ce nombre augmente. Comme je le signale dans mon edit, il doit y avoir moyen d'utiliser les deux formules plus intelligemment.

Par contre, j'étais impressioné par la rapidité de ton programme jusqu'à ce que tu donnes le code...

Le tiens ne fonctionne que lorsque N est une puissance de 10, ce qui simplifie beaucoup le problème. Tu trivialises le problème que pouet_forever et moi avons rencontré, à savoir qu'une permutation des chiffres d'un entier <= N ne donne pas forcément un entier <= N... sauf justement lorsque N est une puissance de 10 !
Mon code a l'avantage de traiter le cas d'un entier N arbitraire. Attention, je ne dis pas que j'aurais été capable de faire un programme aussi rapide, mais quand même.

Citation : darkipod

juste par curiosite ,les formules Bad_Wolf, tu les as trouvés ou?

Sur une feuille de papier, avec un crayon

.
Je mettrai une explication quand j'aurai un peu de temps pour en écrire une.

19 janvier 2010 à 11:49:24

Citation : Bad_Wolf

Le tiens ne fonctionne que lorsque N est une puissance de 10, ce qui simplifie beaucoup le problème.

Le problème ? quel problème a été formulé précisément jusqu'à présent ? Rien de précis.

Trouver le nombre d'entiers positifs inférieurs à une valeur donnée et dont la somme des chiffres de l'écriture décimale prend une valeur donnée, c'est ça le problème ?

darkipod

19 janvier 2010 à 14:15:07

Citation : GurneyH

Toujours avec n = 96
i = 96 % 10 = 6 (ça ne change pas )
n = 96 / 10 = ?... 9 également
On travaille sur des entiers, il ne faut pas oublier.
Dans tous les cas, pour tout n
n % 10 -> chiffre droit du nombre(reste) divisé par 10
n / 10 -> partie gauche du nombre(quotient) divisé par 10

oui, c'est vrai entièrement d'accord avec toi, j'economise comme cela une operation donc du temps

19 janvier 2010 à 17:19:17

Citation : candide

Trouver le nombre d'entiers positifs inférieurs à une valeur donnée et dont la somme des chiffres de l'écriture décimale prend une valeur donnée, c'est ça le problème ?

Beuh, oui c'est ça le problème qui était posé.

Après faire un programme qui doit résoudre ce problème dans différentes bases, c'est une généralisation...

Bad_Wolf et candide, je ne regarde pas vos versions pour le moment.

@darkipod: Le temps est un souci mineur en fait.
C'est surtout que la deuxième forme

r = n % 10
n /= 10

est plus habituelle.

Zeste de Savoir, le site qui en a dans le citron !

19 janvier 2010 à 17:44:51

Citation : GurneyH

Citation : candide

Trouver le nombre d'entiers positifs inférieurs à une valeur donnée et dont la somme des chiffres de l'écriture décimale prend une valeur donnée, c'est ça le problème ?

Beuh, oui c'est ça le problème qui était posé.

Oui, exact :

Citation : GurneyH

Combien de nombres entre 0 et N ont la somme de leurs chiffres égale à S.

mes excuses donc.

19 janvier 2010 à 19:48:59

Merci GurneyH et Pouet_forever
Pour les précisions
En tout cas cette exercice est peux-être simple mais il m'a quand même servit