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[] = new int [max+1];
results[1] = 1;
for (int i=2; i<=max; i++) {
for (int j=1; j<=max/i; j++) {
results[i*j] += results[j];
}
//建议这里加一段code把results print出来看看比较直观
}
[duck (2-12 1:56, Long long ago)]
[ 传统版 |
sForum ][登录后回复]1楼
哈哈，我Forward我组的人这个post了[Climbing (2-12 2:09, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼
(引用 Climbing:哈哈，我Forward我组的人这个post了)太过分了吧！！！你怎么可以这样？
让他们来这里看好了，可别以labTA的身份发给他们啊，不然别的组的人会complain的啊。
浆糊上又将掀起一番腥风血雨的争斗……[duck (2-12 11:23, Long long ago)]
[ 传统版 |
sForum ][登录后回复]3楼
(引用 duck:太过分了吧！！！你怎么可以这样？ 让他们来这里看好了，可别以labTA的身份发给他们啊，不然别的组的人会complain的啊。 浆糊上又将掀起...)~[没落书童 (2-12 12:37, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼
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.
[花露水 (2-12 14:36, Long long ago)]
[ 传统版 |
sForum ][登录后回复]5楼
(引用 花露水:solution to that "difficult question""最后一道题目非常难，题目的意思是，24=2*12=3*8=4*6=2*2*6=... {2, 12}是24的一个set，{3,8}也�...)btwI use only 30 sec to think about this question. If anything wrong, i won't take any responsibility. Haha![花露水 (2-12 14:38, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼
(引用 花露水:solution to that "difficult question""最后一道题目非常难，题目的意思是，24=2*12=3*8=4*6=2*2*6=... {2, 12}是24的一个set，{3,8}也�...)aiyait seems i misunderstood the question, the formula is corrent if only 2 elements in a set is required.[花露水 (2-12 14:42, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼
(引用 duck:太过分了吧！！！你怎么可以这样？ 让他们来这里看好了，可别以labTA的身份发给他们啊，不然别的组的人会complain的啊。 浆糊上又将掀起...)偶是forward这个LINK呀，你，不要激动嘛[Climbing (2-12 17:03, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼
(引用 花露水:solution to that "difficult question""最后一道题目非常难，题目的意思是，24=2*12=3*8=4*6=2*2*6=... {2, 12}是24的一个set，{3,8}也�...)this way, most possibly, will get time out" error.[Climbing (2-12 17:05, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼
(引用 duck:太过分了吧！！！你怎么可以这样？
让他们来这里看好了，可别以labTA的身份发给他们啊，不然别的组的人会complain的啊。
浆糊上又将掀起...)争斗的后面
是一团乱七八糟的浆糊。。。。[mean (2-12 18:25, Long long ago)]
[ 传统版 |
sForum ][登录后回复]10楼
(引用 花露水:aiyait seems i misunderstood the question, the formula is corrent if only 2 elements in a set is required.)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...[duck (2-12 20:08, Long long ago)]
[ 传统版 |
sForum ][登录后回复]11楼
(引用 duck: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...)qie~~Don't teach me like you are my TA. You are a TA, so am I. 没什么了不起，受不了你说话的态度，我闪了。
[花露水 (2-12 20:17, Long long ago)]
[ 传统版 |
sForum ][登录后回复]12楼
哇，当TA好了不起呀！duck and climbing 都是吧？好厉害呀？
你们是不是都拿的A+才可以当的？CAP有没有要求？两位高人想必都是过4.9的吧？崇拜ing~~[我想我是海 (2-12 20:21, Long long ago)]
[ 传统版 |
sForum ][登录后回复]13楼
我这个帖子申请置顶一周，到下周二放下去[duck (2-12 21:58, Long long ago)] [ 传统版 | sForum ][登录后回复]14楼
太神奇了！多谢了。不然还不知道要想多久[我的牛逼 (2-13 20:15, Long long ago)] [ 传统版 | sForum ][登录后回复]15楼
有没有好的方法解决time问题？我的code虽然通过了online jugdge,但我是直接针对online judge来设计的。但是不够efficient. 请老兄提示一下。多谢！^_^[原著 (2-14 22:59, Long long ago)] [ 传统版 | sForum ][登录后回复]16楼
(引用 原著:有没有好的方法解决time问题？我的code虽然通过了online jugdge,但我是直接针对online judge来设计的。但是不够efficient. 请老兄提示一�...)迟些时候吧等这个lab结束以后。我可以考虑把我的program贴出来。:D
[duck (2-14 23:45, Long long ago)]
[ 传统版 |
sForum ][登录后回复]17楼
(引用 duck:迟些时候吧等这个lab结束以后。我可以考虑把我的program贴出来。:D )好，谢谢！^_^[原著 (2-15 0:17, Long long ago)] [ 传统版 | sForum ][登录后回复]18楼