数列切断倒置程序

前端之家收集整理的这篇文章主要介绍了数列切断倒置程序前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

根据Bently写的<<编程珠玑>>(programming pearls)写的一个例程,解决的问题可以简要概述为:

[A,B]-->[B,A]例如:
输入[1,2,3,4,5], 切断位置(partitioning position)为2,那么输出为:
[3,5,1,2]。
问题看似简单,大家千万别小看它的编程难度, 我对编程水平的理解,应该是程序时间(多快的运算时间),空间(多省的内存占用量)以及代码长度(多言简意赅的代码)这三者的综合。
下面代码的编程思想,我可以借用线性代数里面的一个公式概括出来:
(A'B')' = (BA)
just for fun! For more information,please refer to Bentley's book <programming pearls>
place exchange program:
#include <iostream>
#include <assert.h>
using namespace std;
template <class Type>
void exchange_place(const Type *pArr,const int Arr_len,int pos,Type **ppArr_out)
//Effect: pArr [A,B] --> (*ppArr_out)[B,A],with the cutting position 'pos'
//Inputs:
//pArr: the input array
//Arr_len: the length of the input Array
//pos: the partitioning position
//Outputs:
//*ppArr_out: [B,A]
//Author: Su Dongcai at 2011/12/11
//Key ideal:
//(A'B')' = (BA)
{
(*ppArr_out) = new Type[Arr_len];
memcpy(*ppArr_out,pArr,Arr_len*sizeof(Type));
assert(pos < Arr_len);
//A'
reverse(*ppArr_out,pos);
//B'
reverse((*ppArr_out)+pos,Arr_len-pos);
//(A'B')'
reverse(*ppArr_out,Arr_len);
}
template <class Type>
void reverse(Type *pArr,const int Arr_len)
//Effect: reverse the input array: pArr [a,b] --> pArr[b,a]
//inputs:
//pArr: the input array
//Arr_len: the length of input array
//outputs:
//pArr: the reversed Array
//Author: Su Dongcai at 2011/12/11
{
assert(Arr_len > 0);
Type *pArr_cp = new Type[Arr_len];
memcpy(pArr_cp,Arr_len*sizeof(Type));
//now we reverse:
int i;
for(i=0; i<Arr_len; i++)
{
pArr = pArr_cp[Arr_len-i-1];
}
delete [] pArr_cp;
}
template <class Type>
void display(Type *pArr,const int Arr_len)
{
cout<<"[";
int i;
for(i=0; i<Arr_len; i++)
{
cout<<pArr<<",";
}
cout<<"]"<<endl;
}
//main entrance for test purpose:
int main(int argc,char *argv[])
{
int Array[] = {1,5};
int *pArr;
exchange_place<int>(Array,&pArr);
display<int>(pArr,5);
delete [] pArr;
}
原文链接:https://www.f2er.com/javaschema/286976.html

猜你在找的设计模式相关文章