C++ | 奥赛一本通刷题笔记

本文档2023-12-17上线在博客处。

顺序结构程序设计

运算符和表达式

交换2个整型变量的值

  1. 交换指针指向的内容
  2. C++交换函数swap(n1, n2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

using namespace std;

template <class T>

// *pa表示解引用，得到pa所指的值
// 相当于让num1的指针指向num2的值，让num2的指针指向1的值
void swap1(T *p1, T *p2)
{
    T temp = *p1; // temp的值是p1指向的值，作为临时交换变量
    *p1 = *p2;    // p1指向的值是p2指向的值
    *p2 = temp;   // p2指向的值是p1指向的值
}

int main()
{
    int num1, num2, z;
    cin >> num1 >> num2;
    swap1(&num1, &num2); // 传入的是地址&Var，实质是交换指针的指向项；
    cout << num1 << ' ' << num2;
    return 0;
}

买图书

考点是小数的输出，方法有：

  1. c语言printf格式化："%.nf"，n是输出的小数位数，默认6位
  2. c++引用<iomanip>，cout << fixed << setprecision(2);控制输出位数，此后输出的都是2位小数
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    float n, m;
    cin >> n >> m;
    printf("%.2f", n - m * 0.8);
    return 0;
}

计算分数浮点数值

使用了 1.0 * a / b ，使得被除数是一个double类型，才能得到正确的解。否则，小数部分会丢失，整数除以整数结果还是整数。

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

using namespace std;

int main()
{
    int a, b;
    double c;
    cin >> a >> b;
    c = 1.0 * a / b; 
    // 使用了“1.0 * a / b”，使得被除数是一个double类型，才能得到正确的解。否则，小数部分会丢失。
    cout << fixed << setprecision(9);
    cout << c;
    return 0;
}

常量和变量

计算百分数

题目要求：保留三位小数，用百分数输出。

关键在于小数位数的保留和百分数的输出：

  • 小数位数：C语言 printf 格式控制 "$.nf"，c++使用 cout << fixed << setprecision(n);进行小数位数的控制
  • 百分数的输出：C语言 printf 中，在%前面再加一个%

输出
printf 的输出
使用格式控制符来指定输出的格式。
格式控制符以 % 开头，可以和其他字符组合使用。基本的语法是：printf("格式控制", 内容);
格式控制 可以把内容进行格式化，例如 %d 十进制整数、%o 八进制整数、%c 一个字符、%s 字符串、%f 小数形式输出实数（包括单精度、双精度）、%e 指数形式输出实数、%g 字段选择小数形式或指数形式输出，且不输出无意义的0.
m 可确定输出范围，n 确定小数位数
特别地，对于字符串

  • %ms：输出的字符串占m列，如字符串本身长度大于m，则突破获m的限制,将字符串全部输出。若串长小于m，则左补空格。
  • %-ms：如果串长小于m，则在m列范围内，字符串向左靠，右补空格。
  • %m.ns：输出占m列，但只取字符串中左端n个字符。这n个字符输出在m列的右侧，左补空格。

输入

  • C语言可使用
    • scanf()，读取不包括空格和终止符（默认换行符）
    • fgets()
  • C++中可使用
    • cin >>类似于scanf()，是std中的。
    • cin.get()读取单个或指定长度字符，读取包括空格，不包括终止符（默认换行符）。
    • cin.getline()读取指定长度的字符，读取包括空格，不包括终止符，且读取完成后会把输入流设定为Fail状态。可用于char str[100]这样的char类型的字符串整行输入cin.getline(str, sizeof(str))。
    • getline 读取所有空白字符（整个缓存区），不包括换行符，读取完后无残留。是字符串流的函数，只能读取string对象，使用时需要包含头文件<stirng>。可用于string s这样的的string类型的字符串的整行输入getline(cin, s);。

字符串

  • 一个带空格的句子的存储办法可以是str[100]这样的指定长度的字符串（C语言风格）
  • 另一种办法是用封装好的字符串类string（C++风格），动态分配长度
    • 可以进行赋值、连接、获取长度等操作

