C# Problème de factoriel qui vaut 0

**juju742** · 07/08/2015, 18h57

bonjour,

J'ai écrit une méthode pour générer une liste de caractère sans répétition. Dans cette méthode (qui fonctionne) je calcule la taille de de ma boucle while pour avoir le nombre de combinaison possible avec une variable

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
long numberCombination = factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alhpa.Count - 1) - (NumberOfChar - 1));

J'ai écrit la méthode factorial au dessus de la méthode pour calcule la taille de la liste de caractère comme ceci.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
private long factorial(int x)
        {
            if (x == 0) return 1;
            if (x < 2) return 1;
            return x * factorial(x - 1);
        }

Quand ma liste est avec ces caractère "abcdefghijklmnopqrstuvwxyz" cela fonctionne.

Par contre quand je rajoute plus de caractère comme par exemple "abcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()-_+" ma variable numberCombination vaut 0 et ma boucle ne s’exécute pas et rien est générer.

**Kangourex** · 07/08/2015, 23h26

As tu essayé de mettre un point d'arrêt ? et de prendre le temps de lire les variables mises dans les fonctions ? parfois ça aide ^^

**juju742** · 08/08/2015, 15h30

Bonjour,

Merci de ta réponse. C'est avec un point d'arrêt que j'ai trouver le bug. Dans le code j'ai créé une vaviable test comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
long numberCombination = factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alhpa.Count - 1) - (NumberOfChar - 1));
long test += numberCombination; // égal 0

Je comprend pas que je mets 26 lettre cela fonctionne (numberCombination == 240) est quand je met plus de lettre c'est égal à 0. C'est pas logique !

**Kangourex** · 08/08/2015, 15h50

Peux tu mettre plus de code histoire de voir à quoi correspond les variables etc ^^ s'il te plait

EDIT :

Je voudrais revenir sur ta condition, un int peut être positif ou négatif. Or tu as mis :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
if(a == 0) return 1; 
if(a < 2) return 1;

Donc s'il est inférieur à 2, il appartient à l'intervalle [-infini; 1] et 0 est compris dans cet intervalle, donc juste if(a < 2) return 1; (dans ton cas)

**juju742** · 08/08/2015, 21h34

Je met pas le contenu du while qui fait 300 ligne mais en gros ma classe a ces deux méthodes.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
 
        private long factorial(int x)
        {
            if (x == 0) return 1;
            if (x < 2) return 1;
            return x * factorial(x - 1);
        }
 
        private List<string> Generate( int NumberOfChar )
        {
            List<string> alpha = new List<string>(){"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
 
           List<string> resultat = new List <string>(); 
 
            long numberCombination = factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alhpa.Count - 1) - (NumberOfChar - 1));
 
 
               While( i < numberCombination)
               {
                  /*Boucle While qui génére les combinaison pour retourner resultat (en t'autre), mais qui ne s’exécute pas quand je met
                     plus de caractère dans  la liste alpha*/. 
                  i++;
               }
 
           return resultat
        }

Ce qui fonctionne pas c'est quand j'ai une liste plus grand comme ci-dessous et ma boucle while ne s’exécute pas.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
List<string> alpha = new List<string>(){"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","0","1","2","3","4","5","6","7","8","9"}

J'ai tous tester et déboguer et mon code ne fonctionne qu'avec une liste de moins de 26 caractère.

**Kangourex** · 08/08/2015, 22h19

A savoir qu'un factoriel de 6 = 6 * 5 * 4 * 3 * 2

Donc j'ai revu ta fonction factorielle. Par contre dans le paramètre de Generate j'ai mis au pif et je n'obtiens pas 0 je te laisse regarder.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
static void Main(string[] args)
        {
            Console.WriteLine(Generate(10).ToString());
            Console.Read();
        }
 
        private static long factorial(int x)
        {
            long buffer = 1;
            while(x > 1) //tant que x est supérieur a 1
            {
                buffer = buffer * x; // je multiple
                x--; // je decremente mon x
            }
            return buffer;
        }
 
        private static long Generate(int NumberOfChar)
        {
            List<string> alpha = new List<string>() { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
 
            List<string> resultat = new List<string>();
 
            return factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alpha.Count - 1) - (NumberOfChar - 1));
 
        }

et j'obtiens Nom : 227af67807.png
Affichages : 1105
Taille : 529 octets

Après pour ce qu'il s'agit de ta fonction sache qu'il y a aussi des propriétés mathématiques sur les langages de programmations car j'ai réussit à tomber sur des résultats négatifs !

EDIT : une boucle de 300 lignes !!! j'espère qu'elles sont bien organisées car elles peuvent être source d'erreur

**tomlev** · 09/08/2015, 02h29

Avec une liste de 36 caractères, tu te retrouves à calculer la factorielle de 36, qui est un nombre gigantesque : environ 1.0333147966386144929666651337523e+40, soit beaucoup plus que la capacité d'un entier de 64 bits... Du coup tu obtiens un dépassement de capacité.

Je vois au moins 2 options pour résoudre le problème :

