本次Google编程挑战赛在中国举行，由www.topcoder.com承办，先后有1万多人报名参加。从昨天中午(12月11日)12点开始到今天中午12点的24小时是初赛，比赛者可以选择在这段时间内的任何时候登陆进入竞赛系统，参加限时1个小时的比赛。在一个小时之内，参赛者需要完成两道不同难度的编程题，分值分别是250和750。参赛者可以在竞赛平台上编辑、编译、测试并提交自己满意的代码。代码规定可以用C++、java、VB、和C#四中语言，全部都可以在线编译，十分方便。参赛者的最后成绩由所提交代码的测试正确度、编写代码耗时和代码执行效率综合决定。
我今天早上9点左右进入比赛系统，先选了750分的题目,题目是关于字符串搜索，我将在另篇文章中讲述该题。现在先来讲讲我后来做到的250分的题，题目如下：
Question:
Problem Statement
You have several identical balls that you wish to place in several baskets. Each basket has the same maximum capacity. You are given an int baskets, the number of baskets you have. You are given an int capacity, the maximum capacity of each basket. Finally you are given an int balls, the number of balls to sort into baskets. Return the number of ways you can divide the balls into baskets. If this cannot be done without exceeding the capacity of the baskets, return 0.
Each basket is distinct, but all balls are identical. Thus, if you have two balls to place into two baskets, you could have (0, 2), (1, 1), or (2, 0), so there would be three ways to do this.
Definition
Class:
FillBaskets
Method:
countWays
Parameters:
int, int, int
Returns:
int
Method signature:
int countWays(int baskets, int capacity, int balls)
(be sure your method is public)
Constraints
-
baskets will be between 1 and 5, inclusive.
-
capacity will be between 1 and 20, inclusive.
-
balls will be between 1 and 100, inclusive.
Examples：
0)
2
20
2
Returns: 3
The example from the problem statement.
1)
3
20
1
Returns: 3
We have only 1 ball, so we must choose which of the three baskets to place it in.
2)
3
20
2
Returns: 6
We can place both balls in the same basket (3 ways to do this), or one ball in each of two baskets (3 ways to do this).
3)
1
5
10
Returns: 0
We have more balls than our basket can hold.
4)
4
5
10
Returns: 146
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
我的代码如下：
1 /*
2 Code by : yxin1322
3 Email: yxin1322@163.com
4 Date: 2005.12.13
5 */
6
7 import java.util.ArrayList;
8
9 public class FillBaskets
10 {
11 //题目要求完成的函数模块
12 public int countWays(int baskets, int capacity, int balls)
13 {
14 if(baskets*capacity < balls)//如果预计篮子不能装下给定数量的球的话，直接返回0
15 {
16 return 0 ;
17 }
18
19 ArrayList ResultSet=new ArrayList();//用于存放分配方案的
20
21 int[] BallInBaskets=new int[baskets];//以篮子个数为大小构造int数组，用于存放各个篮子被分配到的球数
22 for(int i=0;i<baskets;i++)//初始化各篮子里的球的数量
23 {
24 BallInBaskets[i]=0;
25 }
26
27 this.PlaceBall(BallInBaskets,capacity,balls,1,ResultSet);//调用递归程序求解
28
29 /* for(int i=0;i<ResultSet.size();i++)//打印分配方案
30 {
31 System.out.print("----------------------------------------\n");
32 System.out.println((String)ResultSet.get(i));
33 }
34 System.out.print("----------------------------------------\n");*/
35
36 return ResultSet.size();
37
38 }
39
40 /*
41 递归求解程序
42
43 参数说明：
44 int[] BallInBaskets : 当前各篮子中存放的球的个数
45 int capacity : 篮子的容量上界，所有篮子的容量是一样的，题目中已经说明
46 int balls ： 需要分配的球的个数
47 int CurrentBallNumber : 表明当前正在分配第几个球
48 ArrayList ReslutSet : 用于存放分配方案，作为递归函数的参数起到返回结果的作用，
49 因为java在用对象做参数时采用传引用的方式，所以ReslutSet在递归函数嵌套调用中是全局的，
50 它起到的作用是将上层函数的执行状态传到下层函数，并把下层函数的执行结果返回上层
51 */
52 public void PlaceBall(int[] BallInBaskets, int capacity, int balls,
53 int CurrentBallNumber, ArrayList ResultSet)
54 {
55 for(int i=0;i<BallInBaskets.length;i++)//对每个篮子循环
56 {
57 //-------------------------------------------------------------
58 //得到上层递归的分配状态,存入BallInBasketsTemp中
59 // 因为分配状态要回溯，所以这里的分配状态要当做局部量来使用，不能影响到上层递归函数，
60 // 因此必须重新用new来重新申请空间。甚至分配状态在每次for循环结束后都要回溯，所以对于
61 // BallInBasketsTemp的初始化放在了for循环中
62 int[] BallInBasketsTemp=new int[BallInBaskets.length];
63
64 for(int r=0; r<BallInBaskets.length; r++)
65 {
66 BallInBasketsTemp[ r ] = BallInBaskets[ r ] ;
67 }
68 //-------------------------------------------------------------
69
70 if(BallInBasketsTemp[i]!=capacity)//判断当前的篮子是否到达容量上限
71 {
72 BallInBasketsTemp[i]++; //将当前第CurrentBallNumber个球放入第i号篮子中
73 if(CurrentBallNumber==balls)//判断当前放入篮子的球是不是最后一个球
74 {
75 //--------------------------------------------------------
76 //在分配方案集合中查找当前分配方案，若还未出现过，则加入集合中
77 int sign=0;
78
79 String tem=new String();
80 for(int j=0;j<BallInBasketsTemp.length;j++)//将分配方案组装成String
81 {
82 tem=tem+BallInBasketsTemp[j]+" ";
83 }
84
85 for(int j=0;j<ResultSet.size();j++)//在已有的方案集合中查找
86 {
87 if(tem.equals((String)ResultSet.get(j)))
88 sign=1;
89 }
90 if(sign!=1)//若集合中不存在则加入集合
91 ResultSet.add(tem);
92 //---------------------------------------------------------
93 }
94 else //若当前分配的球不是最后一个，则调用递归函数继续分配下一个
95 {
96 this.PlaceBall(BallInBasketsTemp,capacity,balls,CurrentBallNumber+1,ResultSet);
97 }
98 }
99 }
100 }
101
102 //测试函数
103 public static void main(String[] args)
104 {
105 FillBaskets fb=new FillBaskets();
106 int result=fb.countWays(3,20,2);
107 System.out.println("Result: "+result);
108 }
109 }
这道题要求完成函数public int countWays(int baskets, int capacity, int balls)，该函数的参数指定篮子数，每个篮子可容纳的球数以及待分配的球的数量，每个球可以放在任意的篮子里，但不能超过篮子的容量，通过函数求解分配方案数。题目特别指出球与球之间没有差别，而篮子之间有差别。也就是说如果要将a,b两球分配到C、D两个筐，那么把a、b分别放到C、D筐与分别放到 D、C筐是一样的，只能算一种方案。
因为我先做了750分的题目，所以没时间时间完成这题，当时匆匆写好就提交了，后来发现错得一塌糊涂。这段代码是我下来补充完善的，经过了所有测试数据的测试，能够返回正确的答案，但在测试最后一组数据的时候要很久才能得出结果，我想就算当时能做出来也不会得分了，因为竞赛规则里有一条：任何一组测试数据的执行时间不能超过2秒，内存占用不超过8M，我的程序已显然不能满足。如果有兴趣的同学可以想想算法，我的程序大部分时间都用在排除重复方案上了，如果有更好的算法可以交流一下。
通过这次竞赛，让我深深体会到算法的重要性，因为它直接决定了一个程序的执行效率，进而关系到程序的实用性。以前我们做程序练习的时候都只单单满足于实现，并不管程序的执行效率，我想以后应该改一改习惯了。另外还有就是编码的时间，今天总共只给1个小时的时间，真是编得很仓促，心理想着如果多给自己一个小时，一定会把程序写的漂漂亮亮的。现在想起来，原来自己已经习惯了慢条思理地编程，有条不紊地查资料，如果照这样出去工作估计老板要扣工资了。
所以以后的努力方向，算法、编码时间、执行效率，一个都不能少，一点一点进步吧。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
祝贺reallyh荣任斑竹
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机技术与应用 → 『 编程心得 』 → 算法、编码时间、执行效率，一个都不能少——写在参加Google变成挑战赛之后（ZT）
(订阅本版)
2005/12/14 18:07:00
新浪微博
算法、编码时间、执行效率，一个都不能少——写在参加Google变成挑战赛之后（ZT）
