Factorielle en C sans conditionnelles, boucles et opérateurs arithmétiques

StackOverflow https://stackoverflow.com/questions/653961

  •  19-08-2019
  •  | 
  •  

Question

Comment trouver la factorielle d’un nombre (de 1 à 10) en C sans utiliser:

  • instructions de boucle telles que for, while et do while;
  • opérateurs conditionnels comme if et case; et
  • opérateurs arithmétiques comme +, & # 8722; , *,%, /, ++, & # 8722; & # 8722;?

FYI: J'ai trouvé cette question dans C aptitude.

Était-ce utile?

La solution

Puisqu'il ne s'agit que de 1 à 10, il suffit de le précalculer et de le stocker dans un tableau int simple de taille 11. Pour le premier élément du tableau, indiquez 1. La plage d'entrée n'est pas valide pour votre problème, mais vous pouvez également le faire. être correct.

Nous devons stocker 11 éléments au lieu de 10 car nous aurions sinon besoin d'utiliser l'opération " - " pour obtenir le bon index. La soustraction n’est toutefois pas autorisée dans votre problème. 

int factorial(int x)
{
  return precomputedArray[x];
}

Autres conseils

Voici une solution sans boucles, arithmétique ni conditionnelle et qui n’a pas recours au précalcul. Il n'utilise pas non plus de conditions de court-circuitage comme && ou || qui sont pratiquement équivalentes à if. . Cela semble donc être la première solution appropriée sans condition préalable. Maintenant en C correct sans fonctionnalités C ++:) 

#include <stdio.h>
#define uint unsigned int

void A(uint *a, uint *b)
{
    uint tmp = *a & *b;
    *a = (*a | *b) & ~tmp;
    *b = tmp << 1;
}

#define REPEAT32(s) \
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s

uint add(uint a, uint b)
{
    REPEAT32(A(&a, &b);) return a;
}

uint bitexpand(uint b)
{
    b = (b << 1)  | b; b = (b << 2)  | b; b = (b << 4)  | b;
    b = (b << 8)  | b; b = (b << 16) | b;
    return b;
}

void M(uint *acc, uint *a, uint *b)
{
    *acc = add(*acc, *a & bitexpand(*b & 1));
    *a <<= 1;
    *b >>= 1;
}

uint mult(uint a, uint b)
{
    uint acc = 0;
    REPEAT32(M(&acc, &a, &b);) return acc;
}

uint factorial(int n)
{
    uint k = 1;
    uint result = 0;
    result |= (bitexpand(n == 1) & k);
    k = mult(k, 2); result |= (bitexpand(n == 2) & k);
    k = mult(k, 3); result |= (bitexpand(n == 3) & k);
    k = mult(k, 4); result |= (bitexpand(n == 4) & k);
    k = mult(k, 5); result |= (bitexpand(n == 5) & k);
    k = mult(k, 6); result |= (bitexpand(n == 6) & k);
    k = mult(k, 7); result |= (bitexpand(n == 7) & k);
    k = mult(k, 8); result |= (bitexpand(n == 8) & k);
    k = mult(k, 9); result |= (bitexpand(n == 9) & k);
    k = mult(k, 10); result |= (bitexpand(n == 10) & k);
    return result;
}

int main(int argc, char **argv)
{
    uint i;
    /* Demonstration loop, not part of solution */
    for (i = 1; i <= 10; i++)
    {
        printf("%d %d\n", i, factorial(i));
    }
}

Mise à jour: la discussion contenait l'affirmation selon laquelle le court-circuitage conditionnel comme & amp; & amp; serait acceptable dans une solution qui ne utilise pas si. Voici une macro simple qui imite deux "si" en utilisant & Amp; & Amp; et rend évidemment le problème beaucoup moins intéressant: 

