PTA基础编程题目集

Posted on | Edited on | In ,
| 62k | 8:35

Intro

此Blog用来记录自己的”PTA基础编程题目集之旅(受虐)”。
每道题目包含输入(输出)样例、输入(输出)说明、思路分析及得到AC的源码。
所有AC代码已上传到GitHub上，点击PTA-Basical-Programming-problem-set即可获取。

Programming

7-1 厘米换算英尺英寸

如果已知英制长度的英尺$foot$和英寸$inch$的值，那么对应的米是$(foot+inch/12)×0.3048$。现在，如果用户输入的是厘米数，那么对应英制长度的英尺和英寸是多少呢？别忘了1英尺等于12英寸。

Input Specification

输入在一行中给出1个正整数，单位是厘米。

Output Specification

在一行中输出这个厘米数对应英制长度的英尺和英寸的整数值，中间用空格分开。

Sample Input & Sample Output

  • Input 1:
    170
  • Output 1:
    5 6

Analysis

这道题目乍一看挺简单的，其实也有点绕(题目有点迷😒)。首先，要明确题目需要我们得到的结果是：给出的厘米对应换算为英尺、英寸的长度，也就是说，存在这样一个关系：$170CM≈5foot6inch$(题目只要求整数)，就好比是$103=20×5+3$，而我们要的值就是这个5和3。明白这个之后，就会发现，单纯的将$1foot=12inch$这个条按题目给的方程带入计算是得不出结果的，那么可以先求大的单位($foot$)的值，那么小单位($inch$)的值就是剩下的差了。接下来，还得找$foot$和$CM$的数值关系(这里也可以直接百度)，依据$(foot+inch/12)×0.3048$，这个式子计算结果的单位是$M$，而左边$(foot+inch/12)$的单位是$foot$，所以就可以知道：$1foot=30.48CM$，这样我们就可以直接算出正确的$foot$值了。

Code

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int foot,inch,centimeters;
    scanf("%d", &centimeters);
    // centimeters = 170;
    foot = centimeters / 30.48;
    inch = centimeters / 2.54 - 12*foot;
    printf("%d %d\n", foot, inch);
    return 0;
}

7-2 然后是几点

有时候人们用四位数字表示一个时间，比如1106表示11点零6分。现在，你的程序要根据起始时间和流逝的时间计算出终止时间。
读入两个数字，第一个数字以这样的四位数字表示当前时间，第二个数字表示分钟数，计算当前时间经过那么多分钟后是几点，结果也表示为四位数字。当小时为个位数时，没有前导的零，即5点30分表示为530。注意，第二个数字表示的分钟数可能超过60，也可能是负数。

Input Specification

输入在一行中给出2个整数，分别是四位数字表示的起始时间、以及流逝的分钟数，其间以空格分隔。注意：在起始时间中，当小时为个位数时，没有前导的零，即5点30分表示为530；流逝的分钟数可能超过60，也可能是负数。

Output Specification

输出四位数字表示的终止时间。题目保证起始时间和终止时间在同一天内。

Sample Input & Sample Output

  • Input 1:
    1120 110
  • Output 1:
    1310

Analysis

简单题，求出总的分钟值，然后求出小时的值，在按照题目要求输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int start_time,waste_time;
    scanf("%d %d", &start_time, &waste_time);
    // start_time = 1120; waste_time = 110;
    int hours,minutes;
    minutes = start_time/100*60 + start_time%100 + waste_time;
    hours = minutes/60;
    minutes -= hours*60;
    printf("%d\n", hours*100+minutes);
    return 0;
}

7-3 逆序的三位数

程序每次读入一个正3位数，然后输出按位逆序的数字。注意：当输入的数字含有结尾的0时，输出不应带有前导的0。比如输入700，输出应该是7。

Input Specification

每个测试是一个3位的正整数。

Output Specification

输出按位逆序的数。

Sample Input & Sample Output

  • Input 1:
    123
  • Output 1:
    321

Analysis

这道题目很简单，考察数位拆分，在题目告诉已知3位数的情况下，可以直接进行数位拆分(一般题目都不会给输入数字的位数，而只给范围)；并且题目也已经给出了要注意的地方：700逆序后不能是007。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    // n=700;
    int units,tens,hundred;
    units=n%10;
    tens=n/10%10;
    hundred=n/100;
    printf("%d\n", units*100+tens*10+hundred);
    return 0;
}

7-4 BCD解密

BCD数是用一个字节来表达两位十进制的数，每四个比特表示一位。所以如果一个BCD数的十六进制是0x12，它表达的就是十进制的12。但是小明没学过BCD，把所有的BCD数都当作二进制数转换成十进制输出了。于是BCD的0x12被输出成了十进制的18了！
现在，你的程序要读入这个错误的十进制数，然后输出正确的十进制数。提示：你可以把18转换回0x12，然后再转换回12。

Input Specification

输入在一行中给出一个$[0, 153]$范围内的正整数，保证能转换回有效的BCD数，也就是说这个整数转换成十六进制时不会出现A-F的数字。

Output Specification

输出对应的十进制数。

Sample Input & Sample Output

  • Input 1:
    18
  • Output 1:
    12

Analysis

简单题，题目给的提示很明显，单独出去十进制数的个位和十位后，直接组合计算即可得到。

Code

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int BCD;
    scanf("%d", &BCD);
    // BCD=18;
    int units,tens;
    units=BCD%16;
    tens=BCD/16;
    printf("%d\n", tens*10+units);
    return 0;
}

7-5 表格输出

本题要求编写程序，按照规定格式输出表格。

Input Specification

本题目没有输入。

Output Specification

要求严格按照给出的格式输出下列表格：

1
2
3
4
5
6
7
8
9
------------------------------------
Province      Area(km2)   Pop.(10K)
------------------------------------
Anhui         139600.00   6461.00
Beijing        16410.54   1180.70
Chongqing      82400.00   3144.23
Shanghai        6340.50   1360.26
Zhejiang      101800.00   4894.00
------------------------------------

Analysis

送分题，直接原样输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main(int argc, char const *argv[])
{
    printf("------------------------------------\n");
    printf("Province      Area(km2)   Pop.(10K)\n"); 
    printf("------------------------------------\n");
    printf("Anhui         139600.00   6461.00\n");
    printf("Beijing        16410.54   1180.70\n");
    printf("Chongqing      82400.00   3144.23\n");
    printf("Shanghai        6340.50   1360.26\n");
    printf("Zhejiang      101800.00   4894.00\n");
    printf("------------------------------------\n");
    return 0;
}

7-6 混合类型数据格式化输入

本题要求编写程序，顺序读入浮点数1、整数、字符、浮点数2，再按照字符、整数、浮点数1、浮点数2的顺序输出。

Input Specification

输入在一行中顺序给出浮点数1、整数、字符、浮点数2，其间以1个空格分隔。

Output Specification

在一行中按照字符、整数、浮点数1、浮点数2的顺序输出，其中浮点数保留小数点后2位。

Sample Input & Sample Output

  • Input:
    2.12 88 c 4.7
  • Output:
    c 88 2.12 4.70

Analysis

按题目要求输入输出即可。

Code

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main(int argc, char const *argv[])
{
    float a1,a2;
    int b;
    char c;
    scanf("%f %d %c %f", &a1, &b, &c, &a2);
    printf("%c %d %.2f %.2f\n", c, b, a1, a2);
    return 0;
}

7-7 12-24小时制

编写一个程序，要求用户输入24小时制的时间，然后显示12小时制的时间。

Input Specification

输入在一行中给出带有中间的:符号（半角的冒号）的24小时制的时间，如12:34表示12点34分。当小时或分钟数小于10时，均没有前导的零，如5:6表示5点零6分。
提示：在scanf的格式字符串中加入:，让scanf来处理这个冒号。

Output Specification

在一行中输出这个时间对应的12小时制的时间，数字部分格式与输入的相同，然后跟上空格，再跟上表示上午的字符串AM或表示下午的字符串PM。如5:6 PM表示下午5点零6分。注意，在英文的习惯中，中午12点被认为是下午，所以24小时制的12:00就是12小时制的12:0 PM；而0点被认为是第二天的时间，所以是0:0 AM。

Sample Input & Sample Output

  • Input:
    21:11
  • Output:
    9:11 PM

Analysis

根据输出格式进行输出即可，注意中午12点被认为是PM；输入只需注意:即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int hours,minutes;
    scanf("%d:%d", &hours, &minutes);
    // hours = 21, minutes = 11;
    if(hours == 12){
        printf("%d:%d PM\n", hours, minutes);
    }else if(hours < 12){
        printf("%d:%d AM\n", hours, minutes);
    }else{
        printf("%d:%d PM\n", hours-12, minutes);
    }
    return 0;
}

7-8 超速判断

模拟交通警察的雷达测速仪。输入汽车速度，如果速度超出60 mph，则显示Speeding，否则显示OK。

Input Specification

输入在一行中给出1个不超过500的非负整数，即雷达测到的车速。

Output Specification

在一行中输出测速仪显示结果，格式为：Speed: V - S，其中V是车速，S是Speeding、或者是OK。

Sample Input & Sample Output

  • Input 1:
    40
  • Output 1:
    Speed: 40 - OK
  • Input 2:
    75
  • Output 2:
    Speed: 75 - Speeding

Analysis

根据题目要求直接输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int speed;
    scanf("%d", &speed);
    // speed=75;
    if(speed > 60){
        printf("Speed: %d - Speeding\n", speed);
    }else{
        printf("Speed: %d - OK\n", speed);
    }
    return 0;
}

7-9 用天平找小球

三个球A、B、C，大小形状相同且其中有一个球与其他球重量不同。要求找出这个不一样的球。

Input Specification

输入在一行中给出3个正整数，顺序对应球A、B、C的重量。

Output Specification

在一行中输出唯一的那个不一样的球。

Sample Input & Sample Output

  • Input:
    1 1 2
  • Output:
    C

Analysis

根据题目条件，如果要输出唯一的那个不一样的球，其实就只有三种情况，直接输出就好。

Code

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int main(int argc, char const *argv[])
{
    int A,B,C;
    scanf("%d %d %d", &A, &B, &C);
    // A=1, B=1, C=2;
    if(A != B && A != C) printf("A\n");
    if(B != A && B != C) printf("B\n");
    if(C != A && C != B) printf("C\n");
    return 0;
}

7-10 计算工资

某公司员工的工资计算方法如下：一周内工作时间不超过40小时，按正常工作时间计酬；超出40小时的工作时间部分，按正常工作时间报酬的1.5倍计酬。员工按进公司时间分为新职工和老职工，进公司不少于5年的员工为老职工，5年以下的为新职工。新职工的正常工资为30元/小时，老职工的正常工资为50元/小时。请按该计酬方式计算员工的工资。

Input Specification

输入在一行中给出2个正整数，分别为某员工入职年数和周工作时间，其间以空格分隔。

Output Specification

在一行输出该员工的周薪，精确到小数点后2位。

Sample Input & Sample Output

  • Input 1:
    5 40
  • Output 1:
    2000.00
  • Input 2:
    3 50
  • Output 2:
    1650.00

Analysis

根据题目条件，针对不同情况计算工资即可，实质为分段函数求值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int years,hours;
    float wage;
    scanf("%d %d", &years, &hours);
    // years=3, hours=50;
    if(years >= 5){
        if(hours > 40){
            wage = 50*40 + 1.5*50*(hours - 40);
        }else{
            wage = 50*hours;
        }
    }else{
        if(hours > 40){
            wage = 30*40 + 1.5*30*(hours - 40);
        }else{
            wage = 30*hours;
        }
    }
    printf("%.2f\n", wage);
    return 0;
}

7-11 分段计算居民水费

为鼓励居民节约用水，自来水公司采取按用水量阶梯式计价的办法，居民应交水费$y$（元）与月用水量$x$（吨）相关：当$x$不超过15吨时，$y=4x/3$；超过后，$y=2.5x−17.5$。请编写程序实现水费的计算。

Input Specification

输入在一行中给出非负实数$x$。

Output Specification

在一行输出应交的水费，精确到小数点后2位。

Sample Input & Sample Output

  • Input 1:
    12
  • Output 1:
    16.00
  • Input 2:
    16
  • Output 2:
    22.50

Analysis

根据题目条件，针对不同情况计算水费即可，实质为分段函数求值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int x;
    scanf("%d", &x);
    // x=16;
    float water_fee;
    if(x <= 15){
        water_fee = 4.0*x/3;
    }else{
        water_fee = 2.5*x - 17.5;
    }
    printf("%.2f\n", water_fee);
    return 0;
}

7-12 两个数的简单计算器

本题要求编写一个简单计算器程序，可根据输入的运算符，对2个整数进行加、减、乘、除或求余运算。题目保证输入和输出均不超过整型范围。

Input Specification

输入在一行中依次输入操作数1、运算符、操作数2，其间以1个空格分隔。操作数的数据类型为整型，且保证除法和求余的分母非零。

Output Specification

当运算符为+、-、*、/、%时，在一行输出相应的运算结果。若输入是非法符号（即除了加、减、乘、除和求余五种运算符以外的其他符号）则输出ERROR。

Sample Input & Sample output

  • Input 1:
    -7 / 2
  • Output 1:
    -3
  • Input 2:
    3 & 6
  • Output 2:
    ERROR

Analysis

针对不同的情况使用switch语句分别处理即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int a, b;
    char c;
    scanf("%d %c %d", &a, &c, &b);
    switch(c){
        case '+': printf("%d\n", a + b);break;
        case '-': printf("%d\n", a - b);break;
        case '*': printf("%d\n", a * b);break;
        case '/': printf("%d\n", a / b);break;
        case '%': printf("%d\n", a % b);break;
        default : printf("ERROR\n");
    }
    return 0;
}

7-13 日K蜡烛图

股票价格涨跌趋势，常用蜡烛图技术中的K线图来表示，分为按日的日K线、按周的周K线、按月的月K线等。以日K线为例，每天股票价格从开盘到收盘走完一天，对应一根蜡烛小图，要表示四个价格：开盘价格Open（早上刚刚开始开盘买卖成交的第1笔价格）、收盘价格Close（下午收盘时最后一笔成交的价格）、中间的最高价High和最低价Low。

如果Close<Open，表示为BW-Solid（即“实心蓝白蜡烛”）；如果Close>Open，表示为R-Hollow（即“空心红蜡烛”）；如果Open等于Close，则为R-Cross（即“十字红蜡烛”）。如果Low比Open和Close低，称为Lower Shadow（即“有下影线”），如果High比Open和Close高，称为Upper Shadow（即“有上影线”）。请编程序，根据给定的四个价格组合，判断当日的蜡烛是一根什么样的蜡烛。

Input Specification

输入在一行中给出4个正实数，分别对应Open、High、Low、Close，其间以空格分隔。

Output Specification

在一行中输出日K蜡烛的类型。如果有上、下影线，则在类型后加上with 影线类型。如果两种影线都有，则输出with Lower Shadow and Upper Shadow。

Sample Input & Sample output

  • Input 1:
    5.110 5.250 5.100 5.105
  • Output 1:
    BW-Solid with Lower Shadow and Upper Shadow
  • Input 2:
    5.110 5.110 5.110 5.110
  • Output 2:
    R-Cross
  • Input 3:
    5.110 5.125 5.112 5.126
  • Output 3:
    R-Hollow

Analysis

先判断图形类型，在判断是否包含影线；按照下面的代码的思路，需要将既有下影线又有上影线的情况放在第一位进行判断。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
int main(int argc, char const *argv[])
{
    float open,high,low,close;
    scanf("%f %f %f %f", &open, &high, &low, &close);
    if(close < open){
        printf("BW-Solid");
    }else if(close == open){
        printf("R-Cross");
    }else{
        printf("R-Hollow");
    }
    if(low < open && low < close && high > open && high >close){
        printf(" with Lower Shadow and Upper Shadow\n");

    }else if(high > open && high >close){
        printf(" with Upper Shadow\n");
    }else if(low < open && low < close){
        printf(" with Lower Shadow\n");
    }else{
        printf("\n");
    }
    return 0;
}

7-14 求整数段和

给定两个整数A和B，输出从A到B的所有整数以及这些数的和。

Input Specification

输入在一行中给出2个整数A和B，其中$−100≤A≤B≤100$，其间以空格分隔。

Output Specification

首先顺序输出从A到B的所有整数，每5个数字占一行，每个数字占5个字符宽度，向右对齐。最后在一行中按Sum=X的格式输出全部数字的和X。

Sample Input & Sample output

  • Input:
    -3 8
  • Output:
    -3 -2 -1 0 1
    2 3 4 5 6
    7 8
    Sum = 30

Analysis

考察格式输出和求和，输出时注意格式即可，最好将数字和换行分开输出。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int A,B,i,sum;
    scanf("%d %d", &A, &B);
    // A=1, B=5;
    for(i=0, sum=0; A<=B; A++, i++)
    {
        if(i%5 == 0 && i != 0) printf("\n");
        printf("%5d", A);
        sum+=A;
    }
    printf("\nSum = %d\n", sum);
    return 0;
}

7-15 计算圆周率

根据下面关系式，求圆周率的值，直到最后一项的值小于给定阈值。
${\pi\over2}=1+{1\over3}+{2!\over{3×5}}+{3!\over{3×5×7}}+{\cdots}+{n!\over{3×5×7×{\cdots}×(2×n+1)}}$

Input Specification

输入在一行中给出小于1的阈值。

Output Specification

在一行中输出满足阈值条件的近似圆周率，输出到小数点后6位。

Sample Input & Sample output

  • Input:
    0.01
  • Output:
    3.132157

Analysis

本题比较直观，但需要细心一点。先分析一下给出的关系式的规律，左边常量，我们只看右边就行；假设右边项数是从1开始的，那么$a_1=1$，$a_2={1\over3}$，$a_3={2!\over3×5}$，…，把$a_1$和$a_2$换个写法就是$a_1
={0!\over1}$、$a_2={1!\over{1×3}}$，这下就可以看出规律了，与后面的通项公式是一致的。如果首项的分子从0开始，那么就无法通过循环自动完成阶乘的计算了（或者单独写一个阶乘函数，这样就能从0开始取值了），所以我们直接从$a_1$开始计算，让$\pi$的初始值就为1.0；输出结果时，别忘记了要乘上2倍。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main(int argc, char const *argv[])
{
    float pi=1.0,denominator=3.0,member=1.0,each_item=0.0,i=2.0;
    float threshold;
    scanf("%f", &threshold);
    // threshold=0.01;
    do{
        each_item = member/denominator;
        pi+=each_item;
        member*=i;
        denominator*=(2*i+1);
        i++;
    }while(each_item > threshold);
    printf("%.6f\n", 2*pi);
    return 0;
}

7-16 求符合给定条件的整数集

给定不超过6的正整数A，考虑从A开始的连续4个数字。请输出所有由它们组成的无重复数字的3位数。

Input Specification

输入在一行中给出A。

Output Specification

输出满足条件的的3位数，要求从小到大，每行6个整数。整数间以空格分隔，但行末不能有多余空格。

Sample Input & Sample output

  • Input:
    2
  • Output:
    234 235 243 245 253 254
    324 325 342 345 352 354
    423 425 432 435 452 453
    523 524 532 534 542 543

Analysis

按照题目的意思，将需要输出的三位数，分别输出即可；也可以直接输出一个百位数，但是那样需要计算，会稍微麻烦一点。按照下面的代码，当不同位的数字存在相同的时候，就用continue;语句跳出本次循环，i==j的判断也可以在第三层循环内做，即：改为k==j || k==i || i==j，但当i==j的时候就会运行多次判断了。

Code

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 <stdio.h>
int main(int argc, char const *argv[])
{
    int A,i,j,k,count;
    scanf("%d", &A);
// 	A=2;
    count=0;
    for(i=A; i<A+4; i++)
    {
        for(j=A; j<A+4; j++){
            if(i == j) continue;
            else{
                for(k=A; k<A+4; k++)
                {
                    if(k==j || k==i) continue;
                    else{
                        printf("%d%d%d", i, j, k);
                        count++;
                        if(count%6 == 0) printf("\n");
                        else printf(" ");
                    }
                }
            }
        }
    }
    return 0;
}

7-17 爬动的蠕虫

一条蠕虫长1寸，在一口深为N寸的井的底部。已知蠕虫每1分钟可以向上爬U寸，但必须休息1分钟才能接着往上爬。在休息的过程中，蠕虫又下滑了D寸。就这样，上爬和下滑重复进行。请问，蠕虫需要多长时间才能爬出井？
这里要求不足1分钟按1分钟计，并且假定只要在某次上爬过程中蠕虫的头部到达了井的顶部，那么蠕虫就完成任务了。初始时，蠕虫是趴在井底的（即高度为0）。

Input Specification

输入在一行中顺序给出3个正整数N、U、D，其中D<U，N不超过100。

Output Specification

在一行中输出蠕虫爬出井的时间，以分钟为单位。

Sample Input & Sample output

  • Input:
    12 3 1
  • Output:
    11

Analysis

找规律，先要明确”蚯蚓”整个爬行的过程，在第一分钟会爬行U寸，第二分钟会下滑D寸，第二分钟完后，蚯蚓一共的爬行距离就是U-D，第三分钟的时候，蚯蚓爬行U寸，总距离是2*U-D，第四分钟就是2*U-2*D…。可以发现，U和D的系数之和就是当前的时刻，找到这个规律之后就好办了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int N,U,D;
    scanf("%d%d%d", &N, &U, &D);
    // N=12, U=3, D=1;
    int i,j,times;
    for(i=1, j=0; N<=100; i++, j++)
    {
        if(i*U - j*D >= N){
            times = i+j;
            break;
        }
    }
    printf("%d\n", times);
    return 0;
}

7-18 二分法求多项式单根

二分法求函数根的原理为：如果连续函数$f(x)$在区间$[a,b]$的两个端点取值异号，即$f(a)f(b)<0$，则它在这个区间内至少存在1个根$r$，即$f(r)=0$。
二分法的步骤为：
检查区间长度，如果小于给定阈值，则停止，输出区间中点$(a+b)/2$；否则
如果$f(a)f(b)<0$，则计算中点的值$f((a+b)/2)$；
如果$f((a+b)/2)$正好为0，则$(a+b)/2$就是要求的根；否则
如果$f((a+b)/2)$与$f(a)$同号，则说明根在区间$[(a+b)/2,b]$，令$a=(a+b)/2$，重复循环；
如果$f((a+b)/2)$与$f(b)$同号，则说明根在区间$[a,(a+b)/2]$，令$b=(a+b)/2$，重复循环。
本题目要求编写程序，计算给定3阶多项式$f(x)=a_3x^3+a_2x^2+a_1x+a_0$在给定区间$[a,b]$内的根。

Input Specification

输入在第1行中顺序给出多项式的4个系数$a_3$、$a_2$、$a_1$、$a_0$，在第2行中顺序给出区间端点$a$和$b$。题目保证多项式在给定区间内存在唯一单根。

Output Specification

在一行中输出该多项式在该区间内的根，精确到小数点后2位。

Sample Input & Sample Output

  • Input:
    3 -1 -3 1
    -0.5 0.5
  • Output:
    0.33

Analysis

二分法求多项式单根，所依据的原理其实是函数的零点性质：函数零点两边的函数值是异号的，所以零点两边函数值的乘积小于0。明白这个原理之后，我们按照题目给的算法进行计算即可；既然题目已经给出了函数式，可以直接封装成一个专门求值的函数，函数的系数就用全局变量来保存即可，这样代码的主体就很清晰；f(left)和f(right)这两个函数值为0的情况是单独的，并不能用if-else组成对立关系，注意题目对精度的要求是小数点后2位，所以左端点和右端点的差值要大于0.01，若没有这个条件，提交时会超时。

Code

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
28
29
30
31
32
33
#include <stdio.h>
float a3,a2,a1,a0;
float Cal_polynomial(float n);
int main(int argc, char const *argv[])
{
    float left,right,mid;
    scanf("%f %f %f %f %f %f", &a3, &a2, &a1, &a0, &left, &right);
    while(Cal_polynomial(left) * Cal_polynomial(right) <= 0 && (right-left) > 0.01)
    {
        if(Cal_polynomial(left) == 0){
            printf("%.2f\n", left);
            return 0;
        }
        if(Cal_polynomial(right) == 0){
            printf("%.2f\n", right);
            return 0;
        }
        mid=(left+right)/2;
        if(Cal_polynomial(left) * Cal_polynomial(mid) > 0){
            left = mid;
        }else{
            right = mid;
        }
    }
    printf("%.2f\n", (right+left)/2);
    return 0;
}
float Cal_polynomial(float n)
{
    float ret=0.0;
    ret = a3*n*n*n + a2*n*n + a1*n + a0;
    return ret;
}

7-19 支票面额

一个采购员去银行兑换一张y元f分的支票，结果出纳员错给了f元y分。采购员用去了n分之后才发觉有错，于是清点了余额尚有2y元2f分，问该支票面额是多少？

Input Specification

输入在一行中给出小于100的正整数n。

Output Specification

在一行中按格式y.f输出该支票的原始面额。如果无解，则输出No Solution。

Sample Input & Sample Output

  • Input 1:
    23
  • Output 1:
    25.51
  • Input 2:
    22
  • Output 2:
    No Solution

Analysis

本题乍一看挺懵逼的😓，其实是道数学题。多读几遍题目，可以列出方程：100*f+y-n=200*y+2*f(这里的元、分应该就是RMB中的单位了)，化简得：98*f-199*y=n，依题意，n<100且n>0，说明98*f-199*y>0，这里需要放缩一下，即：98*f-199*y ≈ 100*f-200*y = f-2*y > 0，就是f>2*y了，而f在本题中的单位是分，所以0<f<100(能想到的唯一解释…)，所以就得到：0<f<100, 0<y<50，这就是循环的条件。有点坑爹~

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int y,f,n,flag=0;
    scanf("%d", &n);
    // n=23;
    for(y=0; y<50; y++)
    {
        for(f=0; f<100; f++)
        {
            if(98*f - 199*y == n){
                printf("%d.%d\n", y, f);
                flag=1;
                break;
            }
        }
    }
    if(!flag){
            printf("No Solution\n");
    }
    return 0;
}

7-20 打印九九口诀表

下面是一个完整的下三角九九口诀表：

1
2
3
4
5
6
7
8
9
1*1=1   
1*2=2   2*2=4   
1*3=3   2*3=6   3*3=9   
1*4=4   2*4=8   3*4=12  4*4=16  
1*5=5   2*5=10  3*5=15  4*5=20  5*5=25  
1*6=6   2*6=12  3*6=18  4*6=24  5*6=30  6*6=36  
1*7=7   2*7=14  3*7=21  4*7=28  5*7=35  6*7=42  7*7=49  
1*8=8   2*8=16  3*8=24  4*8=32  5*8=40  6*8=48  7*8=56  8*8=64  
1*9=9   2*9=18  3*9=27  4*9=36  5*9=45  6*9=54  7*9=63  8*9=72  9*9=81

本题要求对任意给定的一位正整数N，输出从11到NN的部分口诀表。

Input Specification

输入在一行中给出一个正整数N（1≤N≤9）。

Output Specification

输出下三角N*N部分口诀表，其中等号右边数字占4位、左对齐。

Sample Input & Sample output

  • Input:
    4
  • Output:
    1
    2
    3
    4
    1*1=1   
    1*2=2   2*2=4   
    1*3=3   2*3=6   3*3=9   
    1*4=4   2*4=8   3*4=12  4*4=16

Analysis

分析一下，九九乘法表的组成，两个值和这两个值的乘积，从这里，应该可以想到双重循环；在仔细观察一下样例，组后的项中的因子等于输入样例的N值的，所以可以推断，因子的值是小于等于N的；另外，还可以发现，第二个因子的值是小于等于第一个因子的值的；按照以上的思路，在注意一下输出格式，就可以拿下这道题了，注意输出的格式，换行可以放在第二层循环内执行，条件改为j == i即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int N,i,j;
    scanf("%d", &N);
    // N=4;
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=i; j++){
            printf("%d*%d=%-4d", j, i, i*j);
        }
        if(j-1 == i){
            printf("\n");
        }
    }
    return 0;
}

7-21 求特殊方程的正整数解

本题要求对任意给定的正整数N，求方程$X^2​+Y^2=N$的全部正整数解。

Input Specification

输入在一行中给出正整数N（≤10000）

Output Specification

输出方程$X^2+Y^2=N$的全部正整数解，其中X≤Y。每组解占1行，两数字间以1空格分隔，按X的递增顺序输出。如果没有解，则输出No Solution。

Sample Input & Sample Output

  • Input 1:
    884
  • Output 1:
    10 28
    20 22
  • Input 2:
    11
  • Output 2:
    No Solution

Analysis

此题不难，看题目形式也是道数学题，大致分析一下，N = X^2+Y^2 >= 2*x*y，既有2*x*y <= N <= 10000，化简得xy <= 5000，又知N的最大值是10000，开方是100，而X和Y的平方之和小于等于N，所以X和Y都不大于100；依据题目的要求，需要按照X递增的顺序进行输出，所以直接以Y为最大值，X从最小开始取值就可以了（也有其他做法）。之所以写break;的原因是：在这道题目中，当X和N确定后，Y也是确定的，同理Y和N确定后，X也是确定的了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int N;
    scanf("%d", &N);
//	N=884;
    int X,Y,flag=0;
    for(Y=100; Y>0; Y--)
    {
        for(X=1; X<=Y; X++)
        {
            if(X*X + Y*Y == N && (X*Y) <= 5000){
                printf("%d %d\n", X, Y);
                flag=1;
                break;
            }
        }
    }
    if(!flag){
        printf("No Solution\n");
    }
    return 0;
}

7-22 龟兔赛跑

乌龟与兔子进行赛跑，跑场是一个矩型跑道，跑道边可以随地进行休息。乌龟每分钟可以前进3米，兔子每分钟前进9米；兔子嫌乌龟跑得慢，觉得肯定能跑赢乌龟，于是，每跑10分钟回头看一下乌龟，若发现自己超过乌龟，就在路边休息，每次休息30分钟，否则继续跑10分钟；而乌龟非常努力，一直跑，不休息。假定乌龟与兔子在同一起点同一时刻开始起跑，请问T分钟后乌龟和兔子谁跑得快？

Input Specification

输入在一行中给出比赛时间T（分钟）。

Output Specification

在一行中输出比赛的结果：乌龟赢输出@_@，兔子赢输出^_^，平局则输出-_-；后跟1空格，再输出胜利者跑完的距离。

Sample Input & Sample output

  • Input:
    242
  • Output:
    @_@ 726

Analysis

这道题的难点在如何计算兔子在T时间内跑过的距离。先看乌龟，乌龟在T时间内跑过的距离比较简单，因为乌龟是不会休息的，所以其距离就是其速度和T的乘积；而兔子会休息，并且是每隔10分钟确认比乌龟快后休息，所以，需要在每个以10分钟为时间间隔的时间点进行判断，与之而来的另外一个问题就是兔子不是休息10分钟，而是休息30分钟，所以，还需要一个表示兔子仍然在休息的标志位，这个标志位会在乌龟前进，兔子休息时，自动减少。当减少到0时，兔子会再次确认是否超过乌龟。输出结果时，注意平局的时候也要输出跑完的距离；并且时间要从0时刻开始，即时间区间为$[0,T-1]$，若区间为$[1,T]$，尽管区间长度时一致的，在30分钟时，兔子的距离就是81，乌龟的距离就是90了，但实际上应该是相等的，即平局。

Code

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
28
29
30
31
32
33
34
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int rabbit_dis=0,turtle_dis=0,rabbit_spd=9,turtle_spd=3,T;
    scanf("%d", &T);
    // T=30;
    int i,rabbit_on=1,break_times=0;
    for(i=0; i<T; i++)
    {
        if(i%10 == 0){
            if(rabbit_dis > turtle_dis && break_times == 0){
                rabbit_on=0;
                break_times=30;
            }else{
                rabbit_on=1;
            }
        }
        if(rabbit_on && break_times == 0){
            rabbit_dis+=rabbit_spd;
        }
        turtle_dis+=turtle_spd;
        if(break_times){
            break_times--;
        }
    }
    if(turtle_dis > rabbit_dis){
        printf("@_@ %d\n", turtle_dis);
    }else if(turtle_dis == rabbit_dis){
        printf("-_- %d\n", turtle_dis);
    }else{
        printf("^_^ %d\n", rabbit_dis);
    }
    return 0;
}

7-23 币值转换

输入一个整数（位数不超过9位）代表一个人民币值（单位为元），请转换成财务要求的大写中文格式。如23108元，转换后变成“贰万叁仟壹百零捌”元。为了简化输出，用小写英文字母a-j顺序代表大写数字0-9，用S、B、Q、W、Y分别代表拾、百、仟、万、亿。于是23108元应被转换输出为“cWdQbBai”元。

Input Specification

输入在一行中给出一个不超过9位的非负整数。

Output Specification

在一行中输出转换后的结果。注意“零”的用法必须符合中文习惯。

Sample Input & Sample output

  • Input 1:
    813227345
  • Output 1:
    iYbQdBcScWhQdBeSf
  • Input 2:
    6900
  • Output 2:
    gQjB

Analysis

这道题有点难😑，借鉴了一下ccDLIyy的思路，并修改了其中一些代码。如果本题只是将输入的数字的每一位拆分出来的话，就十分简单，但是还需要按照中文习惯输出这些数字的读法，就比较麻烦了。首先，需要一个数组来单独存放每一位数，因为，如果不这样，就无法对中文习惯进行判断了(即当前位上的数字非0，前一位或者后一位为0的情况下，此时的读法)；按照这个思路，不妨直接用数组建立起数字和字母的映射关系，这样后面调用也方便一些(不得不说，这个想法很高明也很省事)；另外，在写代码之前，先大概分析一下平常我们都这些数字的读法：23108是读作二万三千一百零八，813227345是读作八亿一千三百二十二万七千三百四十五，从这里，可以看出，万是在数字位数大于等于5的时候才会输出，而亿是在数字位数大于等于9的时候才会输出，在每四位内，进行输出的格式字符都是十、百和千，所以，需要根据位数进行不同情况的判断。另外，在下面的代码中对于100000001这种情况输出的结果是一亿零零零一，对于10这种情况输出的结果是一十。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <string.h>
char num2letter[11]="abcdefghij";
char units[4]="QBS";
void exchange(int num[], int n);

int main(int argc, char const *argv[])
{
    char number[10];
    scanf("%s", number);
    int i,len=strlen(number);
    int num[9]={0};
    for(i=0; i<len; i++){
        num[i]=number[i] - '0';
    }
    if(len <= 4){
        exchange(num, len-1);
    }else if(len <= 8){
        exchange(num, len-5);
        printf("W");
        exchange(num+len-4, 3);
    }else{
        printf("%cY", num2letter[num[0]]);
        exchange(num+1, 3);
        if(num[1]!=0 && num[2]!=0 && num[3]!=0 && num[4]!=0){
            printf("W");
        }
        if(num[len-4] == 0){
            printf("%c", num2letter[0]);
        }
        exchange(num+5, 3);
    }
    return 0;
}
void exchange(int num[], int n)
{
    int index = 0;
    while(num[index] == 0){
        index++;
    }
    if(num[index-1] == 0 && index != 0){
        printf("%c", num2letter[0]);
    }
    while(index <= n)
    {
        if(num[index] != 0 && index <= n){
            if(index != n){
                printf("%c%c", num2letter[num[index]], units[4-n-1+index]);
            }else{
                printf("%c", num2letter[num[index]]);
            }
        }else if(num[index] == 0 && num[index+1] != 0 && index <= n-1){
            printf("%c", num2letter[0]);
        }
        index++;
    }
}

7-24 约分最简分式

分数可以表示为分子/分母的形式。编写一个程序，要求用户输入一个分数，然后将其约分为最简分式。最简分式是指分子和分母不具有可以约分的成分了。如6/12可以被约分为1/2。当分子大于分母时，不需要表达为整数又分数的形式，即11/8还是11/8；而当分子分母相等时，仍然表达为1/1的分数形式。

Input Specification

输入在一行中给出一个分数，分子和分母中间以斜杠/分隔，如：12/34表示34分之12。分子和分母都是正整数（不包含0，如果不清楚正整数的定义的话）。
提示：在scanf的格式字符串中加入/，让scanf来处理这个斜杠。

Output Specification

在一行中输出这个分数对应的最简分式，格式与输入的相同，即采用分子/分母的形式表示分数。如5/6表示6分之5。

Sample Input & Sample output

  • Input:
    66/120
  • Output:
    11/20

Analysis

这道题比较简单，只要知道分子/分母约分到最简形式直接除以二者的最大公约数即可。所以，直接求最大公约数即可，使用辗转相除法或更相减损法皆可，递归与否也皆可。

Code

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
#include <stdio.h>
int gcd(int a, int b);
int main(int argc, char const *argv[])
{
    int member,denominator;
    scanf("%d/%d", &member, &denominator);
    // member=66, denominator=120;
    printf("%d/%d\n", member/gcd(member, denominator), denominator/gcd(member, denominator));
    return 0;
}
int gcd(int a, int b)
{
    if(a > b) return gcd(b, a);
    int temp;
    while(a)
    {
        temp=b%a;
        b=a;
        a=temp;
    }
    return b;
    /* other method: use recursion.
	return a==0?b:gcd(b%a, a);
    */
}

7-25 念数字

输入一个整数，输出每个数字对应的拼音。当整数为负数时，先输出fu字。十个数字对应的拼音如下：

1
2
3
4
5
6
7
8
9
10
0: ling
1: yi
2: er
3: san
4: si
5: wu
6: liu
7: qi
8: ba
9: jiu

Input Specification

输入在一行中给出一个整数，如：1234。
提示：整数包括负数、零和正数。

Output Specification

在一行中输出这个整数对应的拼音，每个数字的拼音之间用空格分开，行末没有最后的空格。如yi er san si。

Sample Input & Sample output

  • Input:
    -600
  • Output:
    fu liu ling ling

Analysis

此题不难，只需对注意负数和输出的格式即可；可以直接当作字符处理，也可以用数位拆分的思路来做，可能稍微会麻烦一点；可以使用指针，也可以不使用指针。

Code

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
28
29
30
31
#include <stdio.h>
int main(int argc, char const *argv[])
{
    char num[100];
    scanf("%s", num);
    char *p = num;
    if(*p == '-'){
        printf("fu ");
        p++;
    }
    for(; *p != '\0'; p++)
    {
        switch(*p)
        {
            case '0': printf("ling");break;
            case '1': printf("yi");break;
            case '2': printf("er");break;
            case '3': printf("san");break;
            case '4': printf("si");break;
            case '5': printf("wu");break;
            case '6': printf("liu");break;
            case '7': printf("qi");break;
            case '8': printf("ba");break;
            case '9': printf("jiu");break;
            default: continue;
        }
        if(*(p+1) == '\0') printf("\n");
        else printf(" ");
    }
    return 0;
}

7-26 单词长度

你的程序要读入一行文本，其中以空格分隔为若干个单词，以.结束。你要输出每个单词的长度。这里的单词与语言无关，可以包括各种符号，比如it's算一个单词，长度为4。注意，行中可能出现连续的空格；最后的.不计算在内。

Input Specification

输入在一行中给出一行文本，以.结束
提示：用scanf("%c",...);来读入一个字符，直到读到.为止。

Output Specification

在一行中输出这行文本对应的单词的长度，每个长度之间以空格隔开，行末没有最后的空格。

Sample Input & Sample Output

  • Input:
    It’s great to see you here.
  • Output:
    4 5 2 3 3 4

Analysis

本题不难，对每一个单词的字符进行遍历即可，每次扫描到空格，就跳过，一旦扫描到下一个单词的第一个字母，就输出上一个单词的长度。注意格式，空句子不需要输出0，直接输出\n即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int length=0,flag=0;
    char ch;
    while((ch=getchar()) != '.')
    {
        if(ch != ' '){
            if(length > 0 && flag > 0){
                printf("%d ", length);
                length=0;
            }
            length++;
            flag=0;
        }
        if(ch == ' ') flag++;
    }
    if(length > 0) printf("%d\n", length);
    else printf("0\n");
    return 0;
}

7-27 冒泡法排序

将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。
本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。

Input Specification

输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。

Output Specification

在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。

Sample Input & Sample Output

  • Input:
    6 2
    2 3 5 1 6 4
  • Output:
    2 1 3 4 5 6

Analysis

此题不难，算是帮助熟悉冒泡排序算法的题吧，按照题目给出的算法，使用两层循环，直接进行处理即可。注意，按照题目的要求，在交换两个相邻的元素的时候，只能交换整个数组内的元素。另外，按照下面的代码，如果不加条件j+1 < N，将6排到最后面后，数字6仍然会和其下一位进行交换。或者不加条件j+1 < N，就需要将第二层循环的条件改为j<N-i

Code

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
28
29
30
#include <stdio.h>
int main(int argc, char const *argv[])
{
    int N,K;
    scanf("%d %d", &N, &K);
    int array[105];
    int i,j;
    for(i=0; i<N; i++)
    {
        scanf("%d", &array[i]);
    }
    for(i=0; i<K; i++)
    {
        int temp=0;
        for(j=0; j<N; j++)	/*j<N ->  j<N-i-1*/
        {
            if(array[j] > array[j+1] && j+1 < N){	/*delete the "&& j+1 < N"*/
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
            }
        }
    }
    for(i=0; i<N; i++)
    {
        if(i == N-1) printf("%d\n", array[i]);
        else printf("%d ", array[i]);
    }
    return 0;
}

7-28 猴子选大王

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

Input Specification

输出在一行中给一个正整数N(≤1000)。

Output Specification

在一行中输出当选猴王的编号。

Sample Input & Sample Output

  • Input:
    11
  • Output:
    7

Analysis

这道题，属于“套路题”，实质是“约瑟夫环”问题；以下的代码介绍了三种方法：回溯法(严格意义上也许不是)、递归和迭代，分别参考了liuxuquan_、Little_Sword和d4shman的代码。感觉使用回溯法是最容易理解的，对于使用递归和迭代的方法，原理是一样的，理解一种了，另外一种也就没问题了；好像还可以通过其他的方式来做，这里暂时先不深究。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#define maxn 1005
int josephus_recursion(int n, int m);
int main(int argc, char const *argv[])
{
    /* method 1: use backtracking
	int N;
	scanf("%d", &N);
	// N=11;
	int i,monkey_array[maxn]={0};
	for(i=1; i<=N; i++){
		monkey_array[i]=i;
	}
	int j,k,temp;
	for(i=N; i>=1; i--)
	{
		for(j=1; j<=3; j++){
			temp=monkey_array[1];
			for(k=1; k<=i; k++){
				monkey_array[k]=monkey_array[k+1];
			}
			monkey_array[i]=temp;
		}
	}
	printf("%d\n", monkey_array[1]);
	*/
    /* method 2: use recursion
	int N;
	N=11;
	if(!N) return 0;
	int result = josephus_recursion(N,3);
	printf("%d\n", result+1);
	*/
    /* method 3: use iteration*/
    int i,N,result=0;
    scanf("%d", &N);
    for(i=2; i<=N; i++)
    {
        result=(result + 3)%i;
    }
    printf("%d\n", result+1);
    return 0;
}
int josephus_recursion(int n, int m)
{
    if(n == 1) return 0;
    else return (josephus_recursion(n-1, m)+m)%n;
}

7-29 删除字符串中的子串

输入2个字符串S1和S2，要求删除字符串S1中出现的所有子串S2，即结果字符串中不能包含S2。

Input Specification

输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串，对应S1和S2。

Output Specification

在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。

Sample Input & Sample Output

  • Input:
    Tomcat is a male ccatat
    cat
  • Output:
    Tom is a male

Analysis

本题不是特别难，不过还是要仔细想一想。对需要删除的字符串进行遍历，比对字符串序列，如果不是子串，就进行下一次循环，若是子串，就将子串后的字符序列前移，然后修改字符串的长度，并让字符串最后一位为\0，这样就删除掉了子串；重复遍历即可删除所有子串。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <string.h>
int main(int argc, char const *argv[])
{
    char s1[85],s2[85];
    gets(s1);
    gets(s2);
    int len1=strlen(s1),len2=strlen(s2);
    int i,k;
    for(k=0; k<len1; k++)
    {
        for(i=0; i<len1; i++)
        {
            if(s1[i] == s2[0]){
                int temp=i,flag=1,j;
                for(i+=1,j=1; j<len2; i++,j++)
                {
                    if(s1[i] != s2[j]){
                        flag=0;
                        break;
                    }
                }
                if(!flag){
                    i=temp;
                }else{
                    for(j=temp; i<len1; j++,i++)
                    {
                        s1[j]=s1[i];
                    }
                    len1=len1-len2;
                    s1[len1]='\0';
                }
                i=temp;
            }
        }
    }
    printf("%s\n", s1);
    return 0;
}

7-30 字符串的冒泡排序

我们已经知道了将N个整数按从小到大排序的冒泡排序法。本题要求将此方法用于字符串序列，并对任意给定的K（<N），输出扫描完第K遍后的中间结果序列。

Input Specification

输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。

Output Specification

输出冒泡排序法扫描完第K遍后的中间结果序列，每行包含一个字符串。

Sample Input & Sample Output

  • Input:
    6 2
    best
    cat
    east
    a
    free
    day
  • Output:
    best
    a
    cat
    day
    east
    free

Analysis

本题不是特别难，但也需要细细想一想，另外感觉题干一开始没说清楚怎样认为一个字符串“大”或“小”，其实就是首字母在字母表顺序来决定大小，若首字母相同则比较首字母后的字母的顺序，依次类推；了解了这些后，可以发现，输入样例中的字符串构成的序列就是2 3 5 1 6 4，而输出样例的序列就是2 1 3 4 5 6，这个与7-27 冒泡法排序是一致的。
解决这个问题的主要思路其实是利用二维数组存储每一个子字符串，进行比较后排序即可。主要该注意的点：abcd和acbd这种前一个或几个字母是相同的子字符串的比较，巧合的是，strcmp函数正好可以处理这样的情况👍，所以，直接使用strcmp函数比较后，在用strcpy函数互换字符串即可（类似整型变量的换值）；strcmp和strcpy这两个函数可以自己写；C++好像自带了应对这种字符串排序需求的处理函数，直接调用即可。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <string.h>
char* mycpy(char* dst, char* src);
int mycmp(char const *s1, char const *s2);

int main(int argc, char const *argv[])
{
    int N,K;
    scanf("%d %d", &N, &K);
    char str[N][11];
    int i,j;
    for(i=0; i<N; i++)
    {
        scanf("%s", str[i]);
    }
    char temp[11];
    char *p=temp;
    for(i=1; i<=K; i++)
    {
        for(j=0; j<N-i; j++)
        {
            if(mycmp(str[j], str[j+1]) > 0){
                mycpy(p, str[j]);
                mycpy(str[j], str[j+1]);
                mycpy(str[j+1], temp);
            }
        }
    }
    for(i=0; i<N; i++)
    {
        printf("%s\n", str[i]);
    }
    return 0;
}
char* mycpy(char *dst, char *src)
{
    char* ret = dst;
    while(*src)
    {
        *dst++ = *src++;
    }
    *dst = '\0';
    return ret;
}
int mycmp(char const *s1, char const *s2)
{
    while(*s1 == *s2 && *s1 != '\0')
    {
        s1++;
        s2++;
    }
    return *s1-*s2;
}

7-31 字符串循环左移

输入一个字符串和一个非负整数N，要求将字符串循环左移N次。

Input Specification

输入在第1行中给出一个不超过100个字符长度的、以回车结束的非空字符串；第2行给出非负整数N。

Output Specification

在一行中输出循环左移N次后的字符串。

Sample Input & Sample Output

  • Input:
    Hello World!
    2
  • Output:
    llo World!He

Analysis

本题不难，熟悉字符数组的存储方式的话做起来会感觉比较容易。主要思路是按照题目给的移动次数，将需要移动的字符按移动顺序放到一个新的字符数组内，将原来的字符数组的剩余字符前移，然后再将新的字符数组内的字符复制回老的字符数组内即可。注意当移动的次数大于字符串的长度时，要取余处理，比如，字符串长度为5，要移动9次，实际上移动的次数就是9%5=4。也可以只使用一个字符数组，先输出移动后的后半段字符，在输出前半段字符，最后换行即可。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
int mylen(char const *s1);
int main(int argc, char const *argv[])
{
    char str1[105];
    char str2[105];
    gets(str1);
    int N,i=1;
    scanf("%d", &N);
    char* p=str1;
    char* q=str2;
    int len=mylen(p);
    for(p+=(N%len); *p != '\0'; p++, q++)
    {
        *q=*p;
    }
    p=str1;
    for(i=1; i<=(N%len); i++, p++, q++)
    {
        *q=*p;
    }
    *q='\0';
    printf("%s\n", str2);
    /* method 2: use one char_array
	int i=0,len=mylen(str);
	char* p=str;
	printf("%s", p+(N%len);
	p=str;
	for(; i<(N%len); i++,p++)
	{
		printf("%c", *p);
	}
	printf("\n");
	*/
    return 0;
}
int mylen(char const *s1)
{
    int len=0;
    while(*s1)
    {
        s1++;
        len++;
    }
    return len;
}

7-32 说反话-加强版

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

Input Specification

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

Output Specification

每个测试用例的输出占一行，输出倒序后的句子，并且保证单词间只有1个空格。

Sample Input & Sample Output

  • Input:
    Hello World Here I Come
  • Output:
    Come I Here World Hello

Analysis

本题本质上而言，不是特别的复杂，但也需要仔细去琢磨一些细节，以下的代码参考了qq_37729102的代码，且文章之内做了很多细节说明；大致的思路，就是从后往前遍历字符串，空格跳过，扫描到非字符时，记录字符的个数(其实就是单词的长度了)，每扫描到下一个空格的时候，就输出前一个单词即可。由于第一个单词比较特殊，如果依然采取从后遍历的方法去输出第一个单词，这样就无法保证与题目格式的一致(换行符)，所以需要先记录第一个单词的首字母在字符数组中的下标，此时，若第一个单词的前面存在空格，跳过，若没有空格，那么循环变量为0后就自动跳出循环了，紧接着，再输出第一个单词就可以了。

Code

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
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <string.h>
#define maxn 500005
int main(int argc, char const *argv[])
{
    char str[maxn];
    gets(str);
    int len=strlen(str);
    int i,j=0,char_cnt=0,next_flag=1,last_flag=1;
    for(i=0; i<len; i++)
    {
        if(str[i] != ' '){
            last_flag=i;
            break;
        }
    }
    for(i=len-1; i>=0; i--)
    {
        if(str[i] != ' '){
            next_flag=0;
            char_cnt++;
        }else if(!next_flag){
            next_flag=1;
            for(j=i+1; j<i+1+char_cnt; j++)
            {
                printf("%c", str[j]);
            }
            if(i+1 != last_flag) printf(" ");
            char_cnt=0;
        }
    }
    for(i=last_flag; i<last_flag+char_cnt; i++)
    {
        printf("%c", str[i]);
    }
    printf("\n");
    return 0;
}

7-33 有理数加法

