没有条件,循环和算术运算符的C中的因子

Question

如何在C中找到数字的阶乘(从1到10),而不使用:

• 循环语句喜欢for,while和do while;
• 条件运算符,如if和case; 和
• 算术运算符如+, - ,*,%,/,++, - ？

仅供参考:我在C aptitude中找到了这个问题.

Answer 1

因为它只有1到10,所以只需预先计算它并将其存储在一个大小为11的简单int数组中.对于数组中的第一个元素,放置1.它不是你问题的有效输入范围,但也可能是正确的.

我们需要存储11个元素而不是我们需要的10个元素,否则我们需要使用操作" - "来获得正确的索引.但是在您的问题中不允许减法.

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

Answer 2

这是一个没有循环,算术或条件的解决方案,并且不依赖于预计算.它也没有使用短路条件语句像&&或者||它们是等效的做法if.所以这似乎是没有任何条件的第一个正确的解决方案.现在适当的C没有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));
    }
}

更新:讨论中包含声称短路条件如&&在不使用if的解决方案中是可接受的.这是一个简单的宏,模仿双向'if'使用&&,显然使整个问题变得不那么有趣:

#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);

然后你可以定义

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

然后问题的其余部分变得微不足道.

Answer 3

#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;
}

(任何使用这个答案来完成家庭作业问题的人都会失败,或者有一位具有良好幽默感的老师.)

(呸,我很慢.其他人已经给出了这个答案.请随意投票给他们答案.)

Answer 4

也许我正在解决某人的作业,但它看起来像一个有趣的挑战,无论如何,这是我的解决方案(编译警告,但不能帮助那些没有让它看起来丑陋(呃))

编辑:我已经改变了程序,使其支持相当长的阶乘(最多20个左右),并通过删除里面的查找表使代码更加整洁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;
}

样品运行:

[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]$

Answer 5

明确禁止使用"+"," - "和"*",但"+ ="," - ="和"*="不是,因此递归实现变为......

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

在"编译为C源模式"时,VC7拒绝编译上面的内容 - 关于"*="的const L值,但是这里是另一个变体:

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

Answer 6

这不是一个完整的答案,只是不同的方法add()和mult()功能:

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

(我相信C,与C++不同,允许在一个内部定义新类型sizeof.)

这是add()基于指针算法的另一个(完全不可移植的)实现:

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