g****g
发帖数: 228 | 1 given an array a of n elements, set a[i] = n!/i (for simplicity, i starts
from 1)
now you have a computer that cannot do division /, how can you set value for
each element of array within o(n) time, assuming each multiplication or
addition is o(1). | g****g
发帖数: 228 | 2 by the way, I don't know the answer yet. I was thinking to factorize n=i*j,
then a[i]=a[n]*j, a[j]=a[n]*i. but factorization also requires division and
this process cannot be done in 0(n) since I might have to a[n-1], a[n-3] too
if they cannot be factorized. | h*****u
发帖数: 1 | 3 notice that a_k = b_k * c_k, where
b_k = (k+1)*b_{k+1} and c_k = (k-1)*c_{k-1}, with b_n = 1 and c_1 = 1.
thus the algorithm goes as follows:
(1) a_n <- 1
(2) for k = (n-1) ... 1, a_k <= (k+1)*a_{k+1}
(3) t <- 1
(4) for k = 2 ... n, t <- (k-1)*t then a_k <- t*a_k
in each loop (2) or (4) there are O(n) multiplications/additions, so the total
time complexity is O(n). The temporary variable t is used to make the
algorithm more readable, if temporaries are not allows, we can use a_1 to
replace t a | g****g
发帖数: 228 | | j*******2
发帖数: 18 | 5 void getArray(int num)
{
int* a = new int[num + 1];
a[0] = 1;
a[1] = 1;
for(int i = 2; i < num + 1; i ++)
a[i] = a[i - 1] * (i - 1);
for(int j = num - 1; j > 0; j --)
{
a[0] = a[0] * (j + 1);
a[j] = a[j] * a[0];
}
for(int k = 1; k < num + 1; k ++)
printf(" %d",a[k]);
delete [] a;
} |
|
