Author Topic: 程序竞赛  (Read 44713 times)

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #15 on: 十二月 03, 2005, 08:17:58 am »
Quote from: 万精油
I assume your n is an integer too. From your comments, it seems your n can be greater than a long integer in C (32 bits, or 64 bits depends on  the machines).

n can be any number, therefore a counter is of size log(n). The condition says you may have a limited number of storage units, each han hold a number no more than n.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 程序竞赛
« Reply #16 on: 十二月 03, 2005, 12:20:30 pm »
Quote
n can be any number, therefore a counter is of size log(n). The condition says you may have a limited number of storage units, each han hold a number no more than n.

This is much clearer. The original phrase is a little misleading. The phrase seemed that we need to allocate an array of size log(n) of integer type (and I think this is what people usually mean).

Now that we have a limited number of storage units of size n,  are you sure O(n) (not n*log(n)) is the speed? Going through the loop from 1 to n is already n,  since you don't have log(n) unit of storage place, you need to go through 1 to n for log(n) times, that give you n*log(n).  Of course, you may have a completely different algorithm. In any event, this is a very interesting problem.

visitor

  • Guest
Re: 程序竞赛
« Reply #17 on: 十二月 04, 2005, 12:59:01 pm »
I probably did not understand your question, but if you do this:
take the sum of all the numbers in that array (i.e., a=0; for i=1 to n, a=a+array(i); then a-.5*n*(n-1) is the repeated number).
It takes n+1 addition and do not use any memory ...
even the repeated number is uniqure, it does not work to me. For example, let n-1= 6.
and the real data is:
1, 2, 2, 3, 4, 6.
 The result of sum(array) - n(n-1)/2 = -3!!!
This formalar works for n+1 number from (1, ..., n) with one repeated number.

visitor

  • Guest
I did not read the question carefully.
« Reply #18 on: 十二月 04, 2005, 03:25:23 pm »
My post is wrong.

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #19 on: 十二月 05, 2005, 10:42:40 am »
设此数组为A。数组A的一个特点是每个值都是数组的指标,也就是可以对数组进行迭代:A[n],A[A[n]],...。这样迭代一定会产生重复,如下图,重复产生在圆和直线相交的地方(J)。我们设计一个找到这一点的方法。



设直线的长度为A,圆周长为B。设有两个人从直线的一头(O)开始前进,第一个人的速度是第二个人的两倍。当第二个人到达交点J时,第一个人在圆周上一点X,X到起点的距离满足 X = 2A mod B。 第二个人到达Y点时第一个人追上他。易见Y到J和J到X的距离相等,都是 A mod B。这时再假设有第三个人从起点O出发,速度和第二个人相同,则他们同时到达J点。

具体程序如下:

x = A[n];
y = A[A[n]];
while (x != y) {
   x = A[x ];
   y = A[A[y]];
}

y = n;
while (x != y) {
   x = A[ x];
   y = A[y];
}
« Last Edit: 十二月 05, 2005, 02:19:40 pm by fzy »

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: 程序竞赛
« Reply #20 on: 十二月 05, 2005, 10:59:30 am »
LOL  This is absolutely the funniest post I have ever seen :D ... Well done, fzy :D ...
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 程序竞赛
« Reply #21 on: 十二月 05, 2005, 02:10:42 pm »
Quote
x = A[n];
y = A[A[n]];
while (x != y) {
   x = A[x ];
   y = A[A[y]];
}

y = n;
while (x != y) {
   x = A[ x];
   y = A[y];
}

This is indeed a great solution, and the time is O(n). 

Just one question, why do you need n to start? Wouldn't start from 1 get the same effect?

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #22 on: 十二月 05, 2005, 02:22:11 pm »
Quote from: 万精油

Just one question, why do you need n to start? Wouldn't start from 1 get the same effect?


It is necessary to start from n. The range of the array is 1 to n-1. Starting from n guarantees that the straight line part has a positive length.

This method is called Pollard's rho, because of the shape of the path.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 程序竞赛
« Reply #23 on: 十二月 05, 2005, 04:09:23 pm »
Quote
It is necessary to start from n. The range of the array is 1 to n-1. Starting from n guarantees that the straight line part has a positive length.

Ah, yes. Otherwise, your J and Y may turn out tol be the same points.

Quote
This method is called Pollard's rho, because of the shape of the path.

This Pollard's rho method used to be (and may still be) one of the important method of primality test.

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: 程序竞赛
« Reply #24 on: 十二月 06, 2005, 01:34:33 pm »
I am sure I must be stupid again. But I still could not see how this method can find ALL the repeated values... :(
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #25 on: 十二月 06, 2005, 01:56:14 pm »
Quote from: idiot94
I still could not see how this method can find ALL the repeated values... :(


It cannot, but that is not required  :lol: