برنامج جافا لحذف node من شجرة بحث ثنائية.

 import java.util.*;

class BinaryTree {

int data;

BinaryTree left, right;

BinaryTree(int x) {

this.left=this.right=null; data=x;

}

public void insert( int i ) {

if (i <= data) {

if (left != null) left.insert(i);

else left = new BinaryTree( i );

}

else if (i >= data) {

if (right != null) right.insert(i);

else right = new BinaryTree( i );

}

}

public void inOrder(BinaryTree tree) {

if(tree!=null) {

inOrder(tree.left);

System.out.print(tree.data+" ");

inOrder(tree.right); }

}

public static int min(BinaryTree node) {

if (node.left == null) {

return node.data;

}

return min(node.left);

}

public static BinaryTree deleteNodeInBST(BinaryTree node, int data) {

if (null == node) {

System.out.println("Element is not in binary search tree");

return null;

}

if (data < node.data) {

node.left = deleteNodeInBST(node.left, data);

} else if (data > node.data) {

node.right = deleteNodeInBST(node.right, data);

} else { // case for equality

// Now we see that whether we can directly delete the node

if (node.left != null && node.right != null) {

int minInRightSubTree = min(node.right);

node.data = minInRightSubTree;

node.right = deleteNodeInBST(node.right, minInRightSubTree);

} else { // either one child or leaf node

if (node.left == null && node.right == null) {

node = null;

} else {// one child case

BinaryTree deleteNode = node;

node = (node.left != null) ? (node.left) : (node.right);

deleteNode = null;

}

}

}

return node;

}

public static void main (String args[]) {

char choice='y'; int n, d;

Scanner sc = new Scanner(System.in);

System.out.print("Enter Root node value = ");

n=sc.nextInt();

System.out.print("Enter ur Choice(y/n) = ");

choice=sc.next().charAt(0); BinaryTree ob=new BinaryTree(n);

while (choice == 'y') {

System.out.print("Enter node value = ");

n=sc.nextInt(); ob.insert(n);

System.out.print("Enter ur Choice(y/n) = ");

choice=sc.next().charAt(0);

}

System.out.print("\nInorder Traversal = "); ob.inOrder(ob);

System.out.print("\nEnter the Node to delete = ");

d = sc.nextInt(); ob.deleteNodeInBST(ob, d);

System.out.print("\n After deleting the Node "+d+" = "); ob.inOrder(ob);

}

}

Output:

Inorder Traversal = 2 10 16 50 110

Enter the Node to delete = 16

After deleting the Node 16 = 2 10 50 110

برنامج جافا لتنفيذ اجتياز INORDER و PREORDER و POSTORDER لشجرة بحث ثنائية.

class Node

{

int key;

Node left, right;

public Node(int item)

{

key = item;

left = right = null;

}

}

public class BinaryTree1

{

Node root;

BinaryTree1()

{

root = null;

}

void printPostorder(Node node)

{

if (node == null)

return;

printPostorder(node.left);

printPostorder(node.right);

System.out.print(node.key + " ");

}

void printInorder(Node node)

{

if (node == null)

return;

printInorder(node.left);

System.out.print(node.key + " ");

printInorder(node.right);

}

public void printPreorder(Node node)

{

if (node == null)

return;

System.out.print(node.key + " ");

printPreorder(node.left);

printPreorder(node.right);

}

void printPostorder() { printPostorder(root); }

void printInorder() { printInorder(root); }

void printPreorder() { printPreorder(root); }

public static void main(String[] args)

{

BinaryTree1 tree = new BinaryTree1();

tree.root = new Node(1);

tree.root.left = new Node(2);

tree.root.right = new Node(3);

tree.root.left.left = new Node(4);

tree.root.left.right = new Node(5);

System.out.println("Preorder traversal of binary tree is ");

tree.printPreorder();

System.out.println("\nInorder traversal of binary tree is ");

tree.printInorder();

System.out.println("\nPostorder traversal of binary tree is ");

tree.printPostorder();

}

}

Output

Preorder traversal of binary tree is

1 2 4 5 3

Inorder traversal of binary tree is

4 2 5 1 3

Postorder traversal of binary tree is

4 5 2 3 1 

الخوارزميات وهياكل البيانات: اشجار البيانات الثنائية binary trees

 الأشجار

إنه رسم بياني متصل غير دوري حيث تحتوي كل عقدة على 7 = 0 أو أكثر من العقد الفرعية وعقدة رئيسية واحدة على الأكثر. العقدة عبارة عن هيكل يحتوي على قيمة وعناوين من اليمين واليسار و child. تحتوي كل عقدة في الشجرة على صفر أو أكثر من العقد الفرعية الموجودة تحتها في الشجرة. العقدة التي لديها child تسمى العقدة child's parent . تحتوي العقدة على parent واحد على الأكثر.  العقدة الداخلية هي أي عقدة في شجرة تحتوي على عقد فرعية. وبالمثل ، فإن العقدة الخارجية (تُعرف أيضًا باسم العقدة الخارجية أو العقدة الطرفية ) ، هي أي عقدة لا تحتوي على عقد فرعية. تسمى العقدة العلوية في الشجرة عقدة الجذر. أمثلة على انواع اشجار البيانات

