### Author Topic: 程序竞赛  (Read 41160 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&nbsp; 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.

#### 万精油

• 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 »

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 ... Well done, fzy ...
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

#### 万精油

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

#### 万精油

• 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