ممكن حد يساعدني في حل هذا algorithm

[almazuoona]

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




// Searching for value in sorted list of n items x[o], x[1], …, x[n-1]
int start=0, middle, end=n-1;
while (start <= end) {
middle = (start + end)/2
if (x[middle] > value)
end=middle-1
else if (x[middle] < value)
Start= middle +1
else
return true
return false

Complete the following table-
Binary Search Algorithm-



1-input size
2-key step
3-worse case
4-average case

[almazuoona]

heeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee lp........lesh kl ma a7e6 she ared 7d ysa3dne feh m7d birod :(

[saeed2008aae]

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




// Searching for value in sorted list of n items x[o], x[1], …, x[n-1]
int start=0, middle, end=n-1;
while (start <= end) {
middle = (start + end)/2
if (x[middle] > value)
end=middle-1
else if (x[middle] < value)
Start= middle +1
else
return true
return false

Complete the following table-
Binary Search Algorithm-



1-input size
2-key step
3-worse case
4-average case

السلام عليكم

معذرة أختي يمكن الرد متأخر شوي، لكن أنا صراحة ما أدش المنتدى كثير،

عالعموم، اللوغاريتم هذا يبحث عن عدد في "جدول من بعد واحد" أو بالإنجليزي"array" أو "table"

نبدأ أولا بشرح الطريقة، بعدين نمر للحل

المبدأ هو:

لنتخيل أنه عندنا هالجدول من الاعداد:



|1 | 5 | 8 | 11 |18 | 22 | 37 | 46 | 53 |


فمبدأ البحث الذي يعتمد عليه هذا اللوغارتم هو كالتالي: (لنفترض أننا نبحث عن العدد 5 داخل الجدول)

ملحوظة: (اللوغارتم يعتبر أن عناصر الجدول مرتبة وليست عشوائية)

1 : نأخذ العدد الذي يوجد بمنتصف الجدول، أي "18"، ونقارنه بالعدد الذي نبحث عنه "5"، نلاحظ أن 5<18 ، إذا سنبحث في النصف الذي يوجد على يسار المنتصف( الجهة الصغرى)، يعني سنعتبر فقط العناصر:


|1 | 5 | 8 | 11 |


والآن نعيد نفس العملية، لدينا 5<8 ، إذا نبحث في النصف الذي على اليسار مجددا:


|1 | 5 |


مجددا نفس العملية، فنجد المنتصف يساوي 5، وبالتالي يساوي العدد الذي نبحث عنه.

هذه هي طريقة اشتغال اللوغارتم، نأتي الآن للحل:
(ما فهمت المقصود ب worse case و key step و Input size لأني ما درست هالشياء بالانجليزية ههه، بس البرنامج التالي يشتغل تمام، يمكن أكون جاوبت عالاسئلة من دون ما اعرف اسمها xDD







#include<stdio.h>

bool function_Name(int x[], int n, int value) // ندخل للدالة الجدول، وعدد مكوناته، العدد الذي نبحث عنه
{
int start=0, middle, end=n-1; // تعريف المتغيرات
bool found=false; // سنعرف دور هذا المتغير بعد قليل، يأخذ إما "صح" أم "خطأ" كقيمة له
while ((start <= end)&&(!found)) { //طالما نقطة بداية البحث أصغر من نقطة نهاية البحث، وطالما لم يتم ايجاد العنصر بعد
middle = (start + end)/2; //المنتصف يساوي نصف مجموع البداية والنهاية (تتغير النتيجة كل مرة طبعا
if (x[middle] > value) // إذا كان المنتصف أكبر من القيمة
end=middle-1; // ابحث في الجهة الصغرى، على اليسار
else if (x[middle] < value) //وإذا كان المنتصف أصغر من القيمة التي نبحث عنها
start= middle +1; // ابحث في الجهة الكبرى، على اليمين
else // وإذا لم يتحقق كلا الشرطين السابقين، فذلك يعني طبعا أن المنتصف يساوي القيمة التي نبحث عنها
{
return true; // "فإذاً اجعل الدالة تُرجع نتيجة "صح
found=true; // واعطي قيمة صح لهذا المتغير حتى يتوقف البحث عندهذه النقطة ولا يتواصل
}
}
if (!found) return false; // سبب وجود هذا في الخارج هو أنه لابد من التحقق أن البحث قد نجح، إن كان لا، فاجعل الدالة تُرجع قيمة خطأ
}


void main() //الدالة الرئيسية لتجريب الدالة التي كتبناها منذ قليل
{
int x[]={0,1,2,3,4,5,6,7,8,9}; //صنعنا جدولا ذو بعد واحد حتى نشتغل عليه

if (function_Name(x,10,12)) printf("Found"); // أدخلنا اسم الجدول، وعدد العناصر "10"، والعدد الذي نبحث عنه
else printf("Not Found\n"); //سنحصل طبعا على النتيجة الثانية، لأنه لا وجود ل 12 في الجدول
}




البرنامج طويل هههه، أنا حطيته كامل حتى يشتغل بمجرد نسخه ولصقةه، دون التعب في اضافة أي شيء آخر :)

أتمنى أن يكون الشرح مفهوما ^.^"

في أمان الله

[almazuoona]

يعطيك العافيه saeed2008aae ينفع تصير مدرس والله اني ما كنت فاهمه شي مش شرح البروفيسور الي حاطين لنا ياه....بس فهمت على شرحك :) شكراااااااااااااااااااااااااااااااااا جدا

[nonete]

Assignment #1 (15 Marks)
Data Structures & Algorithms – CSC 301

(a) Add a member function ReturnLastItem () to the UnsortedType ADT that returns the last element in the list. The function has the following prototype:
ItemType ReturnLastItem();
Preconditions: List is initialized and not empty.
Postconditions: List is unchanged.
(b) Add a member function GreaterThanItem () to the UnsortedType ADT that returns the number of elements which are greater than a given item. The given item is passed as a parameter to the function. The function has the following prototype:
int GreaterThanItem(ItemType givenItem);

(c) Write a recursive client function that prints the elements of a stack (linked implementation) in reverse order (from bottom to top). The function has the following specification:
void printStackReverse(StackType stack)
Function: Prints the elements of stack in reverse order (from bottom to top).
Precondirtion: Stack is not empty.
Postcondition: Stack is not changed.

Note: Assume that ItemType is defined as
typedef int ItemT





plz help me ya saeed2008uae in this homework le2ni ma fahma kif a7la plz plz

[MysteriousGirl]

LoOolzzz
we are realy so funny !! kollo sha3'al she7tah
:p

[almazuoona]

:| ya lhweeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.....wenk ya dr saied t3al shof w atfaraj

[nonete]

really l mafrood howa yekoon l dr o professor kaman 3la l explaination l ra23......


bs yekmlha ma3na o ye7kelna 3la haad l assigmnet plz

plz plz plz plz plz help...