ملاحظة من المترجم - يصعب احيانا الترجمة الحرفية لعبض المصطلحات ولكن رأس الشجرة يسمى parent والافرع المندرجة تحته تسمى children وnodes اطلقت عليها في المقالة عقد

ملاحظة 2 : سميت بالشجرة لان تفرع البيانات في هيكلة البيانات هذه ياخذ شكل التفرع الشجري 

يمكن تعريف الشجرة بشكل متكرر على النحو التالي:

1. الهيكل الفارغ هو شجرة فارغة 

2. إذا كانت t1 ، t2 ، ... ، tk عبارة عن أشجار مفككة ، فإن البنية التي يكون لجذرها أطفال

إذا كانت t1 ، t2 ، ... ، tk عبارة عن أشجار مفككة ، فإن البنية التي يكون لجذرها children  t1 ، t2 ، ... ، tk هي أيضًا شجرة

ويرمز للشجرة ب t متبوعة بعدد اذا كان يوجد لدينا اكثر من شجرة للتحديدها كما في الصورة السابقة

3. فقط الهياكل التي تم إنشاؤها بواسطة القاعدتين 1 و 2 هي الأشجار.

المسار: يجب أن تكون كل عقدة قابلة للوصول من الجذر من خلال سلسلة فريدة من الأقواس.

طول المسار: عدد الأقواس في المسار.

المستوى: مستوى العقدة هو طول المسار من الجذر إلى العقدة زائد 1 ، وهو عدد العقد في المسار.

الارتفاع: هو الحد الأقصى لمستوى العقدة في الشجرة.

بناء ع الصورة السابقة 

الارتفاع = المستوى الأقصى = 4

طول المسار = 3

المستوى = 3 + 1 = 4

هذه لا تعتبر شجرة بيانات

يوجد مسار فريد بين أي عقدتين في الشجرة. الشجرة ليس لها دورات. بمعنى لا تاخذ شكل حلقي كما في الصورة السابقة نلاحظ انها تاخذ شكل حلقي 

ضع في اعتبارك قائمة مرتبطة بالعناصر n. لتحديد موقع عنصر ، يجب أن يبدأ البحث من بداية القائمة ويجب فحص القائمة حتى يتم العثور على العنصر أو الوصول إلى نهاية القائمة. (أفضل حالة: O (1) ، أسوأ حالة: O (n))

الشجرة المنظمة

شجرة منظمة: شجرة يتم فيها تخزين جميع العناصر وفقًا لبعض معايير الترتيب المحددة مسبقًا ، إذا تم تخزين جميع العناصر في شجرة منظمة ، فيمكن تقليل عدد الاختبارات.

الأشجار الثنائية

الشجرة الثنائية هي بنية بيانات شجرية تحتوي كل عقدة فيها على عقدتين فرعيتين على الأكثر ، وعادة ما يتم تمييزهما على أنهما "يسار" و "يمين".

جرة ثنائية كاملة: وهي شجرة ثنائية تحتوي على جميع العقد nodes على جميع المستويات باستثناء اخرها يكون فيها 2children . تحتوي جميع العقد غير الطرفية علىchildrens ، وجميع الأوراق تكون في نفس المستوى.

سيكون هناك 20 عقدة في المستوى 1 (الجذر) ، و 21 عقدة في المستوى 2 ، وبشكل عام ، 2i في المستوى i + 1.

شجرة القرار: هي شجرة ثنائية تحتوي فيها جميع العقد على صفر أو فرعين غير فارغين.

شجرة البحث الثنائية (BST)

إنها بنية بيانات شجرة ثنائية لها الخصائص التالية:

• لا يكتسب الذنب الأيسر للعقدة سوى العقد ذات المفاتيح الأقل من مفتاح العقدة. • الشجرة الفرعية اليمنى للعقدة تحتوي فقط على عقد ذات مفاتيح أكبر من مفتاح العقدة. • يجب أن تكون كل من الأشجار الفرعية اليمنى واليسرى عبارة عن أشجار بحث ثنائية.

قم بإنشاء شجرة بحث ثنائية (BST) ، مع إعطاء التسلسل التالي : 

100، 90، 110، 80، 95، 120، 50، 130، 65، 150، 165، 25، 45، 60، 145 التسلسل العنصر الأول في التسلسل = جذر BST

إنها بنية بيانات شجرة ثنائية لها الخصائص التالية:

