الشبكة العربية لمطوري الألعاب

محترف مشرف عبد اللطيف حاجي علي مشاركة 1

سؤال جديد.. هذه المرة سأحاول أن يكون سهلاً

اللغة: أي لغة عدا لغتي التجميع والآلة (الكود المرفق بالـ C++ كمثال فقط)
الصعوبة: متوسط
المطلوب: حل
الشرح:

أكمل البرنامج التالي:
#include 
#include 
#include 

typedef std::vector IntArray;

void Swap(int &x, int &y)
{
	// Write code here (1)
}

void MinMax(const IntArray& arr, int& min, int& max)
{
	min = std::numeric_limits::max();
	max = std::numeric_limits::min();
	for (IntArray::const_iterator itr=arr.begin();itr!=arr.end();itr++)
	{
		int cur = *itr;
		// Write code here (2)
	}
}

أي اكتب إجرائين الأول يقوم بتبديل قيمة متغيرين من نوع int. والثاني يقوم بإيجاد العددين الأكبر و الأصغر من مصفوفة.
ما رأيكم؟ ماذا؟ أين الحيرة في الموضوع؟ ممم.. لماذا تحبون أن تعقدوا الأمور البسيطة؟
حسناً. أكتب إجراء Swap دون استخدام أي متغير مؤقت. واكتب إجراء MinMax دون استخدام أي if وغير ذلك من التعليمات الشرطية
طبعاً لا يجب أن تستخدم إجراءات من مكاتب أخرى (بما فيها std).

يمكنك تعديل الـ code بما يناسب الحل (مع أن ذلك ليس ضرورياً في الحل الذي جهزته)

عبد اللطيف حاجي علي
مبرمج
In|Framez

موهوب  عبدالله الشمّري مشاركة 2

بالنسبة للـ swap , فقد مر علي هذا السؤال قبل كم سنة  :-) ,



void Swap(int &x, int &y){

x = x + y;
y = x - y;
x = x - y;
}


أما السؤال الاخر .. فلا أعرف حل دون استخدام ( : ) , أو قد يكون حل يتعلّق بالبت من عنوان الموضوع :-) , لا أعرف هل هذا من ضمن الجمل الشرطية الممنوعة :

void MinMax(const IntArray& arr, int& min, int& max)
{
	min = std::numeric_limits::max();
	max = std::numeric_limits::min();
	for (IntArray::const_iterator itr=arr.begin();itr!=arr.end();itr++)
	{
		int cur = *itr;
                min = ( cur <min):cur,min>                max = ( cur >max):max,cur ); 

	}
}

--
طالب - تخصص نظم معلومات .
--

محترف مشرف عبد اللطيف حاجي علي مشاركة 3

حل الـ swap الذي ذكرته حل جيد جداً ويعمل في معظم الحالات. لكن هناك بعض الحالات التي لا يعطي فيها نتائج صحيحة. وذلك عندما يكون مجموع قيمة الرقمين لا يمكن تمثيله بـ 32 بت. هناك حل آخر مشابه جداً (جداً وجداً أخرى) لحلك ويعمل في جميع الحالات. هل يمكنك إيجاده؟



أما في 03 آذار 2009 08:00 م، فقد تنهد الشمري بارتياح وهو يرد:

فلا أعرف حل دون استخدام ( : ) , أو قد يكون حل يتعلّق بالبت من عنوان الموضوع :-)
للأسف فإن استخدام تعملية (:?) يعتبر استخداماً لجملة شرطية. هناك حل آخر لا يستخدم أي جملة من هذا النوع. وهو بالفعل يعتمد على تلاعب ذكي بالبتات كما قلت (الحل الأول كذلك).
يجب أن أذكر هنا أن استخدام تعلميات assembly ليس وارداً طبعاً (هناك تعليمة واحدة xchg تبدل قيمتي متغيرين) سأعدل المشاركة الأساسية بما يتناسب مع ذلك.

عبد اللطيف حاجي علي
مبرمج
In|Framez

خبير  سعيد بسيوني مشاركة 4

 int cur = *itr;
 min = ( cur <min):cur,min> max = ( cur >max):max,cur ); 

أعتقد انك بتقصد العبارة دي:


min = (cur < min) ? cur : min;


😒

محترف  انس مشاركة 5

السلام عليكم

لدي اقتراح فيما يخص swap 



#define swap(a,b) ( (a ^= b ) ,( b^=a ),(a ^= b ) );


يمكن بكل سهولة تحويله الى دالة .

موهوب  عبدالله الشمّري مشاركة 6

وفي 07/ربيع الأول/1430 06:14 م، أعرب سعيد بسيوني عن رأيه بالموقف كالآتي:

أعتقد انك بتقصد العبارة دي:

نعم , هي دي 😄 , شكرا على التصحيح , نادرا ما اكتب بهذه الطريقة فنسيتها .



في 07/ربيع الأول/1430 06:09 م، قال عبد اللطيف حاجي علي بهدوء وتؤدة:

يجب أن أذكر هنا أن استخدام تعلميات assembly ليس وارداً طبعاً


سأحاول ان شاء الله ,

--
طالب - تخصص نظم معلومات .
--

محترف مشرف عبد اللطيف حاجي علي مشاركة 7

وفي 03 آذار 2009 09:43 م، ظهر شبح ابتسامة على وجه انس وهو يقول:

لدي اقتراح فيما يخص swap 

#define swap(a,b) ( (a ^= b ) ,( b^=a ),(a ^= b ) );
نعم بالفعل هذا هو الحل الذي كنت أنتظره (قد لا يكون الوحيد) ☺ . لكن يبدو أن مشاكل الـ assert وتعقيدها لم تقنعك بعد بخطورة استخدام الـ macros 😢
على كلٍ. لقد صادفت هذا الـ code في برنامج أحد زملائي ولكم أن تتصوري مدى دهشتي 😲 . عندما سألته عن سبب استخدامه لهذا الكود بدل الكود التقليدي الذي يعرف متغيراً مؤقتاً قال لي أن هذا يوفر ذاكرة وينفذ بشكل أسرع 😒 . وعندما سألته أسرع بكم؟ لم يستطع إجابتي كونه لم يقس سرعة أي من الطريقتين 🙁 .

في الحقيقة أردت أن أدلكم على هذه الطريقة في الـ swap، ليس كي تستخدموها في برامجكم لكن كي تتفادوها.

- فمن ناحية توفير الذاكرة:
هذه الطريقة "الذكية" توفر 4 بايتات من مساحة محجوزة أصلاً للـ stack. أي أنها لا توفر أي شيء في الحقيقة. وإن اعتبرنا ذلك توفيراً فإن ذلك يشكل 1 بالـ 10 مليارات من ذاكرة جهاز حديث اليوم 😲 .

- أما من ناحية السرعة:
فإن هذه الطريقة قد تكون أبطأ إذ أن التعليمات الثلاث تعتمد على بعضها وبالتالي يجب تنفيذها بشكل متسلسل أما الطريقة التقليدية فيمكن تنفيذ تعليمتيها الأخيرتين بشكل تفرعي. وإن افترضنا أن هذه الطريقة هي الأسرع، فكم هو هذا الإزدياد بالسرعة؟ هل يكفي ذلك لاستخدام هذه الطريقة؟ هل تشكل عملية الـ swap "عنق الزجاجة" في برنامجي؟ أم هل هناك مناطق أخرى تسترعي اهتمامي أكثر من عملية لا تنفذ إلا ما ندر؟ 😨

- ومن ناحية مقروئية الـ code:
فإن هذه الطريقة طبعاً لا يمكن فهمها من أول نظرة بعكس الطريقة التقليدية 🙁 .

