Skywalker - Blog

这题比较简单，但老是有一点细节问题搞不清楚，加上格式看错了，贡献了一个PE。虽然有点慢(15MS)，但还是AC了。

主要算法：高精度加法

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1002

代码（仅供参考，C++）：

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

int main()

{

string s1,s2;

int n1[1001],n2[1001],result[1001],i,n,j,k;

cin>>n;

for(k=1;k<=n;k++){

if(k!=1) cout<<endl<<endl;

cin>>s1>>s2;

memset(n1,0,sizeof(n1));

memset(n2,0,sizeof(n2));

memset(result,0,sizeof(result));

//convert string to number and move all number to right side.

for(i=s1.length()-1,j=1000;i>=0;i–,j–){

n1[j]=s1.c_str()[i]-’0′;

}

for(i=s2.length()-1,j=1000;i>=0;i–,j–){

n2[j]=s2.c_str()[i]-’0′;

}

//add

int len=s1.length()>s2.length()?s1.length():s2.length();

for(i=1000;i>1000-len-1;i–){

result[i]=n1[i]+n2[i];

}

//rearrange

for(i=1000;i>0;i–){

if(result[i]>=10){

result[i-1]+=result[i]/10;

result[i]%=10;

}

}

//output

cout<<”Case “<<k<<”:”<<endl;

cout<<s1<<” + “<<s2<<” = “;

bool flag;

for(i=0,flag=false;i<1001;i++){

if(result[i]!=0) flag=true;

if(flag) cout<<result[i];

}

}

cout<<endl;

return 0;

}

#include <iostream> 
#include <iomanip> 
#include <string> 
using namespace std; 
string convert(int n); 
void main() 
{ 
    int nNum; 
    string str=”"; 
    cout<<”请输入一个整数:”; 
    cin>>nNum; 
    if(nNum<0) 
    { 
        str=str+’-'; 
        nNum=-nNum; 
    } 
    str=str+convert(nNum); 
    cout<<”输出的是:”; 
    cout<<str<<endl; 
} 
string convert(int n) 
{ 
    static string c=”"; 
    if(n<10) 
    { 
        c=(char)(n%10+’0′); 
        return c; 
    } else { 
        c=convert(n/10)+(char)(n%10+’0′); 
        return c; 
    } 

}

#include <stdio.h>
#include <string.h>

char NG[15][10];
int  Total, Have[10], Send[10], Gave[10];
int GetOrder(char *Name);
int main()
{
    int i, k, n, j;
    char tmp[15], to[15];
    FILE *input, *output;

    input = fopen(”gift1.in”, “r”);
    output = fopen(”gift1.out”, “w”);
    fscanf(input, “%d”, &Total);
    for (i = 0; i < Total; i++)
    {
        fscanf(input, “%s”, &NG[i]);
    }
    for (i = 0; i < Total; i++)
    {
        fscanf(input, “%s”, &tmp);
        k = GetOrder(tmp);
        fscanf(input, “%d%d”, &Have[k], &Send[k]);
        for (j = 0; j < Send[k]; j++)
        {
            fscanf(input, “%s”, &to);
            n = GetOrder(to);
            Gave[n] += (Have[k] - Have[k] % Send[k]) / Send[k];
 //           printf(” %s gives %d to %s, %d people need him, he left him %d.\n”,tmp,(Have[k] - Have[k] % Send[k]) / Send[k],NG[n], Send[k], Have[k] % Send[k]);
        }
        if (Send[k] == 0) Gave[k] += Have[k];
        else Gave[k] += Have[k] % Send[k];
    }
    for (i = 0; i < Total; i++)
       fprintf(output, “%s %d\n”, NG[i], Gave[i]-Have[i]);
    return 0;
}
int GetOrder(char *Name)
{
    int i;
    for (i = 0; i < Total; i++)
    {
        if (strcmp(NG[i], Name) == 0) return i;
    }
    return -1;
}

程序员之路──如何学习C语言