• الشجرة الفرعية اليسرى للعقدة تحتوي فقط على عقد ذات مفاتيح أقل من مفتاح العقدة. • الشجرة الفرعية اليمنى للعقدة تحتوي فقط على عقد ذات مفاتيح أكبر من مفتاح العقدة. • يجب أن تكون كل من الأشجار الفرعية اليمنى واليسرى عبارة عن أشجار بحث ثنائية.

 شجرة البحث الثنائية بشكل عام 

في التطبيق الجديد ، العقدة هي تمثيل لفئة مكونة من حقل معلومات وحقلين مرجعيين. يتم استخدام هذه العقدة وتشغيلها بواسطة طرق في فئة أخرى تختص بالشجرة ككل

public class IntBSTNode {

 protected int key; 

protected IntBSTNode left, right;

 public IntBSTNode() {

 left = right = null; 

}

public IntBSTNode(int el) {

 this(el,null,null); 

}

public IntBSTNode(int el, IntBSTNode lt, IntBSTNode rt) {

 key = el; left = It; right - rt; 

}

 public void visit() {

 System.out.print(key + " "); 

}

}

لكل عقدة ، قارن المفتاح الذي سيتم تحديد موقعه بالقيمة المخزنة في العقدة المشار إليها حاليًا.

المفتاح أقل من القيمة ، انتقل إذا إلى الشجرة الفرعية اليسرى وحاول مرة أخرى.

إذا كانت أكبر من تلك القيمة ، فجرب الشجرة الفرعية الصحيحة.

إذا كان هو نفسه يمكن إيقاف البحث.

يمكن إلغاء البحث ، إذا لم يكن هناك طريق للذهاب ، يعني أن المفتاح ليس في الشجرة

دالة البحث في شجرة البحث الثنائية:

يقاس مدى تعقيد البحث بعدد المقارنات التي أجريت أثناء عملية البحث.

يعتمد هذا الرقم على عدد العقد التي تمت مواجهتها على المسار الفريد المؤدي من الجذر إلى العقدة التي يتم البحث عنها.

التعقيد هو طول المسار المؤدي إلى هذه العقدة زائد 1.

يعتمد ذلك على شكل الشجرة وموضع العقدة في الشجرة.

تحتوي الشجرة على العقد من 1 إلى n. إذا كان i هو الجذر ، فإن شجرته الفرعية اليسرى بها عقد i ‐ 1 ، وشجرته الفرعية اليمنى بها عقد n ‐ i. إذا كان المسار ‐ 1 والمسار n ‐ i هما مساران متوسطان في هذه الأشجار الفرعية ، فإن متوسط مسار هذه الشجرة هو:

يمكن أن يكون جذر الشجرة أي رقم i ، 1 <= i <= n لذلك ، يتم الحصول على متوسط مسار الشجرة المتوسطة عن طريق حساب متوسط جميع قيم المسار n (i) على جميع قيم i.

اجتياز الشجرة

اجتياز الشجرة هو عملية زيارة كل عقدة في الشجرة مرة واحدة بالضبط.

اتساع ، أول اجتياز .BREADTH‐FIRST TRAVERSAL.

اتساع - أول اجتياز هو زيارة كل عقدة بدءاً من الجذر والانتقال إلى أسفل مستوى بمستوى ، وزيارة العقد على كل مستوى من اليسار إلى اليمين.

 

تسلسل اجتياز النطاق الأول:

13 ، 10 ، 25 ، 2 ، 12 ، 20 ، 31 ، 29

تنفيذ اتساع ‐ اجتياز الأول

يكون واضحًا تمامًا عند استخدام قائمة انتظار.

بعد زيارة العقدة ، يتم وضع عناصرها الفرعية ، إن وجدت ، في نهاية قائمة الانتظار ، وتتم زيارة العقدة الموجودة في بداية قائمة الانتظار.

ملاحظة: enqueue تعني إدراج عنصر في قائمة الانتظار dequeue يعني حذف عنصر من قائمة الانتظار

عمق الترحيل الأولي DEPTH‐FIRST TRAVERSAL. 

يتقدم قدر الإمكان إلى اليسار (أو اليمين) ، ثم يعود لأعلى حتى أول مفترق طرق ، ويذهب خطوة واحدة إلى اليمين (أو اليسار) ، ومرة أخرى قدر الإمكان إلى اليسار (أو اليمين). كرر هذه العملية حتى تتم زيارة جميع العقد.

هناك ثلاث مهام مهمة في هذا النوع من الاجتياز:

V: زيارة العقدة

L: اجتياز الشجرة الفرعية اليسرى

R: اجتياز الشجرة الفرعية اليمنى

يحدث الاجتياز المنظم إذا تم تنفيذ هذه المهام بنفس الترتيب لكل عقدة. إذن ، هناك ست عمليات اجتياز محتملة:

VLR ، VRL ، LVR ، RVL ، LRV ، RLV

VLR: 13,10,2,12,25,20,31,29

VRL: 13 25,31,29,20,10,12,2

