Partage
  • Partager sur Facebook
  • Partager sur Twitter

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

19 janvier 2010 à 22:00:32

?? J'essaye de comprendre la demarche de candide et bad_Wolf!
Sans toutefois piger ou vous voulez en venir!
C' est quoi la question que vous vous posez?
  • Partager sur Facebook
  • Partager sur Twitter
19 janvier 2010 à 22:14:29

Citation : candide

[Les permutations n'ont rien à faire ici].


Ca dépend de comment tu abordes le problème. Si tu parts comme Bad_Wolf et moi elles ont leur place ;)
  • Partager sur Facebook
  • Partager sur Twitter
19 janvier 2010 à 23:28:13

Citation : darkipod


C' est quoi la question que vous vous posez?



Je l'ai rappelé ICI :


Citation : candide

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é. :p




Oui, exact :

Citation : GurneyH


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




Citation : Pouet_forever

Citation : candide

[Les permutations n'ont rien à faire ici].


Ca dépend de comment tu abordes le problème. Si tu parts comme Bad_Wolf et moi elles ont leur place ;)



Je répondais à bad_Wolf qui disait aimablement que j'avais "trivialisé" votre question de permutation alors que pour moi, cette question ne se pose pas.


Citation : Bad_Wolf


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. !



Trivialisons encore : comme annoncé dans mon précédent message, le code que j'ai donné s'adapte sans difficulté au cas où N N'est PAS une puissance de 10 et comme annoncé, le temps est pour ainsi dire inchangé :


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

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

INT t[NB_MAX_CHIFFRES + 1][VAL_MAX_CHIFFRES + 1] = { {0}};

void tab(int nb_ch, int somme)
{
  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];
      }
}

INT s(char *p, int somme)
{
  int n = strlen(p)-1;
  INT total = 0;

  while (n >= 1 && *p != 0 && somme > 0)
    {
      int i;
      int k = *p - '0';

      for (i = 0; i < k && somme > 0; i++)
        {
          total += t[n][somme];
          somme--;
        }
      n--, p++;
    }
  if (n == 0 && somme <= *p - '0'||somme == 0)
    total++;
  return total;
}

int main(void)
{
  int somme = 27;
  char *p = "123456789012";

  tab(strlen(p) - 1, somme);


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


Petite comparaison. Ton code :

~$ gcc -O2 -W -Wall -std=c89 -pedantic -std=iso9899:199409 -o x main.c partitions.c 
$ time ./x
N = 123456789012, S = 27 -> 367859666

real        0m19.735s
user        0m18.897s
sys        0m0.180s


et le mien (pour les mêmes données) :

$ gcc -O2 -W -Wall -o x sommeChiffres_candide.c
$ time ./x
367859666

real        0m0.004s
user        0m0.000s
sys        0m0.004s










  • Partager sur Facebook
  • Partager sur Twitter
20 janvier 2010 à 4:09:10

J'édite le sujet.

Le problème à la base consistait à trouver comme le précise candide, à
trouver la somme des chiffres d'un nombre dans sa représentation décimale..

J'aurais dû préciser.
Ca n'empêche pas ceux qui le souhaitent d'étendre le principe aux autres bases(ce n'est pas plus compliqué...).
  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
23 janvier 2010 à 14:57:59

Bon bah après m'être creusé la tête pendant un moment je soumet ma solution, en fonction de ce que j'avais dis plus haut.

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

int factorielle(int n) {
	int		res = 1;
	int		i;
	
	for (i = 1; i <= n; i++)
		res *= i;
	
	return res;
}

long calculSomme(size_t len, long nbCherche, long iEnCours,
				 long sumEnCours, long permutations, long * except) {
	long		i;
	long		cpt = 0;
	
	if (len <= 1) {
		long	tmp = 1;
		
		/* On teste tous les nombres de iEnCours à 9 */
		for (i = iEnCours; i < 10; i++) {
			/* Si on à trouvé la somme, et que i != 0 (pour 000000) */
			if ((i + sumEnCours) == nbCherche && i != 0) {
				/* Si le nombre == celui d'avant 99 par ex.
				 * On a une exception */
				if (i == iEnCours)
					except[i]++;
				/* On augmente le nombre de possibilités */
				cpt++;
			}
		}
		/* On calcule le nombre d'exceptions */
		for (i = 0; i < 10; i++) {
			tmp *= factorielle(except[i]+1);
			if ((i + sumEnCours) == nbCherche && i == iEnCours && i != 0)
				except[i]--;
		}
		
		/* Toutes les combinaisons possibles sans doublons */
		cpt *= (permutations / tmp);
		return cpt;
	}
	else {
		/* Une condition pour l'initialisation, pour le premier nombre.
		 * J'envoie -1 pour éviter ce doublon */
		for (i = (iEnCours < 0) ? 0 : iEnCours; i < 10; i++) {
			/* On a une exception */
			if (i == iEnCours)
				except[i]++;
			/* On ajoute le nombre de nombres trouvés  */
			cpt += calculSomme(len-1, nbCherche, i, i+sumEnCours, permutations, except);
			/* On enlève cette exception */
			if (i == iEnCours)
				except[i]--;
		}
		return cpt;
	}
}


long zSommeEgalA(char * str, long nbCherche) {
	size_t		len = strlen(str);
	long		exception[10] = { 0 };
	return calculSomme(len, nbCherche, -1, 0, factorielle(len), exception);
}

int main(void) {
	/* Mettre 9999 ou 1000 revient au même ! */
	/* Je ne compte que la longueur de la chaîne */
	char str[] = "999999999";
	long sum = 27;
	
	printf("%ld", zSommeEgalA(str, sum));
	return EXIT_SUCCESS;
}

Si vous voulez des explications je les mettrai :)
Je peux sûrement améliorer le calcul des factorielles en mettant celles déjà calculées dans un tableau :)
Dîtes moi ce que vous en pensez :)

