首页 > 技术文章 > PAT basic level 1001-1019 解题笔记

luojiahu 2014-03-31 22:07 原文

1002 写出这个数

采用字符串输入数据,再对每位减去字符‘0’,得到该位相应的整数

    int len=s.length();//字符串的长度
    int t=0;
    for(int i=0;i<len;i++)//每位减去‘0’,逐位相加
    {
        t=t+s[i]-'0';
    }

根据题意,所得数应小于1000,获取每位的数字采用整除取余的方法

==================================

1003 我要通过

这道题好坑爹,自己没有做出来,看了网上的程序。根据题意,字符串中有且必须有至少PAT各一个,P和T只能出现一次。aPbTc成立,则aPbATca成立,这里最坑爹,一直理解错误,实际这里的意思是,a,b,c只能是A,a与c中A的数目相同。而且对aPbATc(这里包括了前面说的aPbTc形式),记a,b,c中A的次数分别为t1,t2,t3,则应满足t3=t2*t1。

参考的程序采用了string类的find_first_not_of();函数记录位置。最后判断是否满足上述关系。

===================================

1004 成绩排名

采用了动态数组。判断成绩项的大小,最后输出即可。

=======================================

1005 继续3n+1猜想

思路:利用一个缓存容器存放每个元素计算kalatz数列的结果,并与输入数列全部元素比较,如果有重合的则置零。比较过程中,遇到0不比较。比较结束后,将输入数列中的0元素删除得到“关键”元素,最后排序并输出。p.s. 其实感觉这种方法挺复杂的,不怎么好,智商捉急啊。

实现涉及到容器的删除:

ptr=v.erase(ptr);

=========================================

1007 素数对猜想

这个题目首先得得到素数,关于素数的求法网上有总结,利用素数的特征可以简化求取的过程。

chara1.只能被自己和1整除(1不是素数)

chara2.所有的偶数都不是素数(显然的,但是这条性质理解容易,编程的时候想到不易,且编且珍惜~~~~)

chara3.对数n,只需验证数sqrt(n)之前的素数是否能够整除即可 

简化的方法有两种,一种是分10,100,10000,这样的区间去求,这种方法应该是所有方法中在数字比较大的时候最高效的,因为每次需要验证的数都少了很多。另外一种“筛法”,这种方法好理解,但是经验证在数据超过10000的时候就变得很慢,速度不及前一种方法。(果然还有更简单的方法 http://blog.csdn.net/cstopcoder/article/details/18795823)

至于满足题给条件的素数对,只需逐一验证即可。

==========================================

1008 数组循环右移

简单,先给出了数组的长度n和右移的位数m,只需要先从输入中获取n-m位数据A,再获取m位数据B,再把两组数据接起来就行了BA。

=====================================

1009 说反话

思路也简单,只需要以单词为单元,把单词倒序输出。实现上需要前后空格的位置,采用同1003的方法,把单词逐个压入栈中,最后输出即可(用top函数)。

p.s. 一开始把题目看错了,以为是把每个单词中的字母顺序反过来,费了大半天功夫实现发现不和题意。可见认真审题的重要性啊!

======================================

1010 一元多项式求导

这里需要判断回车,之前采用string类先整体输入,再删除空格,然后转化为数字的方法,但是实现起来相当麻烦。网上搜了半天找到了如下的办法:

    vector<int> v;
    vector<int>::iterator ptr;

    char c;
    int temp;
    while((c=cin.get())!='\n')//判断输入是否为回车
    {
        cin.unget();//若不是则将字符放回流中
        cin>>temp;
        v.push_back(temp);
    }

另外,还需要考虑最后把常数项求导结果删除,采用-1作为特征数,把-1和前面的0删除。还需注意幂为负数的情况。

======================================

1011 A+B和C

看起来很简单,但是两个int型相加有可能会超出int的范围,采用double型数据规避这个问题,不知还有没有好方法……

 

刷了11道basic level 感觉简单的倒是挺简单的,可以很快搞出来,但是需要注意详细审题,把各种情况考虑周全。难的题最多的可能花了一天才搞出来,这还何谈advanced level 90分以上啊!!路漫漫啊!加油!

======================================

1012 数字分类

这道题不难,只需要对每个数字对5取余,按情况分类即可。其中用到了switch,比较基础。另外用到了输出的精度设置。精度的设置需要使用iomanip头文件下的setprecision 函数,在流对象中,setprecision(n)设置有效数字位数为n,如果需要固定小数点后的位数则需另外加上fixed,如

float num=1245.234567;
cout<<num<<endl
      <<setprecision(3)<<num<<endl
      <<fixed<<setprecision(3)<<num<<endl;

输出依次为1245.23,1.25e+003,1245.234,这里没设置精度时默认输出六位有效数字。

==========================================

1013 数素数

按理说,在1007的基础上这道题不难解,但是,按照分段求的方法,需要控制求素数的范围以提高效率。这样就需要知道各段内的素数个数,虽然这样最后实现了,但是程序还是一如既往的乱,绕得晕头转向。最后借鉴了别人的求素数的方法,如1007最后加的连接。

=======================================

1014 福尔摩斯的约会

这道题比较坑,跟PAT那道一样,需要仔细审题,把题目中的意思详细理解清楚。比如第一个求星期那里,需要限制字符A-Z,在这里栽了很多次。

================================

1015 德才论

这道题需要做两件事情,第一是统计总分,第二件是归类。我的思路是先按总分排序,然后依次输出符合每类条件的信息。这样做就有排序按什么排的问题。一开始利用冒泡排,有三个点过不去。后来看了别人的博客,这里有两点需要注意的,第一是排序的方法,最好使用O(nlgn)的算法。STL中自带的sort,可以按照输入待排序数据的个数合理选择方法。另外还有qsort()函数。sort()函数默认是升序排序,如果需要降序可以编写自己的compare函数,如果需要控制排序对象的排序规则,也可以编写自己的compare函数实现。

===============================

1016-1019 都比较简单

================================

1020 月饼

这道题要求算出最大的利润,开始还以为是线性规划,搞得觉得做不出来,变量太多。看了别人的解释,发现自己太没有生意头脑了……至于解的过程是比较简单的的,只要按照单价由高到低购买,直到满足总的采购量为止,算法用了O(n2)的,在1000个数据以内应该没啥问题。没有想出来更好的算法。

推荐阅读