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

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.

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.

If so, you are not able to get itEven if to compute all set with only two elements, your algorithm is not able to get it. 24 = 2^3*3, by your formula, the number of sets are 4*2-1 = 7. In fact, it is {24}, {2, 12}, {3, 8}, {4, 6}, which is only 4. :) I am not going to pointing your mistake here. Anyway, read the question carefully. I do not think this question is able to be solved by permutation and combination formula. Indeed, it is hard to solve it. In programming, we also consider complexity of an algorithm. Another bottleneck to this problem is that there may be about 1000,000 number to compute. Then how? Think about it...