- utiliser le type BigInteger, qui gère des entiers de longueur illimitée. Simple, mais pas très efficace
- utiliser une autre approche pour calculer le nombre de combinaisons, en évitant de passer par de très grands nombres. La méthode décrite sur Wikipedia semble appropriée: https://fr.wikipedia.org/wiki/Combin...e_combinaisons

**Kangourex** · 09/08/2015, 08h51

Envoyé par tomlev

Avec une liste de 36 caractères, tu te retrouves à calculer la factorielle de 36, qui est un nombre gigantesque : environ 1.0333147966386144929666651337523e+40, soit beaucoup plus que la capacité d'un entier de 64 bits... Du coup tu obtiens un dépassement de capacité.

Je vois au moins 2 options pour résoudre le problème :

- utiliser le type BigInteger, qui gère des entiers de longueur illimitée. Simple, mais pas très efficace
- utiliser une autre approche pour calculer le nombre de combinaisons, en évitant de passer par de très grands nombres. La méthode décrite sur Wikipedia semble appropriée: https://fr.wikipedia.org/wiki/Combin...e_combinaisons

Exact en y repensant je me suis dit mais oui il fait de très gros calcul, d'où les combinaisons négatives.
D'après moi l'utilisation d'une variable double (à la place du long) peut te permettre de factoriel jusqu'à 171.

EDIT : 36! = 3.719933267899012e+41

**tomlev** · 09/08/2015, 14h46

Envoyé par Kangourex

Exact en y repensant je me suis dit mais oui il fait de très gros calcul, d'où les combinaisons négatives.
D'après moi l'utilisation d'une variable double (à la place du long) peut te permettre de factoriel jusqu'à 171.

Oui, sauf que comme ce n'est plus un entier, tu n'as plus une valeur exacte

Envoyé par Kangourex

EDIT : 36! = 3.719933267899012e+41

Exact, ce que j'ai mis dans mon message c'est 35! en fait

**juju742** · 09/08/2015, 20h17

Merci de vos réponse, j'ai testé cette après midi est ça fonctionne avec un double.
Ce qui me semble bizarre car je croyez le long plus grand. Par contre j'ai du limitée ma boucle while à 60 000 000 à cause de la liste qui est limité à 2 giga.

Je vois au moins 2 options pour résoudre le problème :

Je suis null en math se qui me sauve c'est ma logique, je garde la premier solution dans un coin de ma tête au cas ou par contre pour la deuxième je vois pas comment coder la calcul.

Exact, ce que j'ai mis dans mon message c'est 35! en fait.

Comment je peut limité le nombre pour pas que ça plante, avec nombre caractère maximum ? Ou je doit limité la taille de la liste à combien ?

**Kangourex** · 09/08/2015, 22h14

Bah si chaque tour de boucle ajoute qu'un élément :

Nom : b73ff9ac26.png
Affichages : 1065
Taille : 761 octets

Après faut savoir que c'est énorme ce que tu demandes faut travailler sur des algorithmes complexes aussi bien mathématiques mais informatiques, utilisé un autre langage aussi plus rapide par exemple en python j'avais eu les anagrammes quasiment 10 fois plus vite qu'avec le C# sur le même algo.

Peut-être trouvé une table arc-en-ciel et faire une requête serait plus simple la partie calcul serait déjà mâche en quelque sorte... Bien sûr je te donne une expérimentation je ne sais pas le résultat.

**tomlev** · 09/08/2015, 22h20

Envoyé par juju742

Merci de vos réponse, j'ai testé cette après midi est ça fonctionne avec un double.
Ce qui me semble bizarre car je croyez le long plus grand.

Le type double a une plage de valeurs plus grande (de -1.79769313486232e308 à +1.79769313486232e308), mais c'est moins précis (+1.79769313486232, c'est équivalent à un entier avec plein de 0 derrière... donc tu perds tous les chiffres "de poids faible"). La valeur que tu obtiens n'est donc pas exacte.

Envoyé par juju742

Je suis null en math se qui me sauve c'est ma logique, je garde la premier solution dans un coin de ma tête au cas ou par contre pour la deuxième je vois pas comment coder la calcul.

Et alors ? y a pas besoin d'être bon en maths, il suffit d'appliquer la formule. Y a même un exemple de déroulé du calcul pour que ce soit clair.

Allez, c'est cadeau

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
long NbCombinaisons(int n, int k)
{
    long product = 1;
    for (int i = 1; i <= k; i++)
    {
        product = product * (n - k + i) / i;
    }
    return product;
}

(n étant le nombre de caractères possibles, et k le nombre de caractères à prendre)

Et hop, plus besoin de factorielle

**juju742** · 12/08/2015, 13h19

Mon algo ne fait aucune répétition. K est le nombre de caractère répété ? Comme k - 1 comme mon algo ne répété pas de caractère ? Ou le nombre total de caractère moins k ?

**tomlev** · 12/08/2015, 14h41

n = alpha.Count
k = NumberOfChar

**juju742** · 16/08/2015, 04h54

Merci à vous tous pour votre aide précieuse. Au plaisir de vous revoir.

C# Problème de factoriel qui vaut 0 [Débutant]

C#

Discussions similaires

Partager

Partager