c - 条件、ループ、および算術演算子を使用しない C の階乗

Question

次を使用せずに、C で数値 (1 から 10 まで) の階乗を見つけるにはどうすればよいですか?

for、while、do while などのループステートメント。
if や case などの条件演算子。と
+ 、 − 、 * 、 % 、 /、++、 −−? などの算術演算子

参考までに: この質問は C aptitude で見つけました。

score 32 · Accepted Answer

1 から 10 までしかないので、単純に事前計算してサイズ 11 の単純な int 配列に格納します。配列の最初の要素に 1 を入力します。これは問題の有効な入力範囲ではありませんが、正しい場合もあります。

必要な 10 個ではなく 11 個の要素を格納する必要があります。そうしないと、正しいインデックスを取得するために操作 "-" を使用する必要があります。ただし、問題では減算は許可されていません。

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

score 16 · Accepted Answer

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

（宿題の質問にこの答えを使用する人は誰でも失敗するか、ユーモアのセンスのある教師を持っています. ）

（ああ、私は遅かったです。他の人がすでにこの回答を提供しています。自由に回答に投票してください。）

score 9 · Accepted Answer

「+」、「-」、「*」は明示的に禁止されていますが、「+=」、「-=」、「*=」は禁止されていないため、再帰的な実装は…</p>

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

VC7 は、「C ソースモードとしてコンパイル」の場合、上記のコンパイルを拒否します – 「*=」の const L 値についてうめき声を上げますが、同じものの別のバリアントを次に示します。

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

score 7 · Accepted Answer

これは完全な答えではありませんが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()これは、ポインター演算に基づくもう 1 つの (完全に移植性のない) 実装です。

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

score 4 · Accepted Answer

これが、必要な制限の下で実際に問題を解決する解決策（これまでのところ唯一のもの）です。

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

テストプログラムは次のとおりです。

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

score 3 · Accepted Answer

asmアセンブリコードを記述するために使用します。

または、プログラムをプリコンパイルして、プログラムから実行します。

なぜあなたはあなたのコードにそのような制限を課すのですか？

score 3 · Accepted Answer

これは、算術演算にポインター演算を使用し、条件に関数ポインターを使用するソリューションです。

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

サンプルラン:

 ~ > 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

score 2 · Accepted Answer

許可された入力ごとに事前計算された値を返す三項演算子の巨大なセットを生成します。マクロを使用して値を計算します。

score 1 · Accepted Answer

階乗の計算は、再帰を使用する最初の (そして多くの人にとっては最後の) 時間です。標準実装は

long fact(int x)
{
   if (x < 2)
     return 1L;
   else
     return fact(x - 1) * x;
}

コンパイラが末尾再帰であることを認識できるように、最後のステートメントは「x * fact(x-1)」にする必要があると主張する人もいます。個人的には、コンパイラがその形式でそれを見て、他の形式でそれを見ていないほど賢いとは思えません。

ただし、「if」または「-」を使用しないように制限しているため、どのように行うかわかりません。

score 1 · Accepted Answer

ラフスケッチ（すでに他の人によって提案されています！）

int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];

score 1 · Accepted Answer

1 <= n <= 10に依存せずに、半分エレガントなことができるかどうか見てみましょう。

もちろん、ループする代わりに再帰を使用します。
再帰を終了する if の代わりに、関数ポインタの配列を使用します! ( and
などの比較演算子はまだ必要です。)<==

編集: damaru は最初に関数ポインターのトリックを使用しました。

これは次のようになります: [すべてのコードはテストされておらず、手元にある C コンパイラはありません! ]

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

とを実装する必要がsub_1ありmultiplyます。キャリーが停止するまでのビットの単純な再帰であるから始めましょうsub_1(これを理解していない場合はadd_1、最後に同様のことを考える方が簡単です)。

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: 私が考えることができる最も単純なものは、ロシアの農民の乗算です。これは、バイナリシフトと加算に還元されます。条件付きで、再帰的な定式化は次のようになります。

 /* 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;
    }
}

条件なしでは、ディスパッチ配列トリックを 2 回使用する必要があります。

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

今、私たちが見逃しているのはadd. 2 つの数値のビットを同時に再帰することで、問題がシフトとに軽減されます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);
}

add_1キャリーが停止するまで、ビットの単純な再帰です。

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

そう思います！[上記のように、すべてのコードはテストされていません! ]

score 1 · Accepted Answer

私も配列に値を入れてみました。ここでは if 条件と while ループを使用しましたが、算術演算子は使用していません。私もそれらを削除できるかどうか試しています。

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

score 0 · Accepted Answer

再帰や算術演算を使用できず、入力の範囲が限られている場合は、結果を配列ルックアップにハードコーディングできます。

それで：

return factorials[x];

factorials関連する値を事前に入力した場所

score 0 · Accepted Answer

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

score 0 · Accepted Answer

ライブラリ関数を使用しないとは言っていないので：

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

score 0 · Accepted Answer

1 から 100 までの階乗を計算しなければならない場合はどうでしょうか。この大きな数をどのように格納するのでしょうか?

c - 条件、ループ、および算術演算子を使用しない C の階乗

18 に答える 18

Related

Reference