2010年2月

大整数阶乘的算法思路

听说中科院软件所09年复试的笔试题就是这个,打算自己写写。

这里的大整数指大于500以上的整数,当然更大也可以。由于整数阶乘递增的很快,远大于指数式递增,对于小整数,比如20,30左右,可以直接使用比如递归的方式进行,这很基本。

但是当整数较大时,阶乘的结果很大,远非一个int或者long就能存的下的,比如1000的阶乘结果有上千位。

所以大整数阶乘设计的关键点就是存储大整数,当选择了存储大整数,那么整数的乘法运算也不能再依靠*了,所以还要重新设计大整数的乘法运算。

上面是我的设计思路。网上找过相关的文章,有高手以4行代码完成了该算法,确实佩服!当然这涉及了算法的优化,不管那么多了,这里要的就是以尽量清晰地思路快速设计该算法,这是使用了STL标准库的容器。

下面是我的算法代码,直接贴这里了,注意看相关的注释:

#include <iostream>
#include <vector>

using namespace std;

// 传入整数:int,和整数-1的阶乘结果,进行相乘的结果
// 结构依然存储到容器中
void Calc(int num,vector<int> &calcresult)
{
    vector<int> tempnum;
    vector<int> rest;
    // 将传入的int拆分之后保存到容器中
    do
    {
        tempnum.push_back(num % 10);
        num = num / 10;
    } while (num);

    // 将分拆之后的num进行乘法计算
    unsigned int i = 0,j = 0;
    for(i = 0;i < tempnum.size();++i)
    {
        int carry = 0;// 存储每位计算时来自低位的进位
        for(j = 0;j < calcresult.size();++j)
        {
            int bit1 = 0,bit2 = 0,res = 0;
            bit1 = calcresult[j];
            bit2 = tempnum[i];
            res = bit1 * bit2;

            // 保存当前位
            if((i+j)<rest.size())
            {
                // 临时结果中有对应位存在,则直接更新
                rest[i+j] += (res + carry) % 10;
            }
            else
            {
                // 没有对应位则需要添加
                rest.push_back((res+carry)%10);
            }
            // 有进位,则更新进位
            carry = (res + carry) / 10;
        }
        // 如果计算之后还有最高位的进位,那么则直接添加进去
        if(carry)
        {
            // 保存当前位
            if((i+j)<rest.size())
            {
                // 临时结果中有对应位存在,则直接更新
                rest[i+j] += carry;
            }
            else
            {
                // 没有对应位则需要添加
                rest.push_back(carry);
            }
        }
    }
    // 上述计算之后,会出现有些位的数字超过了10,那是因为在处理每一位运算结果之后
    // 相加时地位向高位可能存在进位,上面没有考虑,所以需要进行调整
    for(i = 0;i < rest.size();++i)
    {
        if(rest[i] > 9)
        {
            if((i+1) != rest.size())
            {
                // 高位存在,则直接更新高位
                rest[i+1] += rest[i] / 10;
                rest[i] = rest[i] % 10;
            }
            else
            {
                // 高位不存在,则需要插入
                rest.push_back(rest[i] / 10);
                rest[i] = rest[i] % 10;
            }
        }
    }
    // 将计算结果存储到原来的容器中
    calcresult.clear();
    for(i = 0;i < rest.size();++i)
    {
        calcresult.push_back(rest[i]);
    }
}
int main()
{
    int num = 0;
    vector<int> calcresult;
    // 将初值1赋进去
    calcresult.push_back(1);
    // 获取欲求阶乘的整数
    cout<<"输入欲求阶乘的整数:"<<endl;
    cin>>num;

    for(int i = 0;i < num;++i)
    {
        Calc(i+1,calcresult);
    }
    // 输出计算结果
    cout<<num<<"的阶乘:"<<endl;
    for(unsigned int i = calcresult.size();i > 0 ;--i)
    {
        cout<<calcresult[i-1];
    }
    cout<<endl;

    return 0;
}

使用CreateProcessW新建进程时导致的内存写入错误的解决方案

使用CreateProcessW新建进程时导致的内存写入错误的解决方案
回答百度知道上网友的问题,和网友一起讨论之后才发现的这一小错误,顺便记录下来。

就因为MSDN中被忽视的这么一小段话:
The Unicode version of this function, CreateProcessW, can modify the contents of this string. Therefore, this parameter cannot be a pointer to read-only memory (such as a const variable or a literal string). If this parameter is a constant string, the function may cause an access violation.

即CreateProcess的Unicode版函数CreateProcessW会修改其参数lpCommandLine所指向的字符串。因此这个参数不能指向只读内存(比如字符串常量),如果该参数是字符串常量,会导致内存访问异常。

可以看出CreateProcess和CreateProcessW存在一些差异。

因为新版的Visual Studio会将vc创建的项目默认使用Unicode编码的字符串,对应的函数也会使用Unicode版的,比如这里的CreateProcessW。

有这样的一段代码,在vc 2008下会出错:

#include <windows.h>
#include <tchar.h>
int _tmain(int argc, _TCHAR* argv[])
{
    STARTUPINFOW si={sizeof(si)};
    wchar_t *sz_CommandLine=L"notepad";
    PROCESS_INFORMATION pi;
    ::CreateProcessW(NULL,sz_CommandLine,NULL,NULL,FALSE,NULL,NULL,NULL,&si,&pi);
    return 0;
}

需要做如下修改:

#include <windows.h>
#include <tchar.h>
int _tmain(int argc, _TCHAR* argv[])
{
    STARTUPINFOW si={sizeof(si)};
    wchar_t *sz_CommandLine=L"notepad";
    TCHAR temp[255] = {0};
    _tcscpy(temp,sz_CommandLine);
    PROCESS_INFORMATION pi;
    ::CreateProcessW(NULL,temp,NULL,NULL,FALSE,NULL,NULL,NULL,&si,&pi);
    return 0;
}