大家看看这道算法题，谁会，写出答案！！！！！！！！！！！！！！！！！！！！！！！！！！！！

Question

写一个函数，满足以下功能。给定一个2的倍数的整数n（不用考虑n是否错误了，假定n一定正常），比如n=8，那么对于数列1 2 3 4 5 6 7 8，函数调整一次后变为 1 5 2 6 3 7 4 8. 先写一次调整的，然后如果是k次调整呢？

Answer 1

for(int i=0;i<n;i+=2)
{
  temp = a[i+1];
  a[n-i-2] = a[i+1];
  a[i+1] = temp;
}k次就调用k次这个

Answer 2

void Swap(int* a, int n)
{
int i = 0;
int *b = new int[n];
for(i=0;i<n;i++)
{
b[i] = a[i];
} int nMid = n/2;
for(i=0;i<n;i++)
{
if(i%2 == 1)
a[i] = b[nMid+(i/2)];
else
a[i] = b[i/2];
}
delete[] b;
}
看看这回对了吗

Answer 3

为了代码简单，假设用CDWordArray来存储整数。
CDWordArray arNum;
const DWORD n = 8;
const DWORD k = 5;
int m = n/2;
for(int i=0; i<n; i++)
   arNum.Add(i+1);
for(i=0; i<k; i++)
{
   for(int j=0; j<m-1; j++)
   {
      DWORD num = arNum.GetAt(m+j);
      arNum.RemoveAt(m+j);
      arNum.InsertAt(2*j+1,num); 
   }
   CString sNum;
   for(int t=0; t<n; t++)
   {
       DWORD num = arNum.GetAt(t);
       CString sN;
       sN.Format("%d",num);
       sNum += sN;
       if(t != n-1)
          sNum += " ";
   }
   TRACE("%s\r\n",sNum);//输出每次交换后的结果
}

Answer 4

我这还不够简单啊？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
实际就三行：
for(int j=0; j<m-1; j++)
   {
      DWORD num = arNum.GetAt(m+j);
      arNum.RemoveAt(m+j);
      arNum.InsertAt(2*j+1,num); 
   }
你还要多简单？一行？

Answer 5

我也写了一段，来试试：
#include "stdafx.h"
#include <iostream>
#include <tchar.h>
using namespace std;
typedef struct _IntStr
{
int ivalue;
_IntStr *next;
}IntStr;void InitList(IntStr **pList,const int nLen)
{
IntStr *p = *pList;
IntStr *q = NULL;
int i=0;
while (i++<nLen-1)
{
q = new IntStr();
q->ivalue = i+1;
q->next = NULL;
p->next = q;
p = p->next;
}
}void RollNext(IntStr *pList,IntStr **pPre,IntStr **pCurr,int n)
{
int i=0;
IntStr *p = pList;
while (p && p->next && i++<= n)
{
if (i == n)
{
*pPre = p;
*pCurr = p->next;
return;
}
p=p->next;
}
}
void ExChange(IntStr **pList,const int nLen,const int nExChangeCount)
{
int iSubLen = nLen / 2;
IntStr *p = *pList;
IntStr *pre = NULL;
IntStr *cur = NULL;
IntStr *n = NULL;
while(p)
{
RollNext(p,&pre,&cur,iSubLen);
n = p->next;
if (n->next == NULL)
{
break;
}
p->next = cur;
pre->next = cur->next;
cur->next = n;
p = cur->next;
iSubLen --;
//break;
}
}int _tmain(int argc, _TCHAR* argv[])
{
beginning:
int iLen = 8;
int iExTime = 0;
IntStr *pHeader = new IntStr;
pHeader->ivalue = 1;
pHeader->next = NULL;
cout << "please enter lenth and time:"<<endl;
cin>>iLen;
cin >> iExTime;
if (iLen % 2 != 0 || iLen < 2)
{
cout << "error lenth"<<endl;
getchar();
return 0;
}
if (iExTime < 1)
{
cout << "error time"<<endl;
getchar();
return 0;
}
InitList(&pHeader,iLen);
IntStr *p = pHeader;
cout <<"source: ";
while(p)
{
cout << p->ivalue << " ";
p = p->next;
}
cout << endl;
int i=0;

while(i++<iExTime)
{
cout << i << ": " ;
ExChange(&pHeader,iLen,1);
p = pHeader;
while(p)
{
cout << p->ivalue << " ";
p = p->next;
}
cout << endl;
}
getchar();
goto beginning;
return 0;
}

