`
miman2008
  • 浏览: 38162 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

java递归实现一acm题

阅读更多

题目要求:

求满足从1开始,某一整数以内的数组合相加等于其本身的各种情况

例如:整数20,求组合相加等于20的情况:

 1 19
 1 2 17
 1 2 3 14
 1 2 3 4 10
 1 2 3 5 9
 1 2 3 6 8 
 1 2 4 13

 .

 .

 .

 7 13 
 8 12 
 9 11

 

不能重复,交换顺序视为同一种情况。

package alibaba;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;


public class combination {
	static int count = 0;
	public static  void combine(int index,int sum,Set<Integer> set){
	    if(set== null){
	    	 set = new HashSet<Integer>();
	    }
		if( index  < sum/2){//递归入口,sum如果能分成两个比index都大的数则进行递归,否则此轮递归结束,回溯继续运行。
		int i = index + 1;
		int temp = 0;
		set.add(index);
		if(sum%2  ==  0){
			temp = sum /2;
		}else temp = sum/2 +1;
		count++;
		System.out.print(count+": ");
	    for (Integer integer : set) {
			System.out.print(integer+" ");
		}
	    System.out.println(sum);
	   
		for(;i<temp;i++){//temp为中间值,循环变量无法到达这一值,避免重复情况
			set.add(i);
			combine(i, sum-i,set);
			set.remove(i);
		}
	 }
	else{
		set.add(index);
		set.add(sum);
		count++;
		System.out.print(count+": ");
		for (Integer integer : set) {
			System.out.print(integer+" ");			
		}
		System.out.println();
		
		set.remove(index);
		set.remove(sum);
	}
		
	}
	public static void main(String[] args) {
		Scanner  scanner  = new Scanner(System.in);
		System.out.println("请输入两个整数");
		int index = scanner.nextInt();
		int sum = scanner.nextInt();
		for(int i=index; i <sum/2; i ++){
          combine(i,sum-i,null);
		}
		System.out.println("方案总数为:"+count);
	}

}

 

输出结果:

请输入两个整数
1
20
1: 1 19
2: 1 2 17
3: 1 2 3 14
4: 1 2 3 4 10
5: 1 2 3 5 9
6: 1 2 3 6 8
7: 1 2 4 13
8: 1 2 4 5 8
9: 1 2 4 6 7
10: 1 2 5 12
11: 1 2 6 11
12: 1 2 7 10
13: 1 2 8 9
14: 1 3 16
15: 1 3 4 12
16: 1 3 4 5 7
17: 1 3 5 11
18: 1 3 6 10
19: 1 3 7 9
20: 1 4 15
21: 1 4 5 10
22: 1 4 6 9
23: 1 4 7 8
24: 1 5 14
25: 1 5 6 8
26: 1 6 13
27: 1 7 12
28: 1 8 11
29: 1 9 10
30: 2 18
31: 2 3 15
32: 2 3 4 11
33: 2 3 4 5 6
34: 2 3 5 10
35: 2 3 6 9
36: 2 3 7 8
37: 2 4 14
38: 2 4 5 9
39: 2 4 6 8
40: 2 5 13
41: 2 5 6 7
42: 2 6 12
43: 2 7 11
44: 2 8 10
45: 3 17
46: 3 4 13
47: 3 4 5 8
48: 3 4 6 7
49: 3 5 12
50: 3 6 11
51: 3 7 10
52: 3 8 9
53: 4 16
54: 4 5 11
55: 4 6 10
56: 4 7 9
57: 5 15
58: 5 6 9
59: 5 7 8
60: 6 14
61: 7 13
62: 8 12
63: 9 11
方案总数为:63

分享到:
评论

相关推荐

    java,Spring实现ACM国际大学生程序设计竞赛试题 数字三角形

    在本项目中,我们主要探讨的是如何利用Java和Spring框架来实现ACM国际大学生程序设计竞赛中的“数字三角形”问题。ACM竞赛是全球知名的编程竞赛,旨在培养学生的算法设计和编程能力。数字三角形问题通常涉及到动态...

    1道acm 题的解(Java 源代码)

    标题中的“1道acm题的解(Java源代码)”表明这是一个关于算法竞赛(ACM,全称:International Collegiate Programming Contest)的问题解决方案,使用Java编程语言实现。ACM比赛通常涉及逻辑思维、数据结构和算法设计...

    ACM算法题100题-经典算法库

    3. **递归思想**:利用递归调用简化问题的求解过程,适用于分治策略的算法实现。 4. **时间与空间复杂度分析**:评估算法效率的关键指标,帮助开发者选择最适合当前问题的算法。 5. **调试技巧**:通过单元测试、...

    ACM.rar_ACM_ACM习题

    "ACM.rar"是一个压缩包文件,其中包含了“ACM”这个主题的相关学习资源,包括一些基础练习题和讲解。 "www.pudn.com.txt"可能是一个链接或文本文件,通常在这样的压缩包中,它可能是用来提供更多信息的链接,例如...

    Problem D.rar_ACM_ACM试题

    【标题】"Problem D.rar" 是一个压缩文件,其中包含了对 ACM(国际大学生程序设计竞赛,简称ACM/ICPC)某道试题的解答。这个压缩包特别关注的是"ACM_ACM试题",暗示了内容可能涉及过去比赛中的一个问题及其解决方案...

    PKU acm 1000题-2000题

    【标题】"PKU acm 1000题-2000题" 涉及的是北京大学(PKU)ACM/ICPC(国际大学生程序设计竞赛)训练题目的一部分,这个范围涵盖了从1000题到2000题的解题源代码。在ACM/ICPC中,参赛队伍需要编写程序解决一系列算法...

    ACM程序设计大赛\ACM试题训练

    3. **编程语言**:ACM竞赛通常使用C、C++或Java作为编程语言,熟悉这些语言的基本语法、特性以及如何写出高效代码是必要的。 4. **效率优化**:在比赛中,程序运行时间和空间效率至关重要。因此,选手需要学会如何...

    北大ACM题解答代码

    【北大ACM题解答代码】是一份集合了50道北京大学ACM竞赛题目解题思路与源代码的资源,对于想要提升编程技能、学习算法竞赛策略的编程爱好者来说,这是一份非常宝贵的学习资料。ACM(国际大学生程序设计竞赛,...

    acm2008试题及答案

    虽然ACM竞赛不限制编程语言,但C++和Java是最常用的语言,因为它们支持高效的数据结构和算法实现。选手需要熟练掌握语言特性,了解如何编写高效的代码。此外,调试技巧也是必不可少的,包括学会利用编译器的错误提示...

    ACM新手入门练习题

    - **熟悉编程语言:** 通常推荐使用C++或Java进行ACM竞赛的编程实践。 - **培养团队协作精神:** ACM竞赛多为团队赛制,良好的沟通与协作是取得好成绩的关键。 #### 二、数据结构基础 在ACM竞赛中,对数据结构的...

    POJ一些ACM题的代码

    在计算机科学和程序设计的世界里,ACM国际大学生程序设计竞赛(ACM ICPC)无疑是一场展示编程实力和技术深度的盛会。为了在这一竞争激烈的领域脱颖而出,参赛者不仅需要扎实的编程基础,更需要通过大量的实践和反复...

    北大ACM试题部分代码

    在ACM竞赛中,C++和Java是最常用的语言。C++因其高效和灵活性受到青睐,而Java则以其丰富的类库和自动内存管理简化了编程。此外,Python等脚本语言也逐渐在一些简单题目中被采用,因其简洁的语法和快速开发特性。 ...

    北大ACM平台题库源代码

    【北大ACM平台题库源代码】是一个针对编程竞赛爱好者和学习者的宝贵资源,它包含了北京大学ACM(国际大学生程序设计竞赛)平台上的400道题目对应的源代码。这个资源对于想要提升算法理解、训练编程技能以及深入学习...

    北大ACM题库

    3. **编程实现**:熟练使用C++、Java等编程语言实现算法。 4. **调试技巧**:掌握快速定位和解决问题的方法。 5. **阅读理解**:提升理解复杂问题和需求的能力。 6. **逻辑思维**:锻炼严密的逻辑推理能力。 这个...

    杭电ACM入门题 及 相关的答案

    在编程学习的初期,ACM(国际大学生程序设计竞赛,英文为ACM International Collegiate Programming Contest)是一个很好的起点,因为它提供了各种基础到进阶的算法和编程问题。这些题目旨在帮助初学者提升逻辑思维...

    ACM基础训练题

    这些题目涵盖了计算机科学和算法设计中的多个经典问题,主要涉及逻辑推理、数学建模和算法实现。以下是对各个题目所涉及知识点的详细说明: 1. **N皇后问题**:这是一个典型的回溯法问题,用于寻找在N*N棋盘上放置N...

    acm基础训练题19题

    这些题目是ACM竞赛中的基础训练题,主要涵盖了一些经典的算法和问题解决策略,对于初学者来说是非常好的实践材料。以下将分别介绍这些题目涉及的知识点: 1. **N皇后问题**:这是一个典型的回溯法问题,目标是在N*N...

    重庆第一届ACM程序设计比赛A、E、F题答案

    对于A、E、F题,选手们需要熟练掌握C++、Java或Python等主流编程语言,并了解各种基础及高级算法,例如排序、查找、递归、贪心、动态规划等。同时,良好的团队协作和时间管理也是比赛成功的关键因素。 回顾重庆第一...

    关于ACM的题

    ACM,全称是国际大学生程序设计竞赛(International Collegiate Programming Contest,简称ICPC或ACM/ICPC),是一项全球性的编程竞赛,旨在提升大学生的计算机科学问题解决能力,特别是算法设计、分析和编程实现。...

Global site tag (gtag.js) - Google Analytics