Let's Learn it Together !

فى البداية اقرا المقال ده Recursion -- Part 1

احنا فى المرة الى فاتت اتعرضنا لموضوع الrecursionوعرفنا مع بعض يعنى ايه recursionوبنستخدمه امتى وليه وخدنا مثال عليه اللى هو الfactorial وعرفنا ان احنا ممكن نعمل البرنامج ب recursionوممكن من غيرها برضه.

وعرفنا برضه الrecursion بتتكون من ايه.
النهاردة ان شاء الله هنكمل مع بعض وناخد مثال تانى كدة نفهمه مع بعض ونشرحه بالتفصيل
قبل مانبدا لازم بس نكون عارفين شويه تعريفات كدة مهمه يعنى بخصوص موضوع ال recursion.
نبدا باول تعريــــــــــــــــــــــــــــــــــــــــــف......

• Direct Recursion:

A function is directly recursive if it contains an explicit call to itself.

يعنى ايه الكلام ده ؟ الى نفهمه من التعريف ده ان ال recursive funcion بتاعتنا نقدر نسميها direct لو هيا بتنده نفسها جوا الfuntion طيب تعالو ناخد مثال نفهم بيه احسن عندنا مثلا ال مثال ده ...

int foo(int x)

{

if (x <= 0)

return x;

else

return foo(x - 1);

}

هنا لاقينا ان الfunction بتاعتنا ندهت نفسها وهى جوه نفسها

تانى تعريف عندنا

• Indirect Recursion:

A function foo is indirectly recursive if it contains a call to another function which ultimately calls foo.

نقدر نقول على ال function الى عندنا انها Indirect Recursion لو لاقينا فى الfunction بتاعتنا جواها فى calling ل function تانية

int foo(int x)

{

if (x <= 0)

return x;

return bar(x);

}

int bar(int y)

{

return foo(y - 1);

}

هنا زى ماحنا شايفين فى ال 2 functions دول ان فى كل واحده جواها بتنادى على فانكشن تانيه
فى كمان تعريفين كدة انهردة نعرف بس اساميهم لكن مش هانخوض فيهم هانشرحهم ان شاء الله المرة الجايه وهما

• Tail Recursion
• Linear and Tree Recursion

طب تعالوا بقى ناخد مثال النهاردة ونفهمو مع بعض

المثال بتاع النهاردة حاجة اسمها Fibonacci seriesدى عبارة عن sequence بس ليها rule عشان نقدر نكونها يعنى مش اى ارقام وخلاص

عندنا فى ال sequence دى اول 10 ارقام منها هما دووول ومن خلالها نقدر نستنج القانون العام بتاعها

ال 10 ارقام اهم

0 1 1 2 3 5 8 13 21 34

الى انا ملونهم دول اول رقمين يعنى

fib[0] & fib[1]

ودول معروفين اساسا يعنى مش هانجيبهم لكن احنا هانبدا نجيب القانون عشان نجيب اللى بعد ال 1

طب اسيبكم كدة شويه تفكرو فى انكم تجيبو القانون من غير ماتبصو تحت لو مش عرفتوه بعد فترة ممكن تنزلة تبصوا عليه تحت انا كتبه يلا take your time
..........................

........................

......................

...................

...............

.........

.....

..

.

خلاص الوقت خلص نيجى بقى نفهم مع بعض

عندنا اول رقمين معروفين اللى هما 0 1 نيجى نركز شويه معلش استحملونى فى اللى بعد ال 1 نلاقيه 1 وبعد ال 1 نلاقيه 2 معنى كدة ايه....؟

خلاص انا هاقول مانا ادتكم فرصه فوق

معناها ان كل رقم = مجموع الرقمين الى قبليه يعنى عندنا اول رقمين 0 1 مجموعهم = 1

عندنا 1 1 مجموعهم 2 وهكذا .........اما نشوف مين الى فكر صح ؟؟ وجاب القانون من

غير مايبص تحت

طيب معنى كلامك ده ان ال

FIB -->Fibonacci

Fib(0) = 0

Fib(1) = 1

Fib(2) = Fib(1) + Fib(0) = 1

Fib(3) = Fib(2) + Fib(1) = 2

Fib(4) = Fib(3) + Fib(2) = 3

Fib(5) = Fib(4) + Fib(3) = 5

Fib(6) = Fib(5) + Fib(4) = 8

General rule:

Fib(n) = Fib(n-1) + Fib(n-2) for all n >=2

حاجة مهمة بقى
ممكن كل واحد قبل مايشوف الكود بتاع ال function دى يحاول يعمله هو بايده لو هو فهم المرة اللى فاتت واللى معرفش مش مشكله خالص يبص على الكود

int fib(int n) // n >= 0

{

if (n == 0)

return 0;

if (n == 1)

return 1;

return fib(n - 1) + fib(n - 2);

}

وده reference على النت

Definitions

Swapping variables is a very common operation used it tons of algorithms… like sorting. The most common and obvious technique is using a temporary variable to swap values between two variables:

Instead of writing a separate function for each data type, you could write a MACRO or templatize the function.

Swapping without using a temporary variable is an age old trick and there are a few ways to do this. You could use the basic arithmetic operations like +, -, /, *.

The technique involves storing the sum of variables in one of them and then extracting it back by subtracting the other number. There are different variants to this technique… instead of starting by storing the sum, you could store the difference, product or the quotient. The last two could lead you to round-off and integer division errors. However all of them have one fundamental flaw. Its in line 3, and the issue is that this could lead to an overflow error.

This is another technique the gets you around these issues; the XOR Swapping Technique.

This is an elegant technique and should work well with any primitive data type and you could write a simple MACRO like

Thanks to F.M.A.R. who sent me this article...

This is the pdf version of this article.

Hash tables

أحنا درسنا كذا طريقة عشان نعمل search علي أي element زي
linear search: و كان لازم نعدي علي كل element لحد ما نوصل للtarget بتاعنا و في ال worst case هياخدعدد n steps لو الarray حجمها n

binary search: بنوصل لل target يتاعنا بعد log(n) time لكن كان بيقابلنا مشكلة أن في ال adds/ removes ال array لازم كانت نفضل مترتبة فهياخد time n عشان نعمل shift لل elements

BST: و النوع دة كان بيحللنا المشكلة دي فكان ممكن نعمل search/ add/ remove in log(n) time

و كل الأنواع دي كل ما عدد ال elements تزيد بيزيد معاها وقت أو سرعة ال search
عشان كدة أحنا هنتعلم نوع جديد اسمه hashing

*************************

يعني إيه Hashing

بدل ما نعمل traverse علي الarray أو الtree و نضيع وقت عشان نوصل للelement اللي عايزينه, مجرد هنحسب مكان ال element في ال table و بكدة هنوصله في خطوة واحدة و مهما عدد الelements تزيد… وقت ال search/ add/ remove بيكون ثابت.

الصورة دي عبارة عن element X هيعدي علي function اسمها hash function هتحسبله مكانه في الtable اللي هنسميه hash table .


زي ما أحنا شايفين ال hash function اللي عندنا عبارة عن h(X) = X
يعني لو عندنا مثلا رقم 10 هنخزنه في arr[10]و لو عندنا رقم 999 هنخزنه في arr[999]و بكدة هنقدر نوصل لأي رقم في خطوة واحدة و بكل سهولة

لكن لو تلحظوا هتلاقوا أن الموضوع دة في عيب, إيه هو يا تري؟

لنفرض إننا عايزين نخزن رقمين اللي هما مثلا 1 & 998

فكدة ال 1 هنخزنها في [1] arr و ال 998 هنخزنها في arr[998]
يانهار أبيض! هنعمل array حجمها 999 عشان نخزن رقمين!مش هينفع, عارفين ليه؟
عشان ال memory من جبنا :D :P


طيب إزاي نعالج الموضوع دة؟
مجرد نغير ال hash function

إيه رأيكوا نخليها كدة :
h(X) = X mod 2 ----> ال 2 دي ال capacity

و كدة ال 1 & 999 هيتخزنه فين؟
ال1 : %2 = 1 1 -------> فهنخزنها في arr[1]
و ال998: 998%2 = 0 -------> فهنخزنها في arr[0]

و دمتم سالمين! :D
في الحقيقة مادمناش سالمين أوي يعني, عارفين ليه؟
عشان فيه عيب تاني, خدوا دقيقتين عشان تكتشفوه!
..... بعد دقيقتين:

إفرضوا أحنا عايزين نخزن رقمين 4 & 8
هيتخزنوا فين؟
ال4: 4%2 = 0 --------->فهنخزنها فيه arr[0]
ال8: 8%2 = 0 ---------> يا سلام باردو هنخزنها فيه arr[0]

طبعا مش هينفع نخزن رقمين في نفس المكان
و الحالة دي بنسميها collision

لكن ماتقلقوش لكل مشكلة حل و مشكلتنا فيها أكتر من حل زي:
linear probing -1
open- addressing -2
chaining -3

linear probing -1

هنعمل “circular” linear search (يعني لو وصلنا لنهاية الtable و لسة ما وجدناش مكان فاضي هنروح لأول ال table و نكمل بحث
) هيبدأ من المكان اللي حصل فيه collision و ينتهي أول ما يلاقي مكان فاضي و ال element اللي حصله collision هيتحط في المكان الفاضي دة.

open- addressing( jumping) -2


الطريقة دي شبه الlinear probing لكن بدل ما نعمل “circular” linear search كل ما يحصل collision هنعمل الآتي:
لو مثلا عايزين نضيف رقم 282 و ال 31= capacity
زي ما عرفنا هنحسب مكانه كدة:
h(282) = 282 % 31 = 3

طيب لو المكان 3 محجوز, هنضيف عليها 1²

3+²1 = 4

و لو المكان 4 محجوز نطرح 1² من ال 3

3-²1 = 2

و لو باردو محجوز نضيف 2² علي ال3

3+ 2² = 7

و لو المكان 7 محجوز نطرح 2² من ال 3

3-2² = 30 و هكذا لحد ما نلاقي المكان فاضي

يعنيI + 1², I - 1², I + 2², I - 2², I + 3², I - 3², I + 4², …

طيب ندي مثال عشان الصورة توضح:

عايزين نضيف 620, 64, 128, 467, 777, 35, 127& 282

H (620) = 620 % 31 = 0

H (64) = 64 % 31 = 2

H (128) = 128 % 31 = 4

H (467) = 467 % 31 = 2 --> 2+ 1= 3

H (777) = 777 % 31 = 2--> 2+1 =3 -->2-1 = 1

H (35) = 35 % 31 = 4--> 4+1 = 5

H (127) = 127 % 31 = 3--> 3+1 = 4--> 3-1 = 2--> 3+ 4 = 7

H (282) = 282 % 31 = 3--> 3+1 = 4--> 3-1 = 2--> 3+4 = 7--> 3-4 = 30

اللي مستغرب من أن 3-4 = 30 عشان ناقص دي يعني نقص من ال index يعني بدل ما كان ال element هيتحط في arr[3] هنحطه دلوقتي في arr[30]

Chaining -3

و الطريقة دي بيكون ال hash table عبارة عن array of linked lists

هكذا:

و ال hash function في حالة ال strings هتكون كدة:

H(name) = name[0] – ‘a’

الASCII code بتاع ال a = 97 و ال b = 98 و … فالكلمة اللي هتبدأ بحرف ال a هنحطها في arr[0] و اللي هتبدأ بحرف ال b هنحطها في arr[1] و هكذا...

*****************************

طيب بعد ما عرفنا يعني إيه hashing و المشاكل اللي قبلتنا و حلولها هنعرف إزاي نعمل

Search:

مش دايما الواحد بيعمل search عشان يتأكد أن ال element موجود, عادة عشان نحصل علي مزيد من المعلومات, زي في القاموس بنبحث علي الكلمة عشان نعرف معناها, عشان كدة عادة ال Data مقسومة لجزئين: Key & value

ال key هو الجزء اللي بنحدد من خلاله ال location

و فيه مثال تاني أما ندوس double click علي file و بكدة ال file path هو ال key و المحتوي ال file هو ال value

فأحنا دلوقتي هنعمل struct فيها ال key & value

و نستخدم ال hash function عشان نجيب مكان ال element لو المكان دة فيه ال element المطلوب يبقي ال search تم بنجاح و هنرجعله ال struct كلها و لو لأ نبدأ نعمل “circular” linear search لحد ما نلاقي المطلوب أو نرجع للمكان اللي بدأنا منه و دة معناه أن ال element مش موجود في ال hash table

Insert:

هناخد ال struct من ال user و نستخدم ال hash function عشان نجيب مكان ال element اللي هيتحط فيه لو المكان دة فاضي يبقي هنحط ال struct كلها في المكان دة لو لأ نبدأ نعمل “circular” linear search علي أول مكان فاضي يقابلنا.

بعد ما تكتب ال code بنفسك, هيكون مسموحلك نبص علي الcode

دة

لو عايز PDF file للكلام دة نزله من هنا

References:

ADTs, Data Structures, and Problem Solving with C++

Video# 7--> MIT algos … download it from here