المسافرون ، مرحبا.
إذا قرأت هذا ، فإنني أقترح استمرار المادة "المسلية" التي كتبتها من قبل. إذا اتبعت القليل من التفكير ، الذي تفرع إلى ثلاث مقالات ، ولكن الرسالة الرئيسية كانت ، فقط لإظهار الاهتمام بالنهج التعريفي. لسبب ما ، هذا ليس رائعًا ، كما لو أن eSCuel لم يصبح متاحًا وإلزاميًا للجمهور ، لأنه بدونه من المستحيل التفكير في كيفية معالجة البيانات بشكل مختلف. صحيح ، من الأفضل صياغة المهمة وعدم القلق بشأن ما يترجم هذا.
دعنا نبدأ في العمل ، كتبت قبل ذلك عن محاولة الترفيه عنك ، لذلك سأستمر في عرض مثال على استخدام المقدمة ، على الرغم من أن المقالات السابقة أظهرت أن الاهتمام بالثعبان وحتى الذهاب سيثير الاهتمام فورًا لألفي شخص ، هذا الاهتمام بالأخبار حول بطارية جديدة لتيسلا، هو لوحظت وجهات النظر stotysch، ولكتابة البرامج على razrabotnichestskom المدخل ليس عدد قليل جدا، وينظر وراء هذا السلوك على قراءة التعليقات، وربما خمسة منهم، وبعد القراءة الثانية لهذا إيش اقتراح فإنه يخلط بين فكرة أنه ينبغي قراءة المزيد ...
اتضح أن فرضية الفائدة لم تتحقق ، وبعد ذلك فقط أظهر كيفية استخدام المقدمة ، إنها أداة حديثة ومتطورة وموزعة بحرية ، يمكن أخذها وصياغتها ، فقط بحيث يمكن صياغتها لرؤية ميزة.
سأقول أن السفر عبر الزمن غير موجود ، لكننا سنذهب قبل أسبوع ، كان هناك كتابًا مثيرًا للاهتمام حول ثلاثة أجزاء في الشريط ، حيث تم التطرق إلى موضوع حل مشكلة جديدة تم العثور عليها بشكل عشوائي ، وأخذ هذا الموقع المثير للاهتمام ، وأصعب مهمة (فقط لا تحول سلسلة إلى رقم)) ، سأحاول القيام بذلك في Prolog .
توقف عن زيادة الاهتمام ، بدءًا من ...
يسمى تسلسل الأرقام الحسابي إذا كان يتكون من ثلاثة عناصر على الأقل وإذا كان الفرق بين أي عنصرين متتاليين هو نفسه.
على سبيل المثال ، هذه هي تسلسلات حسابية:
1 ، 3 ، 5 ، 7 ، 9
7 ، 7 ، 7 ، 7
3 ، -1 ، -5 ، -9
التسلسل التالي ليس حسابيا.
1 ، 1 ، 2 ، 5 ، 7
بشكل عام ، يجب الحفاظ على الفرق بين الجارتين ، فقط بحاجة للتحقق من ذلك؟
اقرأ:
يتم إعطاء صفيف بدون فهرسة A يتكون من أرقام N. شريحة المتتابعة لهذا الصفيف هي أي تسلسل للأعداد الصحيحة (P0 ، P1 ، ... ، Pk) بحيث يكون 0 ≤ P0 <P1 <... <Pk <N.
تسمى شريحة التتابع (P0 ، P1 ، ... ، Pk) للصفيف A الحساب إذا كان التسلسل A [P0] ، A [P1] ، ... ، [Pk-1] ، A [Pk] حسابي . على وجه الخصوص ، هذا يعني أن k ≥ 2.
يجب أن تُرجع الدالة عدد شرائح التتابع الحسابية في الصفيف A.
رائع ، تحتاج إلى معرفة عدد الشرائح التي يمكنك تلبيتها ، وعدد الخيارات للقوائم الفرعية التي يمكنك العثور عليها ، بحيث لا يختلف الفرق بين العناصر المتجاورة.
يبدو الأمر كما لو كانت القوائم الفرعية في مجموعة واحدة كبيرة من جميع التباديل في قائمة الإدخال.
مثال:
الإدخال: [2 ، 4 ، 6 ، 8 ، 10]
الإخراج: 7
شرح:
جميع شرائح التتابع الحسابية هي:
[2،4،6]
[4،6،8]
[6،8،10]
[2،4،6،8]
[4،6،8،10]
[2،4،6،8،10]
[2،6،10]
أنا أعرف كيف أعبر عن قائمة فرعية في مقدمة ، هذا:
sublists(InputList, SubList):- append(Prefix,Root,InputList), append(SubList,Suffix,Root).
كيفية التحقق من أن قائمة النوع المطلوب ضرورية لتسجيل ثلاثة أضعاف:
is_seq(A,B,C]):-AB =:=BC. is_seq(A,B,C|Tail]):-AB =:=BC, is_seq(B,C|Tail]).
إذا قمنا بتجاهل التباديل لجميع عناصر القائمة ، فقد تبين أن هذه ليست مجرد قائمة فرعية للعناصر التي تقف في مكان قريب ، بل إنها قائمة فرعية تم تشكيلها مع حذف العناصر.
ثم ضعها على النحو التالي:
seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1).
ستعيد مثل هذه القاعدة جميع القوائم الفرعية المحتملة من القائمة ، ولكنها يمكن أن تبدأ من عنصر واحد ، أو تخطيها ، من العنصر التالي ، كما يمكن التخلص من أي كمية في النهاية.
في المجموع ، نحصل على عدد مبالغ فيه من الحلول ، ومن الواضح على الفور أن القائمة الفارغة ستعود عدة مرات ، ولا يمكن تجنب التكرار عندما يتم تجاهل العناصر من النهاية.
بعد مراجعة الاختبارات المقترحة لهذه المشكلة ، اتضح أنه قد تكون هناك قيم مكررة عند الإدخال ، وأنه بالنسبة لهذه القائمة [0،1،2،2،2] يجب أن يكون هناك 4 حلول. يمكن أخذ كل 2-كا بشكل منفصل ، ويجب اعتبار ذلك كشريحة منفصلة ، لذا فإن ثلاثة خيارات [0،1،2] وخيار واحد [2،2،2] مناسبة.
هذا سوء الحظ ، لأن مولد التسلسل سينتج قيمًا مكررة ، ولكن كيف تجعل الحساب فريدًا فقط؟ سيكون عليك وضع علامة عليها ، وجعل القوائم مختلفة عن بعضها البعض. سأبني الحل بالكامل على أساس إنشاء القوائم والتحقق من الحالة واحتساب عدد الحلول. وماذا تفعل مع تكرار القرارات ...
سأقوم بعمل ترقيم بسيط للعناصر ، ودع القائمة تتحول إلى قائمة مكونات / فهرس القيمة ، وهو مصطلح منظم ، وهذا ما يسمونه. بالنسبة للمثال أعلاه ، سيكون هذا [0 / 1،1 / 2،2 / 3،2 / 4،2 / 5]. ستكون جميع التسلسلات الناتجة عن هذا الإدخال مختلفة.
لذا ، يمكنك تحويل القائمة إلى قائمة مميزة:
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).
حسنًا وأهم نقطة ، التحقق من الحساب is_seq ، بعد سلسلة من المحاولات ، مع مراعاة القائمة المميزة ، تحولت هذه القاعدة إلى تعبير معقد إلى حد ما. هنا نتحقق من أن الأرقام الثلاثية تتوافق مع الحالة ، ونحسب مفتاح هذا الحل الخاص ، لاستبعاد الحلول الفريدة ، كان هناك حاجة إلى مفتاح ، سيساعد ذلك في جمع جميع المفاتيح في قائمة ثم عدها.
عند الإدخال قائمة مميزة ، سيكون الناتج هو القيمة الرئيسية ، احسبها كعدد صحيح تمثل أرقامه مجموع القيمة + الفهرس لكل عنصر.
%is_seq , , is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K).
لحساب جميع الحلول ، سأستخدم القدرة المضمنة لتحقيق الهدف وجمع جميع الحلول الفريدة في قائمة setof (). مجرد تجميع قائمة بجميع التسلسلات التي تبين أنها غير فعالة تمامًا ، من هنا جاءت فكرة المفتاح كقيمة أبسط:
get_number(List,N) :- label(List,ListL,1), setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result), length(Result,N),!. get_number(_,0).
بالطبع ، لم يتم التعبير عن الأداء بشكل خاص في مثل هذا الحل.
في ما يلي نص كامل للبرنامج ، مع قائمة بالاختبارات ، يتم اصطيادها من الموقع مع المهمة (هذا مجرد جزء من الاختبارات):
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1). seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1). is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K). get_number(List,N) :- label(List,ListL,1),setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result), length(Result,N),!. get_number(_,0). %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %all test :-assert_are_equal(get_number([2,4,6,8,10],7),true). :-assert_are_equal(get_number([],0),true). :-assert_are_equal(get_number([1],0),true). :-assert_are_equal(get_number([1,2],0),true). :-assert_are_equal(get_number([1,2,3],1),true). :-assert_are_equal(get_number([1,2,3,4],3),true). :-assert_are_equal(get_number([1,2,3,4,5],7),true). :-assert_are_equal(get_number([1,2,3,4,5,6],12),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7],20),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8],29),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9],41),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9,10],55),true). :-assert_are_equal(get_number([2,2,3,4],2),true). :-assert_are_equal(get_number([0,1,2,2,2],4),true). :-assert_are_equal(get_number([0,2000000000,-294967296],0),true). :-assert_are_equal(get_number([1,1,1],1),true). :-assert_are_equal(get_number([1,1,1,1],5),true). :-assert_are_equal(get_number([1,1,1,1,1],16),true). :-assert_are_equal(get_number([1,1,1,1,1,1],42),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1],99),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1],219),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1],466),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1],968),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1],1981),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1],4017),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1],8100),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1],16278),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],32647),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],65399),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],130918),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],261972),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],524097),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],1048365),true).
نتيجة مخيبة للآمال ، هذه الكفاءة هنا:
get_number([2, 4, 6, 8, 10], 7)->ok:0/sec get_number([], 0)->ok:0/sec get_number([1], 0)->ok:0/sec get_number([1, 2], 0)->ok:0/sec get_number([1, 2, 3], 1)->ok:0/sec get_number([1, 2, 3, 4], 3)->ok:0/sec get_number([1, 2, 3, 4, 5], 7)->ok:0/sec get_number([1, 2, 3, 4, 5, 6], 12)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7], 20)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8], 29)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8, 9], 41)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 55)->ok:0/sec get_number([2, 2, 3, 4], 2)->ok:0/sec get_number([0, 1, 2, 2, 2], 4)->ok:0/sec get_number([0, 2000000000, -294967296], 0)->ok:0/sec get_number([1, 1, 1], 1)->ok:0/sec get_number([1, 1, 1, 1], 5)->ok:0/sec get_number([1, 1, 1, 1, 1], 16)->ok:0/sec get_number([1, 1, 1, 1, 1, 1], 42)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1], 99)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1], 219)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1], 466)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 968)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1981)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4017)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 8100)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 16278)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 32647)->ok:1/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 65399)->ok:1/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 130918)->ok:3/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 261972)->ok:6/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 524097)->ok:12/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1048365)->ok:27/sec
يعد جمع قائمة ، حتى مفاتيح القرار فقط ، أمرًا مرهقًا للغاية ، ولكن هذا قرار تعريفي ، والذي بدونه لا يمكن حساب جميع الحلول الفريدة.
الخلاصة.
هذه هي الطريقة التي تصاغ بها المهام في لغة برولوج ؛ ببساطة نقل بيان المشكلة إلى البرنامج محفوف بالكفاءة غير الكافية. أو ربما في هذه المشكلة يتوفر حل خوارزمي فقط؟ ما مدى تعقيد العملية؟
مرة أخرى أترك الأسئلة ...
على الرغم من ذلك ، فإن البحث عن إجابات مثير للاهتمام في مهنتنا ، أليس كذلك؟