Edit : J'ai modifié la fonction factorielle pour ne pas recalculer 2 fois la même chose. Ca améliore grandement le temps :)

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

int factorielle(int n) {
	static long tab[20] = { 0 };
	
	if (tab[n] == 0) {
		int		res = 1;
		int		i;
		
		for (i = 1; i <= n; i++)
			res *= i;
		
		tab[n] = res;
	}
	return tab[n];
}

long calculSomme(size_t len, long nbCherche, long iEnCours,
				 long sumEnCours, long permutations, long * except) {
	long		i;
	long		cpt = 0;
	
	if (len <= 1) {
		long	tmp = 1;
		
		/* On teste tous les nombres de iEnCours à 9 */
		for (i = iEnCours; i < 10; i++) {
			/* Si on à trouvé la somme, et que i != 0 (pour 000000) */
			if ((i + sumEnCours) == nbCherche && i != 0) {
				/* Si le nombre == celui d'avant 99 par ex.
				 * On a une exception */
				if (i == iEnCours)
					except[i]++;
				/* On augmente le nombre de possibilités */
				cpt++;
			}
		}
		/* On calcule le nombre d'exceptions */
		for (i = 0; i < 10; i++) {
			tmp *= factorielle(except[i]+1);
			if ((i + sumEnCours) == nbCherche && i == iEnCours && i != 0)
				except[i]--;
		}
		
		/* Toutes les combinaisons possibles sans doublons */
		cpt *= (permutations / tmp);
		return cpt;
	}
	else {
		/* Une condition pour l'initialisation, pour le premier nombre.
		 * J'envoie -1 pour éviter ce doublon */
		for (i = (iEnCours < 0) ? 0 : iEnCours; i < 10; i++) {
			/* On a une exception */
			if (i == iEnCours)
				except[i]++;
			/* On ajoute le nombre de nombres trouvés  */
			cpt += calculSomme(len-1, nbCherche, i, i+sumEnCours, permutations, except);
			/* On enlève cette exception */
			if (i == iEnCours)
				except[i]--;
		}
		return cpt;
	}
}


long zSommeEgalA(char * str, long nbCherche) {
	size_t		len = strlen(str);
	long		exception[10] = { 0 };
	return calculSomme(len, nbCherche, -1, 0, factorielle(len), exception);
}

int main(void) {
	/* Mettre 9999 ou 1000 revient au même ! */
	/* Je ne compte que la longueur de la chaîne */
	char str[] = "999999999";
	long sum = 27;
	
	printf("%ld", zSommeEgalA(str, sum));
	return EXIT_SUCCESS;
}
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 17:15:22

