关于箱子和球的算法问题

0 0

关于箱子和球的算法问题5

有k个完全相同的盒子，必须把n个球放入盒子中。假设箱子里能放入无限多的球，唯一的限制是每个球必须放入一个盒子中。请打印出球放入盒子里的所以可能情况，如果不能得到任何结果，请打印错误。

输入：
球的数量n,盒子的数量k

输出：
球放入盒子的所以可能情况，如果输入不正确，请打印错误。

样本输入：

5 2 (第一个为球的数量n,第二个为盒子的数量k)

样本输出：

0   5 (5个球全部放入一个盒子，另一个盒子为空)

1   4 (1个球放入一个盒子，4个放入另一个盒子)

2   3 (2个球放入一个盒子，3个放入另一个盒子)

算法

2013年6月14日 06:42

ihyperwin
21
0 0 2

6个答案按时间排序按投票排序

0 0

采纳的答案

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class aatest {

	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		System.out.print("请输入球的数量：");
		BufferedReader boll = new BufferedReader(new InputStreamReader(
				System.in));
		String bollNumStr = null;
		bollNumStr = boll.readLine();

		System.out.print("请输入箱子的数量：");
		BufferedReader box = new BufferedReader(
				new InputStreamReader(System.in));
		String boxNumStr = null;
		boxNumStr = box.readLine();
		System.out.println("\n");

		int bollNum = -1;
		int boxNum = -1;

		try {
			bollNum = Integer.valueOf(bollNumStr);
		} catch (NumberFormatException e) {
			System.out.println("输入球的数量错误，数量不是整数");
		} catch (Exception e) {
			e.printStackTrace();
		}

		try {
			boxNum = Integer.valueOf(boxNumStr);
		} catch (NumberFormatException e) {
			System.out.println("输入箱子的数量错误，数量不是整数");
		} catch (Exception e) {
			e.printStackTrace();
		}

		if (bollNum != -1 && boxNum != -1) {
			System.out.println("球的数量是：" + bollNum);
			System.out.println("箱子的数量是：" + boxNum);
			ArrayList<String> list = new ArrayList<String>();

			if (boxNum < 2) {
				System.out.println(bollNum);
			} else {
				list = twoBox(bollNum, 0, list);

				for (int i = 0; boxNum - 2 > i; i++) {
					list = allBox(list);
				}

				for (String ss : list) {
					System.out.println(ss);
				}
			}

		}
	}

	/**
	 * 将传入的list的每一个元素的第一个数拆分成两个数，并重组数组
	 * @param list
	 * @return 重组后的数组
	 */
	public static ArrayList<String> allBox(ArrayList<String> list) {
		ArrayList<String> listback = new ArrayList<String>();
		for (String s : list) {
			StringBuffer sbs = new StringBuffer(s);
			String[] ss = s.split(" ");
			int i = Integer.valueOf(ss[1]);
			ArrayList<String> partlist = new ArrayList<String>();
			partlist = twoBox(Integer.valueOf(ss[0]) - i, i, partlist);
			for (String str : partlist) {
				if (Integer.valueOf(str.split(" ")[0]) >= i)
					listback.add(str + " " + sbs.substring(ss[0].length() + 1));
			}
		}
		return listback;
	}

	/**
	 * 将一个数分成两数，并组成一个数据（例如：5   分成[5 0,4 1,3 2]）
	 * @param first
	 * @param second
	 * @param list
	 * @return 组合好的list
	 */
	public static ArrayList<String> twoBox(int first, int second,
			ArrayList<String> list) {
		list.add(first + " " + second);
		if (first > second + 1) {
			list = twoBox(first - 1, second + 1, list);
		}
		return list;
	}

}

2013年6月14日 14:12

sanyo0714
50
0 0 3

添加评论

0 0

前面那个写错了点

public class BoxAndBall
{
    static int[]box;
    public static void main(String[] args)
    {
        int m=4,n=10;
        box = new int[m];
        divide(0,n);
    }
    
    public static void divide(int index,int ball){
        for(int i=0;i<=ball;i++){
            if(index==box.length){
                box[index-1]=ball;
                for(int j=0;j<box.length;j++){
                    System.out.print(box[j]+"\t");
                }
                System.out.println();
                return ;
            }
            box[index]=i;
            divide(index+1,ball-i);
        }
    }
}

2013年6月15日 14:34

kidding87
1566
1 1 19

1条评论

0 0

public class BoxAndBall
{
    static int[]box;
    public static void main(String[] args)
    {
        int m=4,n=10;
        box = new int[m];
        divide(0,n);
    }
    
    public static void divide(int index,int ball){
        for(int i=0;i<=ball;i++){
            if(index==box.length){
                for(int j=0;j<box.length;j++){
                    System.out.print(box[j]+"\t");
                }
                System.out.println();
                return ;
            }
            box[index]=i;
            divide(index+1,ball-i);
        }
    }
}

2013年6月15日 14:30

kidding87
1566
1 1 19

添加评论

0 0

运行结果

请输入球的数量：6
请输入箱子的数量：4

球的数量是：6
箱子的数量是：4
6 0 0 0
5 1 0 0
4 2 0 0
3 3 0 0
4 1 1 0
3 2 1 0
2 2 2 0
3 1 1 1
2 2 1 1

2013年6月14日 14:15

sanyo0714
50
0 0 3

添加评论

0 0

调用： k=2 , n=5

Stack<int> stack = new Stack<int>();
BoxBall(2, 0, 5, stack, 5);

返回：
5 0
4 1
3 2

2013年6月14日 11:08

giantfish
30
0 0 0

1条评论

0 0

static void BoxBall(int k, int n, int max, Stack<int> stack, int sum)
        {
            if (k == 0)
            {
                Console.WriteLine("box count can't be 0");
                return;
            }

            if (max == 0)
            {
                Console.WriteLine("ball count can't be 0");
                return;
            }

            if (sum == 0 && stack.Count() == k)
            {
                foreach (var i in stack)
                {
                    Console.Write(i + " ");
                }

                Console.WriteLine();
            }

            if (n <= max && sum > 0)
            {
                stack.Push(n);

                BoxBall(k, n + 1, max, stack, sum - n);

                stack.Pop();

                BoxBall(k, n + 1, max, stack, sum);
            }
        }