- أخيراً من ناحية العمل:
فإن هذه الطريقة فيها مشكلة خطيرة وهي نتيجة تنفيذ عملية swap بين متغير والمتغير نفسه. أي
swap(x,x)
إن هذه العملية ستقوم بتصفير متغير x وضياع قيمته بدل الحفاظ عليها (نفس المشكلة في طريقة الجمع والطرح). طبعاً هذا لا يحدث في الطريقة التقليدية 😄 .
أيضاً الطريقة التقليدية يمكن تعميمها باستخدام إجراء template لتشمل جميع الأنواع ☺ . بعكس هذه الطريقة التي يمكن فقط على الأنواع التي تدعم عملية الـ XOR.

للسجل هذه هي الطريقة التقليدية:

template void Swap(T x, T y) {
    T t = x;
    x = y;
    y = t;
}

قاعدة: ليس الحل الأذكى هو دوماً الحل الأصح 😄

قد تكون هذه هي الحالة في المشكلة الثانية (min, max) وقد لا تكون 😒 . هذه ما سنراه حالما يضع أحدهم الحل ☺ .

عبد اللطيف حاجي علي
مبرمج
In|Framez

محترف  انس مشاركة 8

الشلام عليكم

بعد عناء كبير استطعت ايجاد الجواب الثاني ومع ذلك لم افهم كله نظرا لتعقيده و استخدامه عدة عمليات مختلفة على البت.

الحل :