#define IF(i, t, e) \
(void)((i) && (goto then##__LINE__, 1)); goto else##__LINE__;
then##__LINE__: t; goto cont##__LINE__; \
else##__LINE__: e; cont##__LINE__: ((void)0);

Vous pouvez ensuite définir 

#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))

et le reste du problème devient trivial. 

#include <stdio.h>

static const int factorial[] = {
    1,
    1,
    2,
    6,
    24,
    120,
    720,
    5040,
    40320,
    362880,
    3628800,
};

/* Test/demo program. */
int main(void)
{
    int i;

    for (i = 0; i <= 10; ++i)
        printf("%d %d\n", i, factorial[i]);

    return 0;
}

(Toute personne qui utilise cette réponse pour une question de devoirs échoue ou a un enseignant avec un bon sens de l'humour.)

(Bah, j’étais lent. D’autres personnes ont déjà répondu à cette question. N'hésitez pas à voter pour leur répondez.)

Peut-être que je résous les devoirs de quelqu'un, mais cela ressemblait à un défi amusant, voici ma solution (compile avec des avertissements, mais je ne peux pas aider ceux qui ne le font pas sans lui donner un aspect laid)

EDIT: j'ai modifié le programme pour le rendre compatible avec des factorielles beaucoup plus longues (jusqu'à 20 ou plus) et rendu le code un peu plus ordonné en supprimant la table de recherche à l'intérieur de prev(). 

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

#define _if(CND, OP1, OP2) (((CND) && ((OP1) || 1)) || (OP2))

long long int add(long long int x, long long int y){
    long long int r = x ^ y;
    long long int c = x & y;
        c = c << 1;    
    _if(c != 0, r = add(r, c), 1);

    return r;
}

long long int prev(long long int x){
    return add(x, -1);
}                           

long long int mult(long long int x, long long int y){
    long long int r;

    _if(x == 0,
         r = 0,
       _if(x == 1, 
            r = y, 
            r = add(y, mult(prev(x), y))));

    return r;
}

long long int fac(long long int x){
    long long int r;

    _if(x < 2,
        r = 1,
        r = mult(x, fac(prev(x))));

    return r;
}

int main(int argc, char**argv){
    long long int i;

    for(i = 0; i <= 20; i++)
        printf("factorial(%lli) => %lli\n", i, fac(i));

    return 0;
}

Exemple d'analyse: 

[dsm@localhost:~/code/c]$ gcc -o proc proc.c
[dsm@localhost:~/code/c]$ ./proc #/
factorial(0) => 1
factorial(1) => 1
factorial(2) => 2
factorial(3) => 6
factorial(4) => 24
factorial(5) => 120
factorial(6) => 720
factorial(7) => 5040
factorial(8) => 40320
factorial(9) => 362880
factorial(10) => 3628800
factorial(11) => 39916800
factorial(12) => 479001600
factorial(13) => 6227020800
factorial(14) => 87178291200
factorial(15) => 1307674368000
factorial(16) => 20922789888000
factorial(17) => 355687428096000
factorial(18) => 6402373705728000
factorial(19) => 121645100408832000
factorial(20) => 2432902008176640000
[dsm@localhost:~/code/c]$

" + " ;, " - " et " * " sont explicitement interdites, mais " + = " ;, " - = " et " * = " ne sont pas et donc la mise en œuvre récursive devient & # 8230; 

int factorial( int arg )
{
    int argcopy = arg;
    argcopy -= 1;
    return arg == 1 ? arg : arg *= factorial( argcopy );
}

VC7 refuse de compiler ce qui précède lorsque & "; compile en mode source C &"; & # 8211; gémit au sujet de la valeur L de const pour " * = " ;, mais voici une autre variante du même: 

int factorial( int arg )
{
    int argcopy1 = arg;
    int argcopy2 = arg;
    argcopy1 -= 1;
    argcopy2 *= arg == 1 ? 1 : fact( argcopy1 );
    return argcopy2;
}

Il ne s’agit pas d’une réponse complète mais de différentes approches des add() et mult() fonctions: 

#define add(a, b)  sizeof (struct { char x[a]; char y[b]; })
#define mult(a, b) sizeof (struct { char x[a][b]; })

(Je crois que C, contrairement au C ++, permet de définir de nouveaux types dans un sizeof.)

Voici une autre implémentation (totalement non portable) de <=> basée sur l'arithmétique de pointeur: 

int add(int x, int y) {
    return (int) &((char*) x)[y];
}

Voici une solution (la seule à ce jour) qui résout réellement le problème dans les limites requises. 

int fac( int n )
{
    /* The is the binary representation of the function: */
    /* 0000 => 0000000000000000001 */
    /* 0001 => 0000000000000000001 */
    /* 0010 => 0000000000000000010 */
    /* 0011 => 0000000000000000110 */
    /* 0100 => 0000000000000011000 */
    /* 0101 => 0000000000001111000 */
    /* 0110 => 0000000001011010000 */
    /* 0111 => 0000001001110110000 */
    /* 1000 => 0001001110110000000 */
    /* 1001 => 1011000100110000000 */
    int bit0 = n & 1;
    int bit1 = (n & 2) >> 1;
    int bit2 = (n & 4) >> 2;
    int bit3 = (n & 8) >> 3;
    int notbit0 = bit0 ^ 1;
    int notbit1 = bit1 ^ 1;
    int notbit2 = bit2 ^ 1;
    int notbit3 = bit3 ^ 1;
    return
    (bit0 & notbit1 & notbit2 & bit3) << 18 |
    (bit0 & notbit1 & notbit2 & bit3) << 16 |
    (notbit1 & notbit2 & bit3) << 15 |
    (notbit1 & notbit2 & bit3) << 11 |
    (notbit1 & notbit2 & bit3) << 8 |
    (notbit1 & notbit2 & bit3) << 7 |
    (notbit0 & notbit1 & notbit2 & bit3) << 12 |
    (notbit0 & notbit1 & notbit2 & bit3) << 10 |
    (bit0 & bit1 & bit2 & notbit3) << 12 |
    (bit1 & bit2 & notbit3) << 9 |
    (bit0 & bit1 & bit2 & notbit3) << 8 |
    (bit1 & bit2 & notbit3) << 7 |
    (bit0 & bit2 & notbit3) << 5 |
    (bit2 & notbit3) << 4 |
    (notbit0 & bit1 & bit2 & notbit3) << 6 |
    (bit0 & notbit1 & bit2 & notbit3) << 6 |
    (notbit1 & bit2 & notbit3) << 3 |    
    (bit0 & bit1 & notbit2 & notbit3) << 2 |    
    (bit1 & notbit2 & notbit3) << 1 |    
    (notbit1 & notbit2 & notbit3);
}

Voici un programme de test: 

#include <stdio.h>

int main()
{
    int i, expected, j;
    for( i = 0; i < 10; ++i )
    {
        expected = 1;
        for( j = 2; j <= i; ++j )
        {
            expected *= j;
        }
        if( expected != fac( i ) )
        {
            printf( "FAILED: fac(%d) = %d, expected %d\n", i, fac( i ), expected );
        }
    }
}

Utilisez asm pour écrire le code d'assemblage.

Ou pré-compilez un programme et exécutez-le à partir de votre programme.

Pourquoi voudriez-vous imposer de telles limites à votre code?

Voici une solution qui utilise l’arithmétique de pointeur pour l’arithmétique et les pointeurs de fonction pour les conditions. 

#include <stdio.h>

int fact(int n);

int mul(int a, int b)
{
        struct s {
                char _v[b];
        };
        struct s *p = (struct s*)0;
        return (int) &p[a];
}

int add(int a, int b)
{
        return (int) (&((char *)a)[b]);
}

int is_0(int n)
{
        return (n == 0);
}

int fact_0(int n)
{
        return 1;
}

int fact_n(int n)
{
        return mul(n, fact(add(n,-1)));
}

int (*facts[2])(int) = {fact_n, fact_0};

int fact(int n)
{
        return facts[is_0(n)](n);
}

int main(int argc, char **argv)
{
        int i;
        for(i = 0; i<=10; i++) {
                printf("fact %d = %d\n", i, fact(i));
        }
}

Exemple d'analyse: 

 ~ > gcc -std=c99 fact.c 
 ~ > ./a.out 
fact 0 = 1
fact 1 = 1
fact 2 = 2
fact 3 = 6
fact 4 = 24
fact 5 = 120
fact 6 = 720
fact 7 = 5040
fact 8 = 40320
fact 9 = 362880
fact 10 = 3628800

Produit un ensemble géant d’opérateurs ternaires renvoyant une valeur précalculée pour chaque entrée autorisée. Utilisez des macros pour calculer les valeurs.

Le calcul factoriel est la première (et pour beaucoup de personnes, la dernière) fois que vous utiliserez la récursivité. L'implémentation standard est 

long fact(int x)
{
   if (x < 2)
     return 1L;
   else
     return fact(x - 1) * x;
}

Certains diront que cette dernière déclaration devrait être & "; x * fact (x-1) &"; afin que le compilateur puisse reconnaître qu'il s'agit d'une récursion finale. Personnellement, je doute qu'un compilateur soit assez intelligent pour le voir sous cette forme et ne pas le voir sous l'autre forme.

Cependant, puisque vous l'avez restreint, n'utilisez pas & "if &"; ou " - " ;, je ne sais pas comment vous le feriez.

croquis approximatif (déjà proposé par d'autres!) 

int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];

J'ai aussi essayé en mettant les valeurs dans un tableau. Ici, j'ai utilisé si des conditions et des boucles while, mais aucun opérateur arithmétique impliqué. essayer si je pouvais les supprimer aussi. 

#include <stdio.h>

int add(int a, int b)
{
int t1, t2, ab, bb, cb=0, orb=1, ans=0;

do {
    t1 = a >> 1; 
    t2 = t1 << 1;

    if (a==t2) ab=0; else ab=1;

    t1 = b >> 1;
    t2 = t1 << 1; 

    if (b==t2) bb=0; else bb=1;

    if (ab==1 && bb==1) { 
        if (cb==1) ans=ans | orb; 
        cb = 1; 
        }

    if ( ab!=bb ) { 
        if (cb==0) ans = ans | orb; 
        }

    if (ab==0 && bb==0) {
        if (cb==1) { 
        ans = ans | orb;
        cb=0;
                }
        }

    orb = orb << 1; 
    a = a >> 1;
    b = b >> 1;

    } while (a!=0 || b!=0);

if (cb==1) ans = ans | orb;

return ans;
}



int multiply(int x,int y)
{
    int result = 0, i = 0 , j=0;

    while((i=add(i,1)) <= y)
        result = add(result,x);

    return result;

}

int factorial(int x)
{
    if(x==1)
        return 1;
    else
        return multiply(x,factorial(x-1));

}


int main()
{
    int x;
    printf("Enter a number between 0 and 10: ");
    scanf("%d" , &x);
    printf("\nFactorial: %d\n" , factorial(x));
    return 0;
}

Voyons si nous pouvons faire quelque chose de demi élégant, sans compter sur 1 < = n < = 10 .

  • Au lieu de boucler, nous utiliserons bien sûr la récursivité.
  • Au lieu d'un if pour mettre fin à la récursivité, nous allons utiliser un tableau de pointeurs de fonction !

    (Nous avons encore besoin d’opérateurs de comparaison, tels que < et ==.)

EDIT: damaru a d'abord utilisé l'astuce des pointeurs de fonction.

Cela donne: [ Tout le code n'a pas été testé, aucun compilateur C sous la main! ] 

typedef int (*unary_fptr)(int);

int ret_1(int n) {
    return 1;
}

int fact(int n) {
    unary_fptr ret_1_or_fact[] = {ret_1, fact};
    return multiply(ret_1_or_fact[n > 1](sub_1(n)), n);
}

Nous devons toujours mettre en œuvre sub_1 et multiply. Commençons par add_1, qui est une simple récursion sur les bits jusqu’à ce que le report soit arrêté (si vous ne comprenez pas cela, la même chose add à la fin est plus simple à penser): 

int identity(int n) {
    return n;
}

int sub_1(int n) {
    unary_fptr sub_1_or_identity[] = {sub_1, identity};
    int lsb = n & 1;
    int rest = sub_1_or_identity[lsb](n >> 1);
    return (rest << 1) | (lsb ^ 1);
}

<=>: Le plus simple auquel je puisse penser est Multiplication de paysans russes , ce qui le réduit à des décalages binaires et à l'addition. Avec les conditionnelles, une formulation récursive ressemblerait à ceci: 

 /* If we could use conditionals */
int multiply(int a, int b) {
    int subproduct;
    if(a <= 1) {
       subproduct = 0;
    } else {
       subproduct = multiply(a >> 1, b << 1);
    }

    if(a & 1) {
       return add(b, subproduct);
    } else {
       return subproduct;
    }
}

Sans condition, nous devons utiliser deux fois l'astuce du tableau de répartition: 

typedef int (*binary_fptr)(int, int);

int ret_0(int a, int b) {
    return 0;
}

int multiply(int a, int b) {
    binary_fptr ret_0_or_multiply = {ret_0, multiply};
    int subproduct = ret_0_or_multiply[a >= 2](a >> 1, b << 1);

    binary_fptr ret_0_or_add = {ret_0, add};
    return ret_0_or_add[a & 1](subproduct, b);
}

Il ne nous manque plus que <=>. Vous devriez maintenant deviner comment cela va se passer - une récursion simultanée sur des bits des deux nombres, ce qui réduit le problème aux décalages et <=>: 

int add(int a, int b) {
    int lsb = (a & 1) ^ (b & 1);
    int carry = (a & 1) & (b & 1);

    binary_fptr ret_0_or_add = {ret_0, add};
    int subsum = ret_0_or_add[(a >= 2) & (b >= 2)](a >> 1, b>> 1);

    unary_fptr identity_or_add_1 = {identity, add_1};
    return identity_or_add_1[carry](subsum << 1);
}

et <=> est une simple récursion sur des bits jusqu'à ce que le report soit arrêté: 

int add_1(int n) {
    unary_fptr identity_or_add_1[] = {identity, add_1};
    int lsb = n & 1;
    int rest = identity_or_add_1[lsb](n >> 1);
    return (rest << 1) | (lsb ^ 1);
}

C'est ça je pense! [ Comme indiqué ci-dessus, tout le code n'est pas testé! ]

Si vous ne pouvez pas utiliser la récursion ou l'arithmétique et que vous avez une plage d'entrées limitée, vous pouvez coder en dur le résultat pour qu'il s'agisse d'une recherche de tableau,

alors: 

return factorials[x];

où vous avez pré-rempli factorials les valeurs appropriées

Et si on devait calculer des factorielles de 1 à 100. Comment stocker ces gros nombres? 

#include<stdio.h>
void main()
{
    unsigned long int num,fact,counter;
    while(counter<=num)
    {
        printf("Enter the number");
        scanf("%d",&num);
        fact=fact*counter;
        counter++;
        printf("The factorial of number entered is %lu",fact);
    }
    printf("press any key to exit...");
    getch();
}

Puisqu'il n'a pas dit de ne pas utiliser les fonctions de bibliothèque: 

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

int main( int argc, char** argv)
{
    printf( "%d\n", (int)round( exp( lgamma(2))));
    printf( "%d\n", (int)round( exp( lgamma(3))));
    printf( "%d\n", (int)round( exp( lgamma(4))));
    printf( "%d\n", (int)round( exp( lgamma(5))));
    printf( "%d\n", (int)round( exp( lgamma(6))));
    printf( "%d\n", (int)round( exp( lgamma(7))));
    printf( "%d\n", (int)round( exp( lgamma(8))));
    printf( "%d\n", (int)round( exp( lgamma(9))));
    printf( "%d\n", (int)round( exp( lgamma(10))));
    printf( "%d\n", (int)round( exp( lgamma(11))));

    return 0;
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top