学习C语言不是一朝一夕的事情，但也不需要花费十年时间才能精通。如何以最小的代价学习并精通C语言是本文的主题。请注意，即使是“最小的代价”，也绝不是什么捷径，而是以最短的时间取得最多的收获，同时也意味着你需要经历艰苦的过程。

一、要读就读好书，否则不如不读

所有初学者面临的第一个问题便是：如何选择教材。好的开始是成功的一半，选择一本优秀的教材是事半功倍的关键因素。不幸的是，学校通常会帮你指定一本很差劲的C语言课本；而幸运的是，你还可以再次选择。

大名鼎鼎的谭浩强教授出了一本《C语言程序设计》，据说发行量有超过400万，据我所知，很多学校都会推荐这本书作为C语言课本。虽然本人的名字（谭浩 宇）跟教授仅仅一字之差，但我是无比坚定地黑他这本书的。这本书不是写给计算机专业的学生的，而是给那些需要考计算机等级考试的其它专业学生看的。这本书 的主要缺点是：例子程序非常不专业，不能教给你程序设计应该掌握的思考方式；程序风格相当地不好，会让你养成乱写代码的恶习；错误太多，曾经有人指出过这 本书的上百个错误，其中不乏关键的概念性错误。好了，这本书我也不想说太多了，有兴趣大家可以百度一下：）

Kernighan和 Ritchie的《The C Programming Language》（中译名《C程序设计语言》）堪称经典中的经典，不过旧版的很多内容都已过 时，和现在的标准C语言相去甚远，大家一定要看最新的版本，否则不如不看。另外，即使是最经典最权威的书，也没有办法面面俱到，所以手边常备一本《C语言 参考手册》是十分必要的。《C语言参考手册》就是《C Reference Manual》，是C语言标准的详细描述，包括绝大多数C标准库函数的细节， 算得上是最好的标准C语言的工具书。顺便提一句，最新的《C程序设计语言》是根据C89标准修订的，而《C语言参考手册》描述的是C99标准，二者可能会 有些出入，建议按照C99标准学习。还有一本《C和指针》，写得也是相当地不错，英文名是《Pointers on C》，特别地强调指针的重要性，算是 本书的一个特点吧。不过这本书并不十分适合初学者，如果你曾经学过C语言，有那么一些C语言的基础但又不是很扎实，那么你可以尝试一下这本书。我相信，只 要你理解了指针，C语言便不再神秘。

如果你已经啃完了一本C语言教材，想要更进一步，那么有两本书你一定要看。首先是 《C Traps and Pitfalls》（中译名《C陷井与缺陷》），很薄的一本小册子，内容非常非常地有趣。要注意一点，这本书是二十多年前写成 的，里面提到的很多C语言的缺陷都已被改进，不过能够了解一些历史也不是什么坏事。然后你可以挑战一下《Expert C Programming》（中 译名《C专家编程》），书如其名，这本书颇具难度，一旦你仔细读完并能透彻理解，你便可以放心大胆地在简历上写“精通C语言”了。

切记一个原则，不要读自己目前还看不懂的书，那是浪费生命。如果你看不懂，那你一定是缺失了某些必需基础知识。此时，你要仔细分析自己需要补充哪些内容，然后再去书店寻找讲述的这些内容的书籍。把基础知识补充完毕再回头来学习，才会真正的事半功倍。

Read the rest of this entry »

算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生 看到一些公司在招聘时要求的编程语言五花八门，就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路 方法。其实，大家被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法 和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新 的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。

算法与我

当我在 1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学’，而没有‘物 理科学系’或‘化学科学系’吗？因为人家是真的科学,不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。” 其实，这点他们彻底弄错了。 真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的 最佳演绎就是“算法”。

记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问 我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因 为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的 关键。

还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在 扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵 ”的技术是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一个O(n*m)的动态规划（dynamic programming）居然被他们做成了 O(n*n*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当 时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲 笑学计算机科学的人了吧!

网络时代的算法

有人也许会说：“今天计算机这么快，算法还重要吗?”其实永远不会有太快的计算 机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈 指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网 的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语 音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。

Read the rest of this entry »