类型 char string
定义 char str[size] string s
求长度 函数strlen(str)，操作运算符sizeof(str) 成员函数length()、成员函数size()，也可以转换为char*类型,使用char的strlen（通过s.c_str()）
复制 strcpy(str1, str2) s1 = s2
整行输入 cin.getline(str, needsize) getline(cin, s)
备注 空字符也要算入needsize
读取及修改单个字符 str[i] s[i] 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <iomanip>
#include <stdio.h>

using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    printf("%.3f%%", n*1.0/m*100);
    return 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
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

double cal(int m, double n)
{
    double temp = n;
    for (int i = 0; i < m - 1; i++)
        n *= temp;
    return n;
}

int main()
{
    double a, b, c, d, x, res;
    cin >> x >> a >> b >> c >> d;
    a = a * 1.0 * cal(3, x);
    b = b * 1.0 * cal(2, x);
    c = c * 1.0 * cal(1, x);
    cout << fixed << setprecision(7);
    cout << a + b + c + d << endl;
    return 0;
}

标准数据类型

浮点数取整

（强制类型转换）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

int main()
{
    float a;
    cin >> a;
    int b = int(a);
    cout << b << endl; //或者直接输出int(a)
    //printf("%d\n", (int)b); //C语言的办法
    return 0;
}

输出字符的ASCII值

核心思路还是类型转换，把char变成int

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

int main()
{
    char x;
    scanf("%s", &x);
    printf("%d\n", int(x));
    return 0;
}

输出字符串的长度

不要想太复杂

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

int main()
{
    printf("%d\n", sizeof("Hello, World!"));
    return 0;
}

对字符串赋值

C语言

  1. C语言中，可以通过字符数组进行初始化。注意，不可以对数组名直接赋值。
1
2
3
4
5
6
int main()
{
	char str[10] = "China";//还可以写成char str[10] ;str[10] = "China";
	printf("str = %s", &str);
	return 0;
}
  1. 使用strcpy函数进行初始化。需要注意的是，使用strcpy函数，strcpy(str1,str2)，字符数组1必须定义的足够大，以便容纳被复制的字符串2，避免数组越界。在C语言中，将一个字符串赋值给另一个字符串，只能使用strcpy函数，但是，可以使用赋值号实现对单个字符的赋值，此时需要注意的是，结束后一定要自行添加 ‘\0’。
1
2
3
4
5
6
7
int main()
{
	char str1[10],str2[] = "China";
	strcpy(str1, str2);//此行代码还可以写为 strcpy(str1,"China");
	printf("str1 = %s", str1);
	return 0;
}
  1. 通过指针赋值
1
2
3
4
5
6
7
8
#define _CRT_SECURE_NO_WARNINGS//在VS2019下可以加，否则会出现C4996问题
#include <stdio.h>
int main()
{
	char* string = "I Love China";
	printf("string  = %s", string);
	return 0;
}

数据的输入输出

小孩分糖果

某幼儿园里，有5个小朋友编号为1、2、3、4、5，他们按自己的编号顺序围坐在一张圆桌旁。他们身上都有若干个糖果(键盘输入)，现在他们做一个分糖果游戏。从1号小朋友开始，将自己的糖果均分三份（如果有多余的糖果，则立即吃掉），自己留一份，其余两份分给他的相邻的两个小朋友。接着2号、3号、4号、5号小朋友同样这么做。问一轮后，每个小朋友手上分别有多少糖果。

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
int main()
{
    int a, b, c, d, e;
    int f, g, h, i, j;
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
    
    f = a / 3;
    b = b + f;
    e = e + f;

    g = b / 3;
    c = c + g;
    a = f + g;

    h = c / 3;
    d = d + h;
    b = h + g;
    
    i = d / 3;
    e = e + i;
    c = h + i;

    j = e / 3;
    a = a + j;
    d = i + j;
    e = j;
    printf("%5d%5d%5d%5d%5d", a, b, c, d, e);
    return 0;
}

顺序结构实例

数位调换（水仙花数的思路）

实现百位数和个位数字的调换，思路和水仙花很类似，难点在于如何得到各个数位上的数字。

对于一个n位数，求任意第m位数其实都一样，就是两个思路：

  • 用/得到任意位数的首位数，用%得到末位数字
  • 对于中间位数也就是第m位数，可以把这个n位数用除法变成n-m位数，也就相当于把这个中间位数用除法变到末位，用%得到末位数字

百位数：a\100
十位数：a\10%10

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

using namespace std;

int main()
{
    int x, a, b, c;
    cin >> x;
    a = x / 100;
    b = x % 100 / 10;
    c = x % 10;
    cout << c*100 + b*10 + a << endl;
    return 0;
}

偷懒用cout << c << b<< a;，有少数情况无法通过。不知为何。

三个数比较大小从大到小输出

涉及到排序算法。这里是选择排序，也就是每次选出一个最大的元素

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>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int a, b, c, temp;
    cin >> a >> b >> c;
    if (b >= a)
    {
        temp = a;
        a = b;
        b = temp;
    }
    if (c >= a)
    {
        temp = a;
        a = c;
        c = temp;
    }
    if (c >= b)
    {
        temp = b;
        b = c;
        c = temp;
    }
    cout << a << " " << b << " " << c;
    return 0;
}

排序算法总结

选择排序

  • 从待排序序列中找到最小元素
  • 若这个元素不是第一个元素，将这个元素换到第一位
  • 找到次小的元素，若不是第二位，与之交换
  • 不断重复
  • …

插入排序

  • 从第一个元素开始，该元素可以认为已经被排序.
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果该元素(已排序)大于新元素，将该元素移到下一位置;
  • 重复步骤3，直到找到已排序的元素小于或等于新元素的位置
  • 将新元素插入到该位置后
  • 重复2~5

快排
*

程序的控制结构

switch语句

星期几

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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int x;
    cin >> x;
    switch (x)
    {
    case 1:
        cout << "Monday" << endl;
        break;
    case 2:
        cout << "Tuesday" << endl;
        break;
    case 3:
        cout << "Wednesday" << endl;
        break;
    case 4:
        cout << "Thursday" << endl;
        break;
    case 5:
        cout << "Friday" << endl;
        break;
    case 6:
        cout << "Saturday" << endl;
        break;
    case 7:
        cout << "Sunday" << endl;
        break;
    default:
        cout << "input error!" << endl;
        break;
    }
    return 0;
}

循环结构的程序设计

for语句

等差数列求和

注意：sum 要初始化，也就是 sum = 0;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int x, sum1;
    sum1 = 0;
    cin >> x;
    for (int i = 1; i <= x; i++)
    {
        sum1 += i;
    }
    cout << sum1;
    return 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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int x = 0;
    int sum1 = 0;
    int sum2 = 0;
    cin >> x;
    for (int i = 1; i <= x; i++)
    {
        if (i % 2 == 0)
        {
            sum2 += i;
        }
        else
        {
            sum1 += i;
        }
    }
    cout << sum2 << " " << sum1;
    return 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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int sum = 0;
    int n = 0;
    int a[100] = {0};
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    cout << fixed << setprecision(2);
    cout << sum * 1.0 / n;
    return 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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int n, m, sum;
    sum = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (x == m)
        {
            sum++;
        }
    }
    cout << sum;
    return 0;
}

乘方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int a, n, res;
    cin >> a >> n;
    res = a;
    for (int i = 1; i < n; i++)
    {
        res *= a;
    }
    cout << res;
    return 0;
}

斐波那契

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int num[100] = {0};
    num[0] = 1;
    num[1] = 1;
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        num[i] = num[i - 1] + num[i - 2];
    }
    cout << num[n - 1];
    return 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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    double d[30];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        d[i] = 1.0 * y / x;
    }
    double ji = d[0];
    for (int i = 1; i < n; i++)
    {
        if ((d[i] - ji) > 0.05)
        {
            cout << "better" << endl;
        }
        else if ((d[i] - ji) < -0.05)
        {
            cout << "worse" << endl;
        }
        else
        {
            cout << "same" << endl;
        }
    }
    return 0;
}

救援

取整问题

  • 向上取整ceil
  • 向下取整floor
  • 四舍五入round
  • 朝0方向取整fix，正数向下取，负数向上取
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 <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    int n;
    cin >> n;
    double dis[100][2];
    int people = 0;
    double sumtime = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> dis[i][0] >> dis[i][1];
        cin >> x;
        dis[i][2] = 2 * sqrt(dis[i][0] * dis[i][0] + dis[i][1] * dis[i][1]) / 50;
        sumtime += x * 1.0 * 1.5;
        sumtime += dis[i][2];
    }
    cout << ceil(sumtime) << endl;
    return 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
#include <iostream>
using namespace std;

int main() {
    int savings = 0; // Total savings stored at mom's
    int balance = 0; // Current balance in Jinjin's hand
    int budget; // Monthly budget

    for (int month = 1; month <= 12; ++month) {
        balance += 300; // Add monthly allowance
        cin >> budget; // Read the budget for the month
        balance -= budget; // Subtract the monthly budget

        if (balance < 0) {
            cout << "-" << month << endl; // Output -X if balance is negative
            return 0;
        }

        // Save whole hundreds at mom's
        int save = balance - (balance % 100);
        savings += save;
        balance -= save;
    }

    // Calculate the final amount with 20% interest
    int final_amount = balance + (savings + (savings / 5));
    cout << final_amount << endl;

    return 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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int main()
{
	int m, n, r = 0;
	int f = 0;
	cin >> m >> n;
	r = m;
	for (int i = 1; i <= n; i++)
	{
		int temp;
		cin >> temp;
		if (r >= temp)
		{
			r -= temp;
		}
		else
		{
			f++;
		}
	}
	cout << f;
	return 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
41
42
43
44
45
46
47
48
49
#include <iostream>

using namespace std;

int main()
{
	int n = 0;
	cin >> n;
	int nor[105] = {0};
	int c = 0;
	int max = 0;
	int x, y;
	cin >> x >> y;
	if((90 <= x && x <= 140) && (60 <= y && y <= 90))
	{
		nor[0] = 1;
	}
	for(int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		if((90 <= a && a <= 140) && (60 <= b && b <= 90))
		{
			nor[i] = 1;
			if(nor[i-1] == 1)
			{
				c++;
				if (c>max)
				{
					max = c;
				}
			}
			else
			{
				c = 1;
				if (c>max)
				{
					max = c;
				}
			}
		}
		else
		{
			c = 0;
		}
	}
	cout << max;
	return 0;
}

满足条件的四位数

  • 核心在于各个数位上数字的获取
  • 最简便的方法：%10可取最后一位，因此/10递进向左求即可
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 <iostream>

using namespace std;

int main()
{
	int n = 0;
	cin >> n;
	int num = 0;
	for(int i = 0; i < n; i++)
	{
		int a, b, c, d, x;
		cin >> x;
		a = x%10;
		b = x/10%10;
		c = x/10/10%10;
		d = x/10/10/10%10;
		if(a - d - c - b > 0)
		{
			num++;
		}
	}
	cout << num;
	return 0;
}

求分数序列和

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

using namespace std;

int main()
{
	int n = 0;
	cin >> n;
	int num[100][2] = {0}; //1 is p, 2 is q
	num[0][1] = 1; 
	num[0][2] = 2;
	double sum = num[0][2] / num[0][1];
	for (int i = 1; i< n; i++)
	{
		double temp;
		num[i][1] = num[i-1][2];               // solve pi
		num[i][2] = num[i-1][1] + num[i-1][2]; // solve qi
		sum += num[i][2] * 1.0 / num[i][1];
	}
	printf("%.4f", sum);
	return 0;
}

求小数的某一位

  • 核心是模拟除法竖式运算
    • 用模运算求出余数，即可得到新的被除数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

int main()
{
	int a, b, n, d;//d为某一位的数字
	cin >> a >> b >> n;
	int r = a % b;//初始的被除数，也就是开始求小数的第一位
	for(int i = 1; i <= n; i++)
	{
		r *= 10;//被除数乘以10
		d = r / b;//求出此次相除得到的商，即为第i位的数字
		r %= b;//余数作为新的被除数
	}
	cout << d;
	return 0;
}

求幂的末尾

  • 和求上一题求小数一样，减小运算量，只计算后三位，大于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
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int a, b, s = 1;
	int x, y, z;
	cin >> a >> b;
	for(int i = 0; i < b; i++)
	{
		s *= a;
		if(s > 1000);
		{
			x = s % 10;
			y = s / 10 % 10;
			z = s / 100 % 10;
			s = z * 100 +y * 10 + x;
		}
	}
	if(x == 0 && (y !=0 || z!=0))
	{
		printf("0%d%d", z, y);
	}
	else if(x == 0 && y == 0 && z != 0)
	{
		printf("00%d", z);
	}
	else
	{
		printf("%d%d%d", z, y, x);
	}
	return 0;
}

While循环

最大公约数

c++直接用现成的库函数__gcd(a, b)，属于库algorithm

同理可求出最小公倍数=a * b / __gcd(a, b)

最小n值

  • 注意观察条件是否含有临界值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int m = 0;
	int n = 0;
	double sum = 1;
	cin >> m;
	int i = 1;
	while(sum < m)
	{
		double temp;
		i++;
		temp = 1.0 / i;
		sum += temp;
	}
	cout << i;
	return 0;
}

