Factorial en C sin condicionales, bucles y operadores aritméticos
https://stackoverflow.com/questions/653961
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo puedo encontrar el factorial de un número (de 1 a 10) en C, sin el uso de:
- sentencias de bucle como for, while y do while;
- operadores condicionales como if y case;y
- operadores aritméticos como + , − , * , % , /, ++, --?
FYI:He encontrado esta pregunta en C de aptitud.
Solución
Dado que es solo del 1 al 10, simplemente precalcúlelo y guárdelo en una matriz int simple de tamaño 11. Para el primer elemento de la matriz, coloque 1. No es un rango de entrada válido para su problema, pero también podría ser correcto
Necesitamos almacenar 11 elementos en lugar de los 10 que necesitamos porque de lo contrario tendríamos que usar la operación " - " para obtener el índice correcto. Sin embargo, la resta no está permitida en su problema.
int factorial(int x)
{
return precomputedArray[x];
}
Otros consejos
Aquí hay una solución sin bucles, aritméticos o condicionales y que no recurre a la precomputación. Tampoco utiliza condicionales de cortocircuito como && o || que en la práctica son equivalentes a if. Por lo tanto, esta parece ser la primera solución adecuada sin ningún tipo de condicionales. Ahora en C adecuada sin características de 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));
}
}
Actualizado: la discusión contenía la afirmación de que el cortocircuito condicional como & amp; & amp; sería aceptable en una solución que no use if. Aquí hay una macro simple que imita 'if' bidireccional usando & Amp; & Amp; y obviamente hace que todo el problema sea mucho menos interesante:
#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);
Entonces puedes definir
#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))
y luego el resto del problema se vuelve 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;
}
(Cualquiera que use esta respuesta para una pregunta de tarea falla o tiene un maestro con buen sentido del humor).
(Bah, fui lento. Otras personas ya dieron esta respuesta. Siéntete libre de votar su contesta.)
Tal vez estoy resolviendo la tarea de alguien, pero parecía un desafío divertido, de todos modos, aquí está mi solución (compila con advertencias, pero no puedo ayudar a aquellos sin hacer que se vea feo (er))
EDIT: he cambiado el programa para que admita factoriales considerablemente más largos (hasta 20 o más) e hice el código un poco más ordenado al eliminar la tabla de búsqueda dentro 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;
}
Ejecución de muestra:
[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]$
" + " ;, " - " y " * " están explícitamente prohibidos, pero " + = " ;, " - = " y " * = " no lo son y la implementación recursiva se convierte en & # 8230;
int factorial( int arg )
{
int argcopy = arg;
argcopy -= 1;
return arg == 1 ? arg : arg *= factorial( argcopy );
}
VC7 se niega a compilar lo anterior cuando está en " compilar como modo fuente C " & # 8211; gime sobre el valor L constante para " * = " ;, pero aquí hay otra variante del mismo:
int factorial( int arg )
{
int argcopy1 = arg;
int argcopy2 = arg;
argcopy1 -= 1;
argcopy2 *= arg == 1 ? 1 : fact( argcopy1 );
return argcopy2;
}
Esto no es una respuesta completa, pero sólo diferentes enfoques para add() y mult() funciones:
#define add(a, b) sizeof (struct { char x[a]; char y[b]; })
#define mult(a, b) sizeof (struct { char x[a][b]; })
(Yo creo que el C, a diferencia de C++, permite la definición de nuevos tipos en el interior de un sizeof.)
Aquí está uno más (totalmente no portátiles) implementación de add() basado en la aritmética de punteros:
int add(int x, int y) {
return (int) &((char*) x)[y];
}
Aquí hay una solución (la única hasta ahora) que realmente resuelve el problema bajo las limitaciones requeridas.
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);
}
Aquí hay un programa de prueba:
#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 );
}
}
}
Use asm para escribir el código de ensamblaje.
O bien, precompile un programa y ejecútelo desde su programa.
¿Por qué impondría tales límites a su código?
aquí hay una solución que utiliza aritmética de puntero para aritmética y punteros de función para condicionales.
#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));
}
}
Ejecución de muestra:
~ > 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
Produce un conjunto gigante de operadores ternarios que devuelven un valor precalculado para cada entrada permitida. Use macros para calcular los valores.
Calcular factorial es la primera vez (y para muchas personas, la última) vez que usará la recursividad. La implementación estándar es
long fact(int x)
{
if (x < 2)
return 1L;
else
return fact(x - 1) * x;
}
Algunos dirían que esa última declaración debería ser " x * fact (x-1) " para que el compilador pueda reconocer que es una recursión de cola. Personalmente, dudo que cualquier compilador sea lo suficientemente inteligente como para verlo en esa forma y no verlo en la otra forma.
Sin embargo, dado que lo ha restringido para que no use " if " o " - " ;, no sé cómo lo harías.
bosquejo (¡ya propuesto por otros!)
int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];
también lo intenté poniendo los valores en la matriz. ¡Aquí he usado condiciones if y while, pero no hay operadores aritméticos involucrados! intentando si pudiera eliminarlos también.
#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;
}
Vamos a ver si podemos hacer algo la mitad-elegante, sin depender de 1 <= n <= 10.
- En lugar de bucle vamos a usar la recursividad.
- En lugar de un si para la terminación de la recursividad, vamos a utilizar un array de punteros a funciones!
(Todavía necesitamos operadores de comparación, tales como<y==.)
EDITAR: damaru utilizan los punteros de función truco primera.
Esto nos da:[Todo el código es probado, no el compilador de C de la palma de la mano!]
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);
}
Todavía tenemos que implementar sub_1 y multiply.Vamos a empezar con sub_1, que es un simple recursividad en los bits hasta que el realizar paradas (si usted no entiende esto, el parecido add_1 al final es más sencillo pensar):
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);
}
multiply:La más sencilla que se me ocurre es Campesina rusa de multiplicación, que la reduce a binario turnos y además.Con condicionales, una formulación recursiva tendría este aspecto:
/* 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;
}
}
Sin condicionales, tenemos que utilizar el envío de la matriz truco dos veces:
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);
}
Ahora todo lo que echo de menos es add.Usted debe por ahora adivinar cómo va a ir - simultánea recursión sobre los bits de los dos números, lo que reduce el problema a los cambios y add_1:
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);
}
y add_1 es un simple recursión sobre bits hasta que el realizar paradas:
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);
}
Eso es lo que pienso![Como se señaló anteriormente todo el código que no está probado!]
Si no puede usar la recursividad o la aritmética y tiene un rango limitado de entradas, puede codificar el resultado para que sea una búsqueda de matriz,
entonces:
return factorials[x];
donde ha completado previamente factorials con los valores relevantes
¿y si tenemos que calcular factoriales de 1 a 100. ¿Cómo almacenar estos números grandes?
#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();
}
Como no decía no usar funciones de biblioteca:
#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;
}
