`
1140566087
  • 浏览: 559093 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
博客专栏
2c4ae07c-10c2-3bb0-a106-d91fe0a10f37
c/c++ 入门笔记
浏览量:18523
3161ba8d-c410-3ef9-871c-3e48524c5263
Android 学习笔记
浏览量:314085
Group-logo
J2ME 基础学习课程集
浏览量:18736
A98a97d4-eb03-3faf-af96-c7c28f709feb
Spring 学习过程记录...
浏览量:17581
社区版块
存档分类
最新评论

买不到的数目,组合问题

阅读更多

标题:买不到的数目

    小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。

    小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。

    你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

    本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。

输入:
两个正整数,表示每种包装中糖的颗数(都不多于1000)

要求输出:
一个正整数,表示最大不能买到的糖数

不需要考虑无解的情况

例如:
用户输入:
4 7
程序应该输出:
17

再例如:
用户输入:
3 5
程序应该输出:
7




资源约定:
峰值内存消耗(含虚拟机) < 64M
CPU消耗  < 3000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.6及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。


  package 买不到的数目;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	private static ArrayList<Integer> list  = new ArrayList<Integer>();

	public static  void main(String[] args){
		//test time
		long begin = System.currentTimeMillis();
		
		//接收数据
		String[] arr = new Scanner(System.in).nextLine().split(" ");
		
		f(0,Integer.parseInt(arr[0]),Integer.parseInt(arr[1]),0);	

		int[] a = new int[list.size()];
		for(int i =0 ;i<list.size();i++){
			a[i] = list.get(i);
		}
		
		//排序
		Arrays.sort(a);

		//找出连续并显示最后的结果
		for(int i=1;i<a.length-15;i++){
			if(a[i+10]-a[i]==10){
				System.out.println(a[i]-1);
				break;
			}
		}
		
		long end = System.currentTimeMillis();
		System.out.println("运行:"+(end-begin)/1000f+"秒");
	}	

	public static void f(int base,int n ,int m,int k){
		if(k>=15){
			return;
		}
		if(!list.contains(base)){
			list.add(base);
		}
		f(base+n,n,m,k+1);
		f(base+m,n,m,k+1);
	}

}

1
1
分享到:
评论
3 楼 thihy 2013-07-07  
1140566087 写道
thihy 写道
可以参考 ax+by=k的解法。

那个,有没有相关的资料了!弄来看看,可以不

http://zh.wikipedia.org/zh-cn/%E4%B8%A2%E7%95%AA%E5%9B%BE%E6%96%B9%E7%A8%8B
2 楼 1140566087 2013-07-07  
thihy 写道
可以参考 ax+by=k的解法。

那个,有没有相关的资料了!弄来看看,可以不
1 楼 thihy 2013-07-06  
可以参考 ax+by=k的解法。

相关推荐

    买不到的数目 1

    买不到的数目 1 在这个问题中,我们需要解决的是,given 两个包装的数量,如何求最大不能组合出的数字。这个问题实际上是一个经典的数学问题,称为“Frobenius Coin Problem”。 在这个问题中,小明的糖果店中有两...

    蓝桥杯国赛题之C++买不到的数目.zip

    例如,如果给定的数字集合是{1, 3, 4},那么2和5就是“买不到的数目”,因为无法通过加法或者乘法(题目通常限制操作为加法)将这些数字组合成2或5。这类问题通常需要参赛者具备扎实的算法基础和高效的编程技巧。 ...

    组合数学引论部分课后习题答案

    习题中可能包括计算排列数(排列的总数)和组合数(组合的总数),例如计算n个不同元素的k个排列或k个组合的数目。 第3章可能涉及二项式定理,这是组合数学中的一个关键工具。二项式定理描述了任何两个变量的幂次...

    组合数学——卢开澄组合数学——卢开澄

    母函数和递推关系在解决组合计数问题时发挥着重要作用,母函数可以将一个序列的组合数目转换为一个多项式或者幂级数,并且可以通过分析这个多项式来找到计数问题的解决方案。递推关系则描述了序列中某一项与前一项或...

    组合论(上册).pdf

    计数定理不仅提供了计算不同组合对象数目的方法,还有助于解决诸如有限域上的多项式、图论中的图计数等复杂问题。计数定理包括Polya定理以及它的推广形式,这些定理在解决对称性问题上特别有用,例如置换群中的计数...

    信息学奥赛C++ 组合数学讲义.pdf

    在组合数学中,排列和组合问题的解决往往涉及到巧妙的方法,比如捆绑法和插空法。捆绑法适用于解决相邻问题,即将相邻元素视为一个整体进行排列。插空法则是解决不相邻问题的一种方法,即先排好其他元素,然后在元素...

    组合数学习题答案 组合数学习题答案

    10. **解决实际问题**:通过理解组合数学,我们可以解决各种实际问题,如抽奖、选择团队、分配任务等,涉及到从多个选项中选择的问题都可以运用组合数学方法求解。 以上是关于“组合数学习题答案”这一主题所涵盖的...

    初中 数学竞赛中的组合问题 1.计数问题(2021.01.21).pdf

    综上所述,通过对这些典型例题的分析,我们可以看到初中数学竞赛中的组合问题涵盖了多个重要的数学知识点,包括但不限于质数分拆、格点问题、整除问题以及数字排列等。这些问题不仅考察了学生的基本数学技能,还要求...

    组合数学答案(卢海澄)

    排列问题通常涉及到如何计算n个不同元素的k个排列数目,而组合问题则关注的是n个不同元素的k个组合数目。它们分别用阶乘表示的排列公式n!/(n-k)!和组合公式C(n,k) = n! / [k!(n-k)!]来计算。 2. **二项式系数**:在...

    姜建国组合数学第二版习题答案1

    这个问题通过分类计算得到答案,分为1位数、2位数、3位数和4位数四种情况,分别计算出每种情况的数目,然后相加。 2. 这道题目同样涉及到计数,但多了额外的限制条件。第一部分要求每位数字全不相同的正整数,按照...

    计算组合数并输出组合

    这里我们关注的是“计算组合数”,也就是从一个集合中选择特定数量元素的方法数目,不考虑元素的顺序。这个概念通常用C(n, k)表示,其中n是总元素个数,k是要选择的元素个数。 组合数C(n, k)可以通过以下公式计算:...

    同等学力_在职研究生考研_离散数学&组合数学2007-201805真题及答案.pdf

    真题中有关于从集合A到集合B的不同二元关系和函数的计数问题,以及集合上自反关系和等价关系的数目计算等。 3. 集合论:集合理论是数学的一个基本分支,提供了一套描述集合之间关系和操作的语言。在真题中,通过...

    组合数学第四五章课后习题

    组合数学是一门研究有限集合中元素的组合结构和计数问题的数学分支。在上述的课后习题中,我们涉及到了多个与组合数学相关的概念和计数原理,包括组合计数、排列、子集选择以及递推关系的解决方法。 1. 问题1要求从...

    组合数学Richard-A著 冯舜玺译 版本 课后习题解答(含两份)

    3. **容斥原理**:用于计算不重叠事件的数量,通过考虑所有可能情况并去除重复部分来确定实际数目,是解决计数问题时避免重复计算的关键。 4. **生成函数**:是一种将数列与函数对应的方法,通过分析生成函数的性质...

    组合数学教程

    通过系统学习这个组合数学教程,你将能够掌握如何用数学语言描述和解决涉及到选择和排列的实际问题,这对于理解和设计高效的算法、分析复杂度以及解决概率和统计问题至关重要。无论你是计算机科学家、数据分析师还是...

    组合数学第三版 卢开澄 习题答案

    5. 在计数问题中,有时需要使用分类和分步计数原理,如1.3题中的男生不相邻、女生形成整体以及男生A和女生B相邻的情况,通过乘法原理和组合计数得到解答。 6. 1.10题涉及到整数的唯一表示定理,即每个正整数可以...

    组合理论及其应用

    组合数学是应用数学的一个重要分支,主要研究离散对象组合的性质,包括但不限于计数、优化、构造和存在性问题。它的一个基本问题是找出满足特定条件的不同对象的数量。 【部分内容】中出现了一系列数字和符号,很多...

    卢开澄《组合数学》答案

    9. 最后一个问题讨论了能整除给定整数n的正整数的数目,这涉及到素数分解和指数的乘法规则。 这些问题展示了组合数学在解决实际问题中的应用,包括计数、归纳证明、排列组合、概率模型和数学归纳等方法。理解和掌握...

    组合计数应用与算法相关

    1. **单堆栈问题**:这是一个经典的组合计数问题,要求计算在有限的操作条件下,不同序列的生成数目。初始条件是车厢的原始顺序,递推关系通常涉及操作对序列的影响。解决此类问题,通常需要分析操作的性质,找出...

Global site tag (gtag.js) - Google Analytics