• 0
الصغيره1

مساعدة في كود : الترتيب والبحث

سؤال

السلام عليكم لو سمحتم انا عندي مشروع Find Element Ranked R

ولازم يتوافر فيه جميع الشروط المطلوبه

1. Divide and conquer based.

2. The input lists A, B and C must remain intact.

3. No extra storage allowed other than for simple variables.

4. Code complexity must be logarithmic.

For example the element ranked 6th in the combined lists A = [14, 16, 26, 28, 34, 40], B = [10, 20, 24, 30, 38], and C =[11, 18, 22, 32, 36, 42] is 20. While 16 is the 4th ranked element in the same list

ممنو ع احلها بال Merge

انا حليته بس فيه اخطاء ممكن اللي يحس انه يقدر يساعدني يرسلني علشان ارسله الكود

مع العلم انه تسليمه يوم الخميس القادم فالرجاء الرد باقرب وقت

والله عندي حل ولكن لااستطيع نشره

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

6 إجابة على هذا السؤال .

  • 0

ممكن تبعتيلى شرح سريع للخوارزمية التي إخترتيها فى رسالة خاصة.

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

Very Nice Problem !!

بعد تفكير عميق .. وجدت الخوارزمية التي تحلها في Logarithmic Time

إذا استطعتي الوصول لها فلا اعتقد سيقابلك الكثير من المشكل في كتابة الكود بالسي .. فقط تعاملي جيداً مع ال Special Cases

ال Special Cases ستحدث عندما لا يمكنك تطبيق ال Divide and Conquer على أحد الArrays أكثر من ذلك .. في هذه الحالة اعتقد يمكنك استخدام الMerge و لكن بالطبع بدون عمل Merge في الحقيقه ...

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

بالنسبة للحل التقليدي فهو بالتأكيد عن طريق ال Merge لإستخراج العنصر بالترتيب i و سيأخذ وقت خطي (Linear Time)

أما بالنسبة لحل هذه المسأله على Two Arrays فقط فلنفرض أنهم A و B و أننا نريد إيجاد العنصر ذو الترتيب i

نحن نعلم أن الTwo Arrays are sorted

لنفترض أن لدينا Two Arrays A and B و أن كل منهم تحتوي على 12 عناصر و أن أول عنصر ترتيبه هو صفر

و أننا نريد أن نجد العنصر صاحب الindex الذي هو 6 يعني العنصر السابع

سنحسب أولا i / 2 = 6 / 2 = 3

we will compare A[3] with B[3]

if A[3] == B[3] that means we have 3 elements in A and 3 elements of B which are all less than or Equal to A[3] and B[3] so we have six elements A[0], A[1], A[2], B[0], B[1], B[2] which are all less or equal to A[3] and B[3] and we know that all elements after A[3] and B[3] will be either greater than or equal to them, so we find out that A[3] = B[3] is actually the element with index 6 when merging both of the arrays

otherwise for the case that A[3] > B[3] .. we find that A[3] is bigger than three elements in A at most and at least bigger than 4 elements in B including B[3] ... if the element we are looking for is in A it can't be after A[3] because that elements will now be bigger or equal to 8 elements ... A[0] to A[3] and B[0] to B[3] ... so its rank will be at least 8 ... if the element is in B, it can't be smaller than B[3] because if it does, then it will have a rank lower than that of B[3] which is lower than 6 ... which is impossible, so now we know that the element must be in either A[0 ... 3] or B [3 ... 11] ... so we use recursion on these two subarrays and we take into consideration the elements we neglected from B (which must be smaller than the element we are looking for) so we search in these with an element of rank 6 - 3 = 3

A similar argument applies when A[3] < B[3] .... and there's a similar argument too for 3 Arrays

The main point here is that we are looking for k elements to remove which are smaller than the element we are looking for. we remove the elements from our consideration and take into account how they change the new index we are looking for (i - k) and as long as k is a portion of n ... n/2 ... n/3 ... n/100 ... the running time will be logarithmic