本题要求编写程序，计算两个有理数的和。

Input Specification

输入在一行中按照a1/b1和a2/b2的格式给出两个分数形式的有理数，其中分子和分母全是整形范围内的正整数。

Output Specification

在一行中按照a/b的格式输出两个有理数的和。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

Sample Input & Sample Output

  • Input 1:
    1/3 1/6
  • Output 2:
    1/2
  • Input 3:
    4/3 2/3
  • Output 4:
    2

Analysis

本题算是7-24 约分最简分式的升级版了，题目不难，按照基本计算规则进行约分即可，实质上是对最大公约数和最小公倍数的理解、应用和计算吧。

Code

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 <stdio.h>
int gcd(int a, int b);
int lcm(int a, int b);
int main(int argc, char const *argv[])
{
    int a1,b1,a2,b2;
    scanf("%d/%d %d/%d", &a1, &b1, &a2, &b2);
    int member,denominator,LCM,GCD;
    LCM=lcm(b1, b2);
    member=a1*LCM/b1 + a2*LCM/b2;
    denominator=LCM;
    GCD=gcd(member, denominator);
    if(denominator/GCD == 1){
        printf("%d\n", member/GCD);
    }else{
        printf("%d/%d\n", member/GCD, denominator/GCD);
    }
    return 0;
}
int gcd(int a, int b)
{
    return a==0?b:gcd(b%a, a);
}
int lcm(int a, int b)
{
    return a*b/gcd(a, b);
}

7-34 通讯录的录入与显示

通讯录中的一条记录包含下述基本信息：朋友的姓名、出生日期、性别、固定电话号码、移动电话号码。 本题要求编写程序，录入N条记录，并且根据要求显示任意某条记录。

Input Specification

输入在第一行给出正整数N（≤10）；随后N行，每行按照格式姓名 生日 性别 固话 手机给出一条记录。其中姓名是不超过10个字符、不包含空格的非空字符串；生日按yyyy/mm/dd的格式给出年月日；性别用M表示“男”、F表示“女”；固话和手机均为不超过15位的连续数字，前面有可能出现+。
在通讯录记录输入完成后，最后一行给出正整数K，并且随后给出K个整数，表示要查询的记录编号（从0到N−1顺序编号）。数字间以空格分隔。

Output Specification

对每一条要查询的记录编号，在一行中按照姓名 固话 手机 性别 生日的格式输出该记录。若要查询的记录不存在，则输出Not Found。

Sample Input & Sample Output

  • Input:
    3
    Chris 1984/03/10 F +86181779452 13707010007
    LaoLao 1967/11/30 F 057187951100 +8618618623333
    QiaoLin 1980/01/01 M 84172333 10086
    2 1 7
  • Output:
    LaoLao 057187951100 +8618618623333 F 1967/11/30
    Not Found

Analysis

本题不难，比较直接；直接用结构体构造出来保存通讯录的数据结构即可，然后再从这份通讯录内分别按顺序输出需要的信息即可。其实用二维数组应该也可以达到这样的效果，另外，对于生日这条记录，直接用字符串存储比较方便。

Code

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
28
29
30
31
32
33
34
35
36
#include <stdio.h>
typedef struct address_list
{
    char name[12];
    char brith[12];
    char gender;
    char landline[18];
    char phone[18];
}address_list;
int main(int argc, char const *argv[])
{
    int i,N;
    scanf("%d", &N);
    address_list list[N];
    for(i=0; i<N; i++)
    {
        scanf("%s %s %c %s %s", list[i].name, list[i].brith, &list[i].gender, list[i].landline, list[i].phone);
        getchar();
    }
    int K,j;
    scanf("%d", &K);
    for(i=1; i<=K; i++)
    {
        int j,check_num=0,flag=0;
        scanf("%d", &check_num);
        for(j=0; j<N; j++)
        {
            if(j == check_num){
                printf("%s %s %s %c %s\n", list[j].name, list[j].landline, list[j].phone, list[j].gender, list[j].brith);
                flag=1;
            }
        }
        if(!flag) printf("Not Found\n");
    }
    return 0;
}

7-35 有理数均值

本题要求编写程序，计算N个有理数的平均值。

Input Specification

输入第一行给出正整数N（≤100）；第二行中按照a1/b1 a2/b2 …的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。

Output Specification

在一行中按照a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

Sample Input & Sample Output

  • Input 1:
    4
    1/2 1/6 3/6 -5/10
  • Output 1:
    1/6
  • Input 2:
    2
    4/3 2/3
  • Output 2:
    1

Analysis

本题稍微复杂一点，不过大致思路还算简单；主要的思路就是依次将输入的分式相加，然后除以数量即可得到均值了。由于题目会给输入的分式的数目，所以可以提前定义好存储结构，然后在进行运算；注意每次运算完之后需要对分子分母进行化简，每次计算得到的分子member和分母denominator需要使用long long的类型来定义，否则会超出范围。分式的化简和相加主要依据最小公倍数和最大公约数来完成，最大公约数可以使用欧几里得算法，最小公倍数即为两个数的乘积除以两个数的最大公约数。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
typedef struct Fraction{
    int a;
    int b;
}fraction;
int gcd(int a, int b);
int lcm(int a, int b);
int main(int argc, char const *argv[])
{
    int i,N;
    scanf("%d", &N);
    fraction fra[N];
    for(i=0; i<N; i++)
    {
        scanf("%d/%d", &fra[i].a, &fra[i].b);
    }
    int GCD=0, LCM=0;
    long long member=fra[0].a, denominator=fra[0].b;
    for(i=1; i<N; i++)
    {
        GCD=gcd(denominator, fra[i].b);
        LCM=denominator*fra[i].b/GCD;
        member=member*LCM/denominator + fra[i].a*LCM/fra[i].b;
        denominator=LCM;
        GCD=gcd(member, denominator);
        member/=GCD;
        denominator/=GCD;
    }
    denominator*=N;
    GCD=gcd(member, denominator);
    member/=GCD;
    denominator/=GCD;
    if(denominator == 1) printf("%ld\n", member);
    else printf("%ld/%ld\n", member, denominator);
    return 0;
}
int gcd(int a, int b)
{
    return a==0?b:gcd(b%a, a); 
} 
int lcm(int a, int b){
    return a*b/gcd(a, b);
}

7-36 复数四则运算

本题要求编写程序，计算2个复数的和、差、积、商。

Input Specification

输入在一行中按照a1、b1、a2、b2的格式给出2个复数C1=a1+b1i和C2=a2+b2i的实部和虚部。题目保证C2不为0。

Output Specification

分别在4行中按照(a1+b1i) 运算符 (a2+b2i) = 结果的格式顺序输出2个复数的和、差、积、商，数字精确到小数点后1位。如果结果的实部或者虚部为0，则不输出。如果结果为0，则输出0.0。

Sample Input & Sample Output

  • Input 1:
    2 3.08 -2.04 5.06
  • Output 1:
    (2.0+3.1i) + (-2.0+5.1i) = 8.1i
    (2.0+3.1i) - (-2.0+5.1i) = 4.0-2.0i
    (2.0+3.1i) * (-2.0+5.1i) = -19.7+3.8i
    (2.0+3.1i) / (-2.0+5.1i) = 0.4-0.6i
  • Input 2:
    1 1 -1 -1.01
  • Output 2:
    (1.0+1.0i) + (-1.0-1.0i) = 0.0
    (1.0+1.0i) - (-1.0-1.0i) = 2.0+2.0i
    (1.0+1.0i) * (-1.0-1.0i) = -2.0i
    (1.0+1.0i) / (-1.0-1.0i) = -1.0

Analysis

本题的计算方法比较简单，注意复数的*和/运算即可；此题比较麻烦的地方在于控制输出的格式，由于存在实部和虚部，所以需要分多种情况，这个就需要注意细节了。
若用real代表实部，用imaginary代表虚部，就可以得到以下几种情况：real==0, imaginary==0
、real==0, imaginary>0、real==0, imaginary < 0、real!=0, imaginary>0、real!=0, imaginary<0和real!=0, imaginary==0，根据这六种情况要分别输出结果中虚部前的+和-号；由于输入的数据是小数，在做判断时，得考虑四舍五入的情况，而在输出时，%lf会自动四舍五入；不要用flaot，因为数值可能会有损失，最好直接用double。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <math.h>
double a1,b1,a2,b2;
void print_complex_number(double a, char c, double b);
int main(int argc, char const *argv[])
{
    double real_part=0.0,imaginary_part=0.0;
    scanf("%lf %lf %lf %lf", &a1, &b1, &a2, &b2);
    real_part=a1 + a2;
    imaginary_part=b1 + b2;
    print_complex_number(real_part, '+', imaginary_part);
    real_part=a1 - a2;
    imaginary_part=b1 - b2;
    print_complex_number(real_part, '-', imaginary_part);
    real_part=a1*a2 - b1*b2;
    imaginary_part=a2*b1 + a1*b2;
    print_complex_number(real_part, '*', imaginary_part);
    real_part=(a1*a2 + b1*b2) / (a2*a2 + b2*b2);
    imaginary_part=(a2*b1 - a1*b2) / (a2*a2 + b2*b2);
    print_complex_number(real_part, '/', imaginary_part);
    return 0;
}
void print_complex_number(double a, char c, double b)
{
    if(b1 >= 0 && b2 >= 0){
        printf("(%.1lf+%.1lfi) %c (%.1lf+%.1lfi) = ", a1, b1, c, a2, b2);
    }else if(b1 >= 0 && b2 < 0){
        printf("(%.1lf+%.1lfi) %c (%.1lf%.1lfi) = ", a1, b1, c, a2, b2);
    }else if(b1 < 0 && b2 >= 0){
        printf("(%.1lf%.1lfi) %c (%.1lf+%.1lfi) = ", a1, b1, c, a2, b2);
    }else{
        printf("(%.1lf%.1lfi) %c (%.1lf%.1lfi) = ", a1, b1, c, a2, b2);
    }
    if(fabs(a) < 0.1 && fabs(b) < 0.1){
        printf("0.0\n");
        return;
    }
    int flag=0;
    if(fabs(a) >= 0.1){
        printf("%.1lf", a);
        flag++;
    }
    if(fabs(b) >= 0.1){
        if(flag && b > 0.0){
            printf("+%.1lfi", b);
        }else{
            printf("%.1lfi", b);
        }
    }
    printf("\n");
}

7-37 整数分解为若干项之和

将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。

Input Specification

