jicha.cpp

包括GRAY码

#include<iomanip.h>

#define N 8
int minmum;
int maxmum;
int a[N+1];

void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}

int partition2(int a[],int p,int r)
{int i=p,j=r+1;
int x;
x=a[p];

while(true){
while(a[++i]>x);
while(a[--j]<x);
if(i>=j) break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}

void quicksort2(int a[],int p,int r)
{if(p<r){
	int q;
q=partition2(a,p,r);
quicksort2(a,p,q-1);
quicksort2(a,q+1,r);
        }
}

int partition1(int a[],int p,int r)
{int i=p,j=r+1;
int x;
x=a[p];

while(true){
while(a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}

void quicksort1(int a[],int p,int r)
{if(p<r){
	int q;
q=partition1(a,p,r);
quicksort1(a,p,q-1);
quicksort1(a,q+1,r);
        }
}


void max(int b[N+1],int i)
{
	b[i-1]=b[i]*b[i-1]+1;
	quicksort1(b,1,i-1);
	if(i>1)
		max(b,i-1);
	else maxmum=b[1];
}

void min(int b[N+1],int i)
{
	b[i-1]=b[i]*b[i-1]+1;
	quicksort2(b,1,i-1);
	if(i>1)
		min(b,i-1);
	else minmum=b[1];
}

void main()
{
	int i;
	for(i=1;i<=N;i++)
	{
		cout<<"input array["<<i<<"]:";
		cin>>a[i];
	}
	quicksort1(a,1,N-1);
	max(a,N);
	quicksort2(a,1,N-1);
	min(a,N);
	cout<<"maxmum-minmum="<<maxmum-minmum<<endl;
}