Answer 6

我也写了一段：
#include "stdafx.h"
#include <iostream>
#include <tchar.h>
using namespace std;
typedef struct _IntStr
{
int ivalue;
_IntStr *next;
}IntStr;void InitList(IntStr **pList,const int nLen)
{
IntStr *p = *pList;
IntStr *q = NULL;
int i=0;
while (i++<nLen-1)
{
q = new IntStr();
q->ivalue = i+1;
q->next = NULL;
p->next = q;
p = p->next;
}
}void RollNext(IntStr *pList,IntStr **pPre,IntStr **pCurr,int n)
{
int i=0;
IntStr *p = pList;
while (p && p->next && i++<= n)
{
if (i == n)
{
*pPre = p;
*pCurr = p->next;
return;
}
p=p->next;
}
}
void ExChange(IntStr **pList,const int nLen,const int nExChangeCount)
{
int iSubLen = nLen / 2;
IntStr *p = *pList;
IntStr *pre = NULL;
IntStr *cur = NULL;
IntStr *n = NULL;
while(p)
{
RollNext(p,&pre,&cur,iSubLen);
n = p->next;
if (n->next == NULL)
{
break;
}
p->next = cur;
pre->next = cur->next;
cur->next = n;
p = cur->next;
iSubLen --;
//break;
}
}int _tmain(int argc, _TCHAR* argv[])
{
beginning:
int iLen = 8;
int iExTime = 0;
IntStr *pHeader = new IntStr;
pHeader->ivalue = 1;
pHeader->next = NULL;
cout << "please enter lenth and time:"<<endl;
cin>>iLen;
cin >> iExTime;
if (iLen % 2 != 0 || iLen < 2)
{
cout << "error lenth"<<endl;
getchar();
return 0;
}
if (iExTime < 1)
{
cout << "error time"<<endl;
getchar();
return 0;
}
InitList(&pHeader,iLen);
IntStr *p = pHeader;
cout <<"source: ";
while(p)
{
cout << p->ivalue << " ";
p = p->next;
}
cout << endl;
int i=0;

while(i++<iExTime)
{
cout << i << ": " ;
ExChange(&pHeader,iLen,1);
p = pHeader;
while(p)
{
cout << p->ivalue << " ";
p = p->next;
}
cout << endl;
}
getchar();
goto beginning;
return 0;
}

Answer 7

牛人大哥，你给的CDWordArray类人家没看过呢，太深奥了所以有点不好理解；
若是用数组的话对于初学者就好理解多咯

Answer 8

// 1 2 3 4 5 6 7 8
// 1 5 2 6 3 7 4 8#include <stdio.h>
#include <string.h>void AdjustFun(int *pAdjust, int *pArray, int nLen)
{
int n = nLen/2;
int i, j;
int b = 0; int *pTmp = new int[nLen]; memcpy(pTmp, pArray, nLen*sizeof(int)); for( i = 0, j = nLen-1; n--; ++i, --j )
{
if(&pArray[j] == pAdjust)
{
++b;
continue;
} if( b )
{
pArray[i] = pTmp[i+n];
pArray[j] = pTmp[j-n];
b = 0;
}
else
{
pArray[i] = pTmp[i-1];
pArray[j] = pTmp[j+1];
} if( i%2 )
{
pArray[i] ^= pArray[j] ^= pArray[i] ^= pArray[j];
}
} delete [] pTmp;
}int main(void)
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
int nLen = sizeof(a)/sizeof(int);
int i; int k = 7; // k次调整，循环用 AdjustFun(&a[k], a, nLen); // a[7] == 8 for( i = 0; i< nLen; ++i )
{
printf("%d ", a[i]);
} getchar();
    return 0;
}磨点分~

Answer 9

