Java教程

函数f(m,n)算法设计

本文主要是介绍函数f(m,n)算法设计,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:

设m,n均为自然数,m可表示为一些不超过n的自然数之和,f(m,n)为这种表示方式的数目。

例f(5,3)=5,有5种表示方式:3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。

以下是该函数的程序段,请将未完成的部分填入,使之完整。

int f(int m, int n)
{
    if(m == 1)   return ___;
    if(n == 1)   return ___;
    if(m < n)   return f(m,m);
    if(m == n)     return 1 + ___;
	return f(m,n-1) + f(m-n,___);
}

解析:

我们先对已给出代码进行分析:

int f(int m, int n)   //定义f(m,n)函数,返回值表示方式的数目,返回值类型为整数.
{
    if(m == 1)   return ___;   //当m=1时,显然1只能分解为1+0,即表示方式只有一种,返回值应为1
    if(n == 1)   return ___;   //当m=1时,显然无论m多大,n为1时只能表示为m个1之和,即表示方式只有一种,返回值应为1
    if(m < n)   return f(m,m);   //见下方说明1
    if(m == n)     return 1 + ___;   //见下方说明2
	return f(m,n-1) + f(m-n,___);   //见下方说明3
}
  • 说明1:

    当m<n时,这里需要注意不应该是返回错误,而是将返回值转化为f(m,m)。这hi因为如果所有的加数都为自然数的话,则最大的加数n是不会超过和m的,因此将m小于n的情况转化为m=n的情况,此处使用函数的递归调用。

    如f(2,3)=f(2,2)。

  • 说明2:

    当m=n时,则返回值为1+f(m,n-1),因为f(m,n)只比f(m,n-1)多了一个n+0的表示方法。

    如f(3,3)=1+f(3,2)

  • 说明3:

    当其他情况,即当m>n时,f(m,n) 可以递归地分解为两种情况:

    1. 当最大加数不包含n时,即f(m, n-1)。即最大加数为(n-1)时的表示方式数量。

    2. 当最大加数包含n时,即f(m-n, n)。因加数中至少有一个n,因此表示方式数量相当于剩下的数字m-n可表示为不大于n的自然数之和,按照函数的定义,表示方式的数量为f(m-n,n)。

      如题干中的f(5,3),在去除第一种情况不包含 3 即 f(5,3-1)=f(5,2)(2+2+1,2+1+1+1,1+1+1+1+1)后,其余表示方式数量为 f(5-3,3)=f(2,3)(3+2,3+1+1)=f(2,2)(2+0,1+1)

      再如f(6,2),在去除第一种情况不包含 2 即 f(6,2-1)=f(6,1)=1(1+1+1+1+1+1)后,其余表示方式数量为 f(6-2,2)=f(4,2)

答案:

故答案为:

int f(int m, int n)
{
    if(m == 1)   return 1;
    if(n == 1)   return 1;
    if(m < n)   return f(m,m);
    if(m == n)     return 1 + f(m,n-1);
	return f(m,n-1) + f(m-n,n);
}
这篇关于函数f(m,n)算法设计的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!