分类 C++ 下的文章

大整数阶乘的算法思路

听说中科院软件所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;
}

SDK中使用GDI+出现的编译问题解决方案

GDI+是从windows XP开始提供的图形库,基于GDI构建

在MFC中使用GDI+,编译时不会出现什么大的问题,但是SDK中却会报告很多未定义的类型,其中主要是和COM有关的声明,这里就这一小问题进行解决。

首先要知道,GDI+是操作系统提供的模块,不和特定的编程语言和库相关联,所以纯净的SDK中是肯定可以使用GDI+的

其次,使用GDI+需要的头文件为GdiPlus.h,对应的lib文件为gdiplus.lib,GDI+被声明进Gdiplus命名空间中,GDI+库需要使用GdiplusStartup进行初始化,使用GdiplusShutdown进行清理(类似socket)。

好了,有了上述背景,接着进入要解决的问题。

如果在SDK中使用GDI+的话,做完上述操作之后进行编译,会报告类似如下的编译错误:

1>c:\program files\microsoft sdks\windows\v6.0a\include\gdiplusimaging.h(74) : error C4430: 缺少类型说明符 - 假定为 int。注意: C++ 不支持默认 int
1>c:\program files\microsoft sdks\windows\v6.0a\include\gdiplusimaging.h(74) : error C2440: “初始化”: 无法从“const char [37]”转换为“int”
1> 没有使该转换得以执行的上下文
1>c:\program files\microsoft sdks\windows\v6.0a\include\gdiplusimaging.h(74) : error C2146: 语法错误 : 缺少“;”(在标识符“IImageBytes”的前面)
1>c:\program files\microsoft sdks\windows\v6.0a\include\gdiplusimaging.h(74) : error C2470: “IImageBytes”: 看起来像函数定义,但没有参数列表;跳过明显的函数体
。。。。。。。。。。。。。

。。。。。。。。。。。。。

因为上述需要的声明信息,在windows.h和comdef.h两个头文件中,一般使用SDK写程序的朋友都知道要添加windows.h头文件,其实windows.h中是含有comdef.h的声明的。

但是如果你使用的IDE太智能了(比如我用的VC2008),在stdafx.h中会创建WIN32_LEAN_AND_MEAN宏,所以会屏蔽comdef.h,这样就会导致声明缺失问题。

删除WIN32_LEAN_AND_MEAN宏或者手动添加包含comdef.h头文件就可以了。

Vista下使用Visual Studio 2008(VC)独立编译Boost.Regex库

Boost 1.39.0

大家只要知道这是什么就可以了,Boost中的正则表达式库!
貌似是现在解析正则表达式效率最高的库了,也许有人单独用Regex++,这其实就是Boost中的Regex库,只不过作者单独提供,不知道为什么(懒得探究了),这个库我没法编译,提示Makefile语法有错,未知。。。

正则表达式很适合处理和字符串有关的工作,比如匹配,验证,搜索等等。。。
不了解的朋友可以百度一下相关的资料。。。值得一学!^_^

好了,这里总结一下我的编译过程,互相交流。
因为现在只想使用Regex库(要支持Unicode),其他的Boost库暂时不用(全部编译花了我4.5G,还没编译完。。。),所以进行单独编译。

  1. 因为我主要使用Unicode编码的字符串。所以要Regex支持Unicode,这里需要ICU,从Sourceforge下载(http://nchc.dl.sourceforge.net/sourceforge/icu/icu4c-4_0-src.zip)(需要的话,还有帮助文档)

  2. 编译ICU,比较简单,解压,打开source\allinone子目录下的allinone.sln项目文件,附带的是VS2005的,这里需要升级到2008,一般没什么问题,然后直接编译,Debug或者Release的,看你需要了,之后在lib目录下能够找到库文件,bin目录下有dll文件(动态库编译)。

小提示:因为我之前使用STLPort替换MS的STL,所以第一次编译出了点问题,应该是设置的问题,没有深究,改成原来MS的STL,就可以了。

  1. 解压Boost

  2. 使用bjam。你可以自行编译bjam,我这里直接使用编译好的版本。(之前使用nmake编译,成功了,但是编译之后的库文件的命名为1.38.0的,可能是作者疏忽,如果自己改的话,麻烦,不如直接重新编译,使用bjam就没有这个问题)
    放到解压后的Boost文件夹中的libs\regex\build子文件夹,因为bjam要使用这里的Jamfile.v2文件单独编译Regex

  3. 打开cmd(如果后面编译失败,可以尝试使用管理员身份运行)

  4. 给命令行编译器设置环境变量,直接调用Visual Studio 2008目录中的配置文件,在Common7\Tools子目录中的vsvar32.bat
    我的是:E:\Program Files\Microsoft Visual Studio 9.0\Common7\Tools\vsvar32.bat
    直接在cmd里粘贴"E:\Program Files\Microsoft Visual Studio 9.0\Common7\Tools\vsvar32.bat”
    注意要包含双引号,因为我这里的路径有空格,如果你的也是,就要用双引号括起来

  5. 不停地cd进入到解压后的Boost文件夹中的libs\regex\build子目录,调用如下命令
    bjam –sICU_PATH=icupath threading=multi link=shared,static runtime-link=static
    因为我使用多线程,所以就编译线程安全的multi库,要编译单线程的,用single参数
    icupath是指icu的解压目录(不是ICU编译后的lib目录,lib目录bjam会自己定位),如果这里也包含空格,同样的,也要使用双引号括起来

  6. 等待一会,就会编译完成,在Boost的解压目录中的bin.v2\libs\regex\build\msvc-9.0子目录中就会找的编译好的文件,lib和dll等,而且分类存放了起来
    为了使用方便,我做了如下调整,将所有文件直接存放到bin.v2\libs\regex\build\msvc-9.0下自己新建的lib文件夹里,需要连接什么文件regex的头文件清楚,我们只需指定必要的宏就可以了

  7. 配置Visual Studio 2008。将刚才自己创建的lib子目录添加进VS的库文件的搜索路径,然后将解压后的Boost路径添加进VS的包含文件的搜索路径,即可

  8. 开一个win32的小项目regextest测试一下,代码如下:

#include "stdafx.h"
#include <iostream>
#include <boost/regex.hpp>

int _tmain(int argc, _TCHAR* argv[])
{
     boost::wregex a(L"\\d{4}");
     if(boost::regex_match(L"1325",a))
     {
         std::cout<<"yes"<<std::endl;
     }
     else
     {
         std::cout<<"no"<<std::endl;
     }

     return 0;
}

编译连接通过,测试结果:yes

有什么问题的话,我们互相交流^_^

Vista系统下使用Visual Studio 2008编译STLPort

Vista系统下使用Visual Studio 2008编译STLPort

STLPort 5.2.1

  由于VC中附带的STL实现版本并不完全符合ISO C++标准,效率欠佳,问题也比较多,所以决定换掉MS的STL,现在用得比较多的是STLPort,它是SGI STL的可移植版本,SGI Port是和C++标准比较符合的一个STL实现,是GCC编译器的内置STL,了解Linux下编程的朋友应该都认识GCC,应该算目前最符合C++标准的一个编译器了吧。

  好了废话不多说,进入实战!

  按照帮助文档的编译说明,失败!
  之后在网上看到了许多成功的案例,试着编译,最后还是失败。。。
  最后总算是编译出来了,共享一下!

  我的开发环境是Visual Studio 2008,vista系统,下载的STL Port是5.2.1版本的(暂时最新),最新版的应该也可以按如下方法编译:

编译前的设置:
将VC中的bin目录添加到环境变量PATH中,这样系统可以直接找到命令,比如下面的nmake,编译时要用的cl,link,lib等。
我这里的是E:\Program Files\Microsoft Visual Studio 9.0\VC\bin

  1. 解压STL Port到任意目录,解压路径最好不要包含中文字符,路径中也不要含有空格等特殊字符!(我这里是E:\STLPort)

  2. 打开cmd(如果编译失败,可以试着以管理员身份运行cmd)

  3. 进入STL的安装目录(不会DOS命令的朋友,可以上网找找,学编程还是应该懂点BAT指令才行^_^)

  4. 执行命令configure.bat msvc9
    这是为了简化编译步骤而做的设置,会在build\lib子目录生成Mackfile文件

  5. 执行”E:\Program Files\Microsoft Visual Studio 9.0\Common7\Tools\vsvars32.bat”,在cmd键入命令的时候要用双引号包起来(因为有空格)。
    这一步很重要,这是设置编译时需要的环境变量,因为独立的cl编译器是和IDE做了集成的,cl所需的环境变量是从IDE的设置中获取的,所以这里一定要执行,否则最基本的windows.h它也说找不到

  6. 现再进入build\lib子目录

  7. 执行nmake clean install

  8. 一切搞定,在STLPort的bin和lib目录中会找的编译后的dll和lib文件,添加到IDE中的路径就可以了,还有stlport子目录是所需的头文件,也添加进IDE的包含路径中。

  提醒一下,在设置IDE时一定要将STLPort的包含文件路径和库文件路径放到VC的默认包含路径之前,否则STLport还是一样用不上,因为STLport是对C++标准库中STL的另一种实现,与VC中的标准库实现相对,我们是要覆盖原标准库,使用STLport替代,所以要让编译器和连接器首先使用STLport的头文件和库。