每个输入包含一个测试用例，即正整数N (0<N≤30)。

Output Specification

按递增顺序输出$N$的所有整数分解式子。递增顺序是指：对于两个分解序列$N_1={n_1,n_2,⋯}$和$N_2={m_1,m_2,⋯}$，若存在$i$使得$n_1=m_1,⋯,n_i=m_i$，但是$n_{i+1} < m_{i+1}$,则$N_1$序列必定在$N_2$序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。

Sample Input & Sample Output

  • Input:
    7
  • Output:
    7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
    7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
    7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
    7=2+5;7=3+4;7=7

Analysis

以下代码参考了文之的代码；题目其实不难，也算是“套路题”的一种，采用了深度优先和递归的思想；文之博文内细节说的很清楚，这里暂时先不讨论（其实是自己看的似懂非懂😝）。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
void division(int i);
int N;
int s[31];
int top=-1;
int cnt=0;
int sum=0;
int main(int argc, char const *argv[])
{
    scanf("%d", &N);
    division(1);
    return 0;
}
void division(int i)
{
    if(sum == N){
        cnt++;
        printf("%d=", N);
        int k;
        for(k=0; k<top; k++)
        {
            printf("%d+", s[k]);
        }
        if(cnt%4 == 0 || s[top] == N){
            printf("%d\n", s[top]);
        }else{
            printf("%d;", s[top]);
        }
        return ;
    }
    if(sum > N){
        return ;
    }
    int j;
    for(j=i; j<=N; j++)
    {
        s[++top]=j;
        sum+=j;
        division(j);
        sum-=j;
        top--;
    }
}

7-38 数列求和-加强版

给定某数字$A（1≤A≤9）$以及非负整数$N（0≤N≤100000）$，求数列之和$S=A+AA+AAA+⋯+AA⋯A（N个A）$。例如$A=1, N=3$时，$S=1+11+111=123$。

Input Specification

输入数字$A$与非负整数$N$。

Output Specification

输出其$N$项数列之和$S$的值。

Sample Input & Sample Output

  • Input:
    1 3
  • Output:
    123

Analysis

