函数学习总结（二）

4.放苹果
题目描述:把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入:第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

输出:对输入的每组数据M和N，用一行输出相应的K。

样例输入:1
              7    3
样例输出:8

分析:  样例输出有八组数，可以将这八组数分为两组。
          第一组:
          7 0 0      6 1 0      5 2 0      4 3 0
          可以发现最后一个数总是为0，也就是可以理解为这一组数与m=7，n=2也是相等的。
           第二组:
           5 1 1      4 2 1      3 3 1     3 2 2
           如果将每一个数都减1，可以发现，这组数的个数与m=4,n=3相等。

注意边界：当所放苹果为1或者箱子数为1时，方法只有一种，当然x<0时属于无效输入。

通过以上分析可以得出所求方法总数的递归公式：pa(x,y)=pa(x,y-1)+pa(x-y，y).

#include<bits/stdc++.h>
using namespace std;
int pa(int x,int y)
{
    if(x<0) return 0;
    if(x==1||y==1) return 1;
    return pa(x,y-1)+pa(x-y,y);
}
int main()
{
    int m,n,t;
    cin>>t;
    while(t--)
    {
    	 cin>>m>>n;
       cout<<pa(m,n)<<endl;
    }
    return 0;
}

5.算24

题目描述：给出4个小于10个正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。

这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。

比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。

输入：输入数据包括多行，每行给出一组测试数据，包括4个小于10个正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。

输出：对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。

样例输入：5 5 5 1

1 1 4 2

0 0 0 0

样例输出：YES

分析：

1.将四个数视为一个集合；

2.从集合中随机取两个数，通过加减乘除计算这两个数的结果，然后再将结果放回集合，这样集合就减少了一个元素；

3.重复2的步骤，直到集合中只剩下一个元素为止；

4.查看最后一个元素是否有是24来得出结果。

#include<cstdio>
#include<cmath>
bool finish;
void set(double xl[],int sxl,int idx1,int idx2,double lastresult);
void flag(double xl[],int sxl);
int main()
{
    double xl[4];
    while(1)
    {
        for(int i=0;i<4;i++) scanf("%lf",&xl[i]);
        if(!xl[0] && !xl[1] && !xl[2] && !xl[3]) break;
       
        finish=false;
        flag(xl,4); 
        if(finish) 
            printf("YES\n");
        else
            printf("NO\n");
    }
}
void flag(double xl[],int sxl)
{
    if(finish) return;
    if(sxl==1)
    {
        if(fabs(xl[0]-24.0)<1e-4) finish=true;
    }
    else
    {
        int i,j;
        for(i=0;i<sxl;i++)
        {
            for(j=i+1;j<sxl;j++)
            {
                set(xl,sxl,i,j,xl[i]+xl[j]);
                set(xl,sxl,i,j,xl[i]-xl[j]); 
                set(xl,sxl,i,j,xl[j]-xl[i]);
                set(xl,sxl,i,j,xl[i]*xl[j]);
                if(xl[i]!=0)
                    set(xl,sxl,i,j,xl[i]/xl[j]);
                if(xl[j]!=0)
                    set(xl,sxl,i,j,xl[j]/xl[i]);
            }
        }
    }
}
void set(double xl[],int sxl,int change1,int change2,double num)
{
    int i,sset_xl=0;
    double set_xl[sxl-1];
    for(i=0;i<sxl;i++)
    {
        if(i!=change1 && i!=change2)
            set_xl[sset_xl++]=xl[i];
    }
    set_xl[sset_xl++]=num;
    flag(set_xl,sset_xl);
}

三、心得体会

1.关于简单的定义函数，只是把上学期所写主函数中实现功能的部分代码提取出来变为一个或多个自定义函数的过程而已。

要注意自定义函数只能返回一个值；如果要返回多个值，在自定义函数中用cout就好。

比如：

int fun(int x)
{
    //……
    cout<<……<<endl;
}
int main()
{
    ……
    fun();
    return 0;
}

2.个人感觉函数部分还是递归最难，因为它需要我们找出大规模问题与小规模问题之间的关系，得出递归公式，从而把完整的代码写出来。在这个过程中，在个别的题目中我们还要注意出题者挖的坑和代码处理中的各种细节问题。

比如：算24中，计算两个数相减和相除时要注意各有两种情况，还有做相除运算时要注意分母不能为0.
典型的递归问题有计算数的阶乘、斐波那契数列、爬楼梯问题和半数集问题等等。它们都有推导出来的公式，需要我们去理解。

数的阶乘：f(n)=f(n-1)*n [f(n)表示n的阶乘，f（n-1）同理] （也就是可以视为已知n-1的阶乘求n的阶乘，以此类推，逐层向下调用，直至1的阶乘）

斐波那契数列：1 1 2 3 5 8 13……

通过对数列的分析，我们可以发现第三个数等于前两个数之和，所以可以得到递推公式f(n)=f(n-1)+(n-2)

注意边界：f(1)=1,f(2)=1.

爬楼梯问题：上台阶时你可以有两种选择，即一次上两个台阶或一次一个台阶。

我们可以倒着来分析：到第n阶台阶时，我们想到，可以从第n-1阶迈一个台阶到达第n阶或者从第n-2阶迈两个台阶到达第n阶。所以不难得到递推公式：f(n)=f(n-1)+f(n-2),走到这儿我们会发现其实这道题跟斐波那契数列是一个道理，只不过是换了一个说法而已。注意边界：f(1)=1,f(2)=2.

3.在做题的过程中我发现有关递归的练习会牵扯到其他的算法，比如广搜和深搜、动态规划等等，这需要我们慢慢去积累，用更好的算法写出效率更高的代码。

秒客网

函数学习总结（二）

相关文章