Fattoriale in C senza condizionali, anelli e operatori aritmetici
https://stackoverflow.com/questions/653961
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come posso trovare il fattoriale di un numero (da 1 a 10) in C, senza usare:
- istruzioni in loop come for, while e do while;
- operatori condizionali come if e case; e
- operatori aritmetici come +, & # 8722; , *,%, /, ++, & # 8722; & # 8722 ;?
Cordiali saluti: Ho trovato questa domanda in C aptitude.
Soluzione
Dato che è solo da 1 a 10, è sufficiente pre-calcolarlo e memorizzarlo in un array int semplice di dimensione 11. Per il primo elemento dell'array, inserire 1. Non è un intervallo di input valido per il problema, ma potrebbe anche avere ragione.
Dobbiamo memorizzare 11 elementi invece dei 10 di cui abbiamo bisogno perché altrimenti dovremmo usare l'operazione " - " per ottenere l'indice giusto. La sottrazione non è consentita nel tuo problema.
int factorial(int x)
{
return precomputedArray[x];
}
Altri suggerimenti
Ecco una soluzione senza loop, aritmetica o condizionali e che non ricorre al pre-calcolo. Inoltre non utilizza condizionali di corto circuito come && o || che sono in pratica equivalenti a if. Quindi questa sembra essere la prima soluzione corretta senza alcun condizionale. Ora in C senza funzionalità 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));
}
}
Aggiornato: la discussione conteneva l'affermazione che il cortocircuito condizionale come & amp; & amp; sarebbe accettabile in una soluzione che non utilizza if. Ecco una semplice macro che imita 'if' a due vie usando & Amp; & Amp; e ovviamente rende l'intero problema molto meno 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);
È quindi possibile definire
#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))
e poi il resto del problema diventa banale.
#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;
}
(Chiunque usi questa risposta per una domanda a casa o fallisce o ha un insegnante con un buon senso dell'umorismo.)
(Bah, sono stato lento. Altre persone hanno già dato questa risposta. Sentiti libero di votare il loro rispondi.)
Forse sto risolvendo i compiti di qualcuno, ma sembrava una sfida divertente, comunque, ecco la mia soluzione (compila con avvertimenti, ma non posso aiutare quelli senza farlo sembrare brutto (er))
MODIFICA: Ho modificato il programma per renderlo supportato da fattoriali considerevolmente più lunghi (fino a circa 20) e ho reso il codice un po 'più ordinato rimuovendo la tabella di ricerca all'interno di 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;
}
Esempio di esecuzione:
[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 " * " sono esplicitamente vietati, ma " + = " ;, " - = " e " * = " non lo sono e così l'implementazione ricorsiva diventa & # 8230;
int factorial( int arg )
{
int argcopy = arg;
argcopy -= 1;
return arg == 1 ? arg : arg *= factorial( argcopy );
}
VC7 rifiuta di compilare quanto sopra quando in " compilare come modalità sorgente C " & # 8211; geme sul valore L const per " * = " ;, ma ecco un'altra variante dello stesso:
int factorial( int arg )
{
int argcopy1 = arg;
int argcopy2 = arg;
argcopy1 -= 1;
argcopy2 *= arg == 1 ? 1 : fact( argcopy1 );
return argcopy2;
}
Questa non è una risposta completa, ma solo approcci diversi alle funzioni 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]; })
(Credo che C, a differenza di C ++, consenta la definizione di nuovi tipi all'interno di un sizeof.)
Ecco un'altra implementazione (totalmente non portabile) di <=> basata sull'aritmetica del puntatore:
int add(int x, int y) {
return (int) &((char*) x)[y];
}
Ecco una soluzione (l'unica finora) che risolve effettivamente il problema con le limitazioni richieste.
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);
}
Ecco un programma di 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 );
}
}
}
Usa asm per scrivere il codice assembly.
Oppure precompila un programma ed eseguilo dal tuo programma.
Perché dovresti imporre tali limiti al tuo codice?
ecco una soluzione che utilizza l'aritmetica del puntatore per l'aritmetica e i puntatori di funzione per i condizionali.
#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));
}
}
Esempio di esecuzione:
~ > 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 gigantesco set di operatori ternari che restituiscono un valore precalcolato per ciascun input consentito. Usa le macro per calcolare i valori.
Il calcolo fattoriale è la prima (e per molte persone, l'ultima) volta che userete la ricorsione. L'implementazione standard è
long fact(int x)
{
if (x < 2)
return 1L;
else
return fact(x - 1) * x;
}
Alcuni sostengono che l'ultima affermazione dovrebbe essere " x * fact (x-1) " in modo che il compilatore possa riconoscere che è la ricorsione della coda. Personalmente, dubito che qualsiasi compilatore sia abbastanza intelligente da vederlo in quella forma e non vederlo nell'altra forma.
Tuttavia, poiché lo hai limitato a non utilizzare " if " o " - " ;, non so come lo faresti.
schizzo approssimativo (già proposto da altri!)
int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];
Anch'io ho provato mettendo i valori in array. qui ho usato se le condizioni e mentre i cicli ma nessun operatore aritmetico coinvolto.! cercando di poterli rimuovere anche io.
#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;
}
Vediamo se possiamo fare qualcosa di semi-elegante, senza dipendere da 1 < = n < = 10 .
- Invece del loop useremo ovviamente la ricorsione.
- Invece di un if per terminare la ricorsione, useremo un array di puntatori a funzione !
(Abbiamo ancora bisogno di operatori di confronto, come<e==.)
EDIT: damaru ha usato prima il trucco dei puntatori a funzione.
Questo dà: [ Tutto il codice non è testato, nessun compilatore C sotto 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);
}
Dobbiamo ancora implementare sub_1 e multiply. Cominciamo con add_1, che è una semplice ricorsione sui bit fino a quando il carry non si ferma (se non lo capisci, il add simile alla fine è più semplice da pensare):
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);
}
<=>: La più semplice che mi viene in mente è Russian Peasant moltiplication , che lo riduce a turni binari e addizioni. Con i condizionali, una formulazione ricorsiva sarebbe simile a questa:
/* 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;
}
}
Senza condizionali, dobbiamo usare il trucco dell'array di spedizione due volte:
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);
}
Ora tutto ciò che ci manca è <=>. Dovresti ora indovinare come andrà: una ricorsione simultanea su bit dei due numeri, che riduce il problema a turni e <=>:
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 <=> è una semplice ricorsione su bit finché il carry non si interrompe:
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);
}
Questo è tutto, penso! [ Come notato sopra, tutto il codice non è testato! ]
Se non è possibile utilizzare la ricorsione o l'aritmetica e si dispone di un intervallo limitato di input, è possibile codificare il risultato come una ricerca di array,
così:
return factorials[x];
dove hai pre-compilato factorials con i valori pertinenti
cosa succede se dobbiamo calcolare fattoriali da 1 a 100. Come memorizzare questi numeri grandi?
#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();
}
Dato che non diceva di non usare le funzioni di libreria:
#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;
}
