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...)

太过分了吧！！！你怎么可以这样？ 让他们来这里看好了，可别以labTA的身份发给他们啊，不然别的组的人会complain的啊。 浆糊上又将掀起一番腥风血雨的争斗……

solution to that "difficult question""最后一道题目非常难，题目的意思是，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数找出来。" really? Here is a possible way: Firstly, use recursion to get the factoriazation of the number, say 24 = 2^3*3 N=p1^e1*p2^e2*p3^e3...*(pn^en) p1^e1 means p1 tp the power of e1. Then, use this formula: number of different set=(e1+1)*(e2+1)*...(en+1)-1, here minus 1 is to remove {1, N} and {N, 1} duplication. So surprise, a TA says such question is "very difficult". Do you think you are disappointing the students? Shamed, shamed, shamed...... :D Kidding.