Citation : Pouet_forever

Bon bah après m'être creusé la tête pendant un moment je soumet ma solution,



Tu obtiens un résultat différent de Bad_Wolf et moi-même pour les entrées suivantes (cf. mon précédent message) :

char str[] = "123456789012";
long sum = 27;




La réponse est 367859666 et tu trouves 947732512.
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 17:18:37

Je n'ai pas géré les chaînes autre que 999..99. C'est marqué ici :

/* Mettre 9999 ou 1000 revient au même ! */
/* Je ne compte que la longueur de la chaîne */

Je vais voir comment essayer de faire avec une chaîne 'normale'. Je pense savoir comment faire mais ça va être une usine à gaz encore :-°

Pour l'instant j'ai posté ça pour coller avec l'exo demandé :p
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 18:05:26

Une version qui présente les mêmes limitations que le code de Pouet actuel, N doit être une puissance de 10.

Donc, pas de
char str[] = "123456789012";
long sum = 27;


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

#define LIMIT	1000000000
#define MAX_COL	90

int rechercherSommeDyn(int n, int s)
{
    /* Nombre de chiffres de n, - 1 */
    int p = (int)floor(log10(n));

    if (n > LIMIT)
    {
        printf("Erreur : N doit être inférieur à %d.\n", LIMIT);
        exit(EXIT_FAILURE);
    }
    else if ((int)floor(pow(10, (p))) != n)
    {
        printf("Erreur : N doit être une puissance de 10. %d\n", LIMIT);
        exit(EXIT_FAILURE);
    }
    else
    {
        int tab[2][MAX_COL + 1] = {{0}};
        int col, lin;

        /* ligne précédente */
        int prv;
        /* ligne courante */
        int crt = 0;
        /* On initialise la première ligne du tableau.
        * 1 seule manière d'avoir une somme entre 0 et 9 dans l'intervalle [0, 10]
        */
        for (col = 0; col < 10; ++col)
            tab[0][col] = 1;

        for (lin = 1; lin < p; ++lin)
        {
            /* On échange les index de la ligne précédente et de la ligne courante. */
            prv = crt;
            crt = 1 - crt;

            /* Une seule manière d'avoir une somme de 0 */
            tab[crt][0] = 1;

            for (col = 1; col <= (lin + 1) * 9; ++col)
            {
                tab[crt][col] = 0;
                if (col < 10)
                    tab[crt][col] = tab[prv][col] + tab[crt][col - 1];
                else
                {
                    int k;
                    for (k = col - 1; k > 0 && col - k < 10; --k)
                        tab[crt][col] += tab[prv][k];

                    tab[crt][col] += tab[prv][col];
                }
            }
        }
        return tab[crt][s];
    }
}


int main(void)
{
    int s1 = 27;
    int s2 = 42;
    int n = 1000000000;

    printf("N = %d S = %d - > %d\n", n, s1, rechercherSommeDyn(n, s1));
    printf("N = %d S = %d - > %d\n", n, s2, rechercherSommeDyn(n, s2));

    return 0;
}

Je vais essayer de faire mieux. :-°
  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
23 janvier 2010 à 18:41:17

Citation : Pouet_forever

Je n'ai pas géré les chaînes autre que 999..99.




Tu trivialises dirait Bad_Wolf ;)


Citation : Pouet_forever

Je n'ai pas géré les chaînes autre que 999..99. C'est marqué ici :

/* Mettre 9999 ou 1000 revient au même ! */
/* Je ne compte que la longueur de la chaîne */


Ben non c'est pas clairement dit. Désolé mais j'ai horreur des assertions vagues ou ambiguës.


Citation : Pouet_forever


Pour l'instant j'ai posté ça pour coller avec l'exo demandé :p



Heu, à nouveau non, j'ai rappelé dans ce fil même il y a quelque jours l'énoncé initial.
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 19:00:19

Citation : candide


Tu trivialises dirait Bad_Wolf ;)


Ah ça, pour trivialiser, ça trivialise sévère ! :D
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 19:24:00

Citation : Bad_Wolf


Ah ça, pour trivialiser, ça trivialise sévère ! :D



Tiens un revenant. Et drôle de remarque pour quelqu'un qui a produit un code compliqué et qui tourne plusieurs milliers de fois plus lentement qu'un code tout simple et qui n'a même pas compris que le code simple était capable de résoudre efficacement le problème posé.


Citation : Pouet_forever

Je n'ai pas géré les chaînes autre que 999..99.



Je viens d'essayer avec une chaîne un peu longue :

char str[] = "9999999999999999999999999";
long sum = 27;


et ton code est très lent et donne un résultat incorrect (à cause d'un overflow). Il faut travailler avec des long long ou alors implémenter soi-même ses additions de grands entiers ce qui au passage est un excellent exo.

  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 19:36:19

Citation : candide

Citation : Bad_Wolf


Ah ça, pour trivialiser, ça trivialise sévère ! :D



Tiens un revenant. Et drôle de remarque pour quelqu'un qui a produit un code compliqué et qui tourne plusieurs milliers de fois plus lentement qu'un code tout simple et qui n'a même pas compris que le code simple était capable de résoudre efficacement le problème posé.


Errr... Joke?
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 19:56:50

Citation : candide

à cause d'un overflow


Bah change les long en long long, voire même unsigned long long, ou alors prend une chaîne plus petite ...
J'ai jamais dit non plus que mon code était le plus rapide qu'il soit. J'ai juste implémenté l'idée que j'avais émise plus haut.
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 21:19:43

On reste sympa! :p

Le problème provient d'un énoncé que j'ai mal formulé...

Pas la peine de s'envoyer des noms d'oiseaux! :-°
Le but premier est de proposer des exercices aux débutants, mais j'essaye de laisser de la place pour que les autre puissent s'amuser.
Je ne vois pas de raisons pour que vous vous tiriez dessus!

Alors, svp, on se calme! Merci :)


  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
23 janvier 2010 à 21:31:14

Citation : GurneyH

On reste sympa!



Bien sûr mais il s'agit que chacun reconnaisse ses erreurs.


  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 21:42:04

Citation : candide


implémenter soi-même ses additions de grands entiers ce qui au passage est un excellent exo.


Chiche?... ;) Je suis d'accord! C'est un excellent exercice.

Mais pour l'exercice actuel, il y a de la place pour voir des codes sympas! Alors ce sera la semaine prochaine!
  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
23 janvier 2010 à 22:09:33

Citation : GurneyH

Citation : candide


implémenter soi-même ses additions de grands entiers ce qui au passage est un excellent exo.



Cette addition permet d'ailleurs par exemple de calculer assez rapidement de grandes puissances de 2, genre <math>\(2^{50000}\)</math>.
  • Partager sur Facebook
  • Partager sur Twitter
23 janvier 2010 à 23:21:38

Premier post et titre mis à jour. :)
  • Partager sur Facebook
  • Partager sur Twitter
24 janvier 2010 à 8:11:43

Citation : GurneyH

Une version



Juste quelques remarques :

int p = (int)floor(log10(n));

Le cast n'est pas nécessaire.


int tab[2][MAX_COL + 1] = {{0}};


Effectivement on peut se contenter de deux lignes.

Sinon, c'est ça qui me fait réagir :

/* Nombre de chiffres de n, - 1 */
    int p = (int)floor(log10(n));

ainsi que

(int)floor(pow(10, (p))) != n


pow() produit des calculs approchés et comme tu prends derrière un floor, tu peux à l'arrivée avoir une erreur très gênante. Imaginons que pow(10,3) soit évalué 999.99999999999, l'erreur est infime et pourtant floor(pow(10,3)) ne sera pas égal à 1000. Ce n'est pas du tout un problème imaginaire, on l'a rencontré sur ce forum : fonction floor et racines cubiques.

Donc

*) ou bien on renonce à utiliser des fonctions de math.h pour faire des calculs à visée entière et nécessitant au final un résultat exact
*) ou bien entourer leur utilisation de plus de précautions.

Perso, je n'utilise que très rarement ces fonctions dans ce genre de circonstances bien qu'en pratique, j'ai constaté que leur utilisation ne semblait pas engendrer d'erreurs.

Pour déterminer le nombre de chiffres et pour ne pas réinventer la roue, je préfère faire comme ceci :

#include <stdio.h>

int nbChiffres(int n)
{
  char ch[32] = { 0 };
  return sprintf(ch, "%d", n);
}

int main(void)
{
  printf("%d\n", nbChiffres(1000000000));
  printf("%d\n", nbChiffres(2563));
  printf("%d\n", nbChiffres(0000000));
  return 0;
}


Pour tester si on est une puissance de 10, j'écrirais ceci :

#include <stdlib.h>

int estPuiss10(int n)
{
  char ch[32] = { 0 };
  sprintf(ch, "%d", n);
  return ch[0] == '1' && atoi(ch + 1) == 0;
}
  • Partager sur Facebook
  • Partager sur Twitter
24 janvier 2010 à 10:52:08

Effectivement, pour le nombre de chiffre, c'est maladroit.

J'ai tellement peu l'habitude d'utiliser le retour des fonctions de la famille de printf, que j'en oublie son utilité.

Pour tester si on est en présence d'une puissance de 10, bien vu.

Je prend note. Merci.
  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
26 janvier 2010 à 17:54:32

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

typedef unsigned long long uint64;

enum{MAX_DIGITS = 20, MAX_SUM = MAX_DIGITS * 9};

uint64 tab[MAX_DIGITS + 1][MAX_SUM];

uint64 digitsumForNDigits(int nDgt, int s)
{
    if (nDgt == 1)
        return s < 10;
    else if (s == 0)
        return 1;
    else
    {
        if  (!tab[nDgt][s])
        {
            int k;
            if (s < 10)
                tab[nDgt][s] = digitsumForNDigits(nDgt - 1, s) +
                                digitsumForNDigits(nDgt, s - 1);
            else
                for (k = s; k > 0 && s - k < 10; --k)
                    tab[nDgt][s] += digitsumForNDigits(nDgt - 1, k);
        }
        return tab[nDgt][s];
    }
}



uint64 digitsumCount(char const *limit, int s)
{
    uint64 sum = 0;
    int n, d;

    for (n = (int)strlen(limit) - 1; n * s; --n)
        for (d = *limit++ - '0'; d * s; --d)
            sum += digitsumForNDigits(n, s--);

    sum += *limit != '0';

    return sum;
}


int main(void)
{
    printf("%llu\n", digitsumCount("1000000000", 27));
    printf("%llu\n", digitsumCount("123456789012", 27));
    printf("%llu\n", digitsumCount("9999999999999999999", 42));

    return 0;
}

Snas regarder la version de candide, je n'arrivais pas à voir le principe pour la fonction digitsumCount ... Alors que c'est finalement le même que pour une puissance de 10 quelconque.

Désolé, j'admets volontiers que le code n'est pas ce qu'il y a de plus clair. :-°
  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
26 janvier 2010 à 18:49:03

Citation : GurneyH



Ton code donne des résultats différents du mien, je ne sais pas qui a raison.

En tous cas, ton code ne sort rien (il part en boucle sans fin) avec le main suivant :

int main(void)
{
char *p="99999999999";
    printf("%llu\n", digitsumCount(p,9*strlen(p)));


    return 0;
}


alors que le mien donne 1 comme il se doit.
  • Partager sur Facebook
  • Partager sur Twitter
26 janvier 2010 à 18:58:35

J'ai du mal à saisir vos codes candide et GurneyH, vous pourriez m'expliquer rapidos ? :)
J'aimerais bien le faire moi-même, mais le problème c'est que même en regardant vos codes, j'arrive pas comprendre votre démarche :(
  • Partager sur Facebook
  • Partager sur Twitter
26 janvier 2010 à 20:31:49

Citation : Pouet_forever

J'ai du mal à saisir vos codes candide et GurneyH, vous pourriez m'expliquer rapidos ? :)
J'aimerais bien le faire moi-même, mais le problème c'est que même en regardant vos codes, j'arrive pas comprendre votre démarche :(



Citation : Pouet_forever

J'ai du mal à saisir vos codes candide et GurneyH, vous pourriez m'expliquer rapidos ? :)