球弹跳的高度

注意，整形 /=2 和 *=0.5 得到的结果是不一样的

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 <bits/stdc++.h>

using namespace std;

int main()
{
	
	int h;
	cin >> h;
	double sum = 0;
	double res = h * 1.0;
	int i = 1;
	while(i<=10)
	{
		sum += res;
		res /= 2.0;
		sum += res;
		i++;
	}
	sum -= res;
	cout << sum << endl;
	cout << res;
	return 0;
}

数组

蛇形输出

思路就是：判断是否再边界内且未曾填过数，从而确定是否填入数字，用while循环依次从右上到右下再到左下再到左上再到右上，进行循环。一共填入n*n 个数字，所以最大值也是 n*n

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 <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int a[30][30] = {0};

int main()
{
    int x, y, d, n;
    cin >> n;
    d = 1;
    x = 0;
    y = n - 1;
    memset(a, 0, sizeof(a));
    a[x][y] = 1;
    while (d < n * n)
    { // 向下填数
        while (x < n - 1 && !a[x + 1][y])
        {
            a[++x][y] = ++d;
        }
        // 向左填数
        while (y > 0 && !a[x][y - 1])
        {
            a[x][--y] = ++d;
        }
        // 向上填数
        while (x > 0 && !a[x - 1][y])
        {
            a[--x][y] = ++d;
        }
        // 向右填数
        while (y < n - 1 && !a[x][y + 1])
        {
            a[x][++y] = ++d;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

递归

Hermite函数

用递归函数实现Hermite多项式求值。当x>1时，Hermite多项式定义为：

Hn(x)={1,n=02x,n=12xHn−1(x)−2(n−1)Hn−2(x),n>1;H_n(x)=\begin{cases} 1, & n=0\\ 2x, & n=1\\ 2xH_{n-1}(x)-2(n-1)H_{n-2}(x), & n>1; \end{cases}

当输入整数n和实数x后，求出Hermite多项式第n项的值。

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>
#include <algorithm>

using namespace std;

float Hermite(float a, int n)
{
	float k;
	if (n == 0)
	{
		k = 1;
	}
	else if (n == 1)
	{
		k = 2 * a;
	}
	else if (n > 1)
	{
		k = 2 * a * Hermite(a, n - 1) - 2 * (n - 1) * Hermite(a, n - 2);
	}
	return k;
	}

int main()
{
	float a = 0;
	int n = 0;
	cin >> n >> a;
	cout << "y=" << Hermite(a, n);
	return 0;	
}


分别设计两个递归函数，一个实现整数的正序输出，另一个则实现反序输出。如输入一个整数3456，则输出3456和6543。

算法提示：重复除以10求余，直到商为0为止。如3456％10的余数为6，商为345；345％10的余数为5，商为34；34％10的余数为4，商为3；3％10的余数为3，商为0，至此结束。先输出余数，后递归，则为反序输出；先递归，后输出余数，则为正序输出。
输入示例1：
3456
输出示例：
正序：3456
反序：6543

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 <iostream>
#include <algorithm>

using namespace std;

void posi(int n)
{
	if (n >= 10)
	{
		posi(n / 10);
	}
	cout << n % 10;
}

void nega(int n)
{
	if (n <= 9)
	{
		cout << n;
	}
	else
	{
		cout << n % 10;
		nega(n / 10);
	}
}

int main()
{
	int a;
	cin >> a;
	cout << "正序：";
	posi(a);
	cout << endl;
	cout << "反序：";
	nega(a);
	cout << endl;
	return 0;
}