//汉诺塔
void Hanoi(int n,string A,string B,string C){
if(n == 1)
cout<<A<<"->"<<C<<endl;
else{
Hanoi(n-1,A,C,B);
cout<<A<<"->"<<C<<endl;
Hanoi(n-1,B,A,C);
}
}
//递归实现
int maxNUm(int num[],int n){
if(1 == n)
return num[0];
else
{
int tem = maxNUm(num,n-1);
return (tem > num[n-1]) ? tem : num[n-1];
}
}
int addNum(int num[],int n){
if(1 == n)
return num[0];
else
{
return num[n-1] + addNum(num,n-1);
}
}
int av(int num[],int n){
if(1 == n)return num[0];
else
{
return ((n-1)*av(num,n-1) + num[n-1])/n;
}
}
void pai(int num[],int m,int n){
int j,tem;
if(0 == m){
for (j = 0;j < n;++j)
{
cout<<num[j]<<" ";
}
cout<<endl;
}
else
{
for (j = 0;j<=m;++j)
{
tem = num[m];
num[m] = num[j];
num[j] = tem;
pai(num,m-1,n);
tem = num[m];
num[m] = num[j];
num[j] = tem;
}
}
}
void getNext(char *p,int *next){
int j,k;
next[0] = -1;
j = 0;
k = -1;
int b1 = strlen(p);
while (j < strlen(p) -1)
{
if(k ==-1 || p[j] == p[k] )
{
++j;
++k;
next[j] = k;
}else
k = next[k];
}
}
int KEMMatch(char *t,char *p){
int *next = new int(strlen(p));
getNext(p,next);
int i = 0;
int j = 0;
while (i < strlen(t))
{
if(j == -1 || t[i] == p[j])
{
++i;
++j;
}else
{
j = next[j];
}
if(j == strlen(p))
return i - strlen(p);
}
return -1;
}
/**********************************************************/
//堆插入
//堆插入
void constructHeap(int a[],int n,int value){
a[n] = value;
int j,temp = value;
j = (n-1)/2;
while (j>=0 && n!=0)
{
if(a[j] <= temp)
break;
a[n] = a[j];
n = j;
j = (n-1)/2;
}
a[n] = temp;
}
//堆更新
void UpdataHeap(int a[],int index,int n)
{
int j,temp = a[index];
j = 2*index + 1;
while (j < n)
{
if(j+1 < n && a[j+1] < a[j])
++j;
if(a[j] >= temp)
break;
a[index] = a[j];
index = j;
j = index*2 +1;
}
a[index] = temp;
}
void HeapDelete(int a[],int n){
swap(a[0],a[n-1]);
UpdataHeap(a,0,n-1);
}
//数组堆化
void MakeHeap(int a[],int n){
for (int i = n/2-1; i>=0; --i)
{
UpdataHeap(a,i,n);
}
}
//堆排序
void HeapSort(int a[],int n){
for (int i=n-1; i>=1; --i)
{
swap(a[0],a[i]);
UpdataHeap(a,0,i);
}
}
/*********************************/
/*给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：
要求O（1）空间复杂度和O（n）的时间复杂度；
除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）；
*/
void getB(int a[],int b[],int n){
b[0] = 1;
int i;
for (i = 1;i<n;++i)
{
b[i] = b[i-1] * a[i-1];
}
for (i = n-1;i>=1;--i)
{
b[i] *= b[0];
b[0] *= a[i];
}
}
/*************************************/
//冒泡排序
void BubbleSort(int a[],int n){
int i,j;
int flag = true;
for ( i = 0;i < n;++i)
{
flag = false;
for (j = 1;j < n-i;++j)
{
if(a[j-1] > a[j])
swap(a[j-1],a[j]);
flag = true;
}
if(!flag)
break;
}
}
/*************************************/
//插入排序
void InsertSort(int a[],int n){
int i,j,temp;
for (i = 1;i<n;++i)
{
if(a[i] < a[i-1]){
temp = a[i];
j = i;
do
{
a[j] = a[j-1];
--j;
} while (j>=1 && temp<a[j-1]);
a[j] = temp;
}
}
}
/*************************************/
//希尔排序
void ShellSort(int a[],int n){
int i,j,temp,gap;
gap = n;
do
{
gap = gap/3 +1;
for (i = gap;i < n;++i)
{
if(a[i] < a[i-gap]){
temp = a[i];
j = i;
do
{
a[j] = a[j-gap];
j -= gap;
} while (j>=gap && temp < a[j-gap]);
a[j] = temp;
}
}
} while (gap > 1);
}
/*************************************/
//快速排序
void QuikSort(int a[],int l,int r){
if(l < r)
{
int i = l,j = r,tem = a[l];
while (i < j)
{
while (i<j && a[j] >= tem)
--j;
if(i < j)
a[i++] = a[j];
while (i < j && a[i] <= tem)
++i;
if(i < j)
a[j--] = a[i];
}
a[i] = tem;
QuikSort(a,l,i-1);
QuikSort(a,i+1,r);
}
}
/*************************************/
//选择排序
void SelectSort(int a[],int n){
int i,j,k;
for (i = 0;i<n-1;++i)
{
k = i;
for (j = i+1; j<n;++j)
{
if (a[j] < a[k])
k = j;
}
if(i != k)swap(a[i],a[k]);
}
}
/*************************************/
//斐波那契数列
long Fibonacci1(int n){
if(0 == n)
return 0;
else if(1 == n)
return 1;
else if(n > 1)
return Fibonacci1(n-1) + Fibonacci1(n-2);
else return -1;
}
long fab2(int in){
int x = 0,y = 1,i;
for(i=2;i<=in;i++){
y = x + y;
x = y - x;
}
return y;
};
/************************************/
//给定整数sum，在乱序数组中寻找所有满足x+y=sum的组合
void sumN(int a[],int n,int value){
QuikSort(a,0,n-1);
int i = 0,j = n-1;
while (i < j)
{
if((a[i] + a[j]) == value)
{
cout<<a[i]<<"+"<<a[j]<<endl;
++i;
--j;
}else if((a[i] + a[j]) < value)
++i;
else
--j;
}
}
/************************************/
//寻找在数组中最大的K个数
//堆插入
void constructHeap(int a[],int n,int value){
a[n] = value;
int j,temp = value;
j = (n-1)/2;
while (j>=0 && n!=0)
{
if(a[j] <= temp)
break;
a[n] = a[j];
n = j;
j = (n-1)/2;
}
a[n] = temp;
}
//堆更新
void UpdataHeap(int a[],int index,int n)
{
int j,temp = a[index];
j = 2*index + 1;
while (j < n)
{
if(j+1 < n && a[j+1] < a[j])
++j;
if(a[j] >= temp)
break;
a[index] = a[j];
index = j;
j = index*2 +1;
}
a[index] = temp;
}
void MaxK(int a[],int n,int k){
int i;
int *temp = new int[k];
for (i=0;i<n;++i)
{
if(i < k)
constructHeap(temp,i,a[i]);//先构造k堆
else
{
if (temp[0] < a[i])
{
temp[0] = a[i];
UpdataHeap(temp,0,k);//更新k堆；
}
}
}
for (i=0;i<k;++i)
{
cout<<temp[i]<<" ";
}
delete []temp;
}
/************************************/