Je vais essayer mais j'ai déjà oublié comment j'ai fabriqué mon code (vu que le problème ne me passionne pas). Rappel de mon code :

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

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

INT t[NB_MAX_CHIFFRES + 1][VAL_MAX_CHIFFRES + 1] = { {0}};

void tab(int nb_ch, int somme)
{
  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];
      }
}

INT s(char *p, int somme)
{
  int n = strlen(p)-1;
  INT total = 0;

  while (n >= 1 && *p != 0 && somme > 0)
    {
      int i;
      int k = *p - '0';

      for (i = 0; i < k && somme > 0; i++)
        {
          total += t[n][somme];
          somme--;
        }
      n--, p++;
    }
  if (n == 0 && somme <= *p - '0'||somme == 0)
    total++;
  return total;
}

int main(void)
{
#define Z "99999999999"
    char *p[] = {"1000000000", "123456789012", "9999999999999999999", Z};
  int somme[]= {27, 27, 42, 9*(sizeof(Z)-1)};
  int n=sizeof somme/ sizeof *somme;
  int i;

for (i=0;i<n;i++)
  {tab(strlen(p[i]) - 1, somme[i]);


  printf("%lld\n", s(p[i], somme[i]));}
  return 0;
}




Je tente de t'expliquer l'algorithme, après à toi de voir comment ça s'implémente. Mon tableau t contient à la ligne i et à la colonne j le nombre d'entiers ayant au plus i chiffres et dont la somme des chiffres est j. Je note ce nombre f(i,j). A partir de là, il est facile de déterminer le nombre d'entiers inférieurs ou égaux à un entier z et de somme de chiffres valant v. Disons que je l'appelle g(z,v). Je te donne un exemple. Soit à calculer g(5269,20). Soit x <= 5269 et de somme de chiffres valant 20.
*) Ou bien le premier chiffre (de x) à gauche est 0 et alors il y a f(3,20) solutions;
*) Ou bien le premier chiffre à gauche est 1 et alors il y a f(3,19) solutions;
*) Ou bien le premier chiffre à gauche est 2 et alors il y a f(3,18) solutions;
*) Ou bien le premier chiffre à gauche est 3 et alors il y a f(3,17) solutions;
*) Ou bien le premier chiffre à gauche est 4 et alors il y a f(3,16) solutions;
*) Ou bien le premier chiffre à gauche est 5 et alors il y a g(269,5) solutions;

Donc le nombre cherché vaut :
f(3,20)+f(3,19)+f(3,18)+f(3,17)+f(3,16)+g(269,5).
On recommence avec g(269,5) pour obtenir :
f(3,20)+f(3,19)+f(3,18)+f(3,17)+f(3,16)+f(2,15)+f(2,14)+g(69,13)

Cette expression te laisse comprendre quelle somme des éléments de t il faut faire (je te rappelle que mon code précalcule t) et quelle est la condition d'arrêt.


  • Partager sur Facebook
  • Partager sur Twitter
26 janvier 2010 à 21:33:28

Merci :)
Je vais cogiter tout ça et essayer de le faire moi-même :)
  • Partager sur Facebook
  • Partager sur Twitter
27 janvier 2010 à 4:18:14

Citation : candide


En tous cas, ton code ne sort rien (il part en boucle sans fin) avec le main suivant :



Corrigé, j'ai édité mon post précédent en rajoutant la condition d'arrêt.

