算法笔记第3章入门篇(1) 学习笔记

3.1 简单模拟

模拟题是一类题目怎么说，你就怎么做的题目。这类题目不涉及算法，完全只是根据题目描述来进行代码的编写，所以考察的是代码能力。

PAT B1001 害死人不偿命的(3n+1)猜想 (15分)

卡拉兹(Callatz)猜想：

对任何一个正整数

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数

输入格式：

每个测试输入包含 1 个测试用例，即给出正整数

输出格式：

输出从

输入样例：

输出样例：

#include<cstdio>
int main(){
    int n,count=0;
    scanf("%d",&n);
    while(n!=1){
        if(n%2==0){
            n = n/2;
            count++;
        }else{
            n = (3*n+1)/2;
            count++;
        }
    }
    printf("%d",count);
    return 0;
}

PAT B1032 挖掘机技术哪家强 (20分)

为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：

输入在第 1 行给出不超过 $1 的正整数$

输出格式：

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：

输出样例：

2 150

#include<cstdio>
const int maxn=100010;
int school[maxn]={0};
int main(){
    int n;
    scanf("%d",&n);
    int schid,mark;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&schid,&mark);
        school[schid] = school[schid] + mark;
    }
    int MAX=-1,k=0;
    for(int i=1;i<=n;i++){
        if(school[i]>MAX){
            k = i;
            MAX = school[i];
        }
    }
    printf("%d %d",k,MAX);
    return 0;
}

3.2 查找元素

给定一些元素，然后查找某个满足某条件的元素。

codeeup 1934 链接:http://codeup.cn/problem.php?cid=100000576&pid=1

问题 B: 找x

时间限制: 1 Sec 内存限制: 32 MB

题目描述

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

输入

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

输出

对于每组输入,请输出结果。

样例输入

4
1 2 3 4
3

样例输出

#include<cstdio>
const int maxn = 210;
int num[maxn];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
        }     
        int x;
        scanf("%d",&x);
        int j;
        for(j=0;j<n;j++){
            if(num[j] == x){
                printf("%d
",j);
                break;
            }
        }
        if(j==n){
            printf("-1
");
        }
    }
    return 0;
}

3.3 图形输出

在有些题目中，题目会给定一些规则，需要考生根据规则来进行画图。所谓图形，其实是由若干字符组成的，因此只要弄清楚规则就能编写代码。

PAT B1036 跟奥巴马一起编程 (15分)

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014 年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：

输入在一行中给出正方形边长

输出格式：

输出由给定字符 C 画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的 50%（四舍五入取整）。

输入样例：

10 a

输出样例：

aaaaaaaaaa
a        a
a        a
a        a
aaaaaaaaaa

#include<cstdio>
int main(){
    int n;
    char c;
    int col;
    scanf("%d %c",&n,&c);
    if(n%2==0){
        col = n/2;
    }else{
        col = n/2 +1;
    }
    for(int j=0;j<col;j++){
        if(j==0||j==col-1){
            for(int i=0;i<n;i++){
                printf("%c",c);
            }
            printf("
");
        }else{
            for(int i=0;i<n;i++){
                if(i==0||i==n-1){
                    printf("%c",c);
                } else{
                    printf(" ");
                }
            }
            printf("
");
        }
    }
    return 0;
}

3.4 日期处理

codeup 1928 http://codeup.cn/problem.php?cid=100000578&pid=0

问题 A: 日期差值

题目描述

有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天。

输入

有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD

输出

每组数据输出一行，即日期差值

样例输入

20130101
20130105

样例输出

#include<cstdio>
int isLeap(int year){
    if((year%4==0 && year%100!=0) || (year%400==0)){
        return 1;
    }else{
        return 0;
    }
}
int main(){
    int month[13][2]={{0,0},{31,31},{28,29},{31,31},{30,30},{31,31},{30,30},{31,31}, {31,31},{30,30},{31,31},
                      {30,30},{31,31}};
    int time1,y1,m1,d1;
    int time2,y2,m2,d2;
    while(scanf("%d%d",&time1,&time2)!=EOF)
    {
        int ans=1;    
        if(time1>time2){
            int temp = time1;
            time1 = time2;
            time2 = temp;
        }
        y1 = time1 / 10000; m1 = time1 % 10000 / 100; d1 = time1%100;
        y2 = time2 / 10000; m2 = time2 % 10000 / 100; d2 = time2%100;
        while(y1<y2 || m1<m2 || d1<d2){
            d1++;
            if(d1 == month[m1][isLeap(y1)]+1){
                m1++;
                d1 = 1;
            }
            if(m1==13){
                y1++;
                m1 = 1;
            }
            ans++;
        }
        printf("%d
",ans);
        
    }

    return 0;
}

3.5 进制转换

日常生活中使用的数字一般是十进制，而计算机使用的进制是二进制，另外还有八进制、十六进制以及各种数字的进制，这就会产生一个问题：对两个不同进制，应该如何进行相互转换。

PAT B1022 D进制的A+B (20分)

输入两个非负 10 进制整数

输入格式：

输入在一行中依次给出 3 个整数

输出格式：

输出

输入样例：

123 456 8

输出样例：

#include<cstdio>
int main(){
    int a,b,d;
    scanf("%d%d%d",&a,&b,&d);
    int sum = a + b;
    int ans[31],num=0;
    do{
        ans[num++] = sum % d;
        sum = sum/d;
    }while(sum!=0);
    for(int i=num-1;i>=0;i--){
        printf("%d",ans[i]);
    }
    return 0;
}

3.6 字符串处理

问题 I: 【字符串】回文串

题目描述

读入一串字符，判断是否是回文串。“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

输入

一行字符串，长度不超过255。

输出

如果是回文串，输出“YES”，否则输出“NO”。

样例输入

样例输出

YES

#include<cstdio>
#include<cstring>
bool judge(char str[]){
    int len = strlen(str);
    for(int i=0;i<len/2;i++){
        if(str[i]!=str[len-i-1])
            return false;
    }
    return true;
}
int main(){
    char str[280];
    scanf("%s",str);
    if(judge(str)==true){
        printf("YES");
    }else{
        printf("NO");
    }

    return 0;
}

PAT B1009 说反话 (20分)

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子。

输入样例：

Hello World Here I Come

输出样例：

Come I Here World Hello

#include<cstdio>
int main(){
    char str[90][90];
    int num=0;
    while(scanf("%s",str[num])!=EOF){
        num++;
    }
    for(int i=num-1;i>=0;i--){
        printf("%s",str[i]);
        if(i>0)
            printf(" ");
    }
    return 0;
}