Memory Dot
0%

PTA-基础编程题目集

发表于 更新于 分类于 阅读次数： Valine：

Function

Link: PTA

6-1 简单输出整数 (10 分)

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

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

思路：
题目很简单但是试了好多次才通过，原因是把main函数和PrintN一起提交了，
事实上只用提交自己编写的PrintN函数就可以了，不用提交main函数。



6-2 多项式求值 (15 分)

本题要求实现一个函数，计算阶数为n，系数为a[0] … a[n]的多项式在x点的值。

1
2
3
4
5
6
7
8
9
10
double f( int n, double a[], double x ){
  double sum;
  double x0 = 1; //x0必为 1
  for (int i=0; i <= n; i++){
    	if (i == 0);//i = 0即是x0 = 1，无操作
      else x0 *= x; //随着循环逐个叠加x的次幂
      sum += a[i] * x0;//求和
    }
  return sum;
}

思路：
一开始的思路用了2个for循环，提交后提示复杂度O(n^2)不行。于是，github里查起答案：x0可以在1个循环里逐个叠加



6-3 简单求和 (10 分)

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

1
2
3
4
5
6
int Sum ( int List[], int N ){
  int sum = 0;
  for(int j = 0; j<N; j++)
    sum += List[j];
  return sum;
}

思路：
很简单的一道题，但是还是提交了几次。原因是：sum、j必须的赋初值0。PTA里，系统不会自动赋值0。



6-4 求自定类型元素的平均 (10 分)

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

1
2
3
4
5
6
7
ElementType Average( ElementType S[], int N ){
  ElementType sum = 0;
  for(int i = 0; i < N; i++){
    sum += S[i];
  }
  return sum/(ElementType)N; //N原来是int型，要强制转换为ElementType
}

思路：
被除的N要强制转换为ElementType，让结果输出为浮点数



6-5 求自定类型元素的最大值 (10 分)

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

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

