CS1102 Lab2a, Qn3, Qn4－答重生Paint Disk 那道题非常简单。 给 m 种color, N个sectors，有多少种paint的方法 paint 第一个sector有 m 种可能性，paint 第二个sector有 m-1 种可能性，一直到 第 n 个sector. 这时会有重复的可能，即第一个和最后一个sector是同一种颜色，把这些情况减去即可。 第一个和最后一个sector重复的情况有多少种呢？如果把第一个sector和最后一个sector看成是一个sector，那么每种重复的情况，恰好是 m 种color, N-1 个 sector的情况。所以recursion 就是 PD(m, n) = m*(m-1)^(n-1) - PD(m, n-1) 基本情况有若干种，请自己去分析好了，不再多说。 最后一道题目非常难，题目的意思是，24=2*12=3*8=4*6=2*2*6=... {2, 12}是24的一个set，{3,8}也是24的一个set，{2,12}和{12, 2}算同一个set，{24}也是{24}的一个set。24有7个这样的set。要你算出若干数的set的个数，并且把最大的那个数以及它的set数找出来。 这道题很难。必须用Dynamic Programming才能做出来并且不超时。我用recursion做出来，3个accept，7个超时。想想给的数可能是1000,000，如果recursion做，它的用时该多少啊？ 就算用Dynamic Programming 也很难想出algorithm。请参考以下一段code int results[] = ne (more...)

迟些时候吧等这个lab结束以后。我可以考虑把我的program贴出来。:D