ソフトウェア開発 C言語

多倍長演算により300! - 100! + 200!を計算する

戻る


多倍長演算により多倍長演算により300! - 100! + 200!を計算するコードは、以下の通り。

/* bigfact2.c - 多倍長演算により300! - 100! + 200!を計算する */
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

/* 多倍長演算用の構造体 BIGNUM */
typedef struct tagBIGNUM
{
    int size;
    char *digits;
} BIGNUM;
 
/* BIGNUMに符号なし32-bit/64-bit整数を代入 */
BIGNUM BIGNUM_ui(unsigned int ui)
{
    BIGNUM bn;
    int i;
    unsigned int n, carry;
 
    /* 符号なし64-bit整数は最大で20桁 */
    bn.size = 20;
    bn.digits = (char *)malloc(bn.size);
    memset(bn.digits, 0, bn.size);
 
    carry = ui;
    for(i = 0; carry; i++)
    {
        n = carry;
        bn.digits[i] = n % 10;
        carry = n / 10;
    }
    bn.size = i;
    return bn;
}
 
/* BIGNUMを解放 */
void BIGNUM_delete(BIGNUM bn)
{
    if (bn.digits != NULL)
        free(bn.digits);
}
 
/* BIGNUM同士の比較 */
int BIGNUM_compare(BIGNUM bn1, BIGNUM bn2)
{
    int i;
 
    if (bn1.size < bn2.size) return -1;
    else if (bn1.size > bn2.size) return 1;
 
    for(i = bn1.size - 1; i >= 0; i--)
    {
        if (bn1.digits[i] < bn2.digits[i]) return -1;
        if (bn1.digits[i] > bn2.digits[i]) return 1;
    }
    return 0;
}
 
/* BIGNUM同士の加算 */
BIGNUM BIGNUM_add(BIGNUM bn1, BIGNUM bn2)
{
    BIGNUM bn;
    int i;
    unsigned int n, carry;
 
    if (bn1.size < bn2.size)
        bn.size = bn2.size + 1;
    else
        bn.size = bn1.size + 1;
    bn.digits = (char *)malloc(bn.size);
    memset(bn.digits, 0, bn.size);
 
    carry = 0;
    for(i = 0; i < bn1.size || i < bn2.size || carry; i++)
    {
        n = carry;
        if (i < bn1.size) n += bn1.digits[i];
        if (i < bn2.size) n += bn2.digits[i];
        bn.digits[i] = n % 10;
        carry = n / 10;
    }
    bn.size = i;
    return bn;
}
 
/* BIGNUM同士の差の絶対値を求める。*signは-1, 0, 1のいずれかを返す */
BIGNUM BIGNUM_sub(BIGNUM bn1, BIGNUM bn2, int *sign)
{
    BIGNUM bn;
    int i, n, carry, compare;
 
    compare = BIGNUM_compare(bn1, bn2);
    if (compare == 0)
    {
        if (sign != NULL) *sign = 0;
        return BIGNUM_ui(0);
    }
    else if (compare < 0)
    {
        if (sign != NULL) *sign = -1;
        bn = bn1; bn1 = bn2; bn2 = bn;
    }
    else if (sign != NULL) *sign = 1;
 
    bn.size = bn1.size;
    bn.digits = (char *)malloc(bn.size);
    memset(bn.digits, 0, bn.size);
 
    carry = 0;
    for(i = 0; i < bn1.size; i++)
    {
        n = carry + bn1.digits[i];
        if (i < bn2.size) n -= bn2.digits[i];
        if (n < 0)
        {
            n += 10;
            carry = -1;
        }
        else
            carry = 0;
        bn.digits[i] = n;
    }
    for(i = bn.size - 1; bn.digits[i] == 0 && i >= 0; i--) ;
    bn.size = i + 1;
    return bn;
}
 
/* BIGNUMに符号なし32-bit/64-bit整数を掛け算する */
BIGNUM BIGNUM_mul_ui(BIGNUM bn1, unsigned int ui)
{
    BIGNUM bn;
    int i;
    unsigned int n, carry;
 
    bn.size = bn1.size + 21;
    bn.digits = (char *)malloc(bn.size);
    memset(bn.digits, 0, bn.size);
 
    carry = 0;
    for(i = 0; i < bn1.size || carry; i++)
    {
        n = carry;
        if (i < bn1.size) n += bn1.digits[i] * ui;
        bn.digits[i] = n % 10;
        carry = n / 10;
    }
    bn.size = i;
    return bn;
}
 
/* BIGNUMを表示する */
void BIGNUM_print(BIGNUM bn1)
{
    int i;
    for(i = bn1.size - 1; i >= 0 && bn1.digits[i] == 0; i--) ;
    if (i < 0) putchar('0');
    else for( ; i >= 0; i--) putchar(bn1.digits[i] + '0');
}
 
/* 階乗を計算する */
BIGNUM BIGNUM_fact(unsigned int n)
{
    BIGNUM bn, bn1;
    unsigned int i;
 
    bn = BIGNUM_ui(1);
    for(i = 1; i <= n; i++)
    {
        bn1 = BIGNUM_mul_ui(bn, i);
        BIGNUM_delete(bn);
        bn = bn1;
    }
    return bn;
}
 
int main(void)
{
    BIGNUM bn1, bn2, bn3, bn4, bn5;
    bn1 = BIGNUM_fact(300);
    bn2 = BIGNUM_fact(100);
    bn3 = BIGNUM_fact(200);
    bn4 = BIGNUM_sub(bn1, bn2, NULL);
    bn5 = BIGNUM_add(bn4, bn3);
    printf("300! - 100! + 200! = ");
    BIGNUM_print(bn5);
    putchar('\n');
    BIGNUM_delete(bn1);
    BIGNUM_delete(bn2);
    BIGNUM_delete(bn3);
    BIGNUM_delete(bn4);
    BIGNUM_delete(bn5);
    return 0;
}

割り算の方法が分からない。誰か教えて。

ソース: bigfact2.zip


国内格安航空券サイトe航空券.com

戻る

©片山博文MZ
katayama.hirofumi.mz@gmail.com

inserted by FC2 system