专栏首页AI那点小事简单的整数划分问题

简单的整数划分问题

总时间限制: 100ms 内存限制: 65536kB 描述 将正整数n 表示成一系列正整数之和,n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ,k>=1 。 正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入 标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。 输出 对于每组测试数据,输出N的划分数。 样例输入 5 样例输出 7 提示 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1


解题思路: 该问题是求出n的所有划分个数,即f(n, n)。下面我们考虑求f(n,k)的方法; 根据n和k的关系,考虑以下几种情况: (1)当 n = 1 时,不论k的值为多少(k > 0 ),只有一种划分即 { 1 }; ( 2 ) 当 k = 1 时,不论n的值为多少,只有一种划分即 n 个 1,{ 1, 1, 1, …, 1 }; (3) 当 n = k 时,根据划分中是否包含 n,可以分为两种情况: (a). 划分中包含n的情况,只有一个即 { n }; (b). 划分中不包含n的情况,这时划分中最大的数字也一定比 n 小,即 n 的所有 ( n - 1 ) 划分。 因此 f(n, n) = 1 + f(n, n-1); (4) 当 n < k 时,由于划分中不可能出现负数,因此就相当于 f(n, n); (5) 但 n > k 时,根据划分中是否包含最大值 k,可以分为两种情况: (a). 划分中包含 k 的情况,即 { k, { x1, x2, …, xi } }, 其中 { x1, x2, …, xi } 的和为 n - k,可能再次出现 k,因此是(n - k)的 k 划分,因此这种划分 个数为 f(n-k, k); (b). 划分中不包含 k 的情况,则划分中所有值都比 k 小,即 n 的 ( k - 1 ) 划分,个数为 f(n, k - 1); 因此 f(n, k) = f(n - k, k) + f(n, k - 1);


Java代码如下:

import java.util.Scanner;

public class Main {

    public static int Function(int n,int k){
        if (n == 1 || k == 1){
            return 1;
        }
        if (n < k){
            return Function(n, n);
        }
        if ( n == k){
            return Function(n, k-1)+1;
        }
        return Function(n-k, k)+Function(n, k-1);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(Function(n, n));

        in.close();
    }

}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 开门人和关门人

    题目描述 每天第一个到机房的人要把门打开,最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录,请根据记录找出当天开门和关门的人。 输入...

    AI那点小事
  • 1002. 写出这个数 (20)

    输入格式:每个测试输入包含1个测试用例,即给出自然数n的值。这里保证n小于10100。

    AI那点小事
  • CCF考试——201709-5除法

      小葱喜欢除法,所以他给了你N个数a1, a2, ⋯, aN,并且希望你执行M次操作,每次操作可能有以下两种:   给你三个数l, r, v,你需要将a...

    AI那点小事
  • 面试官:java 最常见面试题 200+ 汇总

    这份面试清单是我从 2015 年做 TeamLeader 之后开始收集的,一方面是给公司招聘用,另一方面是想用它来挖掘我在 Java 技术栈中的技术盲点,然后修...

    用户6983149
  • 面试必备:Java 面试最常见的 200+ 题

    说了这么多,直奔主题,这套面试必备的《Java 最常见 200+ 面试题全解析》到底优质在哪?

    CSDN技术头条
  • 备战金九银十,200+的Java面试必备题,快收藏起来把

    我们这份面试题,包含的内容了十九了模块:Java 基础、容器、多线程、反射、对象拷贝、Java Web 模块、异常、网络、设计模式、Spring/Spring ...

    Java周某人
  • Java 最常见的 200+ 面试题:面试必备

    这份面试清单是我从 2015 年做 TeamLeader 之后开始收集的,一方面是给公司招聘用,另一方面是想用它来挖掘我在 Java 技术栈中的技术盲点,然后修...

    Java中文社群_老王
  • SaaS,PaaS,IaaS都是什么鬼?

    IaaS Infrastructure as a Service,基础设施即服务。 假如你现在要做一个网站,你肯定要有一台服务器或者虚拟机,要么自己搭建,要么买...

    Java技术栈
  • 两面三刀的游戏:由欺骗设计的主动自动防御机制(CS.GT)

    我们提出了一个新的游戏框架,称为两口型游戏,以设计防御欺骗机制。该机制为防御者提供了一种主动和自动化的方式,通过防御欺骗来增强安全性。与隐藏秘密的加密不同,我们...

    用户7236395
  • Facebook 首次因数据泄密丑闻遭罚款:金额 66.4 万美元

    Facebook将因为剑桥分析(Cambridge Analytica)数据泄露事件而面临第一次处罚——来自英国的66.4万美元罚单。

    周俊辉

扫码关注云+社区

领取腾讯云代金券