عذراً على الكتابة بالإنجليزية لكن وجدت من الأسهل شرح الخوارزمية بهذه الصورة

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عذرا ..

ي ليت توضيح أكثر ,,,

وشكرا مقدما,,,

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عذرا ..

ي ليت توضيح أكثر ,,,

وشكرا مقدما,,,

هذه المسأله لا أنكر انها ليست سهله .. و استغرقت بعض الوقت للوصول للحل

وجدت سؤال لكي منذ قليل عن الBinary Search .. و هو من الخوارزميات البدائية و البسيطة جداً مما يعني انك مازلتي في مرحلة بداية تعلم الخوارزميات

على العموم للأسف لا استطيع شرح الخوارزمية بطريقة افضل من ذلك .. فقط حاولي التركيز في ما كتبته جيداً و حاولي التركيز و التجربة ببعض الأمثله ارسميها على الورق

و نفذي الخوارزم على الورق

و إن كنتي بدأتي بتعلم الخوارزميات حديثا ، يجب أن تأخذي الوقت الكافي للتعلم و لمحاولة حل المسائل بنفسك

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

#include <iostream>
using namespace std;

int binary (int a[],int firsta,int lasta,int b[],int firstb,int lastab,int c[],int firstc,int lastc,int r,int g,int n){


if (g!=r)
{
if (a[firsta] < b[firstb] && a[firsta]< c[firstc])
{g=g+1;
binary( a,firsta+1, lasta,b,firstb, lastab, c, firstc, lastc,r,g,n);
n=a[firsta];}
else
{if (b[firstb] < a[firsta] && b[firstb]< c[firstc])
{n=a[firstb];
g=g+1;
binary( a,firsta, lasta,b,firstb+1, lastab,c, firstc, lastc,r,g,n);}
else
{
g=g+1;
binary( a,firsta, lasta,b,firstb, lastab, c, firstc+1, lastc,r,g,n);
n=a[firstc];}
}
}
else

cout <<"The rank number "<<r<<"is"<<n;

}

int min(int a[],int b[],int c[])//min
{

int lowestNum1 = a[0];
int lowestNum2 = b[0];
int lowestNum3 = c[0];
if (lowestNum1 < lowestNum2 && lowestNum1< lowestNum3)

cout << "The rank number 1 is: " << lowestNum1<< endl;
else if (lowestNum2 < lowestNum1 && lowestNum2< lowestNum3)

cout << "The rank number 1 is: " << lowestNum2<< endl;

else
cout << "The rank number 1 is: " << lowestNum3<< endl;
}

int max(int a[],int b[],int c[])//max
{
int maxNum1 = a[5];
int maxNum2 = b[4];
int maxNum3 = c[5];
if (maxNum1 > maxNum2 && maxNum1> maxNum3)

cout <<"The rank number 17 is: " << maxNum1<< endl;
else
if (maxNum2 > maxNum1 && maxNum2> maxNum3)

cout << "The rank number 17 is: " << maxNum2<< endl;
else
cout << "The rank number 17 is: " << maxNum3<< endl;
}


int main () //main
{
int d=0;
int j=0;
int i=0;
int a=6;
int v=5;
int k=6;
int q=0;
int c=0;
int Array1[] = {14, 16, 26, 28, 34, 40};
int Array2[] = {10, 20, 24, 30, 38};
int Array3[] = {11, 18, 22, 32, 36, 42};
int r;
cout <<"what is the rank"<< endl;
cin>>r;
if (r =7)
binary(Array1,d,j,Array2,i,a,Array3,v,k,r,c,q);

else if (r = 1)
min(Array1, Array2, Array3);
else if(r = 17)
max(Array1, Array2, Array3);

/* Scaffolding code for testing purposes */
cin.ignore(256, '\n');
cout << endl<<"Press ENTER to continue..." << endl;
cin.get();
/* End Scaffolding */
return 0;
}

هذي محاولتي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .