الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

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

بدأه الصغيره1 في 12 ديسمبر 2011 · 6 رد · 1,167 مشاهدة · في الأسئلة المجابة
مشاركة: واتساب X فيسبوك تيليجرام
#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

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

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

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

#2

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

1

كيف تسأل الأسئلة بطريقة ذكية

#3

Very Nice Problem !!

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

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

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

#4

بالنسبة للحل التقليدي فهو بالتأكيد عن طريق ال 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

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

#5

عذرا ..

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

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

#6
3D3D كتب:

عذرا ..

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

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

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

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

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

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

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

#7 
#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;
}

هذي محاولتي

مواضيع مشابهة