LVR: 2,10,12,13,20,25,29,31

RVL: 31,29,25,20,13,12,10,2

LRV: 2,12,10,20,29,31,25,13

RLV: 29,31,20,25,12,2,10,13

افترض أن الحركة دائمًا من اليسار إلى اليمين ، إذن هناك ثلاث عمليات اجتياز قياسية:

VLR: اجتياز الشجرة (الثنائي) للطلب المسبق

LVR: اجتياز الشجرة في الترتيب

LRV: اجتياز الشجرة بعد الطلب

الإدراج

 إذا كانت قيمة العنصر الجديد مساوية لقيمة العقدة الحالية ، فلا تقم بأي إجراء.

 إذا كانت قيمة العنصر الجديد أقل من قيمة العقدة الحالية ، فانتقل إلى الشجرة الفرعية اليسرى (child الأيسر) للعقدة. إذا كانت القيمة خالية ، فقم بإدراج العقدة child أيسر للـ parent .

 إذا كانت قيمة العنصر الجديد أكبر من قيمة العقدة الحالية ، فانتقل إلى الشجرة الفرعية اليمنى (child الأيمن) للعقدة. إذا كانت القيمة خالية ، فقم بإدراج العقدة child أيسر للparent.

الحذف :

هناك ثلاث حالات يجب أخذها في الاعتبار أثناء حذف عقدة من BST: • العقدة الطرفية: تم تعيين المرجع المناسب للعقدة parent على "فارغ" والمساحة التي تشغلها العقدة المحذوفة يطالب بها جامع البيانات المهملة لاحقًا

عقدة بها child واحد: تتم إعادة تعيين مرجع الأصل إلى العقدة للإشارة إلى فرع العقدة. يتم رفع child العقدة بمقدار مستوى واحد

عقدة بها 2children: في هذه الحالة ، لا يمكن إجراء عملية من خطوة واحدة لأن المؤشر الأيمن أو الأيسر للparent’s لا يمكن أن يشير إلى كلا 2children في نفس الوقت. لذلك يمكن القيام بذلك عن طريق الحذف عن طريق الدمج أو الحذف عن طريق النسخ

الحذف عن طريق الدمج

• يتكون جذر الشجرة الفرعية اليسرى كجذر الشجرة

• يتكون جذر الشجرة الفرعية اليمنى كجذر الشجرة

الحذف عن طريق النسخ

• انسخ مفتاح الحد الأدنى في الشجرة الفرعية اليمنى لـ x إلى العقدة x ، ثم احذف العقدة باستخدام هذا المفتاح الأدنى

انسخ مفتاح الحد الأقصى في الشجرة الفرعية اليسرى لـ x إلى العقدة x ، ثم احذف العقدة باستخدام هذا المفتاح الأقصى.

تحليل التعقيد - شجرة ثنائية:

• البحث: للبحث عن عنصر 2 ، علينا اجتياز جميع العناصر (بافتراض أننا نقوم باجتياز النطاق الأول). لذلك ، فإن البحث في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n).

• الإدراج: لإدراج العنصر كـchild أيسر لـ 2 ، علينا اجتياز جميع العناصر. لذلك ، فإن الإدراج في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n).

• الحذف: لحذف العنصر 2 ، علينا اجتياز جميع العناصر للعثور على 2 (بافتراض أننا نقوم بعملية اجتياز العرض أولاً). لذلك ، فإن الحذف في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n).

• البحث: للبحث عن العنصر 1 ، علينا اجتياز جميع العناصر. لذلك ، فإن البحث في شجرة البحث الثنائي لديه أسوأ تعقيد للحالة O (n). بشكل عام ، يكون تعقيد الوقت هو O (h) حيث h هو ارتفاع BST.

• الإدراج: لإدخال العنصر 0 ، يجب إدراجه باعتباره تابعًا يسارًا للرقم 1. لذلك ، نحتاج إلى اجتياز جميع العناصر لإدخال 0 الذي يحتوي على أسوأ حالة من التعقيد O (n). بشكل عام ، يكون الوقت المعقد هو O (h).

• الحذف: لحذف العنصر 1 ، يتعين علينا اجتياز جميع العناصر للعثور عليها. لذلك ، فإن الحذف في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n). بشكل عام ، يكون الوقت المعقد هو O (h).

AVL TREES (ADEL’SON ‐ VEL’SKILL & LANDIS)

شجرة AVL (تسمى في الأصل الشجرة المسموح بها) هي شجرة يختلف فيها ارتفاع الشجرة الفرعية اليمنى واليسرى لكل عقدة بمقدار واحد على الأكثر

بالنسبة لشجرة AVL ، يجب أن تكون جميع عوامل التوازن +1 أو 0 أو -1.

• الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى هما شجرتا AVL

• يُقال أن العقدة  مرتفعة إذا كانت الشجرة الفرعية اليسرى أعلى ارتفاعًا

