专栏首页AI那点小事算法训练 未名湖边的烦恼

算法训练 未名湖边的烦恼

问题描述   每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。   每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法) 输入格式   两个整数,表示m和n 输出格式   一个整数,表示队伍的排法的方案数。 样例输入 3 2 样例输出 5 数据规模和约定   m,n∈[0,18]


解题思路

    设F(m,n)为m人还鞋,n人借鞋的排队种数。
    n为0时,F(m,n) = 1
    m<n时,F(m,n) = 0
    m>n时,F(m,n) = F(m-1,n)+F(m,n-1)

AC代码如下:

import java.util.Scanner;

public class Main {

    public static int Fuction(int m ,int n){
        if ( n == 0){
            return 1;
        }else if ( m < n){
            return 0;
        }else{
            return Fuction(m-1, n) + Fuction(m, n-1);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int sum = Fuction(m, n);
        System.out.print(sum);
        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法训练 6-1 递归求二项式系数值

    样例输入 一个满足题目要求的输入范例。 3 10 样例输出 与上面的样例输入对应的输出。 120 数据规模和约定   输入数据...

    AI那点小事
  • 算法训练 5-1最小公倍数

    问题描述   编写一函数lcm,求两个正整数的最小公倍数。 样例输入 一个满足题目要求的输入范例。 例:

    AI那点小事
  • 牛牛的数列

    牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,就可以使得这个连续的子序列是一个严格上升的子序列,牛...

    AI那点小事
  • C# 终极基类Object介绍

    一、简介 Object这个类型,相信everyone都不陌生,这个是CLR定义的最基础的类型,俗称"上帝类"。CLR(运行时)要求所有类型,不管是系统定义的类型...

    郑小超.
  • 根据字符串生成对应Hash值

    参考网址: http://www.partow.net/programming/hashfunctions/

    IBinary
  • Shell 文本处理之【IP列表加掩码去重】

    大大大黑白格子
  • 设计模式之观察者模式

    Define a one-to-many dependency between objects where a state change in one obje...

    beginor
  • 那些被一行代码蒸发1个亿的智能合约,形式化验证了解一下? | 人物志

    区块链大本营
  • pd_ds中的hash

    前言 在c++的STL中,提供了一种hash函数,其用法和map是几乎一样的,但是速度却能快接近一倍 使用方法 需要的头文件 #include<ext/pb_d...

    attack
  • java编程——从jvm角度看懂类初始化、方法重写、重载

    类的声明周期可以分为7个阶段,但今天我们只讲初始化阶段。我们我觉得出来使用和卸载阶段外,初始化阶段是最贴近我们平时学的,也是笔试做题过程中最容易遇到的,假如你想...

    慕容千语

扫码关注云+社区

领取腾讯云代金券