思路：
要额外考虑到max负数的情况，故max初值不能赋值0，要赋值S[0



6-6 求单链表结点的阶乘和 (15 分)

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

1
2
3
4
5
6
7
8
9
10
11
int FactorialSum( List L ){ //return语句，输出输出!!
  int sum = 0;
  int num;
  while (L != NULL){// L-Next指向NULL时，会把其地址给L，所以得判断L的地址
    for (num = 1 ;L->Data >  0 ;L->Data--)
      num *= L->Data;
    sum += num;
    L = L->Next;
  }
  return sum;
}

思路：
一开始运用时，一直在对L->Data重复赋值，导致这道题思路错误。而后，引入num才计算出来。目前会经常忘记return语句，得让自己多注意。



6-7 统计某类完全平方数 (20 分)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int IsTheNumber ( const int N )
{
    int res = N; //让N可以改变，因为N原来是const
    int num[10] = {0};//存放0 ~ 9的计数值
    if((int)sqrt(N) == sqrt(N)){ //或者用：sqrt(N) * sqrt(N) == N，来判断是否为完全平方数
        while(res != 0){
            num[res % 10] ++;//对0 ~ 9某个计数
            res /= 10;//从十位、百位...开始逐个提取
        }
        for (int i = 0; i < 10; i ++ ){
            if(num[i] > 1) return 1;//0 ~ 9某个计数值大于等于2即该数符合要求
        }
    }
    return 0;
}

思路：
用数组num[10]分别计数0 ~ 9，具体要使用取余(%10)，除法(/10)来计数、提取数值



6-8 简单阶乘计算 (10 分)

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

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

思路：
本题没有考虑N > 12的情况，即超出32位Tmax的情况。6-10会考虑。



6-9 统计个位数字 (15 分)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Count_Digit ( const int N, const int D ){
    int n = N;
    int num[10] = {0};
    if (n < 0) n = ~n+1; //负数取补码转为正数，但Tmin仍为Tmin，故单独讨论
    if (n == 0x80000000){//Tmin =0x80000000 = -2147483648
        if(D == 1 | D == 2 | D == 3 | D == 6 | D == 7) return 1;
        if(D == 4) return 3;
        if(D == 8) return 2;
    }
    if (n == 0) {// 0在下面的模块中无法判断，所以单独判断
        if(D == 0) return 1;    
        else return 0;
    }
    else
        while (n){    //参考6-7，提取并计数，但此模块只适用于不是零的正整数（因为自加符号适用于正数计数）
            num[n % 10]++;
            n /= 10;
        }
    return num[D];
}

思路：
分类讨论。1、n == 0x80000000、n == 0，注意要使用==等价符号；2、将负数转为正数处理。



6-10 阶乘计算升级版 (20 分)

本题要求实现一个打印非负整数阶乘的函数。（最大为1000!）

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
void Print_Factorial(const int N) {
    long sum = 1;
    if (N >= 0 && N <= 12) { //Tmax是9位数，12!也为9位数，所以可以直接计算
        for (int i = 0; i <= N; i++) {
            if (i == 0) {
                sum = 1;
            }
            else {
                sum = sum*i;
            }
        }
        printf("%d\n", sum);
    }
    else if (N > 12 && N <= 1000) {//大于12不能直接计算，用数组表示
        int Num[3000] = { 0 };  //确保最终结果的数组足够大：1 ~ 9相乘最多有1*9=9位，10 ~ 99(90个两位数)相乘最多有2*90=180位，100 ~ 999(90个三位数)相乘最多有3*900=2700位，1000是4*1=4位，总计2893，所以取整取3000位
        int i, j, k, n;
        k = 1;  //位数
        n = 0;  //进位
        Num[0] = 1;   //将结果先初始化为1
        int temp;  //阶乘的任一元素与临时结果的某位的乘积结果
        //计算
        for (i = 2; i <= N; i++){  //开始阶乘，阶乘元素从2开始，因为1*2=2;模拟乘法，将临时结果的每位与阶乘元素相乘，并更新
            for (j = 0; j < k; j++){ //实现乘法并提取进位值
                temp = Num[j] * i + n;  //相应阶乘中的一项与当前所得结果的某位相乘，并加上进位
                Num[j] = temp % 10;  //更新结果的位上信息
                n = temp / 10;   //提取进位值
            }
            while (n != 0){ //如果有进位，更新最新位的信息，并扩展最终数值的位数(k)
                Num[k] = n % 10;  //新加一位，更新结果的位上信息。
                k++; //位数增1
                n = n / 10;   //判断还能不能进位，若能，则继续更新；若不能，则将n置0
            }
        }
        //输出
        for (i = k - 1; i >= 0; i--){//从最后一位开始倒着输出
            printf("%d", Num[i]);  
        }
        printf("\n");
    }
    else {
        printf("Invalid input\n");
    }
}

思路：
大于9位时，int无法表示，1000！的数值过于巨大，故采用数组Num[3000]表示。简述：模拟乘法，存储进位值，根据是否有进位扩展数组。
参考：
Link：参考答案；



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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ElementType Median( ElementType A[], int N )
{
    int incr = N;
	int i, j, k;
	do{ 
		incr = incr / 2; //确定增量
		for (i = 0; i < incr; i++){ //实现分组
			for (j = i + incr; j < N; j += incr){ 
				if (A[j] < A[j - incr]){ //实现比较并交换
					ElementType temp = A[j];
					for (k = j - incr; k >= 0 && temp < A[k]; k -= incr){//大于两个元素比较时使用
						A[k + incr] = A[k];
					}
					A[k + incr] = temp;
				}
			}
		}
	} while (incr > 1);
	return A[N / 2];//求N个集合元素A[]的中位数，即序列中第（(N+1)/2向下取整）大的元素
}

思路：
使用希尔算法，时间复杂度为O(n^(1.3 ~ 2))。而选择算法、冒泡算法的时间复杂度为O(n^2)不符合题目时间要求。
参考：
Link：希尔算法java实现图示；参考答案1；参考答案2。



6-12 判断奇偶性 (10 分)

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

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

思路：
n % 2 若有余数为偶数；若无余数即0为奇数



6-13 折半查找 (15 分)

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

1
2
3
4
5
6
7
8
9
10
int  Search_Bin(SSTable T, KeyType k){ //题目强制要求用二分法，不能用for循环历遍
    int start = 0, end = T.length - 1, mid;
    while(start <= end){
        mid = (start + end)/2;
        if(T.R[mid].key == k) return mid;//T.R[].key范围为T.R[1].key ~ T.R[end].key
        else if(T.R[mid].key > k) end = mid - 1; //若k值小于mid元素，则mid在递增数列左边，所以对end取值为mid - 1缩小范围于递增数列左边
        else start = mid + 1;//若k值大于mid元素，则mid在递增数列右边，所以对start取值为mid + 1缩小范围于递增数列右边
    }
    return 0;
}

思路：
虽然没学过c++，但此函数几乎完全用c写。除了特殊的数据元素表示。简述：首尾下标相加除以2确定中位数下标mid，然后根据中位数值与首尾数值的大小比较缩小范围。（此处的中位数不是严格意义上的中位数，若start + end为奇数，则会向下取整）

函数部分完成时间：2021.9.22

Programming

7-1 厘米换算英尺英寸 (15 分)

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

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

float c2f(int cm);
int getinch (int cm);

int main(){
	int cm;
	scanf("%d", &cm);
	printf("%d %d", (int)c2f(cm), getinch(cm));
	return 0;
}

float c2f (int cm){
	float m = cm / 100.0; //100必须是float即100.0，否则cm / 100为int/int是整型输出，直接按float输出，会输出0
	float foot = m / 0.3048;//14 ~ 15也可以写成 float m = cm / 30.48
	return foot;
}

int getinch (int cm){
	return (c2f(cm) - (int)c2f(cm)) * 12; //英寸取整乘以12
}

思路：**int/int直接按float输出，会输出0**。解决方案：将分子、分母任意一个值改成float。



7-2 然后是几点 (15 分)

有时候人们用四位数字表示一个时间，比如1106表示 11点零6分。现在，你的程序要根据起始时间和流逝的时间计算出终止时间。

读入两个数字，第一个数字以这样的四位数字表示当前时间，第二个数字表示分钟数，计算当前时间经过那么多分钟后是几点，结果也表示为四位数字。当小时为个位数时，没有前导的零，例如5点30分表示为530；0点 30分表示为030。注意，第二个数字表示的分钟数可能超过60，也可能是负数。

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

int main() {
	int a, b, Mul60, h, min;
	scanf("%d %d", &a, &b);
	Mul60 = (a / 100) * 60 + (a % 100) + b; // (a / 100)取a的小时部分，并令其为60的倍数；同时(a % 100)取a的分钟部分，最后加上b
	h = Mul60 / 60; //提取小时
	min = Mul60 % 60;//提取分钟
	
	//%d表示打印整型的，
	//%2d表示把整型数据打印最低两位，
	//%02d表示把整型数据打印最低两位，如果不足两位，用0补齐
	printf("%d%02d",h,min);
    return 0;
}

思路：因为60进制转化为60的倍数，并且分为h、min两段输出，注意要使用%02d。



7-3 逆序的三位数 (10 分)

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

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

void neg(int num);//逆序输出

int main() {
	int num;
	scanf("%d", &num); //对于&num，num是数值，&num是地址
	neg(num);
	return 0;
}

void neg(int num) {
	int f = num % 10; //取个位
	int s = (num % 100 - f) / 10; //取十位,除10，保证转移到个位
	int t = num / 100;//取百位
	if (f == 0 && s == 0) printf("%d", t);
	else if (f == 0) printf("%d%d", s, t);
	else printf("%d%d%d", f, s, t);//并列输出
}

思路：用取余、除法取个、十、百位并单独讨论十位、百位都为0；百位为0的情况。并列输出是解决这类题的好方法



7-4 BCD解密 (10 分)

BCD数是用一个字节来表达两位十进制的数，每四个比特表示一位。所以如果一个BCD数的十六进制是0x12，它表达的就是十进制的12。但是小明没学过BCD，把所有的BCD数都当作二进制数转换成十进制输出了。于是BCD的0x12被输出成了十进制的18了！

现在，你的程序要读入这个错误的十进制数，然后输出正确的十进制数。提示：你可以把18转换回0x12，然后再转换回12。

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

void b2t(int num); //二进制转十进制

int main() {
	int num;
	scanf("%d", &num); 
	b2t(num);
	return 0;
}

void b2t(int num) {
	int f = num & 0xf; //取个位
	int s = num >> 4; // 取十位
	if (s == 0) printf("%d", f); //单独处理十位为0的情况
	else printf("%d%d", s, f);//并列输出
}

思路：用位级运算取个、十位，再单独处理十位为0的情况（因为最终是并列输出，防止输出两个0）。位级运算有时确实比数级运算方便。



7-5 表格输出 (5 分)

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

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

int main() {
	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("------------------------------------");
	return 0;
}

思路：注意最后一行无需用\n换行



7-6 混合类型数据格式化输入 (5 分)

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

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

int main() {
	int i;
	float f1, f2;
	char c;
	scanf("%f %d %c %f", &f1, &i, &c, &f2); //一开始写成了%0.2f，但scanf()不支持带点的格式写法
	printf("%c %d %0.2f %0.2f", c, i, f1, f2);
	return 0;
}

//scanf()不支持带点的格式写法，可以有长度限制，但不可以有小数位数限制
//scanf(“%5f”，&f) 这样写可以！
//scanf(“%5.2f”，&f) 这样写不可以！
//scanf(“%0.2f”，&f) 这样写不可以！

思路：scanf()不支持带点的格式写法，可以有长度限制，但不可以有小数位数限制。



7-7 12-24小时制 (15 分)

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

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

int main() {
	int h, min;
	char c;
	scanf("%d%c%d", &h ,&c , &min);
	if (24 == h) printf("0%c%d AM", c, min); //用if判断相等，常量在前，变量在后，可以避免将==写成=
	else if (h > 12) printf("%d%c%d PM", h - 12, c , min);
	else if (12 == h) printf("%d%c%d PM", h, c , min);
	else printf("%d%c%d AM", h, c , min);
    return 0;
}

思路：注意题目并不要求将0输出成00（其实我觉得这样更好看）



7-8 超速判断 (10 分)

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

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

int main() {
	int v;
	scanf("%d", &v);
	if (v > 60 ) printf("Speed: %d - speeding", v); //题目是超出60，暗示着不包括60
	else printf("Speed: %d - OK", v);
	return 0;
}

思路：题目是超出60，暗示着不包括60。



7-9 用天平找小球 (10 分)

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

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

int main() {
	int A, B, C;
	scanf("%d %d %d", &A, &B, &C);
	if (A == B) printf("%c", 'C'); //look at the ansewer need the output is char but not numbers
	if (A == C) printf("%c", 'B');
	if (B == C) printf("%c", 'A');
	return 0;
}

思路：the ansewer need the output is char but not int.



7-10 计算工资 (15 分)

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

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

int main() {
	int p, h;
	scanf("%d %d", &p ,&h);
	if (p >= 5) {
		if (h > 40) printf("%0.2f", 40 * 50 + 1.5 * (h - 40) * 50);
		else printf("%0.2f", h * 50.0);
	}
	else {
		if (h > 40) printf("%0.2f", 40 * 30 + 1.5 * (h - 40) * 30);
		else printf("%0.2f", h * 30.0); //int * int also int, therefore, set to int * float
	}
    return 0;
}

思路：int * int also int, therefore, set to int * float in order to make flaot.



7-11 分段计算居民水费 (10 分)

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

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

int main() {
	float x;
	scanf("%f", &x);
	if (x <= 15) printf("%0.2f", 4 * x / 3);
	if (x > 15) printf("%0.2f", 2.5 * x - 17.5);
	return 0;
}

思路：the input is float.



7-12 两个数的简单计算器 (10 分)

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

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

int main() {
	int a, b;
	char c;
	scanf("%d %c %d", &a, &c, &b);
	if(c == '+')
		printf("%d", a + b);
	else if(c == '-')
		printf("%d", a - b);
	else if(c == '*')
		printf("%d", a * b);
	else if(c == '/')
		printf("%d", a / b);
	else if(c == '%')
		printf("%d", a % b);
	else
		printf("ERROR");														
	return 0;
}

思路：easy.



7-13 日K蜡烛图 (15 分)

股票价格涨跌趋势，常用蜡烛图技术中的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”（即“有上影线”）。请编程序，根据给定的四个价格组合，判断当日的蜡烛是一根什么样的蜡烛。

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

int main() {
	int 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-Hollow");
	else printf("R-Cross");
	if (Low < Open && Low < Close && High > Open && High > Close) //attention to order about "if", two&& big that one&&
		printf(" with Lower Shadow and Upper Shadow");
	else if (Low < Open && Low < Close) printf(" with Lower Shadow");
	else if (High > Open && High > Close) printf(" with Upper Shadow");
        return 0;
}

思路：compare quantity of condition, lots quantity at first and low quantity at second and so on.



7-14 求整数段和 (15 分)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//C(GUN) pass and C(Clang) pass 
#include<stdio.h>

int main() {
	int A, B;
	int i,j;
	int sum = 0;
	scanf("%d %d", &A, &B);
	if ((B - A) <= 4){ //if B - A <= 4, not have a newline.
		for(i = A; i <= B; i++){
			printf("%5d", i);
			sum += i;
	        }
	}
	else
	    for(i = A, j = 1; i <= B; i++, j++){
			printf("%5d", i);
			if ((j % 5) == 0) printf("\n");
			sum += i;
            }
	printf("\nSum = %d", sum);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//C(GUN) not pass but C(Clang) pass 
#include<stdio.h>

int main() {
	int A, B;
	int i,j;
	int sum;
	scanf("%d %d", &A, &B);
	for(i = A, j = 1; i <= B; i++, j++){
	printf("%5d", i);
    	if (B - A > 4)
		if ((j % 5) == 0) printf("\n"); //if B - A > 4, have a newline.
	sum += i;
	}
	printf("\nSum = %d", sum);
	return 0;
}

思路：if B - A <= 4, not have a newline.



7-15 计算圆周率 (15 分)

根据下面关系式，求圆周率的值，直到最后一项的值小于给定阈值。
π / 2 = 1 + 1/3 + 2!/3*5 + 3!/3*5*7 + ... + n!/3*5*7*...*(2n+1)

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

int main() {
	double PI = 1, up = 1, down = 1, last = 1;
	double i;
	double t;
	scanf("%lf", &t); //"scanf" function need address(&)
	for (i = 1; last >= t; i++){
                up *= i;
		down *= i * 2 + 1;
		last = up / down;
		PI += last;
	}
	printf("%0.6lf",  2 * PI);
	return 0;
}

思路：Attention to 0! equal 1!, so set PI = 1(First iteam) and set last = up / down = 1 / 3(Second iteam) at beginning.



7-16 求符合给定条件的整数集 (15 分)

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

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 a, i, j, k, cnt = 0;
	scanf("%d", &a);
	for(i = a; i <= a+3; i++){
		for(j = a; j <= a+3; j++){
			if (i == j) continue;//若 (i == j)再一次执行第二个for循环
			for(k = a; k <= a+3; k++){
				if (i == k || j == k) continue;//若 (i == k || j == k) 再一次执行第三个for循环
				cnt++;
				if ((cnt % 6) == 0)	//保证每行末尾无空格
					printf("%d%d%d", i, j, k);
				else
					printf("%d%d%d ", i, j, k);
				if ((cnt % 6) == 0 && cnt <= 18) printf("\n"); //最后一次不换行
			}
		}
	}
	return 0;
}

思路：i，j，k按递增顺序分别对应四个数，第二个for保证j ！= i，第三个for保证k ！= i && k != j。
它们都是按递增顺序比较是否相等之后再输出，保证了输出是递增的。
在输出的每一行中，第一个for调用一次，第二个for将调用四次，第三个for将调用十八次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//法二：暴力枚举
#include<stdio.h>

int main() {
	int a;
	scanf("%d", &a);
	int b = a + 1;
	int c = a + 2;
	int d = a + 3; 
	printf("%d %d %d %d %d %d\n", a*100+b*10+c, a*100+b*10+d, a*100+c*10+b, a*100+c*10+d, a*100+d*10+b, a*100+d*10+c);
	printf("%d %d %d %d %d %d\n", b*100+a*10+c, b*100+a*10+d, b*100+c*10+a, b*100+c*10+d, b*100+d*10+a, b*100+d*10+c);
	printf("%d %d %d %d %d %d\n", c*100+a*10+b, c*100+a*10+d, c*100+b*10+a, c*100+b*10+d, c*100+d*10+a, c*100+d*10+b);
	printf("%d %d %d %d %d %d\n", d*100+a*10+b, d*100+a*10+c, d*100+b*10+a, d*100+b*10+c, d*100+c*10+a, d*100+c*10+b);
}




7-17 爬动的蠕虫 (15 分)

一条蠕虫长1寸，在一口深为N寸的井的底部。已知蠕虫每1分钟可以向上爬U寸，但必须休息1分钟才能接着往上爬。在休息的过程中，蠕虫又下滑了D寸。就这样，上爬和下滑重复进行。请问，蠕虫需要多长时间才能爬出井？

这里要求不足1分钟按1分钟计，并且假定只要在某次上爬过程中蠕虫的头部到达了井的顶部，那么蠕虫就完成任务了。初始时，蠕虫是趴在井底的（即高度为0）。

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

int main(){
  int n,u,d;
  scanf("%d%d%d",&n,&u,&d);
  int t = 0,place = 0;//时间、位置初始化为0
  while(1){
    place += u; //向上爬
	t++; //增加向上爬的时间
    if(place >= n){ //如果身体爬出井或刚好头部接触井沿，则结束循环
      printf("%d", t);
      break;
    }
    place -= d; //向下滑
	t++;//增加向下滑的时间
  }
	return 0;
}

思路：完全依照题意进行编程，重点是运用了增量这个概念，对时间进行递增，对位置进行递增和递减。



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

二分法求函数根的原理为：如果连续函数f(x)在区间[a,b]的两个端点取值异号，即f(a)f(b)<0，则它在这个区间内至少存在1个根r，即f(r)=0。

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
#include <stdio.h>
//f(x) = a3*x^3 + a2*x^2 +  a1*x + a0
double func(double a3, double a2, double a1, double a0, double x){ 
	return a3 *x*x*x + a2 *x*x + a1 *x +a0; 
}

int main() {
	double a3, a2, a1, a0, a, b, mid, func_a, func_b, func_mid;
	scanf("%lf %lf %lf %lf %lf %lf", &a3, &a2, &a1, &a0, &a, &b); //why forget `&` again ?
	while(b - a > 0.001){
		mid = (a + b) / 2;
		func_a = func(a3, a2, a1, a0, a);
		func_b = func(a3, a2, a1, a0, b);
		func_mid = func(a3, a2, a1, a0, mid);
		if (func_a * func_b < 0){
			if(func_mid == 0) {
				printf("%.2f", mid); //find it have lots time, mid != func_mid
				return 0;
			}
			else if(func_a * func_mid > 0)
      //euqal (func_mid>0 && func_a>0) || (func_mid<0 && func_a<0)
				a = mid;
			else if(func_b * func_mid > 0)
      //euqal (func_mid>0 && func_b>0) || (func_mid<0 && func_b<0)
				b = mid; //x and y have the same sign equal x*y > 0
		}
		else if(func_a * func_b == 0){
			if(func_a == 0){
				printf("%.2f", a);
				return 0;
			}
			else if(func_b == 0){
				printf("%.2f", b);
				return 0;
			}
		}
	}
	printf("%.2f", (a + b) / 2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//segmentation fault
int* get(){
	int *coef;
	int i;
	for(i = 0; i <= 3; i++)
		scanf("%d", &coef[i]); //coef[0] ~ coef[3] order to a3 ~ a0
	return coef;
}
// can't use array[], because it will segmentation fault

int *coef = get();

double func(int *coef, double x){ //f(x) = a3*x^3 + a2*x^2 +  a1*x + a0
	int i; 
	return coef[0] *x*x*x + coef[1] *x*x +coef[2] *x +coef[3]; 
  // can't use pow() function, because it will segmentation fault
  // will use lots time every time use func will use 4 times pow()
}

thoughts：

  • try to submit array address to func, but segmentation fault.
  • try to use double pow(double x , double n) , but also segmentation fault.
  • x and y have the same sign equal x*y > 0.
  • forget & again…when I no pay attention to it.
  • mid != func_mid! ! ! !




7-19 支票面额 (15 分)

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

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

int main(){
  int y, f, n;
  int i = 0; //支票面额从0开始
  scanf("%d", &n);
  while(i <= 10000){ //题目应给出支票面额的取值范围，否则会超时
    y = i / 100;
    f = i % 100;
    if (f*100 + y - n == 2*y*100 + 2*f){
      printf("%d.%d", y, f);
      return 0; //跳出循环，并且结束函数
    }
    i++;
  }
  printf("No Solution");
  return 0;
}

思路：完全依照题意进行编程，思路上按照题意来，然后逐个解决。我是将输出结果看成四位数，然后分别取前两位，后两位。f*100 + y - n == 2*y*100 + 2*f其实是对“结果出纳员错给了f元y分。采购员用去了n分之后才发觉有错，于是清点了余额尚有2y元2f分”的数学表示。注意，**return 0可以不止写一条，只要满足要求**。



7-20 打印九九口诀表 (15 分)

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

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，输出从1*1到N*N的部分口诀表。

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

int main(){
  int i, j, n;
  scanf("%d",&n);
  for(i = 1; i <= n; i++)
    for(j = 1; j <= i; j++){
      if (j*i <= 9 ) printf("%d*%d=%d   ", j, i, j*i);
      else printf("%d*%d=%d  ", j, i, j*i);
      if(j == i) printf("\n");
  }
	return 0;
}

思路：注意输出格式，左对齐，等式右端包括数值一共占4位。



7-21 求特殊方程的正整数解 (15 分)

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

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 i, j, n, flag = 0, a[10], b[10];
	scanf("%d", &n); //scanf的输入是存在地址上的
	for(i = 1; i <= 100; i++)
		for(j = 1; j <= i; j++){
			if (i*i + j*j == n) {
				a[flag] = j;
				b[flag] = i;
				flag++;
			}
			// else 
			// 	continue;
		}
	if(!flag) 
		printf("No Solution");
	else
		for(i = flag - 1; i >= 0; i--)
			printf("%d %d\n", a[i], b[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//参考解法二
#include<stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  int i, j, flag=1;
  for(i=1; i<=100; i++)
    for(j=1; j<=100; j++)
      if(i*i + j*j == n && i < j){
        printf("%d %d\n",i,j);
        flag=0;
      }
  if(flag) printf("No Solution");
  return 0;
}

思路：个人解法中，使用数组使得x<=y，但过于繁琐了，不如参考解法中的i，j共同遍历，满足i < j即可。同时需要注意到题目要求是正整数求解，也就是说不包括0和负数。




7-22 龟兔赛跑 (20 分)

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

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
#include<stdio.h>

int main(){
	int rab_speed = 9, tur_speed = 3;
	int rabbit = 0, turtle = 0;
	int T, rab_sleep = -1, rab_time = 10; 
  /*rab_sleep = -1 because line 17 of 'rab_sleep != 0' and line 22 of 'rab_sleep-- == 0'
  rabbit can't sleep at bgain and We can't every minutes reset 'rab_time = 10'
  */
	scanf("%d", &T);
	while(T--){// count down T
		turtle += tur_speed;
		if(rab_time-- > 0)// count down 10_min
			rabbit += rab_speed;
		if(rab_time == 0){ // Execute when the 10 min countdown is over
		/* rabbit above turtle and rabbit not sleep */
			if(rabbit > turtle && rab_sleep != 0) 
			rab_sleep = 30;
			else 
			rab_time = 10;
    }
		if(rab_sleep-- == 0)// count down sleep_time
			rab_time = 10;
	}
	if(rabbit > turtle)
		printf("^_^ %d", rabbit);
	else if(rabbit < turtle)
		printf("@_@ %d", turtle);
	else
		printf("-_- %d", rabbit);
	return 0;
}

thought：learn using countdown design.




7-23 币值转换 (20 分)

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

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
#include<stdio.h>
int main()
{
	int num, temp;
	int count = 0;
	int dec; 
	int i, j;
	int flag = 0;
	int data[10];
	scanf("%d",&num);
	temp = num;
	if(num == 0){//单个0时输出
		printf("a");
	}
	while(num != 0){//将数字分解，并存入数组data[]中
		i = num % 10; //取最低一位
		data[count] = i;
		count++;
		num = num / 10; //截掉最低位，更新num
	}
	dec = count + 1; //之所以要+1是因为每次使用前要自减（line23）
	for(j = count-1; j >= 0; j--){//j = count-1，是因为while循环结束时，count还要自加一次，减去1以抵消这一次自加
		dec--;// dec表示数字分解后，总共分解出多少个数字
		if(temp > 10000 && data[j] == 0 && data[j-1] == 0 && data[1] != 0 && flag == 0){
			//超过一万，中间连续多个0解决方法
			//原理是要满足：num大于一万，而且至少有两个连续的0，以及num的从右往左数，第2个数为不为0，即data[1] != 0.
			flag++; //最后要用flag保证满足时只输出一次'W'。
			printf("W");
		}
		if(data[j] == 0 && data[j-1] == 0){//只满足至少有两个连续的0，则重新开始循环
			continue;
		}
		switch(data[j]){//数字转字母
			case 0:
				printf("a");
				break;
			case 1:
				printf("b");
				break;
			case 2:
				printf("c");
				break;
			case 3:
				printf("d");
				break;
			case 4:
				printf("e");
				break;
			case 5:
				printf("f");
				break;
			case 6:
				printf("g");
				break;
			case 7:
				printf("h");
				break;
			case 8:
				printf("i");
				break;
			case 9:
				printf("j");
				break;
		}	
		if(data[j] != 0){//数字转单位
			switch(dec)//直到用完分解的数才结束
			{
				case 1:
					break;
				case 2:
					printf("S");
					break;
				case 3:
					printf("B");
					break;
				case 4:
					printf("Q");
					break;
				case 5:
					printf("W");
					break;
				case 6:
					printf("S");
					break;
				case 7:
					printf("B");
					break;
				case 8:
					printf("Q");
					break;
				case 9:
					printf("Y");
					break;
			}	
		}
	}
	return 0;
}

思路：从最低位分解数字，之后要考虑中间连续为0时，是否有过万。




7-24 约分最简分式 (15 分)

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

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

int main(){
  int num, den, x, x_max, com_fac_max;
  char sem;
  scanf("%d%c%d", &num, &sem, &den);
  x_max = num < den ? num : den; //smaller number as x_max
  for(x = 1; x <= x_max; x++)//find 'com_fac_max'
    if (num % x == 0 && den % x == 0) 
      com_fac_max = x; //updata 'com_fac_max'
  printf("%d%c%d", num / com_fac_max, sem, den / com_fac_max);
  return 0;
}

though: traveral 1 ~ x_max to find com_fac_max(maxinum of common factor).

还找到了一个简洁优雅的递归函数来求最大公因数：

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

int gcd(int x, int y){return y ? gcd(y, x%y) : x;}//find maxinum of common factor

int main(){
  int num, den, com_fac_max;
  char sem;
  scanf("%d%c%d", &num, &sem, &den);
  com_fac_max = gcd(num, den);
  printf("%d%c%d", num / com_fac_max, sem, den / com_fac_max);
  return 0;
}




7-25 念数字 (15 分)

输入一个整数，输出每个数字对应的拼音。当整数为负数时，先输出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

**AC 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
#include <stdio.h>
int main(){
  int num, cut[100], i;
  scanf("%d", &num);
  if (num == 0){ 
    printf("ling"); 
    return 0;
  }
  if (num < 0){
    printf("fu ");
    num = ~num + 1;//取补码，即取绝对值，但对int_min = -2147483648无效
  }
  if (num == -2147483648){//单独拎出来输出
    printf("fu er yi si qi si ba san liu si ba");
    return 0;
  }
  for(i = 1; num != 0 ;i++){ //当不等于0时才执行
    cut[i] = num % 10;
    num /= 10; //更新num
  }
  i--;
  while(i){
    switch (cut [i]){
    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;      
    }
    i--; //降序输出
    if (i != 0) //确保最后一个数字之后没有空格，而其它数字之后有空格
      printf(" ");
  }  
  return 0;
}

思路：不断分割输入的整数，但注意for循环结束后的i，比所需的cut[i]的i值多了1，需要减去。同时输出时是按i值降序（从大到小）输出的。



7-26 单词长度 (15 分)

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

**AC 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 (){
  char c;
  int flag = 0, count;
  while(1){
    count = 0; //set(reset) count
    scanf("%c",&c); //set(reset) first character
    while(c != ' ' && c != '.'){ //count and input
      count++; 
      scanf("%c", &c);
    }
    if(count != 0){
      flag++;
      if(flag == 1) printf("%d", count); //first number
      else printf(" %d", count); //other numbers
    }
    if(c == '.') break;
  }
  return 0;
}

ideas:

  • Before counting, we must set(reset) count and the first c.
  • The format of output are one numbers: %d or some numbers: %d %d %d %d, so we must set flag.




7-27 冒泡法排序 (20 分)

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

本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。

输入格式：

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

输出格式：

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

输入样例：

1
2
3
6 2
2 3 5 1 6 4
结尾无空行

输出样例：

1
2
2 1 3 4 5 6
结尾无空行

AC 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 N, K;
  int i, j;
  scanf("%d %d", &N, &K);
  int num[N];
  int temp, flag;
  for(i = 0; i < N; i++){
    scanf("%d", &num[i]);
  }
  for(i = 0; i < K; i++){
    for(j = 1; j < N; j++){
      if(num[j - 1] > num[j]){ //swap
        temp = num[j];
        num[j] = num[j - 1];
        num[j - 1] = temp;
      }
    }
    N--; //last number already is max, so reset `N`
  }
  for(i = 0; i < N+K; i++){ //use flag in order to Format
    if(flag == 0)
      printf("%d", num[i]);
    else
      printf(" %d", num[i]);
    flag++;
  }
  return 0;
}

ideas:

  • Begain using debug;
  • contiune running of models;
  • step over running of ‘’one by one’’(“line by line”);
  • step into into this function, and then do this function of ‘’one by one’’;
  • step out leave this function.




7-28 猴子选大王 (20 分)

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

AC 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
#include <stdio.h>

int main(){
	int N;
	scanf("%d", &N);
	int a[N];
	int i;
	for (i=0; i<N; i++)
		a[i]=i+1;
	int elimination = 0; //淘汰变量 
	int remainder = N; //剩余变量 
	while (remainder > 1){
		for (i=0; i<N; i++){
			if (a[i] == 0) 
				continue; 
			//序号为0的猴已淘汰，不计数，直接进入下一轮循环 
			elimination++;
			if (elimination == 3){
				a[i] = 0; //淘汰之后的猴子序号设为0 
				elimination = 0; //淘汰变量重置 
				remainder--; //剩余猴数减1 
			}
		}
	}
	for (i=0; i<N; i++)
		if (a[i] != 0)
			printf("%d\n", i+1);
	return 0;
}

思路：引入两个计数变量，第一个变量作为淘汰变量，每数到3淘汰一个，重新计数；
第二个变量作为剩余变量，记录剩余猴子数，每淘汰一个减少1，当剩余变量为1时，结束。




7-29 删除字符串中的子串 (20 分)

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

AC code: 

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

int main (){
	char s1[100], s2[100], temp[100];
	gets(s1);
	gets(s2);
	char *s1_s2; //当s1中含有s2时, s1_s2视为s1中的s2首地址
	while(s1_s2 = strstr(s1, s2)){ //比对，当s1中含有s2时，执行循环（此时s1_s2为s1中的s2首地址）；若s1中不含有s2，则循环结束（此时s1_s2为NULL）
		strcpy(temp, s1_s2 + strlen(s2)); //s1_s2加上s2的长度用来跳过想要删除的子串，将跳过之后的字符串复制到临时数组 
		*s1_s2 = '\0'; //把s1_s2此时存放的字符变为'\0'，以下一步用strcat实现拼接
		strcat(s1, temp); //将临时数组拼接在s1_s2的位置之后（即s1的第一个终止符'\0'之后） 
	}
	puts(s1);
	return 0;
}

解答二：利用string.h库中的字符串函数解决

提示：在 C 语言中，字符串实际上是使用字符 \0 终止的一维字符数组。

先来介绍要用到的字符串函数：

1、char *strstr( const char *str1, const char *str2 );

功能：用于判断字符串str2是否是str1的子串。如果是，则该函数返回 str1字符串从 str2第一次出现的位置开始到 str1结尾的字符串；否则，返回NULL。

2、char *strcpy( char *str1, const char *str2 );

功能：复制，把从str2地址开始且含有NULL结束符的字符串复制到以str1开始的地址空间

3、char *strcat( char *str1, const char *str2 );

功能：拼接，把str2所指向的字符串（包括\0）复制到str1所指向的字符串后面（删除str1原来末尾的\0)。注意要保证str1足够长，以容纳被复制进来的*str2。

注意：以上两个函数（strcpy,strcat）中str1和str2所指内存区域不可以重叠且str1必须有足够的空间来容纳str2的字符串。因此代码中定义了一个临时数组。

解法参考链接；字符串函数参考链接；c语言NULL和0区别及NULL详解




7-30 字符串的冒泡排序 (20 分)

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

AC 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
#include <stdio.h>
#include <string.h>

int main(){
  int N, K;
  int i, j;
  scanf("%d %d", &N, &K);
  char str[N][11];//using two-dimensional array so that each element is a string
  char temp[11]; //if have 10 character, the 11 character is '\0'
  for(i = 0; i < N; i++){
    scanf("%s", &str[i]);
  }
  for(i = 0; i < K; i++){
    for(j = 0; j < N - 1; j++){
      if(strcmp(str[j], str[j+1]) > 0){ //swap
				strcpy(temp, str[j]);
				strcpy(str[j], str[j+1]);
				strcpy(str[j+1], temp);
      }
    }
    N--; //last strber already is max, so reset `N`
  }
	for(i = 0; i < N+K; i++)
		printf("%s\n", str[i]);
	return 0;
}

提示：在 C 语言中，字符串实际上是使用字符 \0 终止的一维字符数组。

介绍string.h中的字符串函数：

  • char *strcpy( char *str1, const char *str2 );
    功能：复制，把从str2地址开始且含有NULL结束符的字符串复制到以str1开始的地址空间
  • int *strcmp( char *str1, const char *str2 );
    用于比较两个字符串并根据比较结果返回整数。若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。

字符串函数参考链接；c语言NULL和0区别及NULL详解




7-31 字符串循环左移 (20 分)

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

输入格式：

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

输出格式：

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

输入样例：

1
2
3
Hello World!
2
结尾无空行

输出样例：

1
2
llo World!He
结尾无空行

AC 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
#include <stdio.h>
#include <string.h>

int main(){
  int n;
  char s1[101], s2[101], temp[101];
  char* s1_s2;
  gets(s1);
  scanf("%d", &n);
  int len = strlen(s1);
  if(n % len == 0){ //由于是循环左移，要考虑n是s1长度的倍数的情况
    puts(s1);
    return 0;
  }
  if(n > len){ //由于是循环左移，要考虑n大于s1长度的情况
    n -= (n / len) * len;
  }
  strncpy(s2, s1, n);
  s1_s2 = strstr(s1, s2);
  strcpy(temp, s1_s2 + n);
  *s1_s2 = '\0';
  strcat(s1, temp);
  strncat(s1, s2, n);
  // puts(s1);
  for(int i = 0; i < len; i++){
    printf("%c", s1[i]);
  }
  return 0;
}

思路：又学习了两个字符串函数；参考了7-29，但是要区别这是循环左移；最后发现puts()函数会导致段错误。

提示：在 C 语言中，字符串实际上是使用字符 \0 终止的一维字符数组。

介绍string.h中的字符串函数：

  • char *strncpy( char *str1, const char *str2, int n );
    功能：复制，把从str2地址开始且含有NULL结束符的前n个字符串复制到以str1开始的地址空间
  • char strncat( char *str1, const char *str2, int n );
    功能：拼接，把str2所指向的字符串的前n个字符（再加一个\0）复制到str1所指向的字符串后面（删除str1原来末尾的\0)。注意要保证str1足够长，以容纳被复制进来的str2




7-32 说反话-加强版 (20 分)

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

输入格式：

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

输出格式：

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

输入样例：

1
2
Hello World   Here I Come
结尾无空行

输出样例：

1
2
Come I Here World Hello
结尾无空行

AC 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>//标准c，没有用c++的string，这样首先读取字符串就是个问题了 
#define MAX 500000


int main (){
    char c;//存放单独一个字符 
    char t[MAX];//创建一个字符数组 
    int i = 0, count = 0, flag = 0;

    //先处理字符串，删除多余的空格(包括头尾、中间的空格)，形成新字符串 
    while ((c = getchar()) != '\n') {//getchar每次从标准输入读入一个字符 ，标准输入会有'\n'??? 
        if (c != ' ') {
            flag = 1; //标记遇到单词 
            t[i++] = c;
            count = 0;
        } 
        else if (count > 0) {
            continue;//遇到连续两个空格或以上用contiue跳过
        } 
        else if (flag) {
            t[i++] = c; //只有之前遇到单词的情况下碰到空格才把这个空格写入目标字符串 
            count = 1;
        }
    }
    //删除多余的空格，将目标字符串放入 t 中 
    //这里的count起了什么作用呢？ 
    //如遇到 Hello,都存入t中，遇到第一个空格，此时count=0,flag=1，把这个空格存入t,count=1
	//遇到连续两个空格或以上用continue跳过作用，如World之后有三个空格
    //开头就是空格咋办？啥也不操作 
    
    //倒着输出单词
    count = 0;
    int j;
    for (i -= 1; i >= 0; i--) {//最后一个标号为i里面是存'\0'的，一开始要用i-=1避免输出 
        if (t[i] != ' ') {
            count ++; // 这里的 count 统计的是一个单词里字母的个数 
        } else if (t[i] == ' ' && count > 0) {//遇到空格就输出单词 
            for (j = i+1; j <= i+count; j++) {//但注意对于单个字母而言是顺序输出，对单个单词是倒着输出
                printf("%c", t[j]);
            } 
            printf(" ");
            count = 0;
        }
    }
    // 还剩最后一个单词没输出，因为最后一个单词前方无空格，只完成了count++，但是遇不到空格，那么逻辑是一样的
    count--;
    for (j = 0; j <= count; j++) {//输出最后一个单词
        printf("%c", t[j]);
    } 
    return 0; 
}

思路：多使用标记，如flag, count。Reference Linking



7-33 有理数加法 (15 分)

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

输入格式：

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

输出格式：

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

输入样例1：

1
2
1/3 1/6
结尾无空行

输出样例1：

1
2
1/2
结尾无空行

输入样例2：

1
4/3 2/3

输出样例2：

1
2

AC 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
#include <stdio.h>

int gcd(int x, int y){return y ? gcd(y, x%y) : x;}//find maxinum of common factor

int main(){
	int a1,a2,b1,b2;
	int a,b;
  
	scanf("%d/%d %d/%d", &a1, &b1, &a2, &b2);
	if(b1 == b2){ //add
		a = a1 + a2;
		b = b1;
	}
	else{
		b = b1 * b2;
		a1 = a1 * b2;
		a2 = a2 * b1;
		a = a1 + a2;
	}

	if(a%b == 0) //can exact division
	  printf("%d", a/b);
	else{ //find common factor of maximum
    int com_fac_max = gcd(a, b);
	  printf("%d/%d", a/com_fac_max, b/com_fac_max);
  }
	return 0;
}

idea： refer to [7-24 约分最简分式 ](# 7-24 约分最简分式 (15 分))



7-34 通讯录的录入与显示 (10 分)

日期：21.11.8

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

输入格式：

输入在第一行给出正整数N（≤10）；随后N行，每行按照格式姓名 生日 性别 固话 手机给出一条记录。其中姓名是不超过10个字符、不包含空格的非空字符串；生日按yyyy/mm/dd的格式给出年月日；性别用M表示“男”、F表示“女”；固话和手机均为不超过15位的连续数字，前面有可能出现+。

在通讯录记录输入完成后，最后一行给出正整数K，并且随后给出K个整数，表示要查询的记录编号（从0到N−1顺序编号）。数字间以空格分隔。

输出格式：

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

输入样例：

1
2
3
4
5
6
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
结尾无空行

输出样例：

1
2
3
LaoLao 057187951100 +8618618623333 F 1967/11/30
Not Found
结尾无空行

AC 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
#include<stdio.h>

struct unit{
  char name[11]; //10 characters + 1 '\0' = 16 char
  char day[11];
  char gender;
  char telephone[17]; //15 numbers + 1 '\0' + 1 char of '+' = 17 char
  char mobile[17];
};

int main() {
  int N, K, num;
  int i;
  scanf("%d\n", &N);
  struct unit info[N];
  for(i = 0; i < N; i++){
    scanf("%s %s %c %s %s", &info[i].name, &info[i].day, &info[i].gender, &info[i].telephone, &info[i].mobile);
  }
  scanf("\n%d", &K); // After inputing all strings, you input K 
  for(i = 0; i < K; i++){
    scanf("%d", &num);
    if(num >=0 && num < N) //num is integer so maybe < 0
      printf("%s %s %s %c %s\n", info[num].name, info[num].telephone, info[num].mobile, info[num].gender, info[num].day);
    else
      printf("Not Found\n");
  }
  return 0;
}

idea: use struct array and string %s.




7-35 有理数均值 (20 分)

日期：21.11.8

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

输入格式：

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

输出格式：

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

输入样例1：

1
2
3
4
1/2 1/6 3/6 -5/10
结尾无空行

输出样例1：

1
2
1/6
结尾无空行

输入样例2：

1
2
2
4/3 2/3

输出样例2：

1
1

AC 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
#include <stdio.h>

int gcd(int x, int y){return y ? gcd(y, x%y) : x;}//find maxinum of common factor

int main(){
	int sum = 0, N, com_fac_max;
	scanf("%d", &N);
	int a[N], b[N];
	for (int i = 0; i < N; i++){//每次输入都约分防止求和时溢出
		scanf("%d/%d", &a[i], &b[i]);
		com_fac_max = gcd(a[i], b[i]);
		a[i] = a[i] / com_fac_max;
		b[i] = b[i] / com_fac_max;		
	}

	int big, min, last_min;
	if (N == 1){
		min = b[0];
		last_min = b[0];
	}
	else{ //求分母的最小公约数，按顺序两两比较来求
		big = b[0] > b[1] ? b[0] : b[1]; //如果只有两个数，要单独找
		for (int i = 0; i < N - 1; i++){ //'i < N - 1'是因为最后一个分母是b[(N-2) + 1] = b[N-1]
			big = big > b[i+1] ? big : b[i+1]; //找大的分母
			for(int j = 1; j < 100; j++){ 
				min = big * j; //用大的分母不断线性递增
				if(min % b[i+1] == 0 && min % b[i] == 0){ //使得恰好两个分母都能整除
					last_min = min; //更新分母的最小公约数
					break;
				}
			}
		}
	}
	
	for (int i = 0; i < N; i++){//统一分母为最小公约数后，化简分子
			a[i] = last_min / b[i] * a[i];
	}

	for (int i = 0; i < N; i++){//分子求和
			sum += a[i];
	}

	int down = last_min * N; //分母记得乘上数据个数，以求均值

	if(sum % down == 0) //分子可以完全整除分母时，就直接除
	  printf("%d", sum/down);
	else{ //否则再约分一次
    com_fac_max = gcd(sum, down);
	  printf("%d/%d", sum / com_fac_max, down / com_fac_max);
  }		
	return 0;
}

思路：

  • 主要是求多个分母的最小公约数那一块，要考虑到只有一个数、只有两个数的边界情况。本质上还是用for循环一个个找，使得能够两两被整除。
  • 报错提示：“若不随时化简，则会溢出”，告诉我们要考虑到分子求和可能会溢出的情况，所以每输入一次就化简一次。
  • gcd(int x, int y)仍旧源自 [7-24 约分最简分式 ](# 7-24 约分最简分式 (15 分))




7-36 复数四则运算 (15 分)

日期：21.11.22

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

输入格式：

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

输出格式：

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

输入样例1：

1
2
2 3.08 -2.04 5.06
结尾无空行

输出样例1：

1
2
3
4
5
(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
结尾无空行

输入样例2：

1
1 1 -1 -1.01

输出样例2：

1
2
3
4
(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

AC 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 <stdlib.h>
void Print_left(float a1, float b1, float a2, float b2, char c);
void Print_result(float res1, float res2);
float round(float num); 

int main(){
	float a1,b1,a2,b2;
	scanf("%f %f %f %f", &a1, &b1, &a2, &b2);
	Print_left(a1, b1, a2, b2, '+');
	Print_result(round(a1 + a2), round(b1 + b2));
	Print_left(a1, b1, a2, b2, '-');
	Print_result(round(a1 - a2), round(b1 - b2));
	Print_left(a1, b1, a2, b2, '*');
	Print_result(round(a1*a2 - b1*b2), round(a1*b2 + a2*b1));
	Print_left(a1, b1, a2, b2, '/'); 
	Print_result(round((a1*a2 + b1*b2) / (a2*a2 + b2*b2)), round((-a1*b2 + a2*b1) / (a2*a2 + b2*b2)));
	return 0;
} 

//打印等号左边及等号
void Print_left(float a1, float b1, float a2, float b2, char c){
	if(b1 < 0 && b2 < 0) 
    printf("(%0.1f%0.1fi) %c (%0.1f%0.1fi) = ",a1,b1,c,a2,b2);
	else if(b1 < 0) 
    printf("(%0.1f%0.1fi) %c (%0.1f+%0.1fi) = ",a1,b1,c,a2,b2);
	else if(b2 < 0) 
    printf("(%0.1f+%0.1fi) %c (%0.1f%0.1fi) = ",a1,b1,c,a2,b2);
	else 
    printf("(%0.1f+%0.1fi) %c (%0.1f+%0.1fi) = ",a1,b1,c,a2,b2);
}
//打印结果（即打印等号右边）
void Print_result(float res1, float res2){
	if(res1 == 0 && res2 == 0) 
    printf("0.0\n");
	else if(res1 == 0) 
    printf("%0.1fi\n",res2);
	else if(res2 == 0) 
    printf("%0.1f\n",res1);
	else if(res2 < 0) 
    printf("%0.1f%0.1fi\n",res1,res2);
	else 
    printf("%0.1f+%0.1fi\n",res1,res2);
} 

//四舍五入，要区分正负数的情况 
float round(float num){
	if(num > 0) 
    num = (int)(num*10 + 0.5)/10.0;
	else 
    num = (int)(num*10 - 0.5)/10.0;
	return num;
}

思路：

  • 先计算再四舍五入最后才输出（保留一位小数），注意四舍五入要区分正负数。
  • 复数乘法、除法采用数学公式即可
  • 等号左右式子的格式都需要用if语句区分情况。

参考链接




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

日期：

21.12.20

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

输入格式：

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

输出格式：

按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni*+1<*mi*+1,则N1序列必定在N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。

输入样例：

1
2
7
结尾无空行

输出样例：

1
2
3
4
5
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
结尾无空行

AC 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
#include<stdio.h>

int N;
int num[31]; //用数组存放划分结果
int index = -1; //数组的下标（索引），表示拆分项的个数
int sum = 0; //拆分项的累加和，若sum == N则输出，若sum < N则放弃该递归，若sum < N则执行算法和递归
int count = 0; //统计输出的次数，作为辅助，保证输出格式满足题目要求,每行最多四个式子
//以上都是全局变量

void division (int x);

int main(){
    scanf("%d", &N);
    division(1); //拆分项从最小正整数 == 1开始，直到满足num[0] == sum == N
    return 0;
}

void division (int x) {//拆分 
    //输出部分 
    if (sum == N) {
        count ++;
        printf("%d=", N);
        int j;
        for (j = 0; j < index; j++) 
            printf("%d+", num[j]); //输出拆分项
        if (count % 4 == 0 || num[index] == N) 
            printf("%d\n", num[index]);
        else 
            printf("%d;", num[index]);
        return 0;
    } 

    //算法主体 
    if (sum > N) {
        return 0;
    }
    for (int i = x; i <= N; i++) { //拆分项从最小正整数 i== 1开始，注意，这里只改变某一项的数值
        num[++index] = i; //在完成全1拆分后，从最后一项 i== 2开始
        sum += i; 
        division (i);//进入递归
        sum -= i; //放弃上一个拆分项，以便下一次重新求和
        index --; //在每一个for循环中保持不变，但在进入下一个for时循环执行自减，使数组范围变小
    } 
}

思路：
如图所示，以N = 3为例子，可以看到，一开始拆分项全都为1，而后从最后一项 i== 2开始变化，执行这一次的for循环。总共3个黑框代表3个for循环。最后退出循环是因为只有一个division，没有递归直接return回main。

参考链接




7-38 数列求和-加强版 (20 分)

日期：

21.12.21

给定某数字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。

输入格式：

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

输出格式：

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

输入样例：

1
2
1 3
结尾无空行

输出样例：

1
2
123
结尾无空行

AC 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>
#include <stdlib.h>
 
int main(){
    int A = 0;
    int N = 0;
    scanf("%d%d", &A, &N);
    int flag = 0; //是否为N+1位数的标志
    int carry = 0; //临时存放进位数值
    int* num = (int*)malloc(sizeof(int) * (N + 1)); //创建动态数组指针
    if (A == 0 || N == 0) //独立“0”的特殊情况
        printf("0");
    else{ 
        for (int i = 0; i < N; i++){        
            if (i == 0)
                num[i] = A * N % 10; //个位数值
            else
                num[i] = (A * (N - i) % 10 + carry) % 10; //除个位以外的数值    
            carry = (A * (N - i)  + carry) / 10; //计算进位数值
            if (i == N - 1 && carry != 0){ //N+1位数存在的判断条件
                num[N] = 1;
                flag = 1;
            }
        }
    }
    if (flag == 1)
        for (int i = N; i >= 0; i--)
            printf("%d", num[i]);
    else
        for (int i = N-1; i >= 0; i--)
            printf("%d", num[i]);
    return 0;
}

思路：

  • 双长整型也无法保存100,000个数值，所以用动态数组指针

  • A = 0，N = 0 是特殊情况，单独处理

  • 以计算A = 9，N = 4 为例，计算：9 + 99 + 999 +9,999 = 11,106

    个位：num[0] = 9 * 4 % 10 = A * N % 10 = 6
    个位的进位为carry = (9 * 4 ) / 10 = 3

    十位：num[1] = (9 * 3 % 10 + 3) % 10 = (A * (N - 1) % 10 + carry) % 10 = 0
    十位的进位为carry = (9 * 3 + 3) / 10 = 3

    百位：num[2] = (9 * 2 % 10 + 3) % 10= (A * (N - 2) % 10 + carry) % 10 = 1
    百位的进位为carry = (9 * 2 + 3) / 10 = 2

    千位：num[3] = (9 * 1 % 10 + 2 ) % 10= (A * (N - 3) % 10 + carry) % 10 = 1
    千位的进位为carry = (9 * 1 + 2) / 10 = 1

    万位：num[4] = 1

  • 可见满足规律：
    num[i] = (A * (N - i) % 10 + carry) % 10 和 carry = (A * (N - i) + carry) / 10
    结果必为N位或者N+1位数，其中如果有N+1位数其数值必为1。

参考链接

conclusion

  • 完结了呀
  • 熟悉了c的很多基本操作
  • 期间因为参加六级考试和做csapp的实验，断了一个月的训练时间，不过还是搞定了
  • 是一段艰苦的旅程，但还是很愉快地学到许多技巧
  • 最近在听佐藤直纪的《异邦人の刃》和《空の涯まで》，以及五月天的《有些事现在不做 一辈子都不会做了》，推荐给你们

​ 21.12.21