يمين ‐ مرتفع إذا كانت الشجرة الفرعية اليمنى متساوية في الارتفاع إذا كانت ارتفاعات LST و RST متساوية

موازنة شجرة AVL

بعد إدخال (أ) 60 ؛ (ب) 50 ؛ و (ج) 20 في شجرة بحث ثنائية فارغة في البداية ، فإن الشجرة تصبح غير متوازنة ؛ د) تقوم شجرة AVL المقابلة بتدوير عقدها لاستعادة التوازن.

أ) إضافة 80 إلى شجرة في الصورة السابقة (د) لا يغير توازن الشجرة ؛ (ب) إضافة 90 لاحقًا تجعل الشجرة غير متوازنة ؛ (ج) الدوران الأيسر يعيد التوازن.

تحليل التعقيد - شجرة AVL:

• البحث: للبحث عن العنصر 1 ، علينا اجتياز العناصر (بالترتيب 5 ، 4 ، 1) = 3 = log2n. لذلك ، فإن البحث في شجرة AVL لديه أسوأ حالة تعقيد لـ O (log2n).

• الإدراج: لإدخال العنصر 12 ، يجب إدراجه كعنصر تابع لليمين 9. لذلك ، نحتاج إلى اجتياز العناصر (بالترتيب 5 ، 7 ، 9) لإدخال 12 الذي يحتوي على أسوأ حالة تعقيد لـ O (log2n).

• الحذف: لحذف العنصر 9 ، علينا اجتياز العناصر لإيجاد 9 (بالترتيب 5 ، 7 ، 9). لذلك ، الحذف في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (log2n).

HEAPS

نوع معين من الشجرة الثنائية ، يسمى heaps ، له الخصائص التالية:

• لا تقل قيمة كل عقدة عن القيم المخزنة في كل من فروعها.

• الشجرة متوازنة تمامًا ، والأوراق في المستوى الأخير كلها في أقصى اليسار.

• كل شجرة فرعية هي كومة. يوجد نوعان من الأكوام: Minheap: قيمة كل عقدة أقل من قيمة فروعها او children.، أي الجذر يحتوي على أصغر عنصر Maxheap: قيمة كل عقدة أكبر من قيمة فروعها او كما يطلق عليها children. أي الجذر يحتوي على أكبر عنصر

الشكل أ كلها أكوام ، والشكل ب ينتهك الخاصية الأولى ، والشكل ج ينتهك الخاصية الثانية.

إدراج عنصر في A MIN HEAP

• أدخل العنصر الجديد في الموضع التالي أسفل الكومة.

• بينما العنصر الجديد ليس في الجذر والعنصر الجديد أصغر من العنصر الأصل

• قم بتبديل العنصر الجديد بأصله ، ونقل العنصر الجديد لأعلى

إزالة عنصر من HEAP

قم بإزالة العنصر في العقدة الجذرية عن طريق استبداله بالعنصر الأخير في الكومة (LIH).

• في حين أن العنصر LIH لديه children و LIH أكبر children

• قم بتبديل LIH بchildren الأصغر ، مع تحريك LIH أسفل الكومة.

تحليل التعقيد - الكومة:

• الإدراج: يعتمد عدد العمليات المطلوبة فقط على عدد المستويات التي يجب أن يرتفعها العنصر الجديد لتلبية خاصية الكومة.

  وبالتالي ، فإن عملية الإدراج لها تعقيد زمني أسوأ حالة من O (log n). بالنسبة إلى كومة عشوائية ، ولإدخالات متكررة ، فإن عملية الإدراج لها متوسط تعقيد الحالة O (1).

• الاستخراج: في أسوأ الحالات ، يجب تبديل الجذر الجديد مع فرعه في كل مستوى حتى يصل إلى المستوى السفلي من الكومة ، مما يعني أن عملية الحذف لها تعقيد زمني بالنسبة لارتفاع الشجرة ، أو O (log n).

• البحث: البحث عن عنصر عشوائي يستغرق O (n) من الوقت. يمكن تقليل هذا إلى وقت O (1) المغلق إذا كان لدينا جدول تجزئة يعين عناصر كومة لمؤشرات الكومة أو مؤشرات العناصر.

ترجمة فيصل عسيري لصالح مدونة فاب
المرجع :
Adam Drozdek, Data Structures and Algorithms in Java, 4th edition, Cengage Learning Asia, 2013

برنامج جافا لشرح استخدام التكرار لإيجاد حل لمشكلة رقم ما من تحركات الملكات في طاولة الشطرنج .java Program to demonstrate the use of recursion to find the solution for n queens problem .

 

import java.util.*;

public class Queens {

public static boolean isConsistent(int[] q, int n) {

for (int i = 0; i < n; i++) {

if (q[i] == q[n]) return false; // same column

if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal

if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal

}

return true;

}

public static void printQueens(int[] q) {

int N = q.length;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

if (q[i] == j) System.out.print("Q ");

else System.out.print("* ");

}

System.out.println();

}

