Factorial em C sem condicionais, loops e operadores aritméticos
https://stackoverflow.com/questions/653961
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como posso encontrar o fatorial de um número (de 1 a 10) em C, sem usar:
- instruções de loop como for, while, e fazer ao mesmo tempo;
- operadores condicionais, como se, e caso; e
- operadores aritméticos, como +, -, *,%, /, ++, -?
FYI: Eu encontrei esta pergunta em C aptidão
.Solução
Uma vez que é apenas 1 a 10, simplesmente precompute-lo e armazená-lo em uma matriz int simples de tamanho 11. Para o primeiro elemento na matriz colocar 1. Não é um intervalo de entrada válido para o seu problema, mas poderia muito bem estar correto.
Precisamos armazenar 11 elementos em vez dos 10 que precisamos porque senão tínhamos necessidade de operação de uso "-" para obter o indicador direito. Subtração não é permitido em seu problema embora.
int factorial(int x)
{
return precomputedArray[x];
}
Outras dicas
Aqui está uma solução sem loops, aritmética, ou condicionais e que não recorrem a precomputation. Ele também não usa um curto-circuito condicionais como && ou || que são na prática equivale a if. Portanto, esta parece ser a primeira solução adequada sem condicionais em tudo. Agora em C adequada sem C ++ apresenta:)
#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));
}
}
Atualização: a discussão continha a afirmação de que um curto-circuito condicional como && seria aceitável em uma solução que não usar se. Aqui é um simples macro que imita two-way 'se' usando && e, obviamente, faz com que todo o problema muito menos interessante:
#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);
Você pode então definir
#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))
e, em seguida, o resto do problema torna-se 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;
}
(Qualquer um que usa esta resposta para uma pergunta lição de casa ou falha ou tem um professor com um bom senso de humor.)
(Bah, eu era lento. Outras pessoas deram esta resposta já. Sinta-se livre para votar sua responder-se.)
Talvez eu estou resolvendo a lição de casa de alguém, mas parecia um desafio divertido, de qualquer maneira, aqui está a minha solução (compila com avisos, mas não pode ajudar aqueles sem torná-lo olhar feio (er))
EDIT:. eu mudei o programa para torná-lo apoiar fatoriais consideravelmente mais longo (até 20 ou mais) e fez o código um tidier pouco, removendo a tabela de referência dentro 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;
}
run Amostra:
[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]$
"+", "-" e "*" são expressamente proibidas, mas "+ =" "- =" e "* =" não são e assim a implementação recursiva torna-se ...
int factorial( int arg )
{
int argcopy = arg;
argcopy -= 1;
return arg == 1 ? arg : arg *= factorial( argcopy );
}
VC7 se recusa a compilar o acima quando em "compilação como modo de fonte C" - gemidos sobre a L-valor const para "* =", mas aqui é outra variante do mesmo:
int factorial( int arg )
{
int argcopy1 = arg;
int argcopy2 = arg;
argcopy1 -= 1;
argcopy2 *= arg == 1 ? 1 : fact( argcopy1 );
return argcopy2;
}
Esta não é uma resposta completa, mas apenas diferentes abordagens para funções add() e mult():
#define add(a, b) sizeof (struct { char x[a]; char y[b]; })
#define mult(a, b) sizeof (struct { char x[a][b]; })
(Eu acredito que C, ao contrário do C ++, permite a definição de novos tipos dentro de um sizeof.)
Aqui está mais uma (totalmente não portável) implementação de add() baseado em aritmética de ponteiro:
int add(int x, int y) {
return (int) &((char*) x)[y];
}
Aqui está uma solução (o única um até agora) que realmente resolve o problema sob as limitações necessárias.
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);
}
Aqui está um programa de teste:
#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 de código de montagem de escrita.
Ou, pré-compilar um programa e executá-lo a partir de seu programa.
Por que você iria impor tais limites em seu código?
aqui é uma solução que usa ponteiro aritmética para aritmética e ponteiros de função para condicionais.
#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));
}
}
Executar Amostra:
~ > 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
Produzir um conjunto gigante de operadores ternários retornando um valor pré-calculado para cada entrada permitida. Use macros para calcular os valores.
Cálculo fatorial é o primeiro (e para muitas pessoas, a última) vez que você vai usar recursão. A implementação padrão é
long fact(int x)
{
if (x < 2)
return 1L;
else
return fact(x - 1) * x;
}
Alguns argumentam que essa última afirmação deve ser "x * fato (x-1)" para que o compilador pode reconhecer que é cauda recursão. Pessoalmente, eu duvido que qualquer compilador é inteligente o suficiente para vê-lo nessa forma e não vê-lo em outro formulário.
No entanto, desde que você tenha restringido para não usar "se" ou "-"., Eu não sei como você pode fazê-lo
esboço (já proposto por outros!)
int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];
i também tentou, colocando os valores na matriz. Aqui eu tenho usado se as condições e loops while, mas não operadores aritméticos envolvidos.! tentando se eu poderia removê-los também.
#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 ver se podemos fazer algo meia-elegante, sem depender de 1 <= n <= 10 .
- Em vez de looping nós vamos de uso claro recursão.
- Em vez de um caso para terminar a recursão, vamos usar um array de ponteiros de função !
(Nós ainda precisamos de operadores de comparação, tais como<e==.)
EDIT:. damaru utilizados os ponteiros de função enganar primeira
Isto dá: [! Todo o código não foi testado, nenhum compilador C sob a mão ]
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);
}
Ainda precisamos implementar sub_1 e multiply. Vamos começar com sub_1, que é um simples recursão sobre os bits até o carry paradas (se você não entender isso, o add_1 semelhante no final é mais simples para 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: A mais simples que posso pensar é Russian Peasant multiplicação , o que reduz -lo a mudanças binários e além. Com condicionais, uma formulação recursiva ficaria assim:
/* 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;
}
}
Sem condicionais, temos que usar o truque variedade expedição duas vezes:
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);
}
Agora tudo o que falta é add. Você já deveria adivinhar como ele vai - uma recursão simultânea sobre bits dos dois números, o que reduz o problema de mudanças e 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);
}
e add_1 é um simples recursão sobre pedaços até que o carry pára:
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);
}
É isso que eu penso! [ Como observado acima de tudo código é! Testado ]
Se você não pode usar recursão, ou aritmética e você tem uma gama limitada de entradas, você poderia codificar o resultado seja uma pesquisa array,
forma:
return factorials[x];
onde você factorials pré-preenchida com os valores relevantes
E se o que temos de fatoriais calcular de 1 a 100. Como armazenar estes 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();
}
Uma vez que não disse para não usar funções 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;
}
