《算法笔记》简单模拟、查找元素、图形输出、日期处理、进制转换与字符串处理（例题+代码C++）

一、简单模拟 1、1001 害死人不偿命的(3n+1)猜想 (15 分)

卡拉兹(Callatz)猜想：
对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？

输入格式：
每个测试输入包含 1 个测试用例，即给出正整数 n 的值。

输出格式：
输出从 n 计算到 1 需要的步数。

输入样例：
3
输出样例：
5
AC代码

#include

int main()
{
    int n,cnt=0;
    scanf("%d",&n);
    while(true)
    {
        if(n==1)break;//退出循环条件
        if(n%2==0)
        {
            n/=2;
            cnt++;
        }else
        {
            n=(3*n+1)/2;
            cnt++;
        }
    }
    printf("%d",cnt);
    return 0;
}

2、1032 挖掘机技术哪家强 (20 分)

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

输入格式：
输入在第 1 行给出不超过 10
5
的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

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

输入样例：
6
3 65
2 80
1 100
2 70
3 40
3 0
输出样例：
2 150
AC代码

#include

int main()
{
    int n;
    scanf("%d",&n);
    int no,score;//编号、成绩
    int s[100010]={0};//关键，数组初始化方式，数组大小设置为最大数据量+10
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&no,&score);
        s[no]+=score;//对应编号，分数累加
    }
    int index=1;//最高分编号
    int max=-1;//最高分
    for(int i=1;i<=n;i++)
    {
        if(s[i]>max)
        {
            max=s[i];
            index=i;
        }
    }
    printf("%d %d\n",index,max);
    return 0;
}

二、查找元素 1、codeup1934 找x

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

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

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

样例输入
4
1 2 3 4
3
样例输出
2

#include
 
const int maxn=210;//定义数组大小
int a[maxn];//存放元素
int main()
{
    int n,x;
    while(scanf("%d",&n)!=EOF)//测试数据有多组，一组一组处理
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        scanf("%d",&x);
        int index;
        for(index=0;index<n;index++)
        {
            if(a[index]==x)
            {
                printf("%d\n",index);
                break;
            }
        }
        //遍历完都未找到
        if(index==n)printf("-1\n");
    }
    return 0;
}

2、统计同成绩学生人数

题目描述
读入N名学生的成绩，将获得某一给定分数的学生人数输出。

输入
测试输入包含若干测试用例，每个测试用例的格式为

第1行：N
第2行：N名学生的成绩，相邻两数字用一个空格间隔。
第3行：给定分数

当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

输出
对每个测试用例，将获得给定分数的学生人数输出。

样例输入 Copy
4
70 80 90 100
80
3
65 75 85
55
5
60 90 90 90 85
90
0
样例输出 Copy
1
0
3

#include
const int maxn=1010;
int a[maxn];//定义数组存储成绩
int main()
{
    int N;
    while(scanf("%d",&N),N)//当读到N=0时输入结束
    {
        for(int i=0;i<N;i++)
        {
            scanf("%d",&a[i]);
        }
        int cnt=0;//计数器
        int target;//记录给定分数
        scanf("%d",&target);
        for(int i=0;i<N;i++)
        {
            if(a[i]==target)
            {
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

关于输入测试用例的一些方式可以参考另一篇博客
黑盒测试-数据的读取与输出方式

三、图形输出

方法有两种：

1. 通过找规律，直接进行输出；
2. 定义一个二维字符数组，通过规律填充之，然后输出整个二维数组。

1、1036 跟奥巴马一起编程 (15 分)

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

输入格式：
输入在一行中给出正方形边长 N（3≤N≤20）和组成正方形边的某种字符 C，间隔一个空格。

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

输入样例：
10 a
输出样例：

aaaaaaaaaa
a        a
a        a
a        a
aaaaaaaaaa

注意点：
1、除%c外，其他格式控制符（如%d）的输入是以空白符为结束标志。
所以scanf(“%d %c”,&col,&c);两个格式控制符之间就加上空格
2、整数除以2进行四舍五入的 *** 作可以通过判断它是奇数（除2加1），偶数（除2）来解决，避免浮点数的介入。
3、把图形分为几个部分，分别按规律输出。

#include

int main()
{
    int row,col;//行、列数
    char c;
    scanf("%d %c",&col,&c);//列数是给定的边长
    //计算行数
    if(col%2==0)row=col/2;
    else row=col/2+1;
    //分为三个部分输出
    //1、第一行
    for(int i=0;i<col;i++)
    {
        printf("%c",c);
    }
    printf("\n");//换行
    //2、第2至row-1行
    for(int i=2;i<row;i++)
    {
        printf("%c",c);//每行的第一个字符
        for(int j=0;j<col-2;j++)
        {
            printf(" ");//每行的col-2个空格
        }
        printf("%c\n",c);//每行的最后一个字符,记得换行
    }
    //3、第row行
    for(int i=0;i<col;i++)
    {
        printf("%c",c);
    }
    return 0;
}

四、日期处理

需要处理平年（2月28天）、闰年（29天）；大月（31天）、小月（30天）。
1、闰年的判断：

年份是4的倍数而不是100的倍数；
或者年份是400的倍数；

bool isLeap(int year)
{
    return (year%4==0&&year%100!=0)||(year%400==0);
}

2、大月与小月
1、3、5、7、8、10、12是大月31天
定义一个二维数组来存放每个月的天数，第二维为0时表示平年，1表示闰年。

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}
};

1、codeup1928 日期差值

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

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

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

样例输入
20130101
20130105
样例输出
5

#include
 
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}
};
bool isLeap(int year)
{
    return (year%4==0&&year%100!=0)||(year%400==0);
}
int main()
{
    int time1,y1,m1,d1;
    int time2,y2,m2,d2;
    while(scanf("%d%d",&time1,&time2)!=EOF)//多组测试数据
    {
        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;
        int ans=1;//记录结果日期差
        //第一个日期未达到第二个日期时循环
        while(y1<y2||m1<m2||d1<d2)
        {
            d1++;//天数加1
            if(d1==month[m1][isLeap(y1)]+1)//满当月天数
            {
                m1++;//日期变为下个月1号
                d1=1;
            }
            if(m1==13)//月份满12
            {
                y1++;//日期变为下一年一月
                m1=1;
            }
            ans++;//循环一次，日期差累加
        }
        printf("%d\n",ans);
    }
    return 0;
}

