当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-21.中兴面试题 输入两个整数 n 和 m ,从数列 1 , 2 , 3.......n 中随意取几个数 , 使其和等于 m

发表于: 2012-01-15   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.List; import java.util.Stack; public class CombinationToSum { /* 第21 题 2010 年中兴面试题 编程求解: 输入两个整数 n 和 m ,从数列 1 , 2 , 3.......n 中随意取几个数 , 使其和等
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class CombinationToSum {

	/*
第21 题
2010 年中兴面试题
编程求解:
输入两个整数 n 和 m ,从数列 1 , 2 , 3.......n 中随意取几个数 ,
使其和等于 m , 要求将其中所有的可能组合列出来 .
	 * two solutions
	 * permutation01:Recursion.easy to write and read-->pick n or not,haha
	 * permutation02:put n,then put n-1...if bigger,remove;if smaller,keep putting;if ok,output.
	 */
	public static void main(String[] args) {
		CombinationToSum cts=new CombinationToSum();
		//permutation01(int sum,int n)
		cts.permutation01(10,10);
		System.out.println("===========");
		cts.permutation02(10,6);
	}

	/*Recursion.use Stack<Integer>
	we can use ArrayList,too.
	private List<Integer> list=new ArrayList<Integer>();
	list.add(n);
	list.remove(list.indexOf(n));
	*/
	private Stack<Integer> stack=new Stack<Integer>();
	public  void permutation01(int sum,int n){
		if(n<=0||sum<=0)return;
		if(sum==n){
			printStack(stack);
			System.out.print(n);
			System.out.println();
		}
		stack.add(n);
		permutation01(sum-n,n-1);
		stack.pop();
		permutation01(sum,n-1);
	}
	
	public  void permutation02(int sum, int n) {
		if(n<=0||sum<=0)return;
		for (int i = n; i > 0; i--) {
			if (i == sum) {
				System.out.println(i);
				continue;
			}
			List<Integer> list = new ArrayList<Integer>();
			list.add(i);
			for (int j = i - 1; j > 0;) {
				list.add(j);
				int ret = isOK(list, sum);
				if (ret < 0) {
					j--;
				}
				if (ret == 0) {
					printList(list);
					System.out.println();
					j = list.get(1) - 1;//now we go back and make the second element smaller
					list.clear();
					list.add(i);
				}
				if (ret > 0) {
					list.remove(list.size()-1);//too large,remove the last element
					j--;
				}
			}
		}
	}

	// whether the sum of list element equals to sum or not
	public static int isOK(List<Integer> list, int sum) {
		int re = 0;
		int total = 0;
		for (int each : list) {
			total += each;
		}
		if (total > sum)
			re = 1;
		if (total < sum)
			re = -1;
		return re;

	}

	public void printStack(Stack<Integer> stack){
		/*
		while(!stack.isEmpty()){
			int temp=stack.pop();
			System.out.print(temp+" ");
		}
		*/
		//don't remove the elements in stack
		for(Integer each:stack){
			System.out.print(each+" ");
		}
	}


	public  void printList(List<Integer> list) {
		for (int each : list) {
			System.out.print(each + " ");
		}
	}
	
}

java-21.中兴面试题 输入两个整数 n 和 m ,从数列 1 , 2 , 3.......n 中随意取几个数 , 使其和等于 m

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
背包问题,用递归来解,简单易于理解 void print(int size, bool *flag) { for(int i = 0; i < s
题目 输入两个整数n 和m,从数列1,2,3.......n 中随意取几个数, 使其和等于m ,要求将其中所有的可
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
这道题跟捞鱼问题一样,都是刚进实验室新生培训那会儿做过的题目,不过这个是一师姐当时找工作的面
有 n(n>0) 个数,从中选取 <span style="display: inline-block; positio
打印从n个数种选取m个数的组合数 方法一:利用递归思想。 //从后往前选取,选定位置i后,再在前i-1
已知m,n是正整数,编写程序求m中取n的组合数 源程序: #include<stdio.h> long fac(int k) /
这样在求组合数的时候为了防止中间过程越界,可以c(m,n)=c(m-1,n-1)*m/n int C(intn,int m) { if(m=
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号