uint64 digitsumForNDigits(int nDgt, int s)
{
    if(s > nDgt * 9)
        return 0;
    ...


Citation : candide


Ton code donne des résultats différents du mien, je ne sais pas qui a raison.


Je regarde. Mon petit doigt me dit que c'est moi qui vais modifier mon code. ;)

edit:
Effectivement, j'avais une erreur à cette ligne,
sum += *limit != '0';

modifiée en
sum += s <= *limit - '0'; /* Seconde correction */


Maintenant, on à exactement les mêmes sorties(j'ai laissé tourner plusieurs minutes sur des unsigned long long, aucun écart.)
Par contre, il faut prendre garde à ne créer ton tableau qu'une seule fois(avec les valeurs max), sinon les résultats sont faux.

Mon code corrigé.
#include <stdio.h>
#include <string.h>

typedef unsigned long long uint64;

enum{MAX_DIGITS = 20, MAX_SUM = MAX_DIGITS * 9};

uint64 tab[MAX_DIGITS + 1][MAX_SUM];

uint64 digitsumForNDigits(int nDgt, int s)
{
    if(s > nDgt * 9)    /* première correction */
        return 0;
    else if (nDgt == 1)
        return s < 10;
    else if (s == 0)
        return 1;
    else
    {
        if  (!tab[nDgt][s])
        {
            int k;
            if (s < 10)
                tab[nDgt][s] = digitsumForNDigits(nDgt - 1, s) +
                                digitsumForNDigits(nDgt, s - 1);
            else
                for (k = s; k > 0 && s - k < 10; --k)
                    tab[nDgt][s] += digitsumForNDigits(nDgt - 1, k);
        }
        return tab[nDgt][s];
    }
}



uint64 digitsumCount(char const *limit, int s)
{
    uint64 sum = 0;
    int n, d;

    for (n = (int)strlen(limit) - 1; n * s; --n)
        for (d = *limit++ - '0'; d * s; --d)
            sum += digitsumForNDigits(n, s--);

    sum += s <= *limit - '0'; /* Seconde correction */

    return sum;
}


int main(void)
{
    printf("%llu\n", digitsumCount("100", 2));
    printf("%llu\n", digitsumCount("123456789012", 27));
    printf("%llu\n", digitsumCount("9999999999999999999", 42));
    printf("%llu\n", digitsumCount("99999999999", 99));

    return 0;
}


Je viens de faire une recherche Google rapide, et je n'ai pas trouvé d'autres codes ou algorithmes efficaces pour ce problème... :)
  • Partager sur Facebook
  • Partager sur Twitter
Zeste de Savoir, le site qui en a dans le citron !
27 janvier 2010 à 16:01:49

Citation : GurneyH


Par contre, il faut prendre garde à ne créer ton tableau qu'une seule fois(avec les valeurs max), sinon les résultats sont faux.



Exact, j'ai eu peur à un moment que mon code soit inexact et je n'ai pas envie de m'y replonger ...

Citation : GurneyH


Je viens de faire une recherche Google rapide, et je n'ai pas trouvé d'autres codes ou algorithmes efficaces pour ce problème... :)



Le problème étant très particulier, rien ne va assurer qu'on va trouver facilement une référence. Cela ferait un bon petit exo pour france-ioi ...


Au départ, je pensais que c'était un problème de combinaison avec répétitions mais les valeurs sont comprises entre 0 et 9 donc c'est un peu plus compliqué que je ne pensais et je n'ai pas regardé si on pouvait adapter.

  • Partager sur Facebook
  • Partager sur Twitter
27 janvier 2010 à 18:32:38

On dit plutôt avec remise, mais bon c'est un détail ^^

Ca rejoins un peu ce que j'ai fait en fait. Moi je n'ai pas utilisé les combinaisons, mais tout simplement les arrangements sans remise.
C'est quasiment la même chose à la différence qu'avec les arrangements on a le nombre d'éléments qui doit être supérieur ou égal au nombre qu'on 'prend' pour faire les combinaisons. Les combinaisons c'est l'inverse ^^

Dans mon cas, le nombre d'éléments pris est égal au nombre d'éléments qu'on a, ce qui donne tout simplement la factorielle :)
Mais bon en faisant ça je ne vois pas du tout comment faire pour prendre un nombre 'aléatoire'...
  • Partager sur Facebook
  • Partager sur Twitter
28 janvier 2010 à 12:00:17

Merci Candide pour ton lien sur les combinaisons, j'entreperçois enfin
votre débat sur le sujet :-°
en fait si j'ai bien compris :
123456789
912345678
891234567
....
ont la même somme de leur chiffre, et si j'ai bien suivi
votre algo évite de calculer "plusieurs fois" la même chose ! :-°
  • Partager sur Facebook
  • Partager sur Twitter
28 janvier 2010 à 12:32:32

Oui le but est d'éviter de calculer plusieurs fois la même chose :)

Si je prend ton exemple il y a 9! (factorielle 9) combinaisons possibles ;)
  • Partager sur Facebook
  • Partager sur Twitter