为什么中国苹果坏了换全新机美国坏了换翻新机 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Apple - 家有苹果

为什么中国苹果坏了换全新机美国坏了换翻新机

为什么中国苹果坏了换全新机美国坏了换翻新机# Apple - 家有苹果

v*y2015-08-17 07:08

1 楼

Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
Is there any solution better than O(n^2) ?

h*i2015-08-17 07:08

2 楼

美国公司歧视美国人？

p*n2015-08-17 07:08

3 楼

这种题估计就是每次对半分，然后递归，总的complexity变成O(nlogn)

【在 v******y 的大作中提到】

: Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
: Is there any solution better than O(n^2) ?

z*e2015-08-17 07:08

4 楼

都是官翻机。

k*n2015-08-17 07:08

5 楼

there is an O(N) solution
if n satisfies some conditions (I forgot it, maybe n=3**k-1)
then you can do it perfectly by move a1 to a2 and a2 to a4 ...
and finally when some Xn come back to a1, during this process, no 'collision
' occurs, which means for any Xn, when you want to put it into a new
position Ym,
this Ym position is not the original Ym, but has been transpositioned.
So this is a perfect transposition, with O(n) time and O(1) space complexity.
Having known this, to solve a problem with arbitrary n, just do tail
recursion.

【在 v******y 的大作中提到】

: Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
: Is there any solution better than O(n^2) ?

c*b2015-08-17 07:08

6 楼

In-place shuffle
http://en.wikipedia.org/wiki/In_shuffle
Reference里面有O(n)的算法

【在 v******y 的大作中提到】

: Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
: Is there any solution better than O(n^2) ?

f*n2015-08-17 07:08

7 楼

我贴一下O（n）算法的实现吧，大家自己琢磨
#include "stdio.h"
//轮换
void Cycle(int Data[],int Lenth,int Start)
{
      int Cur_index,Temp1,Temp2;
      Cur_index=(Start*2)%(Lenth+1);
      Temp1=Data[Cur_index-1];
      Data[Cur_index-1]=Data[Start-1];

     while(Cur_index!=Start)
     {
        Temp2=Data[(Cur_index*2)%(Lenth+1
)-1];
        Data[(Cur_index*2)%(Lenth+1)
-1]=Temp1;
        Temp1=Temp2;
        Cur_index=(Cur_index*2)%(Lenth+1);
   }
}
//数组循环移位参考编程珠玑
void Reverse(int Data[],int Len)
{
  int i,Temp;
  for(i=0;i  {
       Temp=Data[i];
       Data[i]=Data[Len-i-1];
       Data[Len-i-1]=Temp;
  }
}
void ShiftN(int Data[],int Len,int N)
{
   Reverse(Data,Len-N);
   Reverse(&Data[Len-N],N);
   Reverse(Data,Len);
}
//满足Lenth=3^k-1的perfect shfulle的实现
void Perfect1(int Data[],int Lenth)
{
     int i=1;
    if(Lenth==2)
  {
         i=Data[Lenth-1];
         Data[Lenth-1]=Data[Lenth-2];
         Data[Lenth-2]=i;
         return;
     }
     while(i   {
         Cycle(Data,Lenth,i);
         i=i*3;
    }
}
//查找最接近N的3^k
int LookUp(int N)
{
   int i=3;
   while(i<=N+1) i*=3;
   if(i>3) i=i/3;
   return i;
}
void perfect(int Data[],int Lenth)
{
   int i,startPos=0;
   while(startPos   {
     i=LookUp(Lenth-startPos);
     ShiftN(&Data[startPos+(i-1)/2],(Lenth-startPos
)/2,(i-1)/2);
     Perfect1(&Data[startPos],i-1);
     startPos+=(i-1);
   }
}
#define N 100
void main()
{
   int data[N]={0};
   int i=0;
   int n;
   printf("please input the number of data you wanna to test
(should less than 100):\n");
   scanf("%d",&n);
   if(n&1)
   {
        printf("sorry,the number should
be even ");
        return;
    }
    for(i=0;i         data[i]=i+1;
   perfect(data,n);
   for(i=0;i       printf("%d   ",data[i]);
}

z*e2015-08-17 07:08

8 楼

我搞不懂为什么对于3^k-1的n，就可以不断地shift之后再cycle，然后就perfect
shuffle了？

【在 f*******n 的大作中提到】

: 我贴一下O（n）算法的实现吧，大家自己琢磨
: #include "stdio.h"
: //轮换
: void Cycle(int Data[],int Lenth,int Start)
: {
:       int Cur_index,Temp1,Temp2;
:       Cur_index=(Start*2)%(Lenth+1);
:       Temp1=Data[Cur_index-1];
:       Data[Cur_index-1]=Data[Start-1];
: