انتهت الجولة الثالثة
وترتيب المتسابقين هو :
10 نقاط للأخ اسلام الكبابي
8 نقاط للإخ عبدالله الصافي
6 نقاط للاخ Fantastico
جميع المشاركين حصلو على +2 بسبب تحقيقهم شرط (الاصغر الاقرب)
تنفيذ الخوارزمية
بما ان هذه الخوارزمية هي اكثر خوارزمية سببت الجدل في جميع مسابقات المنتدى ، فضلت ان اقوم بشرح كيفية تنفيذها بإسهاب كبير حتى تنتشر الفائدة بين الجميع ..
علما بأن طريقة الحل المستخدمة في هذا الرد هي طريقة خاصة
بالدوت نت ، وبالاخص (السي شارب) بسبب ان الاكواد المستخدمة في الحل نفسها تستخدم تقنيات لاتتوفر الا في الـ .Net Framework وكل هذا لكي يكون كود الخوارزمية نظيفا ورائعا وقابلا للفهم .
-----------
1- الدوال المُساعدة
في البداية ، قمنا بإنشاء Extension Methods (الدوال الممتدة) وهي دوال مُساعدة أنشأناها لتساعدنا في حل الخوارزمية ( مجرد دوال مساعدة لاشغل لها بالخوارزمية الفعلية) ..
الدوال الممتدة هي احدى ميزات
الدوت نت ولمن لايعرف اهميتها ، فهي باختصار..
مجرد دوال تستطيع الوصول اليها من المتغير مباشرة :
PHP كود :
public static class MyExtensions
{
//إستبدال حرف مكان حرف بالاندكس
public static string ReplaceAt(this string str, int index, string replace)
{
return str.Remove(index, 1).Insert(index, replace);
}
//حذف علامات الاستفهام واستبدالها بالاصفار
public static string WithoutQMarks(this string str)
{
string final = string.Empty;
foreach (var item in str)
if (item != '?')
final += item;
else
final += '0';
return final;
}
//جلب مواقع علامات الاستفهام
public static int[] QMarksIndexes(this string str)
{
List<int> indexes = new List<int>();
for (int i = 0; i < str.Length; i++)
if (str[i] == '?')
indexes.Add(i);
return indexes.ToArray();
}
}
وظائف الدوال موضحة بالتعليقات الخضراء ، وكما ترون .. هذه الدوال ممتدة هي مجرد دوال مساعدة سنستخدمها لاحقا ..
الفائدة العظمى من الدوال الممتدة هي امكانية الوصول اليها من المتغير مباشرة ، فلاحظ الكود التالي :-
PHP كود :
string myStr = "?33:?4?";
myStr = myStr.WithoutQMarks(); //033:040
//من المتغير مباشرة WithoutQMarks تم الوصول للدالة الممتدة
انا احب الدوال الممتدة اكثر من الدوال العادية في امور معالجة الـ Datatype وذلك بسبب انها تحقق احد مبادئ كتابة الكود high cohesion (عزل الاكواد)
انتهينا من كتابة الدوال الممتدة المساعدة للخوارزمية ، ننتقل للكود الرئيسي :-
2- الكود الرئيسي
PHP كود :
static string CloseMatch(string s1, string s2)
{
//مخزنين لتخزين القيم المحتملة
List<int> values1 = new List<int>();
List<int> values2 = new List<int>();
//جلب مواقع علامات الاستفهام
int[] s1_Q_Indexes = s1.QMarksIndexes();
int[] s2_Q_Indexes = s2.QMarksIndexes();
//اضافة القيم الاولية الى اللستة
values1.Add(int.Parse(s1.WithoutQMarks()));
values2.Add(int.Parse(s2.WithoutQMarks()));
//دالة تكرارية لايجاد المجهول
FillUnknown(ref values1, ref s1, ref s1_Q_Indexes, 0);
FillUnknown(ref values2, ref s2, ref s2_Q_Indexes, 0);
//(حذف المكرر + الترتيب من الاصغر (لتحقيق شرط الاقرب الاصغر
values1 = values1.Distinct().OrderBy(s => s).ToList();
values2 = values2.Distinct().OrderBy(s => s).ToList();
//جلب الفرق الاقرب
int min = int.MaxValue, min_S1 = 0, min_S2 = 0;
values1.ForEach(v1 => values2.ForEach(v2 =>
{
int absoluteMin = Math.Abs(v1 - v2);
if (min > absoluteMin)
{
min_S1 = v1;
min_S2 = v2;
min = absoluteMin;
}
}));
//اضافة اصفار اذا كان الناتج اقل من طول المدخل
string out_S1 = min_S1.ToString().PadLeft(s1.Length, '0');
string out_S2 = min_S2.ToString().PadLeft(s2.Length, '0');
return string.Format("{0} : {1}", out_S1, out_S2);
}
PHP كود :
//مخزنين لتخزين القيم المحتملة
List<int> values1 = new List<int>();
List<int> values2 = new List<int>();
2 لست لتخزين القيم المحتملة ، كل لست يخزن القيم المحتملة لجزء من العينة
values1 : values2
2:
PHP كود :
//جلب مواقع علامات الاستفهام
int[] s1_Q_Indexes = s1.QMarksIndexes();
int[] s2_Q_Indexes = s2.QMarksIndexes();
المتغير s1 يشير الى الجزء الايسر من العينة
المتغير s2 يشير الى الجزء الايمن من العينة
هنا نستعمل الدالة الممتدة ، لجلب مواقع علامات الاستفهام في العينة .
3:
PHP كود :
//اضافة القيم الاولية الى اللستة
values1.Add(int.Parse(s1.WithoutQMarks()));
values2.Add(int.Parse(s2.WithoutQMarks()));
حذف علامات الاستفهام من جميع العينة واستبدالها بأصفار ثم نضيفها للستة القيم المحتملة .
4:
PHP كود :
//دالة تكرارية لايجاد المجهول
FillUnknown(ref values1, ref s1, ref s1_Q_Indexes, 0);
FillUnknown(ref values2, ref s2, ref s2_Q_Indexes, 0);
، استدعاء الدالة التكرارية (Recursive Method)
سنشرح ماذا تفعل هذه الدالة بالتفصيل لاحقا .
ولكن هذه الدالة باختصار ـ تملأ الـ 2 لست بجميع القيم المحتملة للعينة.
5:
PHP كود :
//(حذف المكرر + الترتيب من الاصغر (لتحقيق شرط الاقرب الاصغر
values1 = values1.Distinct().OrderBy(s => s).ToList();
values2 = values2.Distinct().OrderBy(s => s).ToList();
الشرط الذي جنن الجميع ، شرط جلب الاقرب الاصغر عند تساوي الفرق
هنا استعملنا احدى تقنيات الدوت نت ، Linq ، واستخدمنا Distinct لحذف القيم المكررة
واستخدمنا OrderBy للترتيب من الاصغر للاكبر .
هذين الكودين مجرد تمهيد للكود القادم ...
6:
PHP كود :
//جلب الفرق الاقرب
int min = int.MaxValue, min_S1 = 0, min_S2 = 0;
values1.ForEach(v1 => values2.ForEach(v2 =>
{
int absoluteMin = Math.Abs(v1 - v2);
if (min > absoluteMin)
{
min_S1 = v1;
min_S2 = v2;
min = absoluteMin;
}
}));
هنا استعملنا Linq مجددا (كم اشفق على اللغات التي لايوجد لديها Linq )
>> والهدف من الكود واضح
وهو الدوران على اللستة الاولى
، وعند كل دورة
، يتم الدوران على اللستة الثانية وحساب الفرق في القيم.
7:
PHP كود :
//اضافة اصفار اذا كان الناتج اقل من طول المدخل
string out_S1 = min_S1.ToString().PadLeft(s1.Length, '0');
string out_S2 = min_S2.ToString().PadLeft(s2.Length, '0');
return string.Format("{0} : {1}", out_S1, out_S2);
النهاية الدراماتكية عند هذه الاكود ، فبعد جلب قيم s1 وs2 الاصغر والاقرب ، هنا اول سطرين يقومان بمعادلة طول الoutput مع طول الInput من خلال اضافة الاصفار..
مثلا :
3??:?2?
يجب ان يظهر:
023:023
وليس
23:23
واخيرا يتم ارجاع الناتج الى الدالة الرئيسية في البرنامج وهي main لتقوم بطباعة الناتج المرجع.
3- الدالة القلب في الخوارزمية
واخيرا ، نعرض الدالة المسؤولة عن ملأ علامات الاستفهام بشكل صحيح ، وهي دالة Recursive وقد تم شرح قصة الـ Recursive Method في المقالة التالية :
PHP كود :
//Recursive Function - دالة تستدعي نفسها
static void FillUnknown(ref List<int> values, ref string s, ref int[] qmarksIndexes, int startIndex)
{
for (; startIndex < s.Length; startIndex++)
{
if (qmarksIndexes.Contains(startIndex))
{
for (int c = 0; c <= 9; c++)
{
//استبدال موقع علامة الاستفهام بمتغير اللوب
s = s.ToString().ReplaceAt(startIndex, c.ToString());
values.Add(int.Parse(s.WithoutQMarks()));
//الاستدعاء الذاتي للدالة ، مع زيادة الاندكس
FillUnknown(ref values, ref s, ref qmarksIndexes, startIndex + 1);
}
}
}
}
يمكنكم تتبع الدالة سطرا سطرا لتعرفون كيف تعمل ، ولكن هذه الصورة تشرح لكم كيف تعمل بشكل بسيط جدا :
Now s1 List Filed with all possible values
ويتم استدعاء الدالة مرة اخرى لجلب جميع القيم المحتملة لs2 وتخزينها في الValues2 لست 
--
المشروع :
[
attachment=12776]
تم -
الرجاء من الجميع ارفاق السورس كود