لوحة المتصدرين

الرسم التخطيطي أو المخطط هو مجموعة من النقاط والخطوط التي ترتبط ببعضها (يمكن أن تكون فارغة)، وتسمى نقاط المخطط رؤوسًا vertices أو عقدًا nodes، بينما تسمى الخطوط التي تربط رؤوس المخطط أضلاعًا edges أو أقواسًا أو خطوطًا. يعرَّف مخطط G مثلًا كزوْج (V، E)، حيث تمثّل V مجموعة من الحروف، وتمثّل E مجموعة الأضلاع التي تربط تلك الحروف، انظر: E ⊆ {(u,v) | u, v ∈ V}‎‎ تخزين المخططات هناك طريقتان شائعتان لتخزين المخططات، وهما: مصفوفة التجاور Adjacency Matrix. قائمة التجاور. مصفوفة التجاور مصفوفة التجاور هي مصفوفة تُستخدم لتمثيل مخطط محدود finite graph، وتشير عناصر المصفوفة إلى ما إذا كانت أزواج الرؤوس متجاورة (مترابطة) في المخطط أم لا. وفي نظرية المخططات، نقول أنّ العقدة B مجاورة للعقدة A إذا كنا نستطيع الذهاب من العقدة A إلى العقدة B، وسنتعلم الآن كيفية تخزين العُقد المتجاورة عبر مصفوفة التجاور Adjacency Matrix ثنائية الأبعاد، هذا يعني أننا سنمثل العقد التي تتشارك الأضلاع فيما بينها. نرى في الشكل الموضح أعلاه جدولًا إلى جانب المخطط، ويمثّل هذا الجدول مصفوفة التجاور الخاصة بالمخطط المجاور له، وتمثل Matrix[‎i][j] = 1 هنا وجود ضلع بين i و j. بالمقابل، سنكتب Matrix[‎i][j] = 0 إذا لم يكن هناك أيّ ضلع يربطهما. نستطيع وزن تلك الأضلاع، أي إلحاق رقم بكل ضلع -قد يمثل هذا الرقم المسافة بين مدينتين مثلًا-، وهنا نضع الوزن في الموضع Matrix[‎i][j]‎‎ بدلًا من 1. والمخطط الموضح أعلاه ثنائي الاتجاه Bidirectional، أو غير موجّه Undirected، أي أنّه إذا كان بإمكاننا الانتقال من العقدة 2 إلى العقدة 1 فيمكننا أيضًا الانتقال من العقدة 1 إلى العقدة 2. إن لم تتحقّق هذه الخاصية نقول أنّ المخطط موجّه Directed. وتوضع أسهم بدل الخطوط إذا كان المخطط موجَّهًا، كما يمكن استخدام مصفوفات التجاور لتمثيل هذا النوع من المخططات. لكن على خلاف المخططات غير الموجّهة، فإن العقد التي لا تشترك في أيّ ضلع تُمثَّل باللانهاية inf في المخططات الموجّهة كما يبيّن الرسم أعلاه. هناك أمر آخر ينبغي الانتباه له، وهو أنّ مصفوفة التجاور الخاصة بمخطط غير موجّه تكون دائما غير متماثلة. انظر الشيفرة التوضيحية pseudo-code التالية لإنشاء مصفوفة التجاور، حيث يمثل N عدد العُقد: Procedure AdjacencyMatrix(N): Matrix[N][N] for i from 1 to N for j from 1 to N Take input -> Matrix[i][j] endfor endfor فيما يلي طريقة أخرى لتعبئة المصفوفة، يمثل N فيها عدد العُقَد بينما يمثل E عدد الأضلاع: Procedure AdjacencyMatrix(N, E): Matrix[N][E] for i from 1 to E input -> n1, n2, cost Matrix[n1][n2] = cost Matrix[n2][n1] = cost endfor يمكنك إزالة السطر Matrix[n2][n1] = cost من الشيفرة في المخططات الموجّهة. عيوب استخدام مصفوفة التجاور إحدى المشاكل التي تنجم عن استخدام مصفوفات التجاور هو أنّها تستهلك مقدارا كبيرًا من الذاكرة، فمهما كان عدد أضلاع المخطط، سنحتاج دائمًا إلى مصفوفة بحجم N*N، حيث يمثّل N عدد العُقد. أما إذا كانت هناك 10000 عقدة في المخطط فسنحتاج مصفوفة بحجم 4 * 10000 * 10000، أي حوالي 381 ميغابايت، وهذا مضيعة للذاكرة، علمًا أنّ الكثير من المخططات لا تحتوي إلا القليل من الأضلاع. وبفرض أنّنا نريد أن نعرف العقد التي يمكننا الوصول إليها انطلاقًا من العقدة u، فسنحتاج إلى التحقق من الصفّ الخاص بـ u في المصفوفة بالكامل، وهذا سيكلفنا الكثير من الوقت. والفائدة الوحيدة لمصفوفة التجاور هي أنها تمكّننا من العثور بسهولة على مسار بين عقدتين مثل u-v، وكذلك تكلفة cost ذلك المسار، أي مجموع أوزان الأضلاع التي تؤلف المسار. شيفرة جافا التالية تطبق الشيفرة العامّة أعلاه: import java.util.Scanner; public class Represent_Graph_Adjacency_Matrix { private final int vertices; private int[][] adjacency_matrix; public Represent_Graph_Adjacency_Matrix(int v) { vertices = v; adjacency_matrix = new int[vertices + 1][vertices + 1]; } public void makeEdge(int to, int from, int edge) { try { adjacency_matrix[to][from] = edge; } catch (ArrayIndexOutOfBoundsException index) { System.out.println("The vertices does not exists"); } } public int getEdge(int to, int from) { try { return adjacency_matrix[to][from]; } catch (ArrayIndexOutOfBoundsException index) { System.out.println("The vertices does not exists"); } return -1; } public static void main(String args[]) { int v, e, count = 1, to = 0, from = 0; Scanner sc = new Scanner(System.in); Represent_Graph_Adjacency_Matrix graph; try { System.out.println("Enter the number of vertices: "); v = sc.nextInt(); System.out.println("Enter the number of edges: "); e = sc.nextInt(); graph = new Represent_Graph_Adjacency_Matrix(v); System.out.println("Enter the edges: <to> <from>"); while (count <= e) { to = sc.nextInt(); from = sc.nextInt(); graph.makeEdge(to, from, 1); count++; } System.out.println("The adjacency matrix for the given graph is: "); System.out.print(" "); for (int i = 1; i <= v; i++) System.out.print(i + " "); System.out.println(); for (int i = 1; i <= v; i++) { System.out.print(i + " "); for (int j = 1; j <= v; j++) System.out.print(graph.getEdge(i, j) + " "); System.out.println(); } } catch (Exception E) { System.out.println("Something went wrong"); } sc.close(); } } لتشغيل الشيفرة أعلاه، احفظ الملف، ثم صرّف compile الشيفرة باستخدام التعليمة الآتية: ‎javac Represent_Graph_Adjacency_Matrix.java انظر المثال التالي الذي يوضح هذا: $ java Represent_Graph_Adjacency_Matrix Enter the number of vertices: 4 Enter the number of edges: 6 Enter the edges: 1 1 3 4 2 3 1 4 2 4 1 2 The adjacency matrix for the given graph is: 1 2 3 4 1 1 1 0 1 2 0 0 1 1 3 0 0 0 1 4 0 0 0 0 تخزين المخططات (قوائم التجاور) قائمة التجاور هي مجموعة من القوائم غير المرتبة تُستخدم لتمثيل المخططات المحدودة finite graphs، وتصف كل قائمة في المجموعة جيرانَ كلّ حرف من حروف المخطط. وميزة قوائم التجاور أنّها تحتاج مساحة ذاكرة أقل لتخزين المخططات. انظر المثال التالي عن مخططٍ ومصفوفة التجاور الخاصة به: وهذه قائمة التجاور الخاصة بالمخطط أعلاه: تسمى هذه القائمة قائمةَ التجاور adjacency list، وتوضّح الروابط بين العقد. نستطيع إن شئنا تخزين هذه المعلومات باستخدام مصفوفة ثنائية الأبعاد، لكن هذا سيكلفنا نفس مقدار الذاكرة الذي يتطلّبه تخزين مصفوفة التجاور. بدلاً من ذلك، سنستخدم الذاكرة المخصّصة ديناميكيًا لتخزين هذه القيم. تدعم العديد من لغات البرمجة نوعي البيانات المتجهات Vector والقوائم List ، والتي يمكننا استخدامها لتخزين قائمة التجاور، وهكذا لن يكون علينا تحديد حجم القائمة إذ يكفي أن نحدّد الحد الأقصى لعدد العقد. انظر الشيفرة العامة لذلك، حيث يمثل maxN الحد الأقصى للعُقد، بينما يمثل E عدد الأضلاع، ويشير التعبير x, y إلى وجود ضلع يربط بين x وy: Procedure Adjacency-List(maxN, E): edge[maxN] = Vector() for i from 1 to E input -> x, y edge[x].push(y) edge[y].push(x) end for Return edge وبما أنّ هذا المخطط غير موجّه فإنّ وجود ضلع من x إلى y يستلزم وجود ضلع معاكس، أي ضلعٍ من y إلى x، ولن تتحقق هذه الخاصية في المخططات غير الموجّهة. أما بالنسبة للمخططات الموزونة فسنحتاج إلى تخزين التكلفة (الوزن) أيضًا، من خلال إنشاء متجه أو قائمة أخرى باسم cost[]‎‎ لتخزينها، انظر الشيفرة العامة لذلك: Procedure Adjacency-List(maxN, E): edge[maxN] = Vector() cost[maxN] = Vector() for i from 1 to E input -> x, y, w edge[x].push(y) cost[x].push(w) end for Return edge, cost يمكننا الآن أن نعثر بسهولة على العقد المتصلة بعقدة ما وعددها أيضًا، وسنحتاج وقتًا أقل مقارنة بمصفوفة التجاور. بالمقابل، ستكون مصفوفة التجاور أكثر كفاءة إن احتجنا إلى معرفة ما إذا كان هناك ضلع بين u وv. مقدمة إلى نظرية الرسوم التخطيطية نظرية المخططات أو الرسوم التخطيطية Graph Theory هي فرع من فروع الرياضيات يهتم بدراسة الرسوم التخطيطية، وهي كائنات رياضية تُستخدم لنمذجة العلاقات الزوجية بين الكائنات. طُوِّرت نظرية المخططات من قبل اختراع الحاسوب، إذ كتب ليونهارت أويلر Leonhard Euler ورقة حول جسور كونيجسبرج السبعة Seven Bridges of Königsberg والتي تُعدّ أوّل ورقة علمية عن نظرية المخططات، وأدرك الناس منذ ذلك الحين أنه إذا أمكننا تحويل المشاكل إلى مسائل من نوع مدينة-طريق City-Road، فيمكننا حلها بسهولة باستخدام نظرية المخططات. وهناك تطبيقات عديدة لهذه النظرية، لعل أشهرها هو العثور على أقصر مسافة بين مدينتين. فمثلا، ينبغي أن تمرّ عبر العديد من المُوجّهات routers عندما تدخل موقعًا إلكترونيا، انطلاقًا من الخادم، لكي تصل محتويات الموقع إلى حاسوبك. تساهم نظرية المخططات هنا في العثور على الموجّهات التي ينبغي المرور عبرها للوصول إلى حاسوبك في أسرع وقت. كما تُستخدم خلال الحروب لتحديد الطريق الذي يجب قصفه لقطع العاصمة عن المدن الأخرى. وسنتعلم فيما يلي بعض الأساسيات لهذه النظرية. إليك تعاريف من المهم الاطلاع عليها ومعرفتها: المخططات: لنقل أنّ لدينا 6 مدن، نرقّم هذه المدن من 1 إلى 6. سننشئ الآن مخططًا يمثّل هذه المدن، حيث تمثل الرؤوسُ المدن، مع ربط المدن التي تربطها طرق فيما بينها بأضلاع. هذا مخطط بسيط لتمثيل المدن والطرق الرابطة بينها، ونسمي هذه المدن في نظرية المخططات عقدًا Nodes أو حروفًا Vertex فيما نسمّي الطرق أضلاعًا Edge. يمكن أن تمثل العقدة أشياءً كثيرة، إذ قد تمثّل مدنًا أو مطارات أو مربّعات على رقعة الشطرنج. بالمقابل، تمثل الأضلاع العلاقات بين تلك العقد. مثلًا، يمكن أن تمثّل هذه العلاقات الوقت اللازم للانتقال من مطار إلى آخر، أو نقلة الفارس من مربّع إلى المربعات الأخرى على رقعة الشطرنج، وغير ذلك. تمثيل لمسار الفارس على رقعة الشطرنج وببساطة، تمثّل العقدة أيّ نوع من الكائنات، وتمثّل الأضلاع العلاقات بين تلك الكائنات. العقدة المتجاورة Adjacent Node: تكون B مجاورة لـ A إذا اشتركت عقدة A مع عقدة أخرى B في ضلع واحد، أي نقول أنّ العقدتين متجاورتان إذا اتصلت عقدتان اتصالًا مباشرًا، ويمكن لكل عقدة أن يكون لها عدة عقد مجاورة. المخططات الموجّهة وغير الموجّهة Directed and Undirected Graph: توضع علامات توجيهية (مثل الأسهم) على الأضلاع في المخططات الموجّهة للدلالة على أنّ الضلع أحادي الاتجاه. من ناحية أخرى، تحتوي أضلاع المخططات غير الموجّهة على علامات اتجاه على كلا الجانبين، للدلالة على أنها ثنائية الاتجاه. لكن تُحذف علامات التوجيه تلك في الغالب من المخططات غير الموجّهة، وتمثّل حينها الأضلاع كخطوط وحسب. وإذا افترضنا وجود حفلٍ في مكان ما، فسنمثّل الأشخاص الحاضرين بالعُقد، وسنرسم خطًا بين شخصين إذا تصافحا. لا شك أن هذه المخططات غير موجّهة هنا، لأنّه إذا صافح عمرو زيدًا فهذا يعني أنّ زيدًا صافح عَمرًا كذلك، فهي عملية ثنائية. بالمقابل، إذا رسمنا ضلعًا من عمرو إلى زيد إن كان زيد يقدّر عَمرًا ويحترمه فإنّ هذه المخططات ستكون موجّهة، ذلك أن الإعجاب لا يشترط أن يكون متبادلًا. يُطلق على النوع الأول مخططات غير موجّهة undirected graphs، وتسمّى الأضلاع أضلاعًا غير موجّهة undirected edges، بالمقابل، يسمّى النوع الثاني مخططات موجّهة directed graph وتسمّى الأضلاع أضلاعًا موجّهة directed edges. المخططات الموزونة وغير الموزونة Weighted and Unweighted Graph: المخطط الموزون هو مخطط يكون لكلّ ضلع من أضلاعه رقم (وزن)، يمكن أن تمثّل هذه الأوزان التكاليف أو الأطوال أو السعات وغير ذلك، وذلك اعتمادًا على المشكلة المطروحة. بالمقابل، المخططات غير الموزونة هي مخططات نفترض أنّ أوزان جميع أضلاعها متساوية (تساوي1 افتراضيًا ). المسارات: يمثّل المسار طريقًا للانتقال من عقدة إلى أخرى ويتألّف من سلسلة من الأضلاع، ولا شيء يمنع وجود عدة مسارات بين عقدتين. في المثال أعلاه، هناك مساران من A إلى D، الأول هو A-> B ،B-> C ،C-> D ، وكلفته (مجموع أوزان الأضلاع التي تؤلّفه) هي 3 + 4 + 2 = 9، أما المسار الآخر فهو A-> D، وكلفته 10. يقال أن المسار الذي يكلّف أدنى قدر هو المسار الأقصر. الدرجة degree: درجة الحرف degree of a vertex هي عدد الأضلاع المرتبطة به، فإذا كان هناك ضلع يرتبط بالحرف في كلا الطرفين (حلقة loop)، فسيُحسب مرتين. يكون للعُقد في المخططات الموجّهة نوعان مختلفان من الدرجات: الدرجة الداخلية In-degree: عدد الأضلاع التي تشير إلى العقدة. الدرجة الخارجية Out-degree: عدد الأضلاع التي تنطلق من العقدة الحالية وتشير إلى العقد الأخرى. بالنسبة للمخططات غير الموجّهة، يكون هناك نوع واحد طبعا، ويُسمّى درجة الحرف. بعض الخوارزميات المتعلقة بنظرية المخططات: خوارزمية بلمان‎ فورد Bellman–Ford خوارزمية ديكسترا Dijkstra خوارزمية فورد فولكرسون Ford–Fulkerson خوارزمية كروسكال Kruskal. خوارزمية الجار الأقرب Nearest neighbour algorithm. خوارزمية بْرِم Prim. خوارزمية البحث العميق أولا Depth-first search. خوارزمية البحث العريض أولًا Breadth-first search. سوف نستعرضُ بعض هذه الخوارزميات لاحقًا. الترتيب الطوبولوجي Topological Sort يرتّب الترتيب الطوبولوجي حروف مخطط موجّه ترتيبًا خطيًا، إذ يضعها في قائمة مُرتّبة حسب الأضلاع الموجّهة التي تربط تلك الحروف. وليكون هذا الترتيب ممكنا، يجب ألّا يحتوي المخطط على دورة موجّهة directed cycle، فإن كان لدينا مخطط ‎G = (V, E)‎، فالترتيب الخطي رياضيًا هو ترتيب متوافق مع المخطط، أي يحقّق ما يلي: إن كانت ‎G‎ تحتوي الضلع ‎(u, v) ∈‎ E الذي ينتمي إلى E وينطلق من الحرف u إلى v، فستكون u أصغر من v وفق هذا الترتيب. وهنا من المهم ملاحظة أنّ كلّ مخطط موجّه غير دوري directed acyclic graph، أو DAG اختصارًا له ترتيب طوبولوجي واحد على الأقل، وهناك عدد من الخوارزميات التي تمكّننا من إنشاء ترتيب طوبولوجي لمخطط موجّه غير دوري في وقتٍ خطي، هذا مثال عام على إحداها: استدع دالة ‎depth_first_search(G)‎ لحساب أوقات الإنتهاء finishing times ‏بـ ‎v.f‎ لكل حرف ‎v‎ ‏ عقب الانتهاء من حرف ما، أدرِجه في مقدّمة قائمة مرتبطة linked list. يُحدَّد الترتيب الطوبولوجي بقائمة الحروف المرتبطة التي نتجت من الخطوتين السابقتين. يمكن إجراء ترتيب طوبولوجي في مدة ‎V + E، لأنّ "خوارزمية البحث العميق أولًا depth-first search" تستغرق مدّة ‎‎(V + E)‎‎ ـ كما ستستغرق ‎Ω(1)‎ (وقت ثابت) لإدراج كل الحروف ‎|V|‎ في مقدمة القائمة المرتبطة. تستخدم العديدُ من التطبيقات المخططاتَ الموجّهة الدورية directed acyclic graphs لتمثيل الأسبقية بين الأحداث، إذ يُستخدم الترتيب الطوبولوجي للحصول على الترتيب الصحيح لمعالجة كل حرف من حروف المخطط. وقد تمثّل حروف المخططُ المهامَ التي يتعيّن إنجازها، فيما تمثل الأضلاع أسبقية تنفيذ تلك المهام، وهكذا يمثّل الترتيب الطوبولوجي التسلسل المناسب لأداء مجموعة المهام الموضّحة في ‎V‎. مثال ليكن ‎v‎ حرفًا يمثّل مهمّة ‎Task(hours_to_complete: int)‎، بحيث يمثّل الوسيط hours_to_complete الوقت المُستغرَق لتنفيذ المهمة. فمثلًا، تمثّل ‎Task(4)‎ مهمّة تستغرق ‎4‎ ساعات لإكمالها. من جهة أخرى، يمثّل ضلع ‎e‎ قيمة ‎Cooldown(hours: int)‎، والتي تمثّل المدة الزمنية التي تنقضي قبل استئناف المهمة التالية (أي التي يشير إليها الضلع) بعد الانتهاء من المهمة الحالية (التي ينطلق منها الضلع). فإن كان هناك ضلع ‎Cooldown(3)‎ يربط بين مهمّتين أ و ب، فذلك يعني أنه بعد الانتهاء من المهمة أ، ستحتاج أن تنتظر 3 ساعات حتى تستطيع تنفيذ المهمة ب (مثلا ليبرد المحرّك). فيما يلي، المخطط غير الدوري والموجّه ‎dag‎ يحتوي 5 رؤوس: A <- dag.add_vertex(Task(4)); B <- dag.add_vertex(Task(5)); C <- dag.add_vertex(Task(3)); D <- dag.add_vertex(Task(2)); E <- dag.add_vertex(Task(7)); نربط الحروف عبر أضلاع موجّهة بحيث يكون المخططات غير دوري، انظر: // A ---> C -----+ // | | | // v v v // B ---> D ---> E dag.add_edge(A, B, Cooldown(2)); dag.add_edge(A, C, Cooldown(2)); dag.add_edge(B, D, Cooldown(1)); dag.add_edge(C, D, Cooldown(1)); dag.add_edge(C, E, Cooldown(1)); dag.add_edge(D, E, Cooldown(3)); ستكون هناك ثلاثة تراتيب طوبولوجية ممكنة بين ‎A‎ و‎E‎: A -> B -> D -> E A -> C -> D -> E A -> C -> E رصد الدورات في المخططات الموجهة باستخدام الاجتياز العميق أولا Depth First Traversal إذا نتج عن الاجتياز العميق أولًا ضلعٌ خلفي back edge، فذلك يعني أنّ المخطط الموجّه يحتوي دورة cycle. والضلع الخلفي هو ضلع ينطلق من عقدة ويعود إليها أو إلى إحدى أسلافها في شجرة بحث عميق أولًا Depth-first search اختصارًا DFS. بالنسبة لمخطط غير متصل disconnected graph، سنحصل على غابة بحث عميق أولا أو غابة DFS وهي اختصار لـ DFS forest، لذلك سيكون عليك التكرار على جميع الحروف في المخطط لإيجاد أشجار البحث العميق أولًا والمنفصلة disjoint DFS trees. فيما يلي تنفيذ بلغة C++‎‎: #include <iostream> #include <list> using namespace std; #define NUM_V 4 bool helper(list<int> *graph, int u, bool* visited, bool* recStack) { visited[u]=true; recStack[u]=true; list<int>::iterator i; for(i = graph[u].begin();i!=graph[u].end();++i) { if(recStack[*i]) شرح السطر السابق في الشيفرة: عند إيجاد حرف v في مكدس التكرارية الخاص باجتياز DFS، أعِد true، تابع المثال الآتي: return true; else if(*i==u) // في حال كان هناك ضلع من الحرف إلى نفسه return true; else if(!visited[*i]) { if(helper(graph, *i, visited, recStack)) return true; } } recStack[u]=false; return false; } هنا تستدعي دالة التغليف الدالةَ helper على كل حرف لم يُزَر بعد، وتعيد دالة helper القيمة true عند رصد ضلع خلفي في الشجيرة، وإلا فإنها تعيد false، تابع المثال الآتي: bool isCyclic(list<int> *graph, int V) { bool visited[V]; // مصفوفة لتتبع الأحرف المُزارة سلفا bool recStack[V]; // مصفوفة لتتبع الأحرف في المكدس التكراري للاجتياز for(int i = 0;i<V;i++) visited[i]=false, recStack[i]=false; // تهيئة جميع الأحرف على أنها غير مُزارة تكراريًا for(int u = 0; u < V; u++) // التحقق اليدوي مما إذا كانت كل الأحرف مُزارة { if(visited[u]==false) { if(helper(graph, u, visited, recStack)) // التحقق مما إذا كانت شجرةُ “بحثٍ عميقٍ أولًا” تحتوي دورة. return true; } } return false; } /* Driver function */ int main() { list<int>* graph = new list<int>[NUM_V]; graph[0].push_back(1); graph[0].push_back(2); graph[1].push_back(2); graph[2].push_back(0); graph[2].push_back(3); graph[3].push_back(3); bool res = isCyclic(graph, NUM_V); cout<<res<<endl; } تكون النتيجة كما هو موضّح أدناه، أن هناك ثلاثة أضلاع خلفية في المخططات، واحد بين الحرفين 0 و 2؛ وآخر بين الحروف 0 و1 و2؛ والحرف 3. والتعقيد الزمني للبحث يساوي O (V + E)‎‎، حيث يمثّل V عدد الحروف، وE يمثّل عدد الأضلاع. خوارزمية Thorup كيف يمكن العثور على أقصر مسار من حرف (مصدر) معيّن إلى أيّ حرف آخر في مخطط غير موجّهة؟ قدّم "ميكيل توغوب Mikkel Thorup" -نُطْقُ اسمه من الدانماركية- أول خوارزمية تحل هذه المشكلة. يساوي التعقيد الزمني لهذه الخوارزمية O (m)‎‎. وفيما يلي الأفكارُ الأساسية التي تعتمد عليها الخوارزمية: هناك عدّة طرق للعثور على الشجرة المتفرّعة spanning tree في مدة O (m)‎‎ (لن نذكر هذه الطرق هنا)، سيكون عليك إنشاء الشجرة المتفرّعة من الضلع الأقصر إلى الأطول، وسينتج عن ذلك غابة (مجموعة من الأشجار غير المتصلة بالضرورة) تحتوي العديد من المكوّنات المتصلة قبل أن تنمو كاملةً. اختر عددًا صحيحًا b ‏(b> = 2)، ولا تأخذ بالحسبان إلّا الغابات المتفرّعة ذات الطول الأقصى b ^ k، ثم ادمج المكونات المتشابهة في كل شيء ولكن تختلف في قيمة k. سنسمّى أصغر قيم k مستوى المكوّن level of the component. ثم ضع المكوّنات بعد هذا في الشجرة في المكان المناسب بحيث يكون الحرف u أبًا للحرف v إذ كان u هي أصغر مكوّن مختلف عن v ويحتوي v بشكل كامل. الجذر سيكون المخطط بأكمله، أمّا الأوراق فهي الحروف المفردة single vertices في المخطط الأصلي (مستواها يساوي سالب ما لا نهاية). ستحتوي الشجرة على O (n)‎‎ عقدة. حافظ على المسافة بين كل مكوّن وبين المصدر كما هو الحال في خوارزمية Dijkstra، تساوي مسافة مكوّن يحتوي أكثر من حرفٍ المسافةَ الأقل بين أبنائها غير الموسَّعين unexpanded children. اجعل مسافة الحرف الأصلي source vertex على 0، ثمّ حدّث الأسلاف وفقًا لذلك. احسب المسافات بنظام العدّ من الأساس b أو base b، وعند زيارة عقدة في المستوى k للمرة الأولى، ضع أبناءها في مجموعات أو سلَّات buckets مشتركة بين جميع العقد من المستوى k. وخذ بالحسبان أوّل b سلّة وحسب في كل مرة تزور فيها عقدة، وَزُر كلّ واحدة منها ثمّ أزلها، ثمّ حدّث مسافة العقدة الحالية، وَأعِد ربط العقدة الحالية بأصلها باستخدام المسافة الجديدة وانتظر الزيارة القادمة للسلات التالية. عند زيارة ورقة leaf، تكون المسافة الحالية هي المسافة النهائية للحرف. وسِّع جميع الأضلاع المنطلقة منه في المخطط الأصلي، ثمّ حدّث المسافات وفقًا لذلك. زر العقدة الجذرية (المخطط كاملًا) بشكل متكرر إلى أن تصل إلى الوجهة المقصودة. تعتمد هذه الخوارزمية على حقيقة أنّه لا يمكن أن يوجد ضلع ذا طول أقل من l بين مكوّنيْن متصليْن في غابة متفرّعة ذات حدّ طولي يساوي ‏‎‎length limitation، لذلك، يمكنك حصر تركيزك على مكوّن واحد متصل بدءًا من مسافة x إلى أن تصل إلى المسافة x + l. ستزور بعض الحروف في الطريق قبل زيارة جميع الحروف ذات المسافة الأقصر، لكن ذلك لا يهم بما أنّنا نعلم أنّه لن يكون هناك مسار أقصر إلى هنا من تلك الحروف. اجتياز المخططات Graph Traversals هناك العديد من الخوارزميات للبحث في المخططات، سنستعرض إحداها فيما يلي، وهي خوارزمية البحث العميق أولا. تنفذ الشيفرة التالية هذه الخوارزمية، إذ تنشئ دالة تأخذ فهرس العقدة الحالي كوسيط، وقائمة التجاور (مخزّنة في متجهة من المتجهات)، ومتجهة منطقية vector of boolean لتعقّب العقدة التي تمت زيارتها، انظر: void dfs(int node, vector<vector<int>>* graph, vector<bool>* visited) { // التحقّق مما إذا كانت العقدة مُزارة سلفا if((*visited)[node]) return; // set as visited to avoid visiting the same node twice (*visited)[node] = true; // نفّذ بعض الإجراءات هنا cout << node; // اجتياز العقد المتجاورة عبر البحث العميق أولا for(int i = 0; i < (*graph)[node].size(); ++i) dfs((*graph)[node][i], graph, visited); } ترجمة -بتصرّف- للفصلين 9 و10 من كتاب Algorithms Notes for Professionals اقرأ أيضًا المقالة السابقة: الأشجار Trees في الخوازرميات مدخل إلى الخوارزميات دليل شامل عن تحليل تعقيد الخوارزمية النسخة الكاملة من كتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة

نحتاج في بعض الأحيان لتكرار إجراء ما مثل إخراج قيم من قائمة واحدة تلو الأخرى أو تشغيل نفس الشيفرة للأعداد من 1 إلى 10 لكل عدد على حدة. حلقات التكرار (loops) عبارة عن وسيلة لتكرار شيفرة ما عدة مرات. حلقة التكرار while الصيغة الخاصة بها: while (condition) { // الشيفرة المراد تكرار تنفيذها // تدعى جسم الحلقة } طالما كان الشرط condition مُحققًا، أي true، تُنفذ الشيفرة الموجودة في جسم الحلقة. على سبيل المثال، تطبع حلقة التكرار أدناه قيمة المتغير i طالما كان الشرط i < 3 مُحققًا: let i = 0; while (i < 3) { // إظهار 0 ثم 1 ثم 2 alert( i ); i++; } يُسمى التنفيذ الواحد من جسم حلقة التكرار «تكرارًا» (iteration). ينفِّذ المثال السابق ثلاثة تكرارات. إذا كان i++‎ غير موجود في المثال أعلاه، ستُكرَّر الحلقة (نظريًا) إلى اللانهاية. أمَّا عمليًا، يوقف المتصفح تكرار مثل هذه الحلقات اللانهائية عند حدٍّ معيَّن، ويمكنك إنهاء العملية أيضًا من طرف الخادم في JavaScript. شرط حلقة التكرار غير مقصور على تعبيرات الموازنة، بل يمكن أن يكون أي تعبير أو متغير: يُقّيم الشرط ويُحوّل إلى قيمة منطقية بواسطة حلقة التكرار while. على سبيل المثال، الطريقة الأقصر لكتابة while (i != 0)‎ هي while (i)‎: let i = 3; while (i) { // وتتوقف الحلقة false صفرًا 0، يُقيَّم إلى القيمة i عندما تصبح قيمة المتغير alert( i ); i--; } ليس هناك حاجة للأقواس المعقوصة عند كتابة سطر برمجي واحد إذا كان جسم حلقة التكرار عبارة عن سطر واحد، يمكنك حذف الاقواس المعقوصة {…}: let i = 3; while (i) alert(i--); حلقة التكرار do..while يمكن إزاحة شرط حلقة التكرار الى أسفل جسم الحلقة باستخدام الصيغة do..while: do { // جسم الحلقة } while (condition); ستُنفذ أولًا الشيفرة الموجودة في جسم الحلقة ثم يتم التحقق من الشرط؛ فإذا كان الشرط مُحققًا، تُكرَّر هذه العملية مرة أخرى. إليك المثال التالي: let i = 0; do { alert( i ); i++; } while (i < 3); تستخدم هذه الصيغة عندما ترغب في تنفيذ الشيفرة مرة واحدة على الأقل بغض النظر عن كون الشرط محققًا أم لا. عادة ما تُفضل الصيغة الأخرى: while(…) {…}‎. حلقة التكرار for تعد حلقة التكرار for أكثر حلقات التكرار شيوعًا. تبدو صياغة الحلقة بالشكل التالي: for (begin; condition; step) { // ... جسم الحلقة ... } إليك المثال التالي لتتعرف ماهية هذه الأجزاء begin; condition; step. تُنفِّذ حلقة التكرار أدناه الدالة alert(i)‎ لقيمة المتغيِّر i العددية من 0 إلى 3 ( باستثناء العدد 3، لأن الشرط i < 3 لا يشمل العدد 3): for (let i = 0; i < 3; i++) { // إظهار 0 ثم 1 ثم 2 alert(i); } يعرض الجدول التالي شرحًا مفصلًا لأجزاء حلقة التكرار السابقة: الجزء الشيفرة المقابلة الوظيفة البدء (التهيئة) i = 0 يُنفَّذ مرةً واحدةً لحظة ولوج الحلقة الشرط i < 3 يُتحقَّق من هذا الشرط قبل كل تكرار (دورة تنفيذ) للحلقة، فإذا كان غير محقَّق (false)، يوقف تنفيذ الحلقة. الجسم alert(i)‎ يُنفَّذ ما دام الشرط محقَّقًا (true). الخطوة i++‎ يُنفَّذ بعد تنفيذ جسم الحلقة في كل تكرار. تعمل خوارزمية حلقة التكرار كالتالي: دخول الحلقة: -> إذا تحقَّق الشرط -> نفِّذ جسم الحلقة ثمَّ نفِّذ الخطوة -> إذا تحقَّق الشرط -> نفِّذ جسم الحلقة ثمَّ نفِّذ الخطوة -> إذا تحقَّق الشرط -> نفِّذ جسم الحلقة ثمَّ نفِّذ الخطوة -> … في حال كنت مبتدئًا، قد يساعدك ذلك في العودة إلى المثال وتدوين آلية تنفيذه خطوة بخطوة على الورق. إليك شرح لما يحدث في هذه الحالة: // for (let i = 0; i < 3; i++) alert(i) // دخول الحلقة let i = 0 // إذا تحقَّق الشرط -> نفِّذ جسم الحلقة ثمَّ نفِّذ الخطوة if (i < 3) { alert(i); i++ } // إذا تحقَّق الشرط -> نفِّذ جسم الحلقة ثمَّ نفِّذ الخطوة if (i < 3) { alert(i); i++ } // إذا تحقَّق الشرط -> نفِّذ جسم الحلقة ثمَّ نفِّذ الخطوة if (i < 3) { alert(i); i++ } // i == 3 أوقف الحلقة لعدم تحقُّق الشرط 3 > 3 عند التصريح عن المتغيرات داخل نطاق الحلقة يُصرَّح عن المتغير i المسمى «بالعدَّاد» مباشرةً ضمن حلقة التكرار، لذا تكون متاحةً ضمن نطاقها فقط وغير ظاهرة للعموم. for (let i = 0; i < 3; i++) { alert(i); // 0, 1, 2 } alert(i); // خطأ! لا يوجد متغيِّر بهذا الاسم بدلًا من تعريف متغير جديد، يمكنك استخدام متغير معرَّف مسبقًا: let i = 0; for (i = 0; i < 3; i++) { // استعمال متغير موجود مسبقًا alert(i); // 0, 1, 2 } alert(i); // يعرض القيمة 3 لوجوده ضمن النطاق العام تجاهل بعض أجزاء التحكم بحلقة التكرار for يمكن تجاهل أي جزء من أجزاء الحلقة begin; condition; step مثل حذف جزء التهيئة begin في حال لم يكن وجوده مهمًا كما في المثال التالي: let i = 0; // المتغيِّر جاهز for (; i < 3; i++) { // فلا حاجة لقسم التهيئة alert( i ); // 0, 1, 2 } يمكنك أيضًا حذف الخطوة step: let i = 0; for (; i < 3;) { alert( i++ ); } فتصبح حينئذٍ الحلقة for مطابقة للحلقة while (i < 3)‎. يمكنك فعليًا إزالة جميع الأجزاء، وخلق حلقة تكرار لانهائية: for (;;) { // تكرار لا نهائي } يرجى التحقق من وجود الفاصلتين المنقوطتين ; في صيغة حلقة التكرار for. خلاف ذلك، سيُطلَق خطأ. إيقاف حلقة التكرار يتوقف تنفيذ حلقة التكرار عندم عدم تحقُّق الشرط أي أصبح التقييم المنطقي للشرط false. مع ذلك، يمكنك إيقاف تنفيذ الحلقة في أي وقت باستخدام التعليمة break. في المثال التالي، تطلب حلقة التكرار من المستخدم إدخال سلسلة من الأرقام عن طريق الدالة prompt، ويتوقف تنفيذ الحلقة عندما لا يُدخَل أي رقم: let sum = 0; while (true) { let value = +prompt("Enter a number", ''); if (!value) break; // (*) sum += value; } alert( 'Sum: ' + sum ); عند النظر إلى الشيفرة، تُنفَّذ الكلمة المفتاحية break في السطر (*) إذا أدخل المستخدم سطرًا فارغًا أو ألغى عملية الإدخال وبذلك تتوقف حلقة التكرار فورًا، وينتقل تنفيذ الشيفرة إلى السطر الأول بعد حلقة التكرار أي إلى الدالة alert. يمكن استعمال حلقة أبدية (لانهائية) مع الكلمة المفتاحية break في الحالات التي لا يُعرَّف فيها متى يصبح الشرط غير محقَّقٍ. الاستمرار في التكرار التالي الموجِّه continue هو "نسخة أخف" من الموجِّه break، إذ لا يوقف تنفيذ حلقة التكرار بأكملها بل يوقف تنفيذ التكرار الحالي فقط، وينتقل لتنفيذ التكرار التالي (إذا تحقق الشرط طبعًا). أي نستعمله في الحالات التي نرغب فيها بإيقاف تنفيذ التكرار الحالي والانتقال إلى التكرار التالي. حلقة التكرار أدناه تستخدم الموجِّه continue لإخراج القيم الفردية فقط من الأعداد 0 وحتى 10: for (let i = 0; i < 10; i++) { // إذا تحقق التعبير، تخطى جسم الحلقة وانتقل للتكرار التالي if (i % 2 == 0) continue; alert(i); // 1, 3, 5, 7, 9 } فيما يخص القيم الزوجية i، يوقف التعبير البرمجي continue تنفيذ حلقة التكرار وينتقل إلى التكرار التالي في الحلقة for (مع الرقم التالي)، لذلك تظهر الدالة alert فقط القيم الفردية. تقليل مستوى التداخل عبر الموجِّه continue حلقة التكرار المسؤولة عن إخراج القيم الفردية سوف تبدو كما يلي: for (let i = 0; i < 10; i++) { if (i % 2) { alert( i ); } } من الناحية التقنية، هذا مشابه للمثال أعلاه. يمكنك استخدام الشرط if بدلًا من استخدام الموجِّه continue. ولكن سيؤدي ذلك لخلق مستوى إضافي من التداخل (استدعاء الدالة alert داخل الأقواس المعقوصة {}). تقل قابلية القراءة الإجمالية إذا كانت الشيفرة الموجودة داخل التعبير الشرطي if أطول من بضعة أسطر. لا يُستخدم الموجهان break/continue في المعامل الشرطي الثلاثي ? لاحظ أنه لا يمكن استخدام البنى التي لا تشبه صياغتها التعابير البرمجية مع المعامل الثلاثي ? تحديدًا موجهات مثل break/continue. إليك الشيفرة التالية: if (i > 5) { alert(i); } else { continue; } أعد كتابتها باستخدام المعامل الشرطي ?: (i > 5) ? alert(i) : continue; // هنا continue لا يسمح باستخدام الموجه توقفت الشيفرة عن العمل بسبب خطأ في الصياغة (syntax error)، وهذا سبب آخر لعدم استخدام المعامل ? بدلًا من الشرط if. تسمية حلقات التكرار تحتاج في بعض الأحيان لإيقاف حلقات تكرار متداخلة ومتعددة في وقت واحد. على سبيل المثال، تُنفذ حلقتي تكرار في الشيفرة التالية على المتغيرين i و j ، لإخراج الإحداثيات (i, j) من (0,0) إلى (3,3): for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { let input = prompt(`Value at coords (${i},${j})`, ''); // التي تليها؟ alert ماذا لو أردت الخروج من الحلقة والانتقال للدالة } } alert('Done!'); ستحتاج إلى طريقة لإيقاف حلقة التكرار إذا ألغى المستخدم الإدخال. استخدام الموجِّه break بعد input سيُوقف حلقة التكرار الداخلية فقط. هذا ليس كافيًا، فما الحل يا ترى؟! هنا يأتي دور اللافتات (labels)! اللافتة (label) عبارة عن مُعرِّف (وليست كلمةً محجوزةً) يتبعه نقطتين رأسيتين وتأتي قبل حلقة التكرار مباشرةً: labelName: for (...) { ... } يوقف الموجِّه break <labelName>‎ في المثال أدناه تنفيذه حلقة التكرار ذات المُعرِّف <labelName> (أي outer في حالتنا): outer: for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { let input = prompt(`Value at coords (${i},${j})`, ''); // الخروج من كلتا الحلقتين إن ألغيت عملية الإدخال أو أعطيت قيم فارغة if (!input) break outer; // (*) // افعل شيئًا بالقيم المعطاة } } alert('Done!'); وظيفة الموجِّه break outer في المثال السابق إيقاف حلقة تكرار مسماة بالاسم outer؛ لذلك، ينتقل تنفيذ الشيفرة مباشرة من السطر (*) إلى السطر alert('Done!')‎. يمكنك وضع اللافتة في سطر منفصل: outer: for (let i = 0; i < 3; i++) { ... } يُستخدَم الموجِّه continue مع لافتة أيضًا وينتقل تنفيذ التعليمات البرمجية آنذاك إلى التكرار التالي ليس لحلقة التكرار الموجود فيها وإنما للحلقة الموسومة بتلك اللافتة. لا تسمح اللافتات بالقفز إلى أي مكان في الشيفرة لا تسمح لك اللافتات بالانتقال إلى أي سطر تريده في الشيفرة لتنفيذه إجباريًا، فمن المستحيل مثلًا تنفيذ المثال التالي: break label; // label لا يمكن القفز إلى السطر التالي المعنون بـ label: for (...) لا يمكن إستدعاء break/continue إلا من داخل حلقة تكرارية ويمكن استعمال لافتة معهما إن سبق عنونة الحلقة بها مسبقًا. الخلاصة تعرفت إلى الآن على ثلاثة أنواع من حلقات التكرار: while: تتحقَّق من الشرط قبل كل تكرار، ويُنفذ التكرار إذا كان الشرط محققًا. do..while: تتحقَّق من الشرط بعد كل تكرار، ولا يُنفذ التكرار التالي إذا لم يكن الشرط محققًا. for (;;): تتحقَّق من الشرط قبل كل تكرار، وهناك أيضًا عناصر تتيح التحكم أكثر بالحلقة. لبناء حلقة أبدية (لا نهائية)، تُستخدم حلقة التكرار while(true)‎ (أي أن يكون الشرط دائمًا محققًا)، ويمكن إيقاف هذه الحلقة مثل أي حلقة أخرى، عن طريق الموجِّه break. في حال عدم رغبتك بتنفيذ التكرار الحالي وتود الانتقال إلى التكرار التالي، فيمكنك استخدام الموجِّه continue. ويمكنك استخدام الموجين break/continue مع لافتات (labels) شرط أن تكون مُعرّفة قبل بداية حلقة التكرار. فتوفر اللافتة عندما استعمالها مع break/continue تحكمًا أكبر بالحلقات المتداخلة. التمارين قيمة حلقة التكرار الأخيرة الأهمية: 3 ما هي القيمة الأخيرة التي أظهرتها الدالة alert في هذه الشيفرة؟ ولماذا؟ let i = 3; while (i) { alert( i-- ); } الحل الإجابة: 1. let i = 3; while (i) { alert( i-- ); } تَنقص قيمة المتغير i بمقدار 1 في كل تكرار في حلقة التكرار هذه. تتوقف حلقة التكرار while(i)‎ عندما يتحقق الشرط i = 0، وبالتالي تشكل خطوات حلقة التكرار هذه التسلسل التالي: let i = 3; alert(i--); // بمقدار 1 لتصبح 2 i إظهار 3 ثم إنقاص قيمة alert(i--) // بمقدار 1 لتصبح 1 i إظهار 2 ثم إنقاص قيمة alert(i--) // بمقدار 1 لتصبح 0 i إظهار 1 ثم إنقاص قيمة // توقف الحلقة لعدم تحقق الشرط ما هي القيم التي ستظهرها حلقة التكرار while؟ الأهمية: 4 سجّل القيمة الناتجة من كل تكرار في الحلقة، ثم وازنها بالإجابة النهائية. هل تُظهر الدالة alert نفس القيم في الحلقتين أم لا؟ النموذج السابق i++: let i = 0; while (++i < 5) alert( i ); النموذج اللاحق ++i: let i = 0; while (i++ < 5) alert( i ); الحل يوضح هذا التمرين كيف يمكن أن يؤدي النموذج السابق/ اللاحق (postfix/prefix) إلى نتائج مختلفة عند استخدامهما في الموازنات. من 1 إلى 4 let i = 0; while (++i < 5) alert( i ); القيمة الأولى هي i = 1، لأن معامل الزيادة i++ الأول يزيد i ثم يُرجع القيمة الجديدة. لذلك الموازنة الأولى هي‎1 < 5 وتُظهر الدالة alert العدد 1. ثم تتبعها الأعداد 2، 3، 4. تستخدم الموازنة دائمًا القيمة الأخيرة، نظرًا لأن معامل الزيادة ++ قبل المتغير. وأخيرًا، يُزاد i = 4 إلى 5، ولا يتحقق شرط حلقة التكرار while(5 < 5)‎ في هذه الحالة، وتتوقف الحلقة. لذلك لا يظهر العدد 5. من 1 إلى 5 let i = 0; while (i++ < 5) alert( i ); القيمة الأولى هي i = 1. يزيد النموذج اللاحق ++i المتغير i ثم يُرجع القيمة القديمة، لذلك ستستخدم الموازنة i++ < 5 التعبير i = 0 (على عكس ‎++i < 5). لكن استدعاء الدالة alert منفصل وتُنفَّذ بعد معامل الزيادة والموازنة، لذلك تحصل على القيمة الحالية للمتغير i = 1. ثم تتبعها الأعداد 2، 3، 4. عند i = 4، يزيد النموذج السابق i++ قيمة المتغير ويستخدم العدد 5 في الموازنة ولكن هنا لدينا النموذج اللاحق ++i. أي أن قيمة المتغير i تصبح 5، لكنه يُرجع القيمة القديمة. وبهذا تصبح الموازنة while(4 < 5)‎- صحيحة، وتُنفذ الدالة alert. القيمة i = 5 آنذاك هي القيمة الأخيرة، لأن الشرط في التكرار التالي while(5 < 5)‎ غير مُحقق. ما القيم التي ستظهرها حلقة التكرار for؟ الأهمية: 4 سجّل القيمة الناتجة من كل حلقة تكرار، ثم قارنها بالإجابة. هل تُظهر الدالة alert نفس القيم في الحلقتين أم لا؟ النموذج اللاحق ++i: for (let i = 0; i < 5; i++) alert( i ); النموذج السابق i++: for (let i = 0; i < 5; ++i) alert( i ); الحل الإجابة في كلتا الحلقتين: من 0 إلى 4. for (let i = 0; i < 5; ++i) alert( i ); for (let i = 0; i < 5; i++) alert( i ); يمكنك بسهولة استنتاج التالي من الخوارزمية for: تُنفذ التعليمة i = 0 مرة واحدة في البداية. يتم يُتحقَّق من الشرط i < 5. إذا كان الشرط محققًا true- يُنفذ جسم الحلقة alert(i)‎ ويليه معامل الزيادة ++i. معامل الزيادة ++i منفصل عن الشرط في الحالتين، فهو عبارة عن تعليمة أخرى. لا تُستخدَم القيمة التي يعيدها معامل الزيادة هنا، لذلك لا يوجد فرق بين النموذجين ++i و i++. إخراج الأعداد الزوجية باستخدام حلقة التكرار الأهمية: 5 استخدم حلقة التكرار for لإظهار الأعداد الزوجية من 2 إلى 10. الحل for (let i = 2; i <= 10; i++) { if (i % 2 == 0) { alert( i ); } } يمكنك استخدام معامل باقي القسمة (modulo) % للحصول على باقي القسمة والتحقق من التكافؤ هنا. استبدال حلقة التكرار for بحلقة التكرار while الأهمية: 5 أعد كتابة الشيفرة باستبدال حلقة التكرار for بحلقة التكرار while دون تغيير سلوك الشيفرة (يجب أن يظل ناتج حلقة التكرار كما هو). for (let i = 0; i < 3; i++) { alert( `number ${i}!` ); } الحل let i = 0; while (i < 3) { alert( `number ${i}!` ); i++; } كرر حتى يكون الإدخال صحيحًا الأهمية: 5 اكتب حلقة تكرار تطلب من المستخدم إدخال عدد أكبر من 100. إذا أدخل المستخدم عدد آخر، فاطلب منه الإدخال مرة أخرى. يجب أن تسأل حلقة التكرار عن العدد حتى يُدخل المستخدم عدد أكبر من 100 أو يلغي الإدخال / يُدخل سطرًا فارغًا. في هذا التمرين، يدخل المستخدم الأعداد فقط أي ليس هناك حاجة لتنفيذ معالجة خاصة للتحقق من القيم المدخلة. الحل let num; do { num = prompt("Enter a number greater than 100?", 0); } while (num <= 100 && num); تتكرر حلقة التكرار do..while طالما أن الشرط num <= 100 && num محقق: الجزء الأول من الشرط num <= 100- أي أن القيمة التي أدخلها المستخدم لا تزال أقل من 100. الجزء الثاني من الشرط && num- لا يتحقق هذا الجزء إذا كان الإدخال null أو سلسلة نصية فارغة. تتوقف حلقة التكرار while في هذه الحالة أيضًا. ملاحظة: إذا كان المتغير num فارغًا null، فسيكون الجزء الأول من الشرط num <= 100 صحيحًا true، دون الجزء الثاني من الشرط لن تتوقف الحلقة إذا نقر المستخدم على زر الإلغاء (CANCEL). لذا لا يمكن الاستغناء عن أي الجزئين. إظهار الأعداد الأولية الأهمية: 3 يسمى العدد عددًا أولي (prime) إذا كان عددًا صحيحًا أكبر من 1، ولا يقبل القسمة (القسمة دون باقي قسمة) إلا على نفسه وعلى العدد 1. بعبارة أخرى، n > 1 المتغير n عبارة عن عدد أولي إذا كان لا يقبل القسمة بالتساوي على أي عدد باستثناء 1 و n. على سبيل المثال، العدد 5 هو عدد أولي، لأنه لا يمكن تقسيمه بالتساوي دون وجود باقي قسمة بمقدار 2، و 3 و4. اكتب الشيفرة التي تخرج الأعداد الأولية في المجال من 2 إلى n. إذا كانت n = 10 مثلًا، فستكون النتيجة 2,3,5,7. ملاحظة: يجب أن تعمل الشيفرة من أجل أي قيمة للمتغير n، أي لا يكون المتغير n معرّف لقيمة ثابتة. الحل هناك العديد من الخوارزميات لهذا التمرين: كتابة الشيفرة باستخدام حلقة تكرار متداخلة: For each i in the interval { check if i has a divisor from 1..i if yes => the value is not a prime if no => the value is a prime, show it } كتابة الشيفرة باستخدام اللافتة (label): let n = 10; nextPrime: for (let i = 2; i <= n; i++) { // i لكل قيمة من قيم for (let j = 2; j < i; j++) { // ابحث عن المقسوم عليه if (i % j == 0) continue nextPrime; // ليس عددًا أوليًا، انتقل للتكرار التالي } alert( i ); // عددٌ أولي } هناك مساحة كبيرة لتحسين الشيفرة، على سبيل المثال يمكنك البحث عن القواسم من 2 إلى الجذر التربيعي ل i (مثال: القواسم الموجبة للعدد 24 هي 1، 2، 3، 4، 6، 8، 12، 24). على أي حال، إذا كنت تريد تنفيذ التمرين السابق على مجالات كبيرة، فستحتاج إلى تغيير النهج والاعتماد على الرياضيات المتقدمة والخوارزميات المعقدة مثل المنخل التربيعي (Quadratic sieve) أو منخل الأعداد العام (General number field sieve) وما إلى ذلك. ترجمة -وبتصرف- للفصل Loops: while and for من كتاب The JavaScript Language table { width: 100%; } thead { vertical-align: middle; text-align: center; } td, th { border: 1px solid #dddddd; text-align: right; padding: 8px; text-align: inherit; } tr:nth-child(even) { background-color: #dddddd; } .task__importance { color: #999; margin-left: 30px; } .task__answer { border: 3px solid #f7f6ea; margin: 20px 0 14px; position: relative; display: block; padding: 25px 30px; } code { background-color: rgb(250, 250, 250); border-radius: 3px; } اقرأ أيضًا المقال التالي: التعليمة switch المقال السابق: المعاملات المنطقية

سنقوم في هذا الدرس بتغطية الأوامر الأساسية التي لا يُمكنك الاستغناء عنها إن أردت أن تستخدم Git بكفاءة عالية والتي ستقضي وقتك على Git في استخدامها. يُفترض بك بعد إنهاء قراءة هذا الدرس أن تصبح قادرًا على إعداد وتهيئة مُستودع، الشروع في وإيقاف تتبع التغييرات في ملفات مُعينة، إرسال التغييرات إلى منطقة الإدراج وإيداعها. سنشرح لك أيضا كيف ستقوم بتجاهل ملفات مُعينة أو التي تتبع أنماطا خاصة، فيما ستتحدث الدروس التي تلي هذا عن كيفية التراجع عن أخطاء قُمت بها بشكل سريع وسهل، كيفية تصفح تاريخ المشروع والاطلاع على كافة التعديلات التي حدثت ما بين كل إيداعين، وكيف تقوم بدفع التغييرات إلى مُستودع في خادوم بعيد أو سحب البيانات منه. الحصول على مستودع وحفظ التغييرات فيه يُمكنك الحصول على مُستودع Git بطريقتين مُختلفتين. تتمثل الأولى في إنشاء مُستودع لمشروع أو مُجلد مُعد سلفا، وتتم الثانية عبر استنساخ مُستودع موجود على خادوم بعيد. إنشاء مستودع جديد لمشروع موجود مسبقا إن أردت الشروع في تتبع إصدارات وتغييرات مشروع راهن فكل ما عليك القيام به هو الذهاب إلى مُجلد المشروع (بسطر الأوامر طبعا) ومن ثم تنفيذ الأمر التالي: $ git init سيقوم هذا الأمر بإنشاء مُجلد فرعي داخل مُجلد المشروع يحمل الاسم git. والذي سيحتوي جميع ملفات المُستودع الأساسية التي ستشكل هيكل المستودع. بطبيعة الحال لن يتم تتبع أية تغييرات بُمجرد تنفيذ هذا الأمر لوحده. إن أردت الشروع في إدارة نسخ الملفات الراهنة (يعني لن تبدأ بمُجلد فارغ) فإنه يجب عليك أولا الشروع في تتبع هذه الملفات والقيام بأول عملية إيداع. يُمكن القيام بذلك عبر تنفيذ بضعة أوامر git add التي ستحدد فيها أسماء هذه الملفات ثم تُتبعها بأمر للإيداع: $ git add README $ git commit -m "initial project version" بعد تنفيذك لهذه الأوامر (سنشرح ما تقوم به هذه الأوامر بعد قليل) سيكون لديك مُستودع Git يقوم بتتبع التغييرات التي ستطرأ على مجموعة ملفات، إضافة إلى إيداع أولي. نسخ مستودع موجود مسبقا إن أردت استنساخ مُستودع Git راهن -وليكن مُستودعا لمشروع ترغب في المُساهمة فيه- فإن الأمر الذي ستحتاجه للقيام بذلك هو git clone. إن كانت لديك دراية مُسبقة بباقي أنظمة إدارة النُسخ مثل Subversion فإنك ستلحظ بأن الأمر الذي نستعمله هنا هو clone وليس checkout، حيث أن ما سيستقبله Git هو نُسخة من جميع البيانات (أو تقريبا) الموجودة على الخادوم. يعني بأنك ستحصل على كل نسخة من كل الملفات منذ أن تم الشروع في تتبع المُستودع الموجود على الخادوم لدى تنفيذ الأمر git clone. بعبارة أخرى، لو تعرض القرص الصلب لخادومك لعطب ما فإنه بإمكانك استعادة المشروع الذي كنت تعمل عليه كما كان (أو تقريبا) بفضل النُسخ الموجودة في جميع الأجهزة التي تعمل على نفس المشروع. يتم استنساخ المُستودعات باستخدام الأمر التالي: git clone [url] حيث يتم استبدال بعُنوان المُستودع المُراد استنساخه. فعلى سبيل المثال لو أردت استنساخ مُستودع "الدليل البسيط لاستخدام Git" فسيكون الأمر على النحو التالي: git clone git://github.com/arabicgit/simple-guide.git سيتم إنشاء مُجلد يحمل الاسم simple-guide يتم إنشاء مُجلد git. بداخله، ومن ثم سيتم استنساخ جميع البيانات الموجودة في مستودع الدليل على Github التي يُمكن الشروع في العمل عليها. إن أردت أن يتم استنساخ المُستودع داخل مُجلد باسم مُخالف فيُمكن تحديد اسم المُجلد الذي ترغب فيه (وليكن MyGuide) في أمر الاستنساخ على النحو التالي: git clone git://github.com/arabicgit/simple-guide.git MyGuide يدعم Git عدة بروتوكولات للتحويل. استعملنا في المثال السابق بروتوكول git://، لكنه بإمكانك أيضا استخدام (http(s:// أو user@server:/path.git والتي تعتمد على بروتوكول SSH. تسجيل التغييرات الحاصلة في المستودع الآن وبعد أن حصلت على مُستودع يقبل تتبع التغييرات الحاصلة على ملفاته، إضافة إلى جُملة من الملفات التي ستعمل عليها، ستحتاج بطبيعة الحال إلى إحداث تغييرات عليها ومن ثم إيداع تلك التغييرات في كل مرة يصل فيها مشروعك إلى مرحلة ترغب في تسجيلها. تذكر بأن الملفات تكون في إحدى الحالتين التاليتين: مُتتبع tracked أو غير مُتتبع untracked. الملفات المُتتبعة هي التي سبق وأن سجلت حضورا في اللقطة snapshot السابقة. يُمكن لهذه الملفات أن تكون في حالات ثلاثة: مُعدّلة غير مُعدلة مُدرجة staged (أي موجودة في منطقة الإدراج). أما الملفات غير المُتتبعة فهي ما سوى ذلك، ويشمل ذلك أي ملف في مجلد العمل لم يكن موجودًا في اللقطة السابقة وغير موجود في منطقة الإدراج. لدى قيامك باستنساخ مُستودع فإن جميع ملفاته ستكون مُتتبّعة وغير مُعدّلة لأنه -وبكل بساطة- قمت لتوك بسحبها ولم تحدث أية تغييرات عليها. بمُجرد أن تدخل تغييرات على أحد الملفات فسيعتبره Git ملفا مُعدّلا، حيث أن هذه الملفات قد طرأت عليها تغييرات منذ آخر إيداع. ما هي الخُطوة القادمة في هذه الحالة؟ ستقوم أولا بإدراج هذه التغييرات stage (أي وضع الملفات المعنية بالأمر في منطقة الإدراج) ومن ثم تقوم بإيداع تلك التغييرات commit، وستكرر هذه العملية طيلة استخدامك لـ Git، مثلما هو مُوضح في الصورة التالية: التحقق من حالة ملفاتك للتحقق من حالة ملفات مستودعك ستحتاج إلى استخدام الأمر git status. إن قمت بتنفيذ هذا الأمر مُباشرة بعد قيامك باستنساخ مُستودع فإنه يُفترض بهذه النتيجة أن تظهر: $ git status On branch master nothing to commit, working directory clean وهو ما يعني بأنك أمام مُجلد عمل نظيف. بعبارة أخرى لم يتم إحداث تغييرات على أي ملف مُتتبَّع. في هذه الحالة أيضا لا يُظهر Git أي ملفات غير مُتتبعة، لأنه لو كان الأمر غير كذلك فسيقوم حتما بإعلامك بالأمر. يُخبرك هذا الأمر بالفرع branch الذي تتواجد فيه، ومثلما هو ظاهر من النتيجة السابقة فإننا حاليا في الفرع الرئيسي master وهو الفرع الذي يتم استعماله بشكل قياسي. لنفرض الآن بأنك قُمت بإضافة ملف جديد إلى مشروعك، ولنفرض بأنه ملف README. إذا لم يكن هذه الملف موجودا من قبل داخل هذا المُستودع ولدى قيامك بتنفيذ الأمر git status فإن اسم هذا الملف سيظهر في قسم الملفات غير المُتتبعة على النحو التالي: $ vim README $ git status On branch master Untracked files: (use "git add <file>..." to include in what will be committed) README nothing added to commit but untracked files present (use "git add" to track) عدم التتبع عنها يعني بأن git قد عرف بأن الملف لم يكن في اللقطة السابقة لمشروعك (أي آخر إيداع)، لكنه لن يشرع في تتبعه بشكل آلي ما لم تقم أنت بطلب ذلك بشكل صريح، وستجد بأن ذلك مُفيد جدا خاصة لما تعمل على مشروع يُنتج الكثير من الملفات المُوقتة التي لا ترغب في تتبعها. تتبع الملف الجديد الآن وللشروع في تتبع الملف الجديد فإننا سنحتاج إلى الأمر git add على النحو التالي: $ git add README وإذا قمت بتنفيذ الأمر git status من جديد فإن الملف سيظهر مُتتبعا ومُدرجا: $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) new file: README بإمكانك معرفة أن الملف في منطقة الإدراج لأنه يظهر في قسم التغييرات التي سيتم إيداعها "Changes to be committed". إذا قمت بإدراج الملف في هذه المرحلة فإن حالة الملف لدى تنفيذك للأمر git add هي التي ستتم إضافتها إلى اللقطة. يُمكنك تحديد مسار ملف أو مُجلد لدى تنفيذك لأمر git add، ولدى تحديد مُجلد فإنه ستتم إضافة جميع مُحتوياته. إدراج الملفات المعدلة لنقم الآن بتعديل ملف سبق وأن شرعنا في تتبع التغيرات الطارئة عليه. لو أدخلنا تغييرات على الملف benchmark.rb ومن ثم نفذنا الأمر status من جديد لحصلنا على نتيجة مُماثلة لهذه النتيجة: $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) new file: README Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) modified: benchmarks.rb أين يظهر ملف benchmark.db تحت قسم "Changes not staged for commit" (تعديلات لم يتم إدراجها لإيداعها).ومثلما هو ظاهر من هذا الوصف فأننا قمنا بإدخال تعديلات على ملف مُتتبع ولم يتم إدراج تلك التغييرات بعد. ولإدراج هذه التغييرات يكفي أن نُنفذ الأمر git add الذي لديه عدة استخدامات كالشروع في تتبع الملفات مثلما سبق وأن شاهدناه، إدراج الملفات وللقيام بأمور أخرى كتعليم ملفات الدمج المُتضاربة merge-conflicted files كمحلولة. $ git add benchmarks.rb $ git status On branch master Changes to be committed: > (use "git reset HEAD <file>..." to unstage) new file: README modified: benchmarks.rb مثلما نلاحظه الآن، تم إدراج كلا الملفين وسيتم أخذ التغييرات الطارئة عليهما في الحسبان في عملية الإيداع القادمة. لكن لنفرض بأنك تذكرت تغييرا آخرًا تود إدخاله على ملف قبل أن تقوم بعملية الإيداع، وعليه فإنك ستقوم بالتعديل عليه قبل إيداعه. لكن لو قمت الآن بتنفيذ أمر git status من جديد فستظهر هذه النتيجة: $ vim benchmarks.rb $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) new file: README modified: benchmarks.rb Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) modified: benchmarks.rb غريب؟ أليس كذلك؟ يظهر ملف benchmark.rb على أساس أنه مُدرج وغير مُدرج في آن واحد. هل هذا ممكن؟ نعم هذا مُمكن حيث يقوم git بإدراج الملف في حالته التي كان عليها لدى تنفيذ الأمر git add وبالتالي لو قمت بالإيداع الآن فإنه سيتم إيداع ملف benchmark.rb في حالته التي كان عليها لدى تنفيذ الأمر git add وليس على الحال التي هو عليها الآن، وبالتالي فإنه يجب تنفيذ الأمر git add لإدراج تلك التغييرات في كل مرة تقوم بإدخال التعديلات على الملف: $ git add benchmarks.rb $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) new file: README modified: benchmarks.rb تجاهل ملفات عادة ما تكون لديك في المشروع الذي تعمل عليه جُملة أو صنف من الملفات التي لا ترغب من Git أن يقوم بإضافتها بشكل آلي أو حتى في إظهارها كملفات غير مُتتبعة، وعادة ما تكون هذه الملفات تلك التي يتم توليدها بشكل آلي مثل ملفات log أو الملفات التي تنتج عن نظام البناء الخاص بك build system. في مثل هذه الحالات فإن الحل يكمن في استخدام ملف gitignore. الذي يحتوي أنماط أسماء هذه الملفات غير المرغوب فيها: $ cat .gitignore *.[oa] *~ يطلب السطر الأول في الملف (ولا أعني بذلك الأمر cat) من Git أن يتجاهل جميع الملفات التي تنتهي بـ o. أو a. (الكائنات وملفات الأرشيف التي يُحتمل أن تنتج عن عملية بناء شفرتك البرمجية). أما السطر الثاني فيطلب من Git أن يتجاهل جميع الملفات التي تنتهي أسماؤها بمحرف ~ والتي تستخدمها بعض محررات النصوص كمُحرر Emacs لحفظ الملفات المؤقتة. بإمكانك أيضا أن تُضمن في هذا الملف ملفات log ،tmp أو مجلد pid والتوثيق التي يتم توليده بشكل آلي وما إلى ذلك. الشروع في إعداد ملف gitignore. قبل الشروع في العمل على المشروع من شأنه أن يُجنبك إيداع ملفات لا ترغب أن تظهر في مستودعك لاحقا. القواعد العامة التي تتبعها أنماط أسماء الملفات المُضمنة في ملف gitignore. هي على النحو التالي: يتم تجاهل الأسطر الفارغة والأسطر التي تبدأ بمحرف # يتم أخذ الأنماط المبسطة للتعابير القياسية Standard glob patterns في الحسبان بإمكانك إنهاء النمط بـ / للدلالة على المجلدات. بإمكانك عكس النمط بتسبيقه بعلامة تعجب ! الأنماط المبسطة للتعابير القياسية Standard glob patterns هي نسخة مُبسطة من التعابير القياسية التي يُمكن استخدامها على سطر الأوامر. فـ * تدل على 0 أو أكثر من محرف، و [abc] تتوافق مع أي حرف ضمن هذه القائمة (في هذه الحالة: a ،b و c). أما علامة الاستفهام فتتوافق مع محرف واحد. أما لو استخدمنا هذه الصيغة [0-9] فإنها ستوافق أي محرف يقع ما بين 0 و 9. إليكم مثالا آخر عن ملف gitignore.: # a comment - this is ignored # no .a files *.a # but do track lib.a, even though you're ignoring .a files above !lib.a # only ignore the root TODO file, not subdir/TODO /TODO # ignore all files in the build/ directory build/ # ignore doc/notes.txt, but not doc/server/arch.txt doc/*.txt # ignore all .txt files in the doc/ directory doc/**/*.txt النمط **/ مُتوفر بداية من الإصدار 1.8.2 إظهار التغييرات المدرجة وغير المدرجة إذا كانت النتيجة التي يُظهرها الأمر git status غير دقيقة بالنسبة إليك أو إن كنت ترغب في معرفة التغييرات التي حصلت بدقة وليس مجرد معرفة قائمة الملفات التي تم تغييرها فإنه بإمكانك الاستعانة بالأمر git diff للقيام بذلك. لسنا هنا بصدد تفصيل الأمر git diff (سنقوم بذلك في مقال لاحق) لكنك ستحتاجه للإجابة على سؤالين مُحددين: ما الذي قُمت بالتعديل عليه ولم تقم بإدراجها بعد، وما الذي قمت بإدراجه لكن لم تقم بإيداعه بعد. بالرغم من أنه بإمكان git status الإجابة على هذين السؤالين، إلا أن الأمر git diff كفيل بالإجابة عنها بشكل أدق، حيث سيخبرك عن أي سطر تمت إضافته وعن أي سطر تمت إزالته. لنفرض بأنك قمت بتحرير وإيداع ملف README من جديد ومن ثم قمت بتحرير ملف benchmarks.rb من دون إدراجه. لو قمت بتنفيذ الأمر status فإنك ستحصل على نتيجة مُشابه للنتيجة التالية: $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) new file: README Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) modified: benchmarks.rb لكن لو رغبت في معرفة التغييرات التي حصلت والتي لم يتم إدراجها فاستعن بالأمر git diff: $ git diff diff --git a/benchmarks.rb b/benchmarks.rb index 3cb747f..da65585 100644 --- a/benchmarks.rb +++ b/benchmarks.rb @@ -36,6 +36,10 @@ def main @commit.parents[0].parents[0].parents[0] end + run_code(x, 'commits 1') do + git.commits.size + end + run_code(x, 'commits 2') do log = git.commits('master', 15) log.size يقوم هذا الأمر بمقارنة مُحتوى مُجلد العمل بما هو موجود في منطقة الإدراج، وبالتالي فإن النتيجة ستُخبرك بالتغييرات التي قُمت بها والتي لم تقم بإدراجها بعد. أما إذا أردت رؤية التغييرات المُدرجة التي سيتم أخذها في الحسبان في الإيداع القادم فما عليك سوى استخدام الأمر git diff --cached (في الإصدار 1.6.1 والإصدارات التي تليه أصبح بالإمكان استخدام الأمر git diff --staged بدلا عنه، حيث يُعتبر هذا الأمر أسهل للتذكر من سابقه). يقوم هذا الأمر بمقارنة مُحتوى منطقة الإدراج بآخر إيداع قمت به: $ git diff --cached diff --git a/README b/README new file mode 100644 index 0000000..03902a1 --- /dev/null +++ b/README2 @@ -0,0 +1,5 @@ +grit + by Tom Preston-Werner, Chris Wanstrath + http://github.com/mojombo/grit + +Grit is a Ruby library for extracting information from a Git repository تجدر الإشارة إلى أن الأمر git diff بدون أية معاملات إضافية لا يقوم بإظهار كل التغييرات التي قُمت بها منذ آخر إيداع، حيث تكتفي بإظهار التغييرات التي لم يتم إدراجها. هذا الأمر قد يكون مُربكا بعض الشيء بحكم أنه لو قمت بإدراج جميع التغييرات التي قمت بها فإن أمر git diff لن يُظهر أية نتيجة. مثال آخر، لو قمت بإدراج الملف benchmarks.rb ومن ثم قمت بالتعديل عليه فإنه بإمكانك استخدام الأمر git diff لرؤية التغييرات التي تمت على الملف والتي تم إدراجها وتلك التغييرات التي لم يتم إدراجها أيضا: $ git add benchmarks.rb $ echo '# test line' >> benchmarks.rb $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) modified: benchmarks.rb Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) modified: benchmarks.rb الآن يُمكنك استخدام الأمر git diff لمعرفة ما الذي لم يتم إدراجه بعد: $ git diff diff --git a/benchmarks.rb b/benchmarks.rb index e445e28..86b2f7c 100644 --- a/benchmarks.rb +++ b/benchmarks.rb @@ -127,3 +127,4 @@ end main() ##pp Grit::GitRuby.cache_client.stats +# test line والأمر git diff --cached لمعرفة ما الذي قُمت بإدراجه إلى حد الآن: $ git diff --cached diff --git a/benchmarks.rb b/benchmarks.rb index 3cb747f..e445e28 100644 --- a/benchmarks.rb +++ b/benchmarks.rb @@ -36,6 +36,10 @@ def main @commit.parents[0].parents[0].parents[0] end + run_code(x, 'commits 1') do + git.commits.size + end + run_code(x, 'commits 2') do log = git.commits('master', 15) log.size إيداع التغييرات الآن وبعد أن قمت بإعداد منطقة الإدراج على النحو الذي ترغب فيه، بإمكانك الآن القيام بإيداع التغييرات التي قمت بها. تذكر دائما بأن أي تغيير لم تم بإيداعه -أي ملف قمت بإنشائه أو التعديل عليه والذي لم تقم بإضافته بتنفيذ الأمر git add عليه منذ إنشائه أو منذ آخر تحديث عليه- لن يتم أخذه بالحسبان في الإيداع القادم، بل سينظر إليه النظام كملف تم تعديله. في هذه الحالة، ولدى تنفيذك للأمر git status آخر مرة فإنك لاحظت بأنه تم إدراج جميع التغييرات وبالتالي فإنك جاهز لإيداع التغييرات. يتم ذلك باستخدام الأمر git commit على النحو التالي: git commit تنفيذ هذا الأمر سيقوم بفتح مُحرر النصوص المُفضل لديك (والذي يتم تحديده عبر قيمة مُتغيرالنظام EDITOR$ والذي يُمكن أن يكون vim ،emacs أو أي مُحرر نصوص آخر، كما أنه يُمكنك تحديد عبر الأمر git config --global core.editor مثلما سبق وأن تطرقنا إليه في درس إعداد Git للمرة الأولى. سيقوم المُحرر بإظهار النص التالي (المثال التالي مأخوذ من مُحرر النصوص Vim): # Please enter the commit message for your changes. Lines starting # with '#' will be ignored, and an empty message aborts the commit. # On branch master # Changes to be committed: # new file: README # modified: benchmarks.rb # ~ ~ ~ ".git/COMMIT_EDITMSG" 10L, 283C مثلما نلاحظه هنا فإن نص/رسالة الإيداع القياسية تحتوي مُخرجة الأمر git status على هيئة تعليق، إضافة إلى سطر فارغ يسبق ذلك. بإمكانك حذف هذا التعليق وكتابة النص الذي ترغب فيه، كما أنه بإمكانك الإبقاء عنها لتتذكر الملفات التي تم تعديلها في هذا الإيداع ( للحصول على تذكير أدق يُمكنك تمرير المُعامل v- لأمر git commit سابق الذكر، وستحصل حينها على تفاصيل التغييرات التي حدثت على الملفات لما يتم فتح المُحرر المفضل لديك). لدى إغلاقك لمحرر النصوص سيقوم Git بإنشاء الإيداع ويقوم بإرفاق ذلك النص/الرسالة به مع التخلص من التعليقات وتفاصيل التغييرات التي أدخلت على الملفات. يُمكنك أيضا كتابة نص الإيداع مُباشرة مُرفقا بأمر الإيداع وذلك بتسبيقه بـ m- على النحو التالي: $ git commit -m "Story 182: Fix benchmarks for speed" [master 463dc4f] Story 182: Fix benchmarks for speed 2 files changed, 3 insertions(+) create mode 100644 README كما تلاحظ فإنك قمت بعمل أول عملية إيداع لك وحصلت على بعض المعلومات حوله، كاسم الفرع الذي ينتمي إليه (master) وما هي قيمة هاش SHA-1 الخاصة به 463dc4f، عدد الملفات التي تم تحديثها، إضافة إلى عدد الأسطر التي تمت إضافتها أو حذفها. يجب التذكير بأن عملية الإيداع تقوم بأخذ صورة عن البيانات التي تم إدراجها وأي تغييرات لم تقم بإرسالها إلى منطقة الإدراج لن يتم أخذها بالحسبان، وعليه يجب إضافتها من جديد إلى منطقة الإدراج قبل إيداعها من جديد. كل مرة تقوم فيها بعملية إيداع فإنك تأخذ صورة عن حالة مشروعك في اللحظة التي تم التقاط تلك الصورة فيها وبإمكانك الرجوع إلى تلك الحالة لاحقا إن رغبت في ذلك. تجاوز منطقة الإدراج بالرغم من أن منطقة الإدراج في غاية الأهمية لتمكيننا من "بناء" إيداعات على الشكل الذي نرغب فيه، إلا أنها تُعتبر في بعض المرات مرحلة إضافية لا نرغب فيها. إذا رغبت في تجاوز منطقة الإدراج ما بين الحين والآخر فإن Git يسمح لك بالقيام بذلك، حيث يكفي إضافة خيار a- إلى أمر git commit ليقوم git بإضافة جميع الملفات التي كنت تتبعها سابقا قبل عملية الإيداع الحالية (يعني يقوم باختصار أمر git add). $ git status On branch master Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) modified: benchmarks.rb no changes added to commit (use "git add" and/or "git commit -a") $ git commit -a -m 'added new benchmarks' [master 83e38c7] added new benchmarks 1 files changed, 5 insertions(+) لاحظ كيف أننا لم نحتج إلى تنفيذ الأمر git add على الملف benchmarks.rb في هذه الحالة قبل أن تقوم بعملية الإيداع. حذف الملفات لحذف ملف من مشروع Git فإنه يجب عليك أن تحذفه من قائمة الملفات المُتتبّعة (أو بالأحرى من قائمة الملفات المُدرجة) قبل أن تقوم بعملية إيداع. يُمكّن أمر git rm من القيام بذلك ويقوم بحذف الملف من مُجلد العمل مما سيُجنّب ظهوره في قائمة الملفات غير المُتتبعة. إذا قمت بحذف الملف يدويا من المشروع فإن اسمه سيظهر في قائمة التغييرات التي لم يتم إدراجها لما تقوم بتنفيذ الأمر git status: $ rm grit.gemspec $ git status On branch master Changes not staged for commit: (use "git add/rm <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) deleted: grit.gemspec no changes added to commit (use "git add" and/or "git commit -a") ومن ثم إذا قمت بتنفيذ الأمر git rm فإنه سيتم "إدراج" الملف للحذف: $ git rm grit.gemspec rm 'grit.gemspec' $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) deleted: grit.gemspec وفي المرة القادمة التي تقوم فيها بالإيداع فإن الملف سيختفي كُليّة. إذا كنت قد عدّلت على الملف وقمت بإضافته إلى الفهرس index فإنه يجب فرض إزالته عبر تمرير الخيار -f. يتم الاستعانة بذلك لتجنب حذف بيانات لم يتم تسجيلها في سجلات Git عن طريق الخطأ (وبالتالي لن يُصبح بالإمكان استرجاعها). أمر آخر قد ترغب في القيام به والمُتعلق بحذف الملف من git مع إبقائه في مُجلد العمل الخاص بك. بعبارة أخرى قد تكون أضفت ملفا مُعينا عن طريق الخطأ ولكن لا ترغب في مواصلة تتبعه عبر git، وعادة ما يكون الأمر مُتعلقا بملفات نسيت إضافتها إلى gitignore. كملفات log كبيرة الحجم أو ملفات a. الناتجة عن ترجمة المشروع. كل ما تحتاج إلى القيام به هو إضافة خيار cached-- على الشكل التالي: $ git rm --cached readme.txt بإمكان تمرير أسماء ملفات، مُجلدات أو حتى أنماطا مُبسطة للتعابير القياسية file-glob patterns لأمر git rm. يعني يُمكن القيام مثلا بالتالي: $ git rm log/\*.log لاحظ وجود محرف \ الذي يسبق * والذي يُعتبر ضروريا لأن git يستعمل نظامه الخاص لتفسير هذه الأنماط إضافة إلى النظام الخاص بسطر الأوامر الذي تستخدمه. أما على نظام Windows فإنك لن تحتاج إلى إضافته. يقوم هذا الأمر بحذف جميع الملفات التي تملك المُلحق log. في مُجلد log/. بإمكانك أيضا تنفيذ الأمر التالي لحذف جميع الملفات التي تنتهي أسماؤها بـ ~: $ git rm \*~ نقل الملفات على عكس ما هو مُتداول عليه باقي أنظمة إدارة الإصدارات فإن Git لا يقوم بتتبع حركة الملفات بشكل مُباشر. إن قمت بتغيير اسم ملف مثلا فإن git لا يحتفظ بأية بيانات حول الأمر، إلا أن النظام يملك مقدارا مُعينا من "الذكاء" يسمح له باستنتاج ذلك لاحقا. سنقوم بالتطرق لتتبع حركة الملفات في مقال لاحق. قد يبدو الأمر غامضا نوعا ما خاصة وأن git يملك الأمر mv. إن أردت إعادة تسمية ملف فإنه يُمكن القيام بذلك على النحو التالي: $ git mv file_from file_to وسيتم ذلك على النحو المُتوقّع، حيث يظهر ذلك واضحا على النحو التالي: $ git mv README README.txt $ git status On branch master Changes to be committed: (use "git reset HEAD <file>..." to unstage) renamed: README -> README.txt في المقابل، الأمر السابق مُماثل في نتيجته للتالي: $ mv README README.txt $ git rm README $ git add README.txt حيث سيعرف git بأنك تقوم بإعادة تسمية الملف، وبالتالي لا يهم الآلية التي تتبعها للقيام بذلك. الاختلاف الوحيد ما بين الطريقتين هو أن mv عبارة عن أمر واحد بدل الأوامر الثلاثة في الطريقة الثانية. الأهم من ذلك يُمكن الاستعانة بأية طريقة ترغب فيها لإعادة تسمية الملفات، كل ما يهمك أن تقوم بتنفيذ أوامر add/rm اللازمة قبل أن تقوم بعملية الإيداع. ترجمة -وبتصرف- للفصلين: Git Basics – Getting a Git Repository و Git Basics – Recording Changes to the Repository من كتاب Pro Git لصاحبه Scott Chacon.