int minMax( int * tab, int size)
{
   int i;
   int max = tab[0];
   int min = tab[0];

   for (i=1; i<size;>   {
      max ^= ( (max - tab[i]) >> 31 ) & ( tab[i] ^ max);
      min ^= ( (tab[i] - min) >> 31 ) & ( tab[i] ^ min);
   }

   printf("max = %d\nmin = %d", max, min);
   return 0;
}






و في الحقيقة ليست لي رغبة على الاطلاق في استخدام هذه الطريق في المستقبل,فهي اولا غير مفهومة من الوهلة الاولى. و ثانيا تستخدم عدة عمليات اما الطريقة المعروفة فتقوم باتحقق من الشرط فقط .... قد اكون مخطا لكن هذه الطريقة ليست ضرورية و لا اكثر فعالية ( و ان كانت اكثر فعالية فلن يكون الفرق كبيرا ).

شكرا على هذه الاسئلة 😄 .

ملاحظات :

لم اجد الحل بنفسي بل قمت بالبحث عنه  لانني لاحظت انه لم تكن هناك اجابات في المنتدى ... الحل وجدته في الموقع siteduzero.com و بالتحديد :
http://www.siteduzero.com/forum-83-379114-3506422-trouver-le-min-max-d-un-tableau.html#r3506422
 الموقع بالغة الفرنسية .

الطريقة لاتعمة لا تعمل الا مع الاعداد ذات 4 بايت (32 بت).

محترف مشرف عبد اللطيف حاجي علي مشاركة 9

نعم بالفعل هذه هي الطريقة الصحيحة (كنت على وشك وضع الحل).
 
لنبسط العملية قليلاً ولنكتب إجراءً يأخذ رقمين ويرجع رقمين الأول هو الأصغر بين الرقمين المدخلين والثاني هو الأكبر بينهما.

int MinMax(int x, int y, int& min, int &max);

لنفكر معاً. لو كان لدي طريقة أحصل فيها على متغير من نوع bool تكون قيمته صفراً إن كان الرقم الأول أكبر من الثاني و واحداً إن كان الرقم الثاني أكبر أو يساوي الرقم الأول فأني لن أحتاج العملية الشرطية أبداً حيث أنني استعضت عنها بهذا الرقم.
ثم لو وجدت طريقة أستطيع فيها اختيار أحد الرقمين بناءً على قيمة هذا المتغير فإن المسألة تعد منتهية. إذ أنني أستطيع اختيار الرقم الأكبر والأصغر.

الآن لنجب عن السؤال الأول. هل هناك طريقة للحصول على هذا المتغير؟
الأمر بسيط، اطرح الرقم الثاني من الأول فإذا كانت الرقم سالباً (إشارة السالب موجودة) كان الرقم الثاني هو الأكبر وإلا (إشارة السالب غير موجودة) فإن الرقم الأول هو الأكبر (أو الرقمان متساويان، دعونا نهمل هذه الحالة مبدئياً)

جميل، لكن كيف نترجم هذا الكلام (إشارة السالب موجودة أم لا) إلى ما تفهمه الآلة? أنت تعلم (أو يجب أن تعلم) أن الأرقام ترمز في (معظم) المعالجات باستخدام تقنية الـ 2’s complement وأحد خواصها أن البت الأخير يكون واحداً إذا كان الرقم سالباً (إشارة السالب موجودة) وإلى فيكون صفراً (إشارة السالب غير موجودة). كما أنه يمكننا باستخدام عملية إزاحة البتات الحصول على هذا البت بالذات. إذاً يمكننا عمل التالي:

unsigned int x, y;
unsigned int negative = (x-y) >> 31;

إذاً الآن حصلنا على متغير يكون قيمته 1 إذا كان y أكبر من x و 0 إذا كان x أكبر من y.
نأتي الآن للسؤال التالي. كيف يمكننا اختيار أحد الرقمين بناء على قيمة المتغير negative؟ بما أن الرقم يكون 1 أو 0 فلم لا تضربه وعكسه بالرقمين وتجمع ناتج الضرب لتحصل على الرقم المطلوب. أي كما يلي:

min = negative*x + !negative*y;

لو كانت قيمة negative مساوية لـ 1 (y أكبر من x) فإن حاصل ضرب x بـ negative تساوي x و حاصل ضرب y بعكس negative (أي القيمة 0) تساوي 0 ومجموعة الناتجين يساوي x وهو الرقم الأصغر.  في الحالة الأخرى (negative=0 و x أكبر من y)  فإن النتيجة ستكون y  (يمكنك التحقق من ذلك)
بنفس الطريقة:


max = !negative*x + negative*y;

وهكذا نكون قد حصلنا على الأكبر والأصغر بين الرقمين. المشكلة هنا هي أن هذا يستهلك أربع عمليات ضرب وهو أبطأ بكثير من عملية شرطية بسيطة. لذلك نحتاج إلى طريقة أخرى.

لنفرض أني أعطيتك متغيراً mask كل بتاته (bits) مساوية لـ 1 إذا كان y أكبر من x و مساوية لـ 0 إذا كان y أكبر من x. هل تستطيع اختيار الأكبر والأصغر بين وx وy بالاعتماد عليه؟ الأمر بسيط ومشابه جداً للطريقة السابقة.


min = (mask&x) | (~mask&y);

لو كانت جميع بتات mask مساوية لـ 1 (y أكبر من x) فإن:


mask & x = x;
~mask = 0;
~mask & y = 0 & y= 0;
x | 0 = x;   // وهو الرقم الأصغر

ولو كانت مساوية للصفر فإن min ستساوي y (تحقق من هذا). بنفس الطريقة:


max = (~mask&x) | (mask&y);

يبقى السؤال كيف نحصل على mask؟ يمكنك استخدام الطريقة التالية:

int x,y;
unsigned int mask = (x-y) >> 31;

ما الذي تختلف فيه هذه الطريقة عن طريقتنا في الحصول على negative؟ هنا نتعامل مع متغيرات من نوع int وليس unsigned int. أي أن الإزاحة حسابية وليست منطقية وبالتالي فإن بت الإشارة (البت الأخير من x-y) سيتم تكراره بدل إضافة أصفار كما هي الحالة في الإزاحة المنطقية. وبالتالي سنحصل إما على صفر (عندما x أكبر من y ويتم تكرار بت الإشارة، صفر) أو على 0xFFFFFFFF (عندما y أكبر من x  ويتم تكرار بت الإشارة، واحد). 
أي أن الحل ككل سيكون كما يلي:

int MinMax(int x, int y, int& min, int &max)
{
     unsigned int mask = (x-y) >> 31;
     min = (mask&x) | (~mask&y);
     max = (~mask&x) | (mask&y);
}

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

عبد اللطيف حاجي علي
مبرمج
In|Framez

محترف مشرف عبد اللطيف حاجي علي مشاركة 10

مرحباً... حباً... حباً... بأً... 😲
هل من أحد هناك في الخارج؟
تباً. أمقت الوحدة الموحشة 😭

حسناً. لننهي المسألة بتحديد الاختلاف بين الطريقة التي طرحتها والطريقة التي طرحها أنس.
نلاحظ أولا أن حساب الـ mask متكافئ في الطريقتين. حيث أن السطر:
max ^= ( (max - tab[i]) >> 31 ) & ( tab[i] ^ max);

مكافئ لـ :
int mask = (max - tab[i]) >> 31;
max ^= mask & (tab[i] ^ max);

بقي أن نجد العلاقة بين طريقة أنس وطريقتي (الكلام بالمجاز هنا ☺ ). في الحقيقة العلاقتان متكافئتان والتالي يبرهن ذلك (لا ترتعب، الأمر أسهل مما يبدو عليه ☺ ، تابع العمليات واحدة تلو الأخرى وإن وجدت أحداها غير مفهومة ضع سؤالاً وسأحاول شرحها بالتفصيل 😄 ). لاحظ أن التعليقات تحدد القوانين المستخدمة في العملية التالية.
حسناً أشرب كوباً من الشاي وفكر معي 😒 :
result ^= mask & (y^x);

// (p ^= q) <=> (result = p ^ q)
result = x ^ (mask & (y^x));

// (p ^ q) <=> (~p&q) | (p&~q)
result = (~x & (mask & (y^x))) | (x & (~mask | ~(y^x)));

// ~(q ^ p) <=> (q ^ ~p)
result = (~x & mask & (y^x)) | (x & (~mask | (y^~x)));

// (p ^ q) <=> (~p&q) | (p&~q) مرتان
result = (~x & mask & ((~y&x) | (y&~x))) | (x & (~mask | ((~y&~x) | (y&x))));

// توزيع & على |
result = ((~x&mask&~y&x) | (~x&mask&y&~x)) | (x & (~mask | (~y&~x) | (y&x))));

// ~p&p <=> 0
// p&p <=> p
// 0 | p <=> p
result = (mask&~x&y) | ((x&~mask) | (x&~y&~x) | (x&y&x));

// ~p&p <=> 0
// p&p <=> p
// 0 | p <=> p
result = (mask&~x&y) | (x&~mask) | (x&y);

// توزيع الـ | على الـ &
result = (mask&~x&y) | (((x&~mask)|x) & ((x&~mask)|y));

// (p & q) | p <=> p
result = (mask&~x&y) | (x & ((x&~mask)|y));

// توزيع الـ | على الـ &
result = (mask&~x&y) | (x & (x|y) & (~mask|y));

// p & (p|q) <=> p
result = (mask&~x&y) | (x & (y|~mask));

// توزيع & على |
result = (mask&~x&y) | (x&y) | (x&~mask);

// إخراج y من القوسين
result = (y & ((mask&~x) | x)) | (x&~mask);

// (p&~q) | q <=> p|q
result = (y & (x|mask)) | (x&~mask);

// توزيع & على |
result = (y&x) | (y&mask) | (x&~mask);

// q & 1 <=> q
// 1 <=> (p|~p)
result = ((y&x) & (mask|~mask)) | (y&mask) | (x&~mask);

// توزيع & على |
result = (y&x&mask) | (y&x&~mask) | (y&mask) | (x&~mask);

// إعادة ترتيب
result = (y&x&mask) | (y&mask) | (y&x&~mask) | (x&~mask);

// (p&q) | p <=> p
result = (y&mask) | (x&~mask)

الآن خذ نفساً عميقاً وأعد من البداية ☺

عبد اللطيف حاجي علي
مبرمج
In|Framez