Other windows programs

Development Platform:
Visual C++

main.cpp：Code Content
							#include <iostream>
#include <cstdlib>
#include <ctime>
#include <math.h>
static unsigned long jz,jsr=123456789;
#define SHR3 (jz=jsr, jsr^=(jsr<<13), jsr^=(jsr>>17), jsr^=(jsr<<5),jz+jsr)
#define UNI (.5 + (signed) SHR3*.2328306e-9)
#define IUNI SHR3
static long hz;
static unsigned long iz, kn[128], ke[256];
static float wn[128],fn[128], we[256],fe[256];
#define RNOR (hz=SHR3, iz=hz&127, (fabs(hz)<kn[iz])? hz*wn[iz] : nfix())
#define REXP (jz=SHR3, iz=jz&255, (    jz <ke[iz])? jz*we[iz] : efix())
#define ranf() 
  ((float)rand()/(1.0+(float)RAND_MAX)) // Uniform from interval [0,1)
using namespace std;
void make_array(int);
int binary_search(int *,int,int);
int exp_interpolation_search(int *,int,int);
float gauss();
float efix();
void zigset(unsigned long);
void quicksort(int *A,int m);
void taxytaksinomisi(int *A,int p, int r);
int diamerisi(int *A, int p, int r);
int count=0;
int main(){
	int size;
	cout << "Dose megethos pinakan";
	cin >> size;
	make_array(size);
}
void make_array(int size) {
  int i,katanomi,search;
  int found;
  int x;
  int *array=new int[size];
  srand(time(0));
  cout << "Diale3e katanomi:n1.Gaussian katanomin2.Omoiomorfin3.Ekthetikin";
  cin >> katanomi;
  if (katanomi==1)
    for (i=0; i<size; i++)
      array[i] = (gauss()+5)*1000;
  else if (katanomi==2)
    for (i=0; i<size; i++)
      array[i] = (float)(rand()%1000000) +1 ;
  else if (katanomi==3)
    { zigset(86947731);
      for (i=0; i<size; i++)
        array[i] = efix()*100000;
    }
  //for (i=0; i<size; i++)
    //cout << array[i] << " ";
  cout << "n";
  quicksort(array,size);
  cout << "n";
  for (i=0; i<size; i++)
    cout << array[i] << " ";
  cout << "n";
  cout << "Dose to stoixeio gia euresin";
  cin >> x;
  cout <<"Diale3e searchn1.Binary Searchn2.Interpolation Searchn";
  cin >> search;
  if (search==1)
   {  found = binary_search(array,x,size);
        if (found!=0) 
		  { cout << "To stoixeio vre8ike sti 8esi " << found<<endl; 
		    cout << "O arithmos ton sigkriseon = "<<count<<endl; }
        else cout << "To stoixeio den vre8ike";
      cout << "n"; }
  else if (search==2)
   {
	  found = exp_interpolation_search(array,x,size);
        if (found!=0) 
		  { cout << "To stoixeio vre8ike sti 8esi " << found<<endl; 
		    cout << "O arithmos ton sigkriseon = "<<count<<endl; }
      else cout << "To stoixeio den vre8ike";
      cout << "n"; }
}
void quicksort(int *A,int m) {
     cout << "nquickn";
     taxytaksinomisi(A,0,m-1);
}
void taxytaksinomisi(int *A,int p, int r) {
      int q;
      if (p<r) {
          q=diamerisi(A, p, r);
          taxytaksinomisi(A,p,q-1);
          taxytaksinomisi(A,q+1,r);
      }
}
int diamerisi(int *A, int p, int r) {
      int x=A[r];
      int i=p-1;
      int t;
      for(int j=p; j<r; j++) {
          if (A[j]<=x) {
             i++;
             t=A[j];
             A[j]=A[i];
             A[i]=t;
           }
      }
      t=A[r];
      A[r]=A[i+1];
      A[i+1]=t;
      return i+1;
}
int binary_search(int *array,int x,int size) {
  int left,right,i,mikos;
  mikos=size;
  left=0;
  right=mikos;
  while(mikos!=0) {
    mikos=(right-left)/2;
	count++;
	if (x==array[left+mikos])
	  return left+mikos+1;
    else 
	  if (x>array[left+mikos]) 
	    { count++; left=left+mikos; }
	  else 
	    { count++; right=right-mikos; }
  }
  return 0;
}
int exp_interpolation_search(int *array,int x,int size) {
  int left,left2=0,right,right2,next,i=1,j,y,d=0,k,root_size,mikos;
  bool out_of_bounds=false,out_of_bounds2=false,found=false;
  //elegxos gia size<=3
  if (size<=3)
   { for (j=0; j<size; j++)
	   if (array[j]==x) 
	     { count++; return j+1; }
     return 0; }
  root_size=(int)sqrt((float)size);
  int *array3 = new int[root_size];
  //euresi next
  left=0;
  right=size-1;
  if (x==array[right])
    next=size;
  else
	  next=size*((float)(x-array[left])/(array[right]-array[left]))+1;
  
  if ((next>size)||(next<=0))
	  return 0;
  //euresi diastimatos pou vrisketai to x
  cout << "next:" << next << "n";
  count++;
  if (x==array[next-1])
    return next;
  else
    if (x>array[next-1]) {
	  if (next-1+i*root_size-1>=size)
	    { count++; i=1; out_of_bounds=true; }
	  else
	    { count++;
          while (x>array[next-1+i*root_size-1]) {
  	        i=2*i;   
		    count++;
		    if (next-1+i*root_size-1>=size) 
			  { out_of_bounds=true; break; }
	      }
	    }
      right=next+i*root_size;
	  left=next+(i/2)*root_size; 
	}
	else {
	  if (next-1-i*root_size+1<0)
	    { count++; i=1; out_of_bounds2=true; }
	  else
	    { count++;
	      while (x<array[next-1-i*root_size+1]) {
	        i=2*i;
		    count++;
            if (next-1-i*root_size+1<0)
			  { out_of_bounds2=true; break; }
	      }
	    }
	  right=next-(i/2)*root_size;
	  left=next+1-i*root_size;
	} 
  //elegxos otan to alma einai megalitero tou size
  if (out_of_bounds) {
	//euresi megistou ipodiastimatos pou vgainei out of bounds
    for (j=1; j<(i/2); j++)
	  if ((left+j*root_size)>size) break;
	//euresi ean iparxei ipodiastima riza(n)
	for (k=1; k<j; k++)
	  if (x<array[left+k*root_size])
	    { count++; found=true; break; }
    if (found)
	   left2=(k-1);
	else
	  { for (j=left-1+(k-1)*root_size; j<size; j++)
	      if (array[j]==x) 
	        return j+1; 
	    return 0; } 
  }
  //elegxos otan to alma einai mikrotero tou 0
  else if (out_of_bounds2) {
    //euresi elaxistou ipodiastimatos pou vgainei out of bounds
    for (j=1; j<(i/2); j++)
	  if ((right-j*root_size<0)) break;
	//euresi ean iparxei ipodiastima riza(n)
	for (k=1; k<j; k++)
	  if (x>array[right-k*root_size])
	    { count++; found=true; break; }
    if (found)
	  { cout<< k<<endl;
	    left2=0;
		left=right-k*root_size+1;
	  }
	else
	  { left=0;
		for (j=left; j<(right-(k-1)*root_size+1); j++)
		  if (array[j]==x) 
			  return j+1; 
	    return 0; }
  }
  //dimiourgia pinaka gia binary search
  else {
    mikos=i/2;
    //otan to i!=1(gia diastimata pou mporoun na spasoun 
    //             se riza(n) ipodiastimata)
    if (i!=1) {
      int *array2 = new int[mikos];
      k=0;
      for (j=0; j<mikos; j++)
	    { array2[j]=array[left-1+k*root_size];
          k++; }
	
      for (k=0; k<mikos; k++)
	    cout << array2[k]<< " ";
      cout << "n";
      //binary search(euresi ipodiastimatos riza(n))
      left2=0;
      right2=mikos;
      while(mikos!=1) {
        mikos=(right2-left2)/2;
	    count++;
        if (x==array2[left2+mikos])
	      return (left2+mikos)*root_size;
        else 
	      if (x>array2[left2+mikos]) 
		    left2=left2+mikos;
	      else right2=right2-mikos;
	  }
  }  
    //otan i=1(den mporei na spasei se pairetero ipodiastimata)
    else
      {left2=0; right2=0;}
  }
  //dimiourgia neou pinaka mege8ous riza(n) gia anadromiki klisi
  for (j=0; j<root_size; j++)
	  array3[j]=array[left-1+left2*root_size+j];
  for (j=0; j<root_size; j++)
      cout << array3[j]<< " ";
  
	y=exp_interpolation_search(array3,x,root_size); 
  if (y==0)  
    return 0;
  else
    if (i==1)
	  return left-1+y;
	else
	  return left-1+left2*root_size+y;
}
float gauss(){                     
      float x1, x2, w, y1; 
      static float y2; 
      static bool y2next=false;
      if (y2next==true){ y2next=false; 
         y2 = y2*10000;
         y2 = floor(y2 + 0.5); 
         return y2/10000;      
      return y2; }
         do {
                 x1 = 2.0 * ranf() - 1.0;
                 x2 = 2.0 * ranf() - 1.0;
                 w = x1 * x1 + x2 * x2;
         } while ( w >= 1.0 );
         w = sqrt( (-2.0 * (log(w)/log(exp((float)1))) ) / w );
         y1 = x1 * w;
         y2 = x2 * w;
         y2next=true;
           y1 = y1*10000;
           y1 = floor(y1 + 0.5); 
         return y1/10000;
}
float efix(void)
{ float x;
 for(;;)
  {  if(iz==0) return (7.69711-log(UNI));          /* iz==0 */
     x=jz*we[iz]; if( fe[iz]+UNI*(fe[iz-1]-fe[iz]) < exp(-x) ) return (x);
      /* initiate, try to exit for(;;) loop */
   jz=SHR3;
   iz=(jz&255);
   if(jz<ke[iz]) return (jz*we[iz]);
  }
}
void zigset(unsigned long jsrseed)
{  const double m1 = 2147483648.0, m2 = 4294967296.;
   double dn=3.442619855899,tn=dn,vn=9.91256303526217e-3, q;
   double de=7.697117470131487, te=de, ve=3.949659822581572e-3;
   int i;
   jsr^=jsrseed;
/* Set up tables for REXP */
    q = ve/exp(-de);
    ke[0]=(de/q)*m2;
    ke[1]=0;
    we[0]=q/m2;
    we[255]=de/m2;
    fe[0]=1.;
    fe[255]=exp(-de);
   for(i=254;i>=1;i--)
  {de=-log(ve/de+exp(-de));
   ke[i+1]= (de/te)*m2;
   te=de;
   fe[i]=exp(-de);
   we[i]=de/m2;
  }
}

						