逛奔的蜗牛

我不聪明，但我会很努力
   ::  :: 新随笔 ::  ::  :: 管理 ::
C/C++: 求1! + 2! + ... + n!
#include <iostream>
#include <cstdlib>

const unsigned int MAX_ELEMENT_VALUE_PLUS_1 = 10000;
const unsigned int BITS_MAX_ELEMENT_VALUE = 4;

/**
 * 求出数组中从左到右中第一个不为0的元素的下标
 */
size_t posOfFirstNoZero(unsigned int *array, size_t length) {
    size_t pos = 0;
    for (size_t i = 0; i < length; i++) {
        if (array[i] != 0) {
            pos = i;
            break;
        }
    }

    return pos;
}

/**
 * 数与大数相乘, 大数放在一个数组中
 */
void multiply(unsigned int *array, unsigned int num, size_t length) {
    unsigned int carry = 0;
    unsigned int temp = 0;
    

    // 求出第一个非0元素的下标, 
    // 由于相乘可能会进位, 所以可能会使用到第一个非0元素的前一个元素.
    size_t end = posOfFirstNoZero(array, length);
    for (size_t index = length - 1; index >= end - 1; index--) {
        temp = array[index] * num + carry;
        array[index] = temp % MAX_ELEMENT_VALUE_PLUS_1;
        carry = temp / MAX_ELEMENT_VALUE_PLUS_1;
        
        // 否则, 当index为0时, 因为是unsigned int, 所以index--结果为最大正数
        // 会造成死循环, 这种情况下end - 1为0.
        if (index == 0) {
            break;
        }
    }
}

/**
 * 打印出大数
 */
void print(unsigned int *array, size_t length) {
    // 数组从左到右中第一个不为0的元素的下标
    size_t start = posOfFirstNoZero(array, length);

    for (size_t i = start; i < length; i++) {
        int temp = array[i];
        int bits = 0;
        // 求出数组中每个元素的位数
        while (temp != 0) {
            ++bits;
            temp /= 10;
        }

        // 如果一个数的位数不足BITS_MAX_ELEMENT_VALUEU位, 这个数的前面用0补足.
        for (size_t j = 0; j < BITS_MAX_ELEMENT_VALUE - bits; j++) {
            std::cout << 0;
        }

        if (bits != 0) {
            std::cout << array[i] << " ";
        } else {
            std::cout << " ";
        }
    }
}

int main(int argc, char *argv[]) {
    const size_t length = 2;
    unsigned int result[length] = { 0 };
    result[length - 1] = 1;
    unsigned int n;

    std::cout << "Calculate 1! + 2! + 3! +  + n!" << std::endl;
    std::cout << "Please input a positive number: n = ";
    std::cin >> n;

    // 计算阶乘
    for (unsigned int i = 1; i <= n; i++) {
        multiply(result, i, length);
        print(result, length);
        std::cout << std::endl;
    }

    size_t start = posOfFirstNoZero(result, length);
    std::cout << "数组中还有" << start << "个空位" << std::endl;

    return EXIT_SUCCESS;
}

posted on 2008-03-18 15:30 逛奔的蜗牛 阅读(826) 评论(0)  编辑 收藏 引用 所属分类: C/C++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理