الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

ممكن توضيح هذا السؤال؟

بدأه الاخير زمانه في 6 فبراير 2012 · 5 رد · 479 مشاهدة · في الرياضيات والخوارزميات
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم

في كتاب الخوارزميات - يوجد هذا السؤال

Design a theta(n lg n)-time algorithm that, given an array A of n integers
and another integer x, determines whether or not there exist two (not necessarily
distinct) elements in A whose sum is exactly x.

انا حسب فهمي للسؤال - كتبت خوارزمية هكذا

for i=1 --> n
no = A
for j=i+1 --> n

if no + A == x
return true


return false

الخوارزمية كتبتها على عجالة ولم يتسنى لي التأكد من صحتها بعد

لكن سؤالي هو - وجدت مجموعة حلول على النت لهذا السؤال

وهذا واحد منها

1 Merge-Sort(A)
2 i   1
3 j   length(A)
4 while i  j
5 if A + A[j] equals x
6 return A,A[j]
7 if A + A[j] < x
8 then i   i + 1
9 if A + A[j] > x
10 then j   j − 1

انا لم افهم هذا الحل - كل الحلول التي وجدتها تقوم بترتيب المصفوفة - وطريقة الجمع غريبة - لماذا يجمع اول و اخر رقم؟

هل انا فاهم السؤال خطأ؟!!

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#2

لأ مش غلط ولا حاجة بس الفكرة إنك كتبت خوارزمية من O(n2) مما يعنى أنها ليست theta(nlogn).

بصراحة طريقة الجمع تبدو غريبة و لست متأكدا من أنها ستنجح, هل جربتها؟

كيف تسأل الأسئلة بطريقة ذكية

#3

شكرا على الرد اخي - فعلا انا لم اخذ بنظر الاعتبار جعل الخوارزمية من نوع theta(n lg n).

لا صراحة لم اجرب الخوارزمية لاني لم افهمها اساسا.

هل ممكن ان اعدل على الطريقة الخاصة بيي التي كتبتها في الاعلى لتصبح من نوع n lg n ؟؟

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#4

السلام عليكم

أخي العزيز الخوارزمية التي وجدتها بسيطة و ليست من الصعوبة بمكان لنبدأ بها سطراً سطراً:

Merge-Sort(A)

تعقيدها من رتبة n log n

الآن لدينا المصفوفة مرتبة تصاعدياً :

اقتباس
if A + A[j] < x

then i i + 1

إذا كان مجموع العنصر الأصغر (i دليل أول عنصر في المصفوفة في الحالة الابتدائية) و العنصر الأكبر (j دليل آخر عنصر في الحالة الابتدائية) أصغر من العدد المطلوب و بالتالي يتوجب علينا زيادة مجموع الرقمين و بالتالي زيادة الـ i لأن الـ j هو دليل العنصر الأكبر (أي آخر عنصر) و لا يمكن زيادته (في الحالة البتدائية) و لا معنى لزيادته في الحالات الأخرى -عليك بتجريب مثال عددي لتتضح لك الأمور-

اقتباس
if A + A[j] > x

then j j − 1

إذا كان مجموع العنصر الأصغر و العنصر الأكبر أكبر من العدد المطلوب يتوجب علينا إنقاص المجموع و ذلك باختبار مجموع العنصر قبل الأخير (أي ثاني أكبر عنصر) مع العنصر الأصغر و الذي هو الأول في الحالة البدائية

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

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

ملاحظة :

theta في أسوأ الحالات يساوي n/2 و في أفضل الحالات هو 1

1
#6
الاخير زمانه كتب:

و عليكم السلام

جزاك الله خيرا اخي على التوضيح

وإياكم أخي

مواضيع مشابهة