2021年秋季L4班题解

陪你们走过了夏天、秋天和冬天
春天即将到来
你们的步伐愈发坚定
老师可以欣慰地与你们说再见了

题目知识点和难度排序

A. 汉诺双塔：递推，递归

B. 最大公约数和最小公倍数问题：递归

C. 放橘子：递归

D. 合影效果：排序

E. noip2007普及组 4.Hanoi双塔问题:高精度乘法，递推

F. 斜列求和：二维数据一般运用

老师认为的题目难度：

A < D < B < F = E < C

题目讲解和AC代码

A. 汉诺双塔：递推，递归

题解：

题意：easy。就是两倍的2^n-1。

做法：怎么样做都行。

代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	long long int ans = 1;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		ans *= 2;
	}
	cout << (ans-1)*2;
}

B.最大公约数和最小公倍数问题：递归

题解

题意：按题意来，题意比较清晰。枚举所有P、Q的可能性，统计个数。

做法：需要递归求一下最大公约数，然后带入式子判断是否满足条件。

代码

#pragma warning(disable:4996)；
#include<bits/stdc++.h>
using namespace std;
int f(int a, int b) {//求最大公约数
	if (a % b == 0) {
		return b;
	}
	return f(b, a % b);
}
int main()
{
	int x, y;
	cin >> x >> y;
	int ans = 0;
	for (int i =1; i * x <= x * y; i++)//遍历范围，并注意优化for循环
	{
		if (x * y % (i * x) == 0 && f(i * x, x * y / (i * x)) == x) {
			ans++;
		}
	}
	printf("%d\n", ans);
}

C. 放橘子：递归

题解

题意：题意简单。

做法：

设dfs(m,n) 为m个橘子，n个盘子的放法数目，则先对n作讨论，
当n>m：必定有n-m个盘子永远空着，去掉它们对摆放橘子方法数目不产生影响。
即if(n>m) dfs(m,n) = dfs(m,m)。
当n<=m：不同的放法可以分成两类：
1、一种是每个盘子都有一个橘子，那剩下的m-n个橘子放进盘子，结果是dfs(m-n,n)
2、一种是至少一个盘子空着,注意这里是至少，递归下去，会搜索到n-2,n-3，结果是dfs(m,n-1).
而总的放橘子的放法数目等于两者的和，即 dfs(m,n) =dfs(m,n-1)+dfs(m-n,n)
递归出口条件说明：
当n=1时，所有橘子都必须放在一个盘子里，所以返回１；
当没有橘子可放时，定义为１种放法；
递归的两条路，第一条n会逐渐减少，终会到达出口n==1;
第二条m会逐渐减少，因为n>m时，我们会return dfs(m,m)，所以终会到达出口m==0。

代码

#pragma warning(disable:4996)；
#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int k[10086];
int dfs(int m, int n)
{
	if (m == 0 || m == 1 || n == 1)//橘子没了，或者橘子只有一个，或者盘子只要一个
	{
		return 1;//返回结果为1
	}
	if (m < n)//如果橘子数量<盘子数量，最多只能放m个盘子，结果必然是dfs(m,m);
	{
		return dfs(m, m);
	}
	if (m >= n)//如果橘子的数量>盘子数量，两种情况考虑：
    //1.一种是每个盘子都有一个橘子，那剩下的m-n个橘子放进盘子，结果是dfs(m-n,n)；
    //2.一种是至少一个盘子空着,注意这里是至少，递归下去，会搜索到n-2,n-3，结果是dfs(m,n-1)。
    //两个结果要进行累加
	{
		return dfs(m - n, n) + dfs(m, n - 1);
	}
}
int main()
{
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cin >> m >> n;
		cout<<dfs(m, n)<<endl;
	}
	
	return 0;
}

D. 合影效果：排序

题解

题意：将男生和女生分开排序，男生从矮到高排，女生从高到矮排序。

做法：根据male和female存入两个不同的数组，然后可以用sort直接排。

代码

#include<bits/stdc++.h>
using namespace std;
bool cmp(double a, double b)//写一个排序的函数，从大到小
{
	return a > b;
}
int main()
{
	int n;
	cin >> n;
	int pos1 = 0, pos2 = 0;//男生和女生的数组大小
	double boy[50], girl[50];//注意类型是用double类型存储
	for (int i = 0; i < n; i++)
	{
		string sex;
		double height;
		cin >> sex >> height;
		if (sex == "male")//如果是男生，存进boy数组
		{
			boy[pos1] = height;
			pos1++;
		}
		else//否则存入女生数组
		{
			girl[pos2] = height;
			pos2++;
		}
	}
	sort(boy, boy + pos1);//男生从高到矮排序
	sort(girl, girl + pos2, cmp);//女生从矮到高排序
	//输出，保留两位小数
    for (int i = 0; i < pos1; i++)
		printf("%.2lf ", boy[i]);
	for (int i = 0; i < pos2; i++)
		printf("%.2lf ", girl[i]);
}

E. noip2007普及组 4.Hanoi双塔问题

题解

题意：A题升级版本。

做法：高精度乘法。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],n,top=0;
int main()
{
	int i,j;
	scanf("%d",&n);
	a[1]=1;

	for(i=0; i<=n; i++)
	{
		for(j=1; j<=200; j++)
		{
			a[j]=a[j]*2+a[j-1]/10;
			a[j-1]=a[j-1]%10;
		}
	}
	a[1]=a[1]-2;
	i=1;
	while(a[i]<0)
	{
		a[i]=a[i]+10;
		a[i+1]--;
	}
	for(i=200; i>0; i--)
	{
		if(a[i])
		{
			top=i;
			break;
		}
	}
	for(i=top; i>=1; i--) printf("%d",a[i]);
	return 0;
} 
 

F. 斜列求和：二维数据一般运用

题解

题意：这题根据样例解释可以看出，它的求和先从左下角开始的，
3=3

4=0+4

8=2+3+3

7=2+0+1+3

7=3+0+3

6=3+3

4=4
然后逐渐往上移动，去求斜列的和，是有些难度。

做法：两种做法：1.将二维数组拆分为两部分去处理，一部分是矩形的左下角部分，另一部分是右上角部分；2.将题目里的式子运用到数组里，稍微有些难理解。

代码

方法一：

#include<bits/stdc++.h>
using namespace std;
int n,sum;
int a[505][505];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)//存n*n的二维矩阵
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    //这是左下角的部分
    for(int i=1;i<=n;i++)
    {
    	int k=n,g=i;//横纵坐标
    	sum=0;//求和
        while(k>0&&g>0)
        {
            sum=sum+a[k][g];
            k--;
            g--;
        }
        cout<<sum<<endl;
    }
    //这是右上角的部分
    for(int i=n-1;i>=1;i--)
    {
    	int k=i,g=n;//横纵坐标
    	sum=0;//求和
        while(k>0&&g>0)
        {
            sum=sum+a[k][g];
            k--;
            g--;
        }
        cout<<sum<<endl;
    }
    return 0;
} 

方法二：

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005], ans[2005];
int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i <= n - 1; i++)//特殊的存矩阵方式，坐标位置按题目要来存
		for (int j = n - 1; j >= 0; j--)
			scanf("%d", &a[i][j]);
	for (int i = 1; i <= 2 * n - 1; i++)//需要求的和的长度
	{
		int sum = 0;
		for (int x = 0; x <= n - 1; x++)
		{
			ans[i] = ans[i] + a[x][-x + i - 1];//按斜率和x的公式求出对应的y，即可求和
		}
	}
	for (int i = 2 * n - 1; i >= 1; i--) cout << ans[i] << endl;
}

打赏