这道题，不是特别难，其实这种类型的题目大体上算，大概又两种方法去解决；首先是比较直接的就是利用数组去模拟整个计算过程，其实质是用数组进行基本四则运算；另外一种方法就是数学，每一次数位的相加，其实是(A*(N-i) + carry，其中A是数位值，(N-i)是数位上的加的次数，carry是进位值，所以(A*(N-i) + carry的结果取余后才是这个数位真正的值。下面的代码中分别给出了用数组模拟的方法和数学方法，且数学方法理解起来不难，要能想到这样去解决的话，还需要积累。

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
#define maxn 100002
int main(int argc, char const *argv[])
{
    /* method 1: use the array do analog computation, but Time Limit Exceeded
	int A,N,sum[maxn],num[maxn];
	// scanf("%d %d", &A, &N);
	A=1, N=3;
	if(N == 0){
		printf("0\n");
	}else if(N == 1){
		printf("%d\n", A);
	}else{
		int i,j,temp,len,flag=0,carry=0;
		for(i=1; i<=N; i++)
		{
			num[i]=A;
		}
		while(N)
		{
			carry=0;
			for(i=1; i<=N-1; i++)
			{
				sum[i]=A;
			}
			for(i=1; i<=N-1; i++)
			{
				temp = num[i] + sum[i];
				num[i] = (temp + carry)%10;
				carry = (temp + carry)/10;
			}
			for(j=i; j<=N; j++)
			{
				temp = num[i] + sum[i];
				num[i] = (temp + carry)%10;
				carry = (temp + carry)/10;
			}
			while(carry)
			{
				num[j++] = carry%10;
				carry/=10;
				len = j;
				flag = 1;
			}
			for(i=1; i<=N-1; i++)
			{
				sum[i]=0;
			}
			N--;
			if(N == 1) break;
		}
		if(flag){
			for(i=len; i>1; i--){
				printf("%d", num[i]);
			}
			printf("%d\n", num[i]);
		}else{
			for(i=j; i>1; i--){
				printf("%d", num[i]);
			}
			printf("%d\n", num[i]);
		}
	}
	return 0;
	*/
    /* method 2: use the '%' */
    int num[maxn]={0},i,j,carry,flag,A,N;
    scanf("%d%d", &A, &N);
    // A=9, N=4;
    if(N == 0) printf("0\n");
    else if(N == 1) printf("%d\n", A);
    else{
        carry=0, flag=0;
        for(i=0; i<N; i++)
        {
            num[i] = (A*(N-i) + carry)%10;
            carry = (A*(N-i) + carry)/10;
        }
        while(carry)
        {
            num[i++] = carry%10;
            carry = carry/10;
            flag = 1;
        }
        if(flag == 1){
            for(i=N; i>0; i--)
            {
                printf("%d", num[i]);
            }
            printf("%d\n", num[i]);
        }else{
            for(i=N-1; i>0; i--)
            {
                printf("%d", num[i]);
            }
            printf("%d\n", num[i]);
        }
    }
    
}

Code-Completion

6-1 简单输出整数

本题要求实现一个函数，对给定的正整数N，打印从1到N的全部正整数。

Function interface definition

void PrintN ( int N );
其中N是用户传入的参数。该函数必须将从1到N的全部正整数顺序打印出来，每个数字占1行。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
void PrintN ( int N );
int main ()
{
    int N;

    scanf("%d", &N);
    PrintN( N );

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    3
  • Output:
    1
    2
    3

Analysis

热身题🧐。

Code

1
2
3
4
5
6
void PrintN(int N){
    int i;
    for(i=1;i<=N;i++){
        printf("%d\n",i);
    }
}

6-2 多项式求值

本题要求实现一个函数，计算阶数为n，系数为a[0]…a[n]的多项式$f(x)=\sum_{i=0}^n(a[i]×xi)$在x点的值。

Function interface definition

double f( int n, double a[], double x );
其中n是多项式的阶数，a[]中存储系数，x是给定点。函数须返回多项式f(x)的值。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

#define MAXN 10

double f( int n, double a[], double x );

int main()
{
    int n, i;
    double a[MAXN], x;
    
    scanf("%d %lf", &n, &x);
    for ( i=0; i<=n; i++ )
        scanf(“%lf”, &a[i]);
    printf("%.1f\n", f(n, a, x));
    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    2 1.1
    1 2.5 -38.7
  • Output:
    -43.1

Analysis

直接按照公式求值即可，注意直接算有测试点会超时，可用提取公因式的办法来解决。

Code

1
2
3
4
5
6
7
8
9
10
11
12
double f( int n, double a[], double x ) {
    int i;
    double sum=0,X=x;
    if(n == 0) {
        sum=a[0]*1.0;
    } else {
        sum=a[n]*X + a[n-1];
        for(i=n-2; i>=0; i--) {
            sum=sum*X + a[i];
        }
    }
    return sum;

6-3 简单求和

本题要求实现一个函数，求给定的N个整数的和。

Function interface definition

int Sum ( int List[], int N );
其中给定整数存放在数组List[]中，正整数N是数组元素个数。该函数须返回N个List[]元素的和。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

#define MAXN 10

int Sum ( int List[], int N );

int main ()
{
    int List[MAXN], N, i;

    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%d", &List[i]);
    printf("%d\n", Sum(List, N));

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    3
    12 34 -5
  • Output:
    41

Analysis

基础求和，很简单。

Code

1
2
3
4
5
6
7
8
9
int Sum ( int List[], int N )
{
    int i,ret=0;
    for(i=0; i<N; i++)
    {
        ret+=list[i];
    }
    return ret;
}

6-4 求自定类型元素的平均

本题要求实现一个函数，求N个集合元素S[]的平均值，其中集合元素的类型为自定义的ElementType。

Function interface definition

ElementType Average( ElementType S[], int N );
其中给定集合元素存放在数组S[]中，正整数N是数组元素个数。该函数须返回N个S[]元素的平均值，其值也必须是ElementType类型。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Average( ElementType S[], int N );

int main ()
{
    ElementType S[MAXN];
    int N, i;

    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%f", &S[i]);
    printf("%.2f\n", Average(S, N));

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    3
    12.3 34 -5
  • Output:
    13.77

Analysis

基础求平均值，很简单。

Code

1
2
3
4
5
6
7
8
9
10
ElementType Average( ElementType S[], int N )
{
    ElementType sum=0;
    int i=0;
    for(; i<N; i++)
    {
        sum+=S[i];
    }
    return sum/N;
}

6-5 求自定类型元素的最大值

本题要求实现一个函数，求N个集合元素S[]中的最大值，其中集合元素的类型为自定义的ElementType。

Function interface definition

ElementType Max( ElementType S[], int N );
其中给定集合元素存放在数组S[]中，正整数N是数组元素个数。该函数须返回N个S[]元素中的最大值，其值也必须是ElementType类型。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#define MAXN 10
typedef float ElementType;
ElementType Max( ElementType S[], int N );
int main ()
{
    ElementType S[MAXN];
    int N, i;

    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%f", &S[i]);
    printf("%.2f\n", Max(S, N));

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    3
    12.3 34 -5
  • Output:
    34.00

Analysis

基础求最大值，也很简单。

Code

1
2
3
4
5
6
7
8
9
10
ElementType Max( ElementType S[], int N )
{
    int i=0;
    ElementType max=S[i];
    for(; i<N; i++)
    {
        if(max < S[i]) max = S[i];
    }
    return max;
}

6-6 求单链表结点的阶乘和

本题要求实现一个函数，求单链表L结点的阶乘和。这里默认所有结点的值非负，且题目保证结果在int范围内。

Function interface definition

int FactorialSum( List L );
其中单链表List的定义如下：

1
2
3
4
5
6
typedef struct Node *PtrToNode;
struct Node {
    int Data; /* 存储结点数据 */
    PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

Test procedure case

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 <stdio.h>
#include <stdlib.h>
typedef struct Node *PtrToNode;
struct Node {
    int Data; /* 存储结点数据 */
    PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
int FactorialSum( List L );
int main()
{
    int N, i;
    List L, p;

    scanf("%d", &N);
    L = NULL;
    for ( i=0; i<N; i++ ) {
        p = (List)malloc(sizeof(struct Node));
        scanf("%d", &p->Data);
        p->Next = L;  L = p;
    }
    printf("%d\n", FactorialSum(L));

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    3
    5 3 6
  • Output:
    846

Analysis

链表求阶乘，本质上是对链表的遍历操作，对链表而言，注意判空条件可以写成L或者L->Next。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int FactorialSum( List L )
{
    int fac_sum=0,i,fac;
    while(L)
    {
    	fac=1;
        for(i=1; i <=L->Data ; i++)
        {
            fac*=i;
        }
        fac_sum+=fac;
        L=L->Next;
    }
    return fac_sum;
}

6-7 统计某类完全平方数

本题要求实现一个函数，判断任一给定整数N是否满足条件：它是完全平方数，又至少有两位数字相同，如144、676等。

Function interface definition

int IsTheNumber ( const int N );
其中N是用户传入的参数。如果N满足条件，则该函数必须返回1，否则返回0。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <math.h>
int IsTheNumber ( const int N );
int main()
{
    int n1, n2, i, cnt;
    
    scanf("%d %d", &n1, &n2);
    cnt = 0;
    for ( i=n1; i<=n2; i++ ) {
        if ( IsTheNumber(i) )
            cnt++;
    }
    printf("cnt = %d\n", cnt);

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    105 500
  • Output:
    cnt = 6

Analysis

这个题看着有点烦，其实也很简单，哈哈，出题者给出了#define <math.h>（感谢）这个条件后，对数字的操作就很简单了（不过自己写sqrt，应该也能搞定😉），注意sqrt这个函数的返回类型是double，所以需要强制类型转换(int)sqrt(n)；现在就只用去判断这个数中各数位数字出现次数至少出现2次即可。测试程序中传入函数的参量是int，所以，数组长度用11就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int IsTheNumber ( const int N )
{
    int ret=0,digit[11]={0};
    if( ((int)sqrt(N)) * ((int)sqrt(N) ) == N){
        int i,j,temp=N;
        for(i=0; temp; temp/=10, i++)
        {
            digit[temp%10]++;
        }
        for(j=0; j<10; j++){
            if(digit[j] >= 2){
            	ret=1;
            	break;
            }
        }
    }
    return ret;
}

6-8 简单阶乘计算

本题要求实现一个计算非负整数阶乘的简单函数。

Function interface definition

int Factorial( const int N );
其中N是用户传入的参数，其值不超过12。如果N是非负整数，则该函数必须返回N的阶乘，否则返回0。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int Factorial( const int N );
int main()
{
    int N, NF;
    scanf("%d", &N);
    NF = Factorial(N);
    if (NF)  printf("%d! = %d\n", N, NF);
    else printf("Invalid input\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    5
  • Output:
    5! = 120

Analysis

基本阶乘计算，注意$0!=1$即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
int Factorial( const int N )
{
    int i,ret=1;
    if(N < 0) return 0;
    else if(N == 0) return ret;
    else{
        for(i=1; i<=N; i++)
        {
            ret*=i;
        }
    }
    return ret;
}

6-9 统计个位数字

本题要求实现一个函数，可统计任一整数中某个位数出现的次数。例如-21252中，2出现了3次，则该函数应该返回3。

Function interface definition

int Count_Digit ( const int N, const int D );
其中N和D都是用户传入的参数。N的值不超过int的范围；D是$[0, 9]$区间内的个位数。函数须返回N中D出现的次数。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int Count_Digit ( const int N, const int D );

int main()
{
    int N, D;
    
    scanf("%d %d", &N, &D);
    printf("%d\n", Count_Digit(N, D));
    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    -21252 2
  • Output:
    3

Analysis

考察数位拆分，注意如果是复数，需要先转换为其绝对值即可。

Code

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
int Count_Digit ( const int N, const int D )
{
    int times=0,n;
    if(N < 0) n = -N;
    else{
        n=N;
        if(n == 0 && D == 0){
            return 1;
        }
    }
    int mask=1,temp=n;
    do{
        temp/=10;
        mask*=10;
    }while(temp > 9);
    temp = n;
    int digit;
    do{
        digit = temp/mask;
        temp%=mask;
        mask/=10;
        if(digit == D) times++;
    }while(mask > 0);
    return times;
}

6-10 阶乘计算升级版

本题要求实现一个打印非负整数阶乘的函数。

Function interface definition

void Print_Factorial ( const int N );其中N是用户传入的参数，其值不超过1000。如果N是非负整数，则该函数必须在一行中打印出$N!$的值，否则打印“Invalid input”。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
void Print_Factorial ( const int N );
int main()
{
    int N;
    
    scanf("%d", &N);
    Print_Factorial(N);
    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    15
  • Output:
    1307674368000

Analysis

很明显是个大数问题，利用数组来模拟乘法计算即可，注意每一次进位的处理，感觉数组模拟乘法要比加法容易一些😧。

Code

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
28
29
30
31
void Print_Factorial ( const int N )
{
    if(N < 0){
        printf("Invalid input\n");
    }else if(N == 0){
        printf("1\n");
    }else{
        int carry=0,i,j,k=1,temp,num[3000]={0};
        num[0]=1;
        for(i=2; i<=N; i++)
        {
            for(j=0; j<k; j++)
            {
                temp = num[j]*i + carry;
                num[j] = temp%10;
                carry = temp/10;
            }
            while(carry)
            {
                num[k]=carry%10;
                carry/=10;
                k++;
            }
        }
        for(i=k-1; i>0 ;i--)
        {
            printf("%d", num[i]);
        }
        printf("%d\n", num[i]);
    }
}

6-11 求自定类型元素序列的中位数

本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第$⌊N/2+1⌋$大的元素。其中集合元素的类型为自定义的ElementType。

Function interface definition

ElementType Median( ElementType A[], int N );
其中给定集合元素存放在数组A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#define MAXN 10
typedef float ElementType;

ElementType Median( ElementType A[], int N );

int main ()
{
    ElementType A[MAXN];
    int N, i;

    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%f", &A[i]);
    printf("%.2f\n", Median(A, N));

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input:
    3
    12.3 34 -5
  • Output:
    12.30

Analysis

注意题目的描述，求的是中位数，而$⌊N/2+1⌋$这里是向下取整哦。也即是说，按照题目的要求，要先给传入函数的数组进行排序，然后再输出其中第$⌊N/2+1⌋$大的数，而此时对于数组（从0开始）而言下标就是N/2；明白这个之后，还有排序的问题要解决，如何排序呢？排序算法很多，冒泡排序和插入排序都有一个测试用例无法通过，所以这里使用希尔排序。举个希尔排序的简单例子，对于a[3]={3, 1, 2}这个序列而言，希尔排序会有一个增量d，并按照这个增量d来进行排序，d初始化为3(个数)/2=1，那么第一次希尔排序，就会对a[0]=3和a[0+d]=2这两个数字进行排序，由于不存在a[2]，所以a[1]不会参与排列；第二次循环时，检查已经有序就会跳出循环了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ElementType Median( ElementType A[], int N )
{
    int i,j;
    ElementType temp;
    int d;
    for(d=N/2; d>0; d/=2)
    {
        for(i=d; i<N; i++)
        {
            temp=A[i];
            for(j=i; j>=d; j-=d)
            {
                if(temp < A[j-d]){
                    A[j] = A[j-d];
                }else break;
            }
            A[j]=temp;
        }
    }
    return A[N/2]; 
}

6-12 判断奇偶性

本题要求实现判断给定整数奇偶性的函数。

Function interface definition

int even( int n );
其中n是用户传入的整型参数。当n为偶数时，函数返回1；n为奇数时返回0。注意：0是偶数。

Test procedure case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int even( int n );
int main()
{    
    int n;

    scanf("%d", &n);
    if (even(n))
        printf("%d is even.\n", n);
    else
        printf("%d is odd.\n", n);

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input & Sample Output

  • Input 1:
    -6
  • Output 1:
    -6 is even.
  • Input 2:
    5
  • Output 2:
    5 is odd.

Analysis

判断奇偶性直接对2取余就好，并且0是偶数，如果不确定的话可以手算一下。

Code

1
2
3
4
int even(int n){
    if(n%2==0) return 1;
    else return 0;
}

6-13 折半查找

给一个严格递增数列，函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。

Function interface definition

int Search_Bin(SSTable T, KeyType k)
其中T是有序表，k是查找的值。

Test procedure case

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
28
29
30
31
32
33
#include <iostream>
using namespace std;
#define MAXSIZE 50
typedef int KeyType;

typedef  struct                     
{ KeyType  key;                                             
} ElemType;

typedef  struct
{ ElemType  *R; 
  int  length;
} SSTable;      

void  Create(SSTable &T)
{ int i;
  T.R=new ElemType[MAXSIZE+1];
  cin>>T.length;
  for(i=1;i<=T.length;i++)
     cin>>T.R[i].key;   
}
int  Search_Bin(SSTable T, KeyType k);

int main () 
{  SSTable T;  KeyType k;
   Create(T);
   cin>>k;
   int pos=Search_Bin(T,k);
   if(pos==0) cout<<"NOT FOUND"<<endl;
   else cout<<pos<<endl;
   return 0;
}
/* 请在这里填写答案 */

Sample Input & Sample Output

  • Input 1:
    5
    1 3 5 7 9
    7
  • Output 1:
    4
  • Input 2:
    5
    1 3 5 7 9
    10
  • Output 2:
    NOT FOUND

Analysis

题目给出的测试程序是C++的语法，但是也没事，有C的功底看懂是没有太大问题的，不过实际上，因为，要写的只是函数，好像跟其他的好像也没啥关系，主要看懂有序表L的结构就好了。另一个，就是折半查找的算法了，大致思路就是利用左标记和右标记来遍历有序表，如果有符合条件的值就弹出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int  Search_Bin(SSTable T, KeyType k)
{
  int serial_num=0,left,right=T.length,mid=1,j=1;
  while(j <= T.length){
    mid=(left + right)/2;
    if(T.R[mid].key == k){
        serial_num = mid;
        break;
    }else{
        if(T.R[mid].key < k){
            left = mid;
        }
        if(T.R[mid].key > k){
            right = mid;
        }
    }
    j++;
  } 
  return serial_num; 
}

Summary

虽说是基础编程题目集，但是感觉里面有些题目还真不是特别好想，可能是我比较菜😂。
尽管每道题目都给出了题目、输入（输出）样例、说明等，字数真是多啊，哈哈，有点水文的嫌疑。
另外，关于每道题目的AC代码，已经全部被上传到GitHub上了，可以点击PTA-Basical-Programming-problem-set来获取源文件。

Buy me a coffee ? :)
0%