System.out.println();

}

public static void enumerate(int N) {

int[] a = new int[N];

enumerate(a, 0);

}

public static void enumerate(int[] q, int n) {

int N = q.length;

if (n == N) printQueens(q);

else {

for (int i = 0; i < N; i++) {

q[n] = i;

if (isConsistent(q, n)) enumerate(q, n+1);

}

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N;

System.out.print("Enter number of queens = ");

N = sc.nextInt();

enumerate(N);

}

}

Output

Enter number of queens = 4

* Q * *

* * * Q

Q * * *

* * Q *

* * Q *

Q * * *

* * * Q

* Q * *

برنامج جافا لتوضيح استخدام التكرار لعرض فيبوناتشي لرقم معين. recursion to display the Fibonacci sun of a given. number. java code

 import java.util.*;

class Fibona {

int num;

Scanner sc = new Scanner(System.in);

public void read() {

System.out.print("Enter a Number: ");

num = sc.nextInt();

}

public long fibonacci(int n) {

if(n<2) //basis part

return n;

return fibonacci(n-1) + fibonacci(n-2); //recursive part

}

public static void main(String args[]) {

Fibona f=new Fibona();

f.read();

long result=f.fibonacci(f.num);

System.out.println("The Fibonacci SUM is: "+result);

}

}

Output

Enter a Number: 7

The Fibonacci SUM is: 13

الخوارزميات وهياكل البيانات : الركيرشن (دالة التكرار)

الخوارزميات وهياكل البيانات
مقدمة في دوال التكرار

ما هي البيانات؟

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

هياكل البيانات

بنية البيانات هي طريقة لتنظيم كل عنصر في البيانات الذي لا يأخذ فقط في الاعتبار العنصر المخزن ولكن أيضًا علاقتها ببعضها البعض.

يمكن البحث في أي مؤسسة لمجموعة من السجلات أو معالجتها بأي ترتيب أو تعديلها.

يمكن أن يؤدي اختيار بنية البيانات والخوارزمية إلى إحداث فرق بين البرنامج الذي يتم تشغيله في بضع ثوانٍ أو عدة أيام.

الكفاءة: يُقال إن الحل يكون فعالًا إذا كان يحل المشكلة ضمن قيود موارده (المكان والزمان)

حدد هيكل البيانات كما يلي:

* تحليل المشكلة لتحديد قيود الموارد التي يجب أن يفي بها الحل.

* تحديد العمليات الأساسية التي يجب دعمها.

حدد قيود الموارد لكل عملية.

* حدد هيكل البيانات الذي يلبي هذه المتطلبات على أفضل وجه.

تعريف الريكيرشن.

تُعرف الدالة التي تستدعي نفسها بالريكيرشن.

  وهي طريقة لتعريف الدوال حيث يتم تطبيق الدالة التي يتم تعريفها ضمن تعريفها الخاص ، فهي تقنية خوارزمية حيث تقوم الدالة  من أجل إنجاز مهمة ، باستدعاء نفسها مع جزء من المهمة.

تعرض الدالة سلوكًا تكراريا و يمكن تعريفها بخاصيتين أو قاعدتين

1. حالة أساسية بسيطة (أو حالات) 

2. مجموعة من القواعد التي تقلل جميع الحالات الأخرى تجاه الحالة الأساسية و تسمى الحالة التكرارية.

تتكون الحالة التكرارية من ثلاثة مكونات:

(أ)تقسّم المشكلة إلى جزء واحد أو أكثر أبسط أو أصغر من المشاكل ،

(ب) استدعاء الدالة (بشكل متكرر) على كل جزء ، 

(ج) الجمع بين حلول والأجزاء في حل المشكلة.

مثال 1 : العامل " عملية رياضية لحساب عاملي عدد معين او كما تسمى بالانجليزية factorial

سنبدأ بمثال العامل ، والمشار إليه "!".

3! = 3* 2* 1

5! = 5* 4 *3 *2 *1

X! = X *(X − 1)* (X − 2)* (X − 3) *...* 3* 2* 1

0! = 1

فكيف نحسب ذلك !؟

هذه دالة تكرارية تقوم بذلك:

n!=n*(n − 1)! for n> 1, و n! = 1 for n ≤ 1. ie

• عامل (0) هو 1 [في الحالة الأساسية]

• عامل (1) هو 1 [في الحالة الأساسية]

نرمز بn لجميع الأعداد الصحيحة n> 1:  * عاملي العدد (n ‐ 1) [تعريف متكرر]

ويتم تحويله لبرنامج جافا كما يلي 

int factorial(int n)

{

if (n <= 1)

return 1;

else

return n * factorial(n‐1);

}

مثال 2: متتالية فيبوناتشي Fibonacci 

ليوناردو فيبوناتشي - عالم رياضيات

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