第一种方案，用一个结构体，因为这个函数主要是改变数值的排序，数值本身没有改变，所以只要改变结构体中的成员变量c就可以了,控制台程序已验证！
#include <iostream>
using namespace std;struct Sort
{
int b;//保存数值
int c;//保存数值在数列中位置信息，主要是改变这个数值，
};int GetResult(int n,int k)
{
Sort* a=new Sort[n];
//为结构体成员赋值；
for(int i=0;i<n;i++)
{
a[i].b=i+1;
a[i].c=i+1;//开始的时候数值在数列中的位置与数值相同
}

for(int f=0;f<k;f++)
{
for(int i=0;i<n;i++)
{
if(a[i].c*2>n)
{
a[i].c=a[i].c*2-n;//发现顺序的改变规律是当前顺序乘以2，如果大于数列元素个数n，则减去
//n就是新的位置；反之只要减去一即可；
}
else
{
a[i].c=a[i].c*2-1; 
}
}
}
//此处只要对结构体数组按照c值排序输出即可
for(int e=1;e<=n;e++)
{
for(int k=0;k<n;k++)
{
if(a[k].c==e)
cout<<a[k].b<<"";
}
}

delete [] a;
return 0;
}int main()
{
int n,k;
while(1)
{
cin>>n;
cin>>k;
GetResult(n,k);
}

return 0;

}
方案2：分析可知，第一个数和最后一个数是不会改变的，中间的数平分为两部分，前一部分对应于改变后的数列中的奇数位置的数据，而后一部分则是对应于偶数位置部分，那么就用两个数组，第一个数组b[]保存原始数据，另一个数组a[]从第一个数组b[]中获取数据进行改变，完成后，将b[]与a[]同步，这样两个数组的值又相同了，可以进行下一次改变；控制台已验证#include <iostream>
using namespace std;GetResult(int n,int k)
{
int m;
int *a=new int[n],*b=new int[n];
for(int p=0;p<n;p++)
{
  a[p]=p+1;
  b[p]=p+1;
}for(int i=0;i<k;i++) 
{
  m=n/2;
  for(int f=1;f<(n-1);) //填充偶数位置的数据
  { 
    a[f]=b[m];
    m=m+1;
f=f+2;
  }
  m=1;
  for(int e=2;e<(n-1);)//填充奇数位置的数据
  {
    a[e]=b[m];
    m=m+1;
e=e+2;
  }
  for (int d=0;d<n;d++)  //同步b[]与a[]数组，为下次转换做准备；
    b[d]=a[d];
 
}
for(int g=0;g<n;g++)
cout<<a[g];delete []a;
delete []b;
return 0;
}int main()
{
    int n,k;
while(1)
{
 cin>>n;
 cin>>k;
 GetResult(n,k);  
}
return 0;
}

Answer 10

把
  for (int d=0;d<n;d++)  //同步b[]与a[]数组，为下次转换做准备；
    b[d]=a[d];
改为
memcpy(b,a,sizeof(int)*n);

Answer 11

我想  最原始也最简单的算法就是造个与a[k]等长数组b[k]
for(int i=1,int j=1;i<k;i+=2,j++)
{
   b[i]=a[j];
   b[i-1]=a[j+k/2];
}

Answer 12

大意了 改成下面的才对
for(int i=1,int j=k/2;i<k;i+=2,j++)
{
   b[i]=a[j];
   b[i-1]=a[j];
}

Answer 13

大意了 改成下面的才对
for(int i=1,int j=1;i<k;i+=2,j++)
{
   b[i]=a[j];
   b[i-1]=a[j+k/2-1];
}

Answer 14

先要把周期算出来
以lz的数据为例
 1 2 3 4 5 6 7 8
 1 5 2 6 3 7 4 81->1
2->3->5->2
4->7->6->4
8->8
一共有4个循环 ，求所有循环长度的最小公倍数m将输入的k对m取模 再按楼上的方法算，这样会快一些。
不知可否。

Answer 15

void binary( int *arr, int len )
{
    int *tmp = new int[ len+1 ] ;    memcpy( tmp, arr, sizeof(int)*len ) ;    for( int i=0; i<len/2; i++ )
    {
        arr[2*i] = tmp[i] ;
        arr[2*i + 1] = tmp[ len/2 + i] ;
    }    delete []tmp ;
}void binary_k( int *arr, int len, int count )
{
    for( int i=0; i<count; i++ )
    {
        binary( arr, len ) ;
    }
}