سؤال سهل جداً, و لكن هناك خدعة!

[Khaled Alshaya 826]

السلام عليكم ...

استغرقت في حل هذا السؤال أقل من دقيقة على غير العادة :cool:. السؤال بسيط جداً و سهل, و لكن حاول اقتراح خوارزمية جيدة لحل السؤال.

تصور أن لدينا قيمتان متكررتان في مصفوفة من حجم n. بحيث أن القيمة الأولى بتكراراتها موجودة في القسم الأول من المصفوفة و القيمة الثانية بتكراراتها موجودة في القسم الثاني من المصفوفة. مثلاً, قد يكون لدينا أعداد زوجية و أعداد فردية:

1 9 8 6 2 0

قد تكون الأعداد الزوجية قبل الأعداد الفردية و لكن كلا النوعين منفصلان عن بعضهما و يبدأ الآخر مع نهاية الأول. الآن, نحن نعلم:

حجم المصفوفة: n من العناصر.

عدد عناصر النوع الأول: غير معروف. (نريد حسابه)

عدد عناصر النوع الثاني: غير معروف. (نريد حسابه)

ماهو عدد عناصر كلا النوعين؟ في مثالنا, النوع الأول عنصران, و النوع الثاني أربعة عناصر.

فكر في السؤال جيداً, و اطرح أفضل خوارزمية لديك :)

تم تعديل 13 Mar 2012 بواسطه Khaled.Alshaya

[DeltaAziz.com 23]

السلام عليكم ...

وعليكم السلام ورحمة الله

كيف الحال اخي خالد ان شاء الله بخير

محاولة على السريع

لننظر ماذا لدينا من معلومات على الطاولة

n عدد العناصر معروف

العناصر مرتبة مجموعة بجهة والثانية بالجهة الاخرى

هذا يعني او وجدناا عدد المجموعة الاولى فالثانية هي n ناقص هذا العدد

ربما الخدعة هي عدم معرفة من اي نوع ننطلق

لذلك نستخدم منغير منطقي Boolean نسميه b

ننشى function تعطينا صحيح او خطا في حالتنا عدد زوجي

ننطلق من أول عنصر - نستخدم متغير i كدليل على العنصر

نستدعي دالة التحقق ونحتفظ بالنتيجة بالمتغر المنطقي b

نكرر عملية التحقق ونضيف واحد للدليل i حتى نحصل على نتيجة مغاير لb

عند توقف الحلقة تكون لدينا النتيجة

عدد عناصر المجموعة الاولى قيمة المتغير i

عدد عناصر المجموعة الثانية نتيجة طرح i من n

وهذه كود بباسكال/دلفي

Const
  n=6;
  A:array[0..n-1]of integer= (1,9,8,6,2,0);
Var
  i: integer;
  b: Boolean;
begin
  i:=0;
  b:=odd(A[i]);
  repeat
    i:=i+1;
  until b<>odd(A[i]);
  ShowMessage('Groupe1 '+IntToStr(i));
  ShowMessage('Groupe2 '+IntToStr(n-i));
end;

[daziplqa 559]

ننشى function تعطينا صحيح او خطا في حالتنا عدد زوجي

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

[Ala2 VB 95]

قراءة أول عدد في المصفوفة (مثلاً زوجي) ويكون المطلوب البحث عن عكسه

بمعرفة عدد العناصر n يمكن تقسيم المصفوفة إلى قسمين واختبار العنصر الذي في المنتصف

إذا كان زوجي نستبعد البحث في الناحية اليسرى من المصفوفة (بين المنتصف والعنصر الأول)

تقسيم الناحية اليمنى إلى قسمين والتحقق من العنصر الذي في المنتصف , وبالتالي يتم استبعاد البحث ضمن مجموعة كبيرة من الأعداد

أما إذا كان فردي , نقسم الناحية اليسرى ونستبعد اليمنى

وهكذا ..

بالطبع هناك متغير يتم زيادته أو إنقاصه بمقدار معين لإبقاء موقع البحث الحالي في المصفوفة محفوظاً

الفكرة أقرب إلى خوارزمية Binary Search كما ترون :)

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

يمكن اعتبار دالة التحقق من الشرط متوفرة مسبقاً -بغض النظر عن ما هو الشرط تحديداً- , فقد فهمت أن المهم هو كيفية حساب عدد كل نوع

تم تعديل 14 Mar 2012 بواسطه Delphawi

[Khaled Alshaya 826]

نور المنتدى أخي B.M.AbdelAziZ :cool:

حل الأخ Delphawi هو الأفضل حقيقة, و هذا ما كنت أشير إليه بالخدعة أي أن البيانات مرتبة أصلاً. كل ما علينا هو إيجاد نقطة النهاية للنوع الأول باستخدام binary_search في الاتجاهين.

تحياتي...