الاختلاف الوحيد هو القاعدة التي تخص متوالية فيبوناتشي

is fib(n)= fib(n − 1) + fib(n − 2) for n> 1, and fib(n) = 1 for n > 1.

يظهر هذا النوع من التعريف التكراري "الركيرشن" بشكل متكرر في الرياضيات ، ويسمى أيضًا علاقة التكرار.

• فيبوناتشي (0) تساوي 0 [في الحالة الأساسية]

• فيبوناتشي (1) هي 1 [في الحالة الأساسية]

نرمز لجميع الأعداد الصحيحة n> 1

 n> 1: Fib (n) is (Fib (n ‐ 1) + Fib (n ‐ 2)) [متكررتعريف]

ويتم تمثيله بلغة الجافا كما يلي : 

int fib(int n)

{

if (n == 0)

return 0;

elseif (n == 1)

return 1;

else

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

}

مثال 3: دالة القوى او الاسس

تعد دالة القوى أيضًا مثالًا على التكرار "recursion". قاعدة دالة القوة هي القوة (x, n) =

x * power(x , n‐1) for n> 0, and power(x , n ) = 1 for n = 0.

int power(double x, int n)

{

if (n == 0)

return 1;

else

return x * power(x,n‐1);

}

طرق الاستدعاء وتنفيذ التكرار "الركيرشن " 

سجل التنشيط

يتكون مكدس الاستدعاء "stack" من إطارات مكدسة (تسمى أيضًا سجلات التنشيط أو إطارات التنشيط).

هذه هياكل بيانات تعتمد على الآلة تحتوي على معلومات حالة الروتين الفرعي. 

يتوافق كل إطار مكدس مع استدعاء لإجراء فرعي لم ينته بعد ويقوم بالعودة.

 إطار المكدس الموجود أعلى المكدس مخصص للإجراء العمليات المنفذه حاليًا.

 يشتمل إطار المكدس عادةً على العناصر التالية على الأقل:

• رابط ديناميكي لسجل تنشيط المستدعيات

• عنوان المرسل إلى المستدعي الروتيني

• قيمة الإرجاع (إن وجدت)

مخطط الكتلة : 

تفصيل استدعاء التكرار

• ضع في اعتبارك مثال العامل المستخدم سابقًا

int factorial(int n) {

if(n == 0) { return 1; }

else { return n * factorial(n‐1); }

}

فكر الآن في الكود التالي لـ  دالة main ()

void main() {

int f = factorial(3);

System.out.print(f);

}

طريقة عمل استدعاء التكرار

تحليل التعقيد:

هو تحليل لحساب مقدار الوقت والمساحة التي ستستغرقها الخوارزمية / الدالة لإكمال العمليات من خلال حساب عدد العمليات الإجمالية.

  يُشار إليه عادةً بـ Θ 

دعنا نقول الدالة T (n) تشير إلى عدد العمليات الأولية التي يؤديها استدعاء الوظيفة Sum (n).

int Sum(n int) {

if n == 1 {

return 1

}

return n + Sum(n-1)

}

نحدد خاصيتين لـ T (n).

نظرًا لأن Sum (1) يتم حسابه باستخدام عدد ثابت من الدوال k1 ، T (1) = k1.

إذا كانت n> 1 ، فستؤدي الدالة عددًا ثابتًا من العمليات k2 ، وبالإضافة إلى ذلك ، ستقوم بإجراء استدعاء متكرر

لمجموع (n-1). سيؤدي هذا الاستدعاء المتكرر عمليات T (n-1).و في المجموع  نحصل على T (n) = k2 + T (n-1).

إذا كنا نبحث فقط عن تقدير مقارب لتعقيد الوقت ، فلا نحتاج إلى تحديد القيم الفعلية للثابتين k1 و k2. بدلاً من ذلك ، ندع k1 = k2 = 1 لإيجاد التعقيد الزمني لدالة الجمع Sum ، يمكن بعد ذلك تقليلها إلى حل علاقة التكرار

T(1) = 1

T(n) = 1 + T(n-1), حيث n > 1.

من خلال تطبيق هذه العلاقات بشكل متكرر ، يمكننا حساب T (n) لأي رقم موجب n.

T(n) = 1 + T(n-1)

= 1 + (1 + T(n-2))

= 2 + T(n-2)

=2 + (1 + T(n-3))

= 3 + T(n-3) = …

=k + T(n-k) = …

= n - 1 + T(1)

= n - 1 + 1= Θ(n)

   تكرار الذيل. او تيل ريكيرشن "TAIL RECURSION."

يتميز تكرار الذيل باستخدام استدعاء تكراري واحد فقط

في نهاية تنفيذ الدالة. الاستدعاء التكراري ليس فقط العبارة الأخيرة في الكود ، ولكن لا توجد فيه اسادعاءات تكراريه سابقة ، مباشرة أو غير مباشرة 

