专注都难不倒 (7)

在上一篇日志中说到了如何在 M 的数字中找到 N 个最大的数字。其实是同学们纷纷要找工，面对了一些千奇百怪的笔试面试题目很头疼才来问我的。最近基本上没研究算法，净看《C++ Primer》去了（很惭愧，大一时候老师就推荐看了，竟然到现在才翻一下）。

看的动机很神奇，因为突然某一天随便翻翻目录，竟然发现有 STL。本来就觉得 STL（Standard Library Template）真的很神奇，对于我这种写个堆就要寻死觅活的人而言，STL 绝对是福音。特别是 vector，Sicily 中的 1646《Abbreviation》（我和虫虫第一次参加 ACM，死在这道题上）。我原本是用 C 风格写的，要 80+的代码才写完，一上 vector，不到 30 行代码就华丽丽飘过了。

不过代价是时间代价从 0.00 秒上升到了 0.01 秒。不如贴上代码让虫虫羞愧一下吧:-)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<iostream>
#include<string>
#include<cctype>
using namespace std;
int main()
{
    int t;
    string s,out;
    cin>>t;   
    for(int i=0;i<t;++i)
    {
        cin.get();
        out.clear();
        while(cin.peek()!='\n')
        {
            cin>>s;
            for(int j=0; j!=s.size(); j++)
                s[j] = toupper(s[j]);
            if(s.size()<3 || s=="AND" || s=="FOR" || s=="THE")
                continue;
            else
                out += s[0];
        }
        cout<<out<<endl;
    }
}

吹水完毕，下面是一道很经典的笔试题：求 1000！的阶乘。

毫无疑问，要用高精度算法。这里我们就先不管阶乘所固有的数学属性，而再做优化，直接上大数乘法。如果用 char 数组，每位储存 1 个数字，室友试过了，用 10+秒的时间是可以算出来的。可以优化成用 int 数组，每位储存 4 个数字（注意如果储存 5 个数字的话会溢出，可以估算出来）。

算法的原理可以参考《计算机组成原理》，原码乘法计算原理。继续偷懒，用 vector，原来我也厌烦了自己手动进行存储管理。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
    vector<int> v;
    //v中每个int保存大数的4位数字，从低位保存到高位
    //如12345678，将被保存为（5678）和（1234）
    v.push_back(1); 
    int flag;
    for(int i=2;i<=1000;++i)
    {
        flag=0;  //表示进位
        for(vector<int>::iterator iter=v.begin(); iter!=v.end(); ++iter)
        {
            int tmp=*iter * i +flag;
            *iter = tmp {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}10000;           
            flag=tmp/10000;  
        }
        if(flag!=0)
            v.push_back(flag);  //最高位有进位
    }
    for(vector<int>::reverse_iterator iter=v.rbegin(); iter!=v.rend(); ++iter)
        printf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}04d",*iter);  //输出，注意要输出每4位数中缺省的0
    return 0;
}

写完这两段，我狠狠地被 STL 打击到了，原来写代码可以写得这样优美。

5 评论

留下评论

Captcha Code

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。