Faktoriellen in C ohne Bedingungen, Schleifen und arithmetische Operatoren
https://stackoverflow.com/questions/653961
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie kann ich die Fakultät einer Zahl zu finden (von 1 bis 10) in C, ohne Verwendung:
- Schleifenanweisungen wie für, während, und tun, während;
- bedingte Operatoren wie wenn und Fall; und
- arithmetische Operatoren wie +, -, *,%, /, ++, -?
Zur Info: Ich fand diese Frage in C aptitude
.Lösung
Da es nur 1 bis 10 ist, precompute es einfach und speichern sie in einem einfachen int Array der Größe 11. Für das erste Element in dem Array 1. setzen Es ist keine gültige Eingabebereich für Ihr Problem, sondern könnte genauso gut richtig sein.
Wir brauchen 11 Elemente speichern anstelle der 10 brauchen wir denn sonst würden wir den Betrieb verwenden müssen „-“ den richtigen Index zu erhalten. Subtraktion ist in Ihrem Problem aber nicht erlaubt.
int factorial(int x)
{
return precomputedArray[x];
}
Andere Tipps
Hier ist eine Lösung ohne Schleifen, arithmetics oder conditionals und die zu precomputation nicht zurückgreifen. Es ist verwenden auch nicht kurzgeschlossen conditionals wie && oder || die in der Praxis gleichwertig sind if. So scheint dies überhaupt die erste richtige Lösung ohne conditionals zu sein. Jetzt in der richtigen C ohne C ++ Merkmale:)
#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));
}
}
Aktualisiert: die Diskussion enthielt die Behauptung, dass Kurzschließen bedingte wie && in einer Lösung akzeptabel wäre, die, wenn nicht verwendet. Hier ist ein einfaches Makro, das ahmt Zwei-Wege ‚wenn‘ mit && und macht offenbar das ganze Problem viel weniger interessant:
#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);
Sie können dann definieren
#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))
und dann der Rest des Problems wird 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;
}
(Jeder, der diese Antwort für eine Hausaufgaben Frage entweder nicht oder hat einen Lehrer mit einem guten Sinn für Humor.)
(Bah, ich war langsam. Andere Leute schon diese Antwort gab. Fühlen Sie sich frei, ihre stimm Antwort auf.)
Vielleicht hat jemand die Hausaufgaben Ich bin zu lösen, aber es sah aus wie eine lustige Herausforderung, sowieso, hier meine Lösung ist (kompiliert mit Warnungen, aber diejenigen, die nicht helfen, ohne dass es hässlich aussehen (er))
EDIT:. ich das Programm geändert haben, um es deutlich länger factorials zu machen Unterstützung (bis zu 20 oder so) und machte den Code ein wenig aufgeräumter durch die Lookup-Tabelle in prev() Entfernen
#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;
}
Probendurchlauf:
[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]$
"+", "-" und "*" sind ausdrücklich verboten, aber die "+ =" "- =" und "* =" sind nicht und so die rekursive Implementierung wird ...
int factorial( int arg )
{
int argcopy = arg;
argcopy -= 1;
return arg == 1 ? arg : arg *= factorial( argcopy );
}
VC 7 weigert sich, die oben, wenn in „kompilieren als C-Quelle-Modus“ zu kompilieren - stöhnt über die const L-Wert für „* =“, aber hier ist eine weitere Variante der gleiche:
int factorial( int arg )
{
int argcopy1 = arg;
int argcopy2 = arg;
argcopy1 -= 1;
argcopy2 *= arg == 1 ? 1 : fact( argcopy1 );
return argcopy2;
}
Dies ist keine vollständige Antwort, sondern nur verschiedene Ansätze zum add() und mult() Funktionen:
#define add(a, b) sizeof (struct { char x[a]; char y[b]; })
#define mult(a, b) sizeof (struct { char x[a][b]; })
(Ich glaube, dass C, im Gegensatz zu C ++ ermöglicht die Definition neuer Arten in einem sizeof.)
Hier ist eine weitere (total nonportable) Implementierung von add() basierend auf Pointer-Arithmetik:
int add(int x, int y) {
return (int) &((char*) x)[y];
}
Hier ist eine Lösung (die nur ein bisher), das tatsächlich das Problem, unter den vorgeschriebenen Grenzen löst.
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);
}
Hier ist ein Testprogramm:
#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 );
}
}
}
Verwenden asm Assembler-Code zu schreiben.
Oder ein Programm vorkompilieren und es von Ihrem Programm aus.
Warum würden Sie solche Grenzen für Ihren Code verhängen?
Hier ist eine Lösung, die Pointer-Arithmetik für Arithmetik und Funktionszeiger für conditionals verwendet.
#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));
}
}
Beispiel Run:
~ > 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
Erstellen Sie eine riesige Menge von ternären Operatoren einen vorberechneten Wert für jede erlaubte Eingabe zurück. Verwenden von Makros, um die Werte zu berechnen.
Die Berechnung Fakultät ist die erste (und für viele Menschen, das letzte) Mal werden Sie Rekursion verwenden. Die Standardimplementierung ist
long fact(int x)
{
if (x < 2)
return 1L;
else
return fact(x - 1) * x;
}
Einige würden argumentieren, dass diese letzte Aussage sollte „x * Tatsache (x-1)“ sein, so dass der Compiler kann erkennen, dass es Endrekursion. Persönlich bezweifle ich, jeder Compiler ist intelligent genug, es in dieser Form zu sehen und sehen, daß es nicht in der anderen Form.
Da Sie jedoch beschränkt habe es nicht verwenden „wenn“ oder „-“. Ich weiß nicht, wie Sie es tun würden
grobe Skizze (bereits von anderen vorgeschlagen!)
int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];
Auch ich versucht, indem die Werte in Array setzen. Hier habe ich, wenn die Bedingungen und While-Schleifen, aber keine arithmetischen Operatoren beteiligt sind, verwendet.! versuchen, wenn ich sie entfernen könnte.
#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;
}
Lassen Sie uns sehen, ob wir etwas halb elegant tun können, ohne in Abhängigkeit von 1 <= n <= 10 .
- Anstelle von looping wir werden natürlich Verwendung Rekursion.
- Statt eines, wenn für die Rekursion beendet wird, werden wir eine Array von Funktionszeigern verwenden!
(Wir müssen noch Vergleichsoperatoren, wie<und==.)
EDIT: damaru verwendet, um den Funktionszeiger Trick erster
.Das gibt: [! Die gesamten Code ist nicht getestet, kein C-Compiler unter der Hand ]
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);
}
Wir brauchen noch sub_1 und multiply zu implementieren. Lassen Sie sich mit sub_1 beginnen, die auf dem Bits, bis die Carry-Anschläge eine einfache Rekursion ist (wenn Sie dies nicht verstehen, der ähnliche add_1 am Ende ist einfacher zu denken):
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: Am einfachsten kann ich mir vorstellen Russische ländliche Multiplikation , die reduziert es Verschiebungen und zusätzlich binär. Mit conditionals, wie dies eine rekursive Formulierung aussehen:
/* 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;
}
}
Ohne conditionals müssen wir zweimal den Versand Array Trick verwenden:
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);
}
Jetzt alles, was wir vermissen ist add. Sie sollten nun erraten, wie es geht - eine gleichzeitige Rekursion über Bits der beiden Zahlen, die das Problem zu Verschiebungen und add_1 reduziert:
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);
}
und add_1 ist eine einfache Rekursion über Bits, bis der Übertrag stoppt:
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);
}
Das ist es denke ich! [ Wie vor allem notiert Code ist nicht getestet! ]
Wenn Sie nicht Rekursion verwenden können, oder Rechen- und Sie haben eine begrenzte Anzahl von Eingängen, könnten Sie schwer Code das Ergebnis ein Array-Lookup sein,
so:
return factorials[x];
, wo Sie factorials mit den entsprechenden Werten vorgefüllter haben
Was ist, wenn die wir haben factorials von 1 bis 100 zu berechnen, wie diese großen Zahlen speichern?
#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();
}
Da es nicht gesagt, nicht Bibliotheksfunktionen zu verwenden:
#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;
}
