היי,
הנה חלק הקוד שאני משתמש בו,
מקווה שיעזור לך והמון בהצלחה!
/*********************************************************************
* findMedian help func of RectangleLand
* Description:
* finding the median of the 5 inputs
* First - find the minimum, and than find the maximum,
* than narrow your search to understand, which is the median
* according to the max and the min.
*
* Inputs:
* int first,second,third,fourth,fifth
*
* Output:
* minimum of (first,second,third)
*
*********************************************************************/
int RectangleLand::findMedian(int first,int second,int third,int
fourth,int fifth)
{
int result;
int min=first;
int last=0;
if(second<min)
min=second;
if(third<min)
min=third;
if(fourth<min)
min=fourth;
if(fifth<min)
min=fifth;
if(min==first)
first=0;
else if(min==second)
second=0;
else if(min==third)
third=0;
else if(min==fourth)
fourth=0;
else if(min==fifth)
fifth=0;
if(first==0)
last=second;
else
last=first;
if(second!=0 && second<last)
last=second;
if(third!=0 && third<last)
last=third;
if(fourth!=0 && fourth<last)
last=fourth;
if(fifth!=0 && fifth<last)
last=fifth;
if(first==last)
first=0;
else if(second==last)
second=0;
else if(third==last)
third=0;
else if(fourth==last)
fourth=0;
else if(fifth==last)
fifth=0;
/*Now find the median*/
if((first==0) && (second==0))
result=third;
else if(first!=0)
result=first;
else
result=second;
if((first!=0) && (first<result))
result=first;
if((second!=0) && (second<result))
result=second;
if((third!=0) && (third<result))
result=third;
if((fourth!=0) && (fourth<result))
result=fourth;
if((fifth!=0) && (fifth<result))
result=fifth;
return result;
}
/*********************************************************************
* moduleSelection help func of RectangleLand
* Description:
* In order to compute execute the MosnterAttack func in O(n+m),
* we are using "Selection" algorithm to find in O(n),
* implemented as described in the Lecture.
*
* Inputs:
* int* aray,int Idx,int n
*
* Output:
* the desired element we searched.
*
*********************************************************************/
int RectangleLand::moduleSelection(int* array,int index,int n)
{
int result;
if(n==1)
return array[0];
int a=0, b=0, c=0, d=0, e=0; /*used to find the median*/
int counter=0,number=0,low,high;
int median=0, small=0, Idx=0, jdx=0;
int count=0;
int v=(int)(n/5);
v=v+1;
int *medians=new int[v];
while( counter < n )
{
if(a!=0 && b!=0 && c!=0 && d!=0 && e!=0)
{
median=findMedian(a,b,c,d,e); /*Median of medians*/
medians[count]=median;
count++;
a=b=c=d=e=0;
}
if(a==0)
a=array[counter];
else if(b==0)
b=array[counter];
else if(c==0)
c=array[counter];
else if(d==0)
d=array[counter];
else if(e==0)
e=array[counter];
counter++;
}
if(a!=0)
{
medians[count]=a;
count++;
}
if(b!=0)
{
if(a<b)
medians[count-1]=a;
else
medians[count-1]=b;
}
if(c!=0)
medians[count-1]=minimal(a,b,c);
if(d!=0)
medians[count-1]=minimal(a,b,c,d);
if(e!=0)
{
median=findMedian(a,b,c,d,e);
medians[count-1]=median;
}
number=moduleSelection(medians,(int)(count/2),count);
delete[] medians;
low=high=counter=0;
while(counter<n)
{
if(array[counter]<=number)
low++;
counter++;
}
high=n-low;
int *LeftArr=new int[low];
int *RightArr=new int[high];
LeftArr=create(array,n,LeftArr,0,number);
RightArr=create(array,n,RightArr,1,number);
if(low<n)
{
if(index<=low)
result=moduleSelection(LeftArr,index,low);
else
result=moduleSelection(RightArr,index-low,high);
delete[] RightArr;
delete[] LeftArr;
return result;
}
else
{
Idx=0;
small=LeftArr[0];
while(Idx<low)
{
if(LeftArr[Idx]<small)
small=LeftArr[Idx];
Idx++;
}
//small=smallest number
counter=Idx=0;
while(Idx<low)
{
if(LeftArr[Idx]==small)
counter++;
Idx++;
}
if((counter>=index )||((counter>=n) && (n<=index)))
{
delete[] LeftArr;
delete[] RightArr;
return small;
}
else
{
int *tmpArr=new int[low];
Idx=0;
jdx=0;
while(Idx<low)
{
if(LeftArr[Idx]!=small)
{
tmpArr[jdx]=LeftArr[Idx];
jdx++;
}
Idx++;
}
result=moduleSelection(tmpArr,index-counter,jdx);
delete[] LeftArr;
delete[] RightArr;
delete[] tmpArr;
return result;
}
}
}
ר.ה.
On 22 יוני, 21:38, Aviel Avraham <[email protected]> wrote:
> מישהו יכול לתת לי פונקציה שמבצעת select ?? שלנו לא עובד ככ טוב..
> תודה מראש [email protected]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Technion References" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/reference-technion?hl=en
-~----------~----~----~----~------~----~------~--~---