مثال : 

Example:

void tail (int i)

{

if (i>0)

{

System.ou t.p rintln(i);

tail(i‐1);

}

}

تكرار الذيل هو مجرد حلقة  او لوب "loop" ويمكن استبداله بسهولة بمثل هذا الكود.

void IterativeEquivalentofTail(int i)

{

for ( ; i>0; i‐‐)

System.ou t.p rint(i);

}

* يمكن للمترجمات الذكية "compilers"  اكتشاف تكرار الذيل وتحويله إلى تكراري لتحسين التعليمات البرمجية.

* يستخدم لتنفيذ الحلقات في اللغات التي لا تدعم هياكل الحلقة بشكل صريح. (مثل برولوج prolog).

* في اللغات المدعومة  بحلقة أو ما يعادلها ، مثل إذا تم دمج العبارة مع تعليمة goto ، فإن تكرار الذيل ليس ميزة موصى بها.

 عدم تكرار الذيل NON‐TAIL RECURSION.

تسمى الطرق التكرارية التي لا تكون متكررة الذيل  non-tail recursion

هنا يجب أن تقوم الدالة بإجراء طباعة واستدعاء آخر بعد الدالة التكرارية الأولى ، وبالتالي فهي مثال على عدم تكرار الذيل

الإدخال: "ABC" ، يصف التغييرات في المكدس او stack وقت التشغيل أثناء تنفيذ العكس ()

ملاحظة - من الكاتب - : يصعب احيانا ترجمة بعض عمليات الخورزميات للعربية لعدم وجود مصطلحات عربية معتمدة في مجال علوم الحاسب بشكل عام لذلك اقوم بعرضها باللغتين لتصل الفكرة 

تكمن مشكلة الخوارزمية غير الطرفية في أنها تستهلك الكثير من عمليات المكدس stack وليست فعالة 

تحويل عدم تكرار الذيل إلى تكرار الذيل 

يمكن تحويل طريقة التكرار غير الذيلية إلى طريقة تكرار الذيل عن طريق معلمة "مساعدة auxiliary" تُستخدم لتشكيل النتيجة.

يتم استخدام هذه التقنية عادةً مع دالة "مساعدة auxiliary".

وذلك  ببساطة للحفاظ على بناء الجملة البرمجية  بشكل نظيف وإخفاء حقيقة أن هناك حاجة إلى المعلمات المساعدة.

هل طريقةعامل العدد "factorial"  هي طريقة الذيل التكراري ؟

int fact(int x){

if (x==0)

return 1;

else

return x*fact(x‐1);

}

عند العودة من استدعاء متكرر ، لا يزال هناك عملية واحدة معلقة ، وهي الضرب.

لذلك ، العامل يعتبر  طريقة عدم تكرار الذيل "non‐tail recursive"

تحويل عدم تكرار الذيل إلى تكرار الذيل بالمثال البرمجي : 

int fact_aux(int n, int result) {

if (n == 1)

return result;

return fact_aux(n ‐ 1, n * result)

}

int fact(n) {

return fact_aux(n, 1);

}

التكرار المفرط "Excessive Recursion"

عندما تكرر الطرق التكرارية في  العمليات الحسابية لبعض المعلمات ،ينتج عن ذلك  وقت حساب طويل حتى بالنسبة للحالات البسيطة.

   وبذلك قد تكون هناك إمكانية لتكرار الحلول المحسوبة بالفعل.

على سبيل المثال: أرقام fibananci

باستخدام هذا المثال ، يمكننا بسهولة إظهار مدى عدم كفاءة الصيغة التكرارية، دعنا نحاول معرفة كيفية تقييم Fib (6).

هنا تم حساب fibananci للـ 4 مرتين ، 3 محسوبة 3 مرات ، 2 محسوبة 5 مرات ، 1 محسوبة 8 مرات و 0 محسوبة 5 مرات. هذا يعني أنه يتم حساب نفس الدالة مرات عديدة دون داع 

التراجع BACKTRACKING

يتيح لنا التراجع تجربة جميع السبل المتاحة بشكل منهجي من نقطة معينة الى نقطة اخرى

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

ولناخذ على سبيل المثال مشكلة تحركات حجر الملكة في لعبة الشطرنج على طاولة تتيح مساحة تحرك 4*4

حيث يمكن تحريك كل حجر في اي من المسارات المجاورة عمودية او افقية  شريطة الا يعترضها اي حجر اخر 

مشكلة تحركات حجر الملكة في لعبة الشطرنج على طاولة تتيح مساحة تحرك 8*8

التهيئة

الملكة الأولى

الملكة الثانية

الخ ...

مثال برمجي على خوارزمية التراجع 

ترجمة فيصل عسيري لصالح مدونة فاب
المرجع :

Adam Drozdek, Data Structures and Algorithms in Java, 4th edition, Cengage Learning Asia, 2013