2、打印日期

题目描述
给出年分m和一年中的第n天，算出第n天是几月几号。

输入
输入包括两个整数y(1<=y<=3000)，n(1<=n<=366)。

输出
可能有多组测试数据，对于每组数据，按 yyyy-mm-dd的格式将输入中对应的日期打印出来。

样例输入
2013 60
2012 300
2011 350
2000 211
样例输出
2013-03-01
2012-10-26
2011-12-16
2000-07-29

#include
 
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
    int y,n;
    while(scanf("%d%d",&y,&n)!=EOF)
    {
        if((y%4==0&&y%100!=0)||(y%400==0))
        {
            month[2]=29;//闰年    
        }else
        {
            month[2]=28;//平年
        }
        int m=1;
        while(n>month[m])//天数大于当前月份的天数
        {
            n-=month[m++];//就要减去当前月份天数，然后月份加1
        }
        printf("%04d-%02d-%02d\n",y,m,n);//格式输出，高位不足补0
    }
    return 0;
}

关于格式控制可以参考这篇博文
scanf、printf的输入输出（格式控制符）

五、进制转换

对一个P进制的数，要转换为Q进制，需要分为两步：
1、将P进制数x转换为十进制数y

十进制数y=d1d2……dn,可以写成
y=d1*10^(n-1)+d2*10^(n-2)+……+dn
同样，P进制数x=a1a2……an，写成这个形式之后使用十进制的加法和乘法，
就可以转换成十进制数y=a1*P^(n-1)+a2*P^(n-2)+……+an

这个公式可以用循环实现

int y=0,product=1;//product在循环中会不断乘P，得到1、P、p^2……
while(x!=0)
{
	y=y+(x%10)*product;//x%10获取个位数字
	x=x/10;
	product=product*P；
}

2、将十进制数y转换成Q进制数z
采用“除基取余法”，基是Q进制，就是每次将待转换数除以Q，然后将得到的余数作为低位存储，而商继续除以Q进行上面的 *** 作，最后当商为0时，将所有位从高到低输出即得到z。
例子：将十进制数11转换为二进制数

11/2=5		11%2=1
5/2=2		5%2=1
2/2=1		2%2=0
1/2=0 		1%2=1
将余数从后往前输出，得到11的二进制数1011

实现代码：将十进制数y转换成Q进制数，结果存放于数组z。

int z[40],num=0;
do{
	z[num++]=y%Q;
	y=y/Q;
}while(y!=0)；

1、1022 D进制的A+B

输入两个非负 10 进制整数 A 和 B (≤2^30−1)，输出 A+B 的 D (1

输入格式：
输入在一行中依次给出 3 个整数 A、B 和 D。

输出格式：
输出 A+B 的 D 进制数。

输入样例：
123 456 8
输出样例：
1103

#include
int main()
{
    int a,b,d;
    scanf("%d%d%d",&a,&b,&d);
    int sum=a+b;
    int ans[31],num=0;//ans存放D进制数的每一位
    do{
        ans[num++]=sum%d;
        sum/=d;
    }while(sum!=0);
    for(int i=num-1;i>=0;i--)
    {
        printf("%d",ans[i]);
    }
    return 0;
}

基本数据类型的范围

2、进制转换问题

题目描述
大家都知道，计算机中是以二进制存储的！但是在现实生活中，我们遇到过各种各样的进制情况，
我们接触得最多的就是十进制，不过，生活中还存在各种进制计数的情况。例如：一个星期七天，是7进制。一年十二个月，是12进制等等。小明最近在学c语言，熟悉了c语言中的各种进制转换问题，所以就尝试着各种进制转换的程序。

现在他想写一个程序，就是把一个无符号数n,转化成在b进制下的表示。例如： n为10，b为2，则转化后为1010。又如：n为10，b为16，则转化后为0xA.

输入
文件包含T组测试样例，第一行为数字T，第二行开始，输入两个数,分别为n,b。n表示要转化的数，b表示b进制。运行到文件结尾（0 <= n <= 1000000000,2<=b<=16).
输出
输出n在b进制下的表示。注意：如b为16输入时记得加上0X,字母都是以大写的形式）
样例输入
4
10 2
10 16
100 7
1000000000 16
样例输出
1010
0XA
202
0X3B9ACA00
本地测试成功，但提交显示答案错误

#include
using namespace std;
int main()
{
    int T,n,b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&b);
        int ans[31],num=0;
        do{
            ans[num++]=n%b;
            n/=b;  
        }while(n!=0);
            
        if(b==16)
        {
            char hex[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
            cout<<"0X";
            for(int i=num-1;i>=0;i--)
            {
                int m=ans[i];
                cout<<hex[m];
            }
        }else
        {
          for(int i=num-1;i>=0;i--)
          {
              printf("%d",ans[i]);
          }
        
        }
        cout<<endl;
    }
    return 0;
}

六、字符串处理

注意输入输出格式

1、codeup5901 回文串

回文串就是正读和反读都一样的字符串，因此只需要遍历字符串的前一半，不需要到i==length/2,如果出现str[i]!=str[len-1-i]，说明不是回文串。

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

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

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

样例输入
12321
样例输出
YES

#include
#include
#include
const int maxn=256;
bool judge(char str[])
{
    int len=strlen(str);
    for(int i=0;i<len/2;i++)
    {
        if(str[i]!=str[len-1-i])//只需枚举前一半字符
        {
            return false;
        }
    }
    return true;
}
int main()
{
    char str[maxn];
    while(scanf("%s",str)!=EOF)
    {
        bool flag=judge(str);
        if(flag==true)
        {
            printf("YES\n");
        }else
        {
            printf("NO\n");
        }
    }
    return 0;
}

2、1009 说反话

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

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

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

输入样例：
Hello World Here I Come
输出样例：
Come I Here World Hello
做法一C++

#include

int  main()
{
    int num=0;//单词个数
    char ans[90][90];//char型字符串
    //读入每一个单词，%s以空白和换行作为读入结束标志，一直读到文件尾
    while(scanf("%s",ans[num])!=EOF)
    {
        num++;
    }
    //逆序输出
    for(int i=num-1;i>=0;i--)
    {
        printf("%s",ans[i]);
        if(i>0)printf(" ");//最后一个单词后面没有空格
    }
    return 0;
}

做法二C语言

#include
#include
int  main()
{
    char str[90];
    //使用gets函数读入一整行，本来使用C++的，但是编译出错，猜测规范不一样
    //所以换成C语言就通过了
    gets(str);
    int len=strlen(str);
    int r=0,h=0;//行、列
    char ans[90][90];//ans[0]~ans[r]存放单词
    //一个一个字符先判断再存放
    for(int i=0;i<len;i++)
    {
        if(str[i]!=' ')//不是空格
        {
            ans[r][h++]=str[i];
        }else
        {
        //是空格说明一个单词结束，末尾要加结束符[
            ans]r[]h=';'++;
            r=0
            h;}}
        for
    (
    int=; i0r;i>=--)iprintf(
    {
        "%s",[]ans)i;if(
        0)i>printf(" ");}return
    0
    ; }import
.

做法三Java正则表达式

. java*util;publicclass

Main public static{

    void main ( String[] args)String;
    {
        Scanner s=
        new inScanner( System.);in=.
        snextLinein();String[
        ] ans=.splits("\s+");//正则表达式，匹配空格for(
        int=. i-ans1length;0;i>=--)iSystem.
        {
            .printout([]ans)i;if(
            0)i>System.{
                .printout(' ');}}
            }
        }
    

关于Java的正则表达式，可以参考
正则表达式相关知识