2022春 南哪大学 程序设计基础 OJ答案参考（5）之自主训练任务

Problem 1 题目描述

编写递归函数，求经典的多项式序列埃尔米特（Hermite）多项式中第n+1项Hn(x)的值，并在main函数中调用、输出结果。

Hn(x)定义为：

H0(x) = 1 H1(x) = 2x Hn(x) = 2xHn-1(x) – 2(n-1)Hn-2(x) （n > 1）

输入

两个数。

第一个整数n，表示多项式的第n+1项。

第二个浮点数x。

输出

Hn(x)的值，结果保留两位小数。

样例输入

3 5.25

​

样例输出

1094.62

参考代码：

# include 

double H( double x, int n );
int main()
{
	double x, y;
	int n;
	scanf( "%d %lf", &n, &x );
	 
	y = H( x, n );
	printf( "%.2f", y );
	return 0;
}

double H( double x, int n )
{
	if( n==0 )
		return 1;
	else if( n==1 )
		return 2*x;
	else
		return 2*x*H( x, n-1 )-2*( n-1 )*H( x, n-2);
}

注： 这道题和2022春 南哪大学 程序设计基础 OJ答案参考（4）之自主训练任务_MEDlATOR的博客-CSDN博客中的Ackermann函数很类似，注意数据类型直接按函数定义即可。

Problem 2 题目描述

今年疫情期间W同学去某游戏公司实习，被安排参与开发一款Naruto同人系列益智类的游戏，来帮助疫情在家的人们舒缓心情。

这款游戏中，一共有n个怪兽，而玩家每一次可以选择以下三种技能进行打怪：

1. 千鸟：每次能打掉1只怪兽
2. 螺旋手里剑：如果剩余的怪兽数 n 能被 2 整除，那么才能使用且可以打掉 n/2 只怪兽。
   

   
   

3. 地爆天星：如果剩余怪兽数 n 能被 3 整除，那么才能使用且可以打掉 2*(n/3) 只怪兽。
   

   
   

每次玩家只能从以上 3 种技能中选择一种技能发动，技能发动次数越少，最后玩家得到的奖励越多。

现在为了得到最多的奖励，请你设计相关程序（可能需要使用递归函数来做）计算，打掉所有 n 个怪兽最少需要发动多少次技能。

提示1：你需要理解递归函数的执行过程。

提示2：既然每一次都最多有三种选择，那么可以贪心地选择其中递归结果最优的作为返回的值，注意，为了不漏解，每一层的三种选择都可能导致最优解，需要比较。

输入

输入：1行，n表示怪兽的数量（1<=n<=100）

输出

输出：1行，1个整数，表示最少需要发动的技能次数。

样例输入

10

样例输出

4

解释

总共有 10 只怪兽。



第 1 次：可以选择技能1，打掉 1 只怪兽，剩余怪兽数 10 - 1 = 9。



第 2 次：可以选择技能3，打掉 6 只怪兽，剩余怪兽数 9 - 2*(9/3) = 9 - 6 = 3。

（9 可以被 3 整除）

第 3 次：可以选择技能3，打掉 2 只怪兽，剩余怪兽数 3 - 2*(3/3) = 3 - 2 = 1。



第 4 次：可以且只能选择技能1，打掉最后 1 只怪兽，剩余怪兽数 1 - 1 = 0。



需要发动至少 4 次技能打掉 10 只怪兽。

参考代码 

# include 
# include 

int main()
{
	int n;
	int m;
	scanf( "%d", &n );
	m = 800*n;
	int f[n][m];  //定义二维数组

	int i, j, flag = 0;
	f[1][1] = 1;
	for( i=1; i<=n; i++ ){
		for( j=1; j<=pow( 3, i-1 ); j++ ){
			if( j%3 == 1 ){
				f[i][j] = f[i-1][ (j+2)/3 ] + 1;
			}
			else if( j%3 == 2 ){
				f[i][j] = f[i-1][ (j+2)/3 ] * 2;
			}
			else if( j%3 == 0 ){
				f[i][j] = f[i-1][ (j+2)/3 ] * 3;  //从1开始反向枚举倒数第i步可能出现的所有结果
			}

			if( f[i][j] == n ){
				printf( "%d", i );  //当等于n的数第一次出现 输出此时所需的步数。


				flag = 1;
				break;
			}
		}
		if( flag == 1){
			break;
		}
	}
	
	return 0;
} 

注：hhh这次也真的是”参考代码“了，没有按题目的提示使用迭代函数，而是通过二维数组从1开始反向枚举倒数第i步可能出现的所有结果（既对于上一步每一个出现的数值都执行+1，*2，*3三种 *** 作， 直到等于n的数第一次出现 输出此时所需的步数。

举个例子，对于10，

10

f[1][1]=1



f[2][1]=2
f[2][2]=2
f[2][3]=3



f[3][1]=3
f[3][2]=4
f[3][3]=6

f[3][4]=3
f[3][5]=4
f[3][6]=6

f[3][7]=4
f[3][8]=6
f[3][9]=9



f[4][1]=4
f[4][2]=6
f[4][3]=9

f[4][4]=5
f[4][5]=8
f[4][6]=12

f[4][7]=7
f[4][8]=12
f[4][9]=18

f[4][10]=4
f[4][11]=6
f[4][12]=9

f[4][13]=5
f[4][14]=8
f[4][15]=12

f[4][16]=7
f[4][17]=12
f[4][18]=18

f[4][19]=5
f[4][20]=8
f[4][21]=12

f[4][22]=7
f[4][23]=12
f[4][24]=18

f[4][25]=10
4

但不可否认，这种代码也会出现一些问题，比如当数据量比较大时，数组会越界（m=1000*n是试出来在样例中不会越界的一个值），按理论来说m可以取3^n，但同样，当n足够大时，二维数组会溢出，所以后续有空的话可能会找一个平衡点hhh。

声明：

本专栏为2022春 南哪大学 程序设计基础 课程作业，答案为po主本人初次提交时所写，OJ判定满分，但非老师给出的参考答案，侵删。

前几次自主训练任务较为简单，故不作记录，往后可能都会有所记录。

为优化阅读体验，给出注释。

有问题可在评论区写出，有空会解答或另写补充。