• الإعلانات

    • فيصل الحربي

      تسجيل عضوية جديدة في المنتدى   01/31/2016

      السلام عليكم ورحمة الله وبركاته  عزيزي العضو الجديد :  حاليا رسالة الإيميل لتأكيد صحة إيميلكم تذهب للبريد العشوائي ( جاري حل المشكلة )  فإذا لم تجد رسالة التحقق من إيميلكم في صندوق الوارد لديكم إتجه للبريد العشوائي ( JUNK)  وقم بتفعيل إشتراككم من هناك   

البحث في المنتدى

Showing results for tags 'upper_bound'.

  • البحث بالتاقات

    اكتب الكلمات المفتاحيه بينها علامه الفاصله
  • البحث بكاتب الموضوع

تم إيجاد 1 نتيجة

  1. السلام عليكم ورحمة الله وبركاته   لتكن لدينا القائمة التالية : 1 2 7 9 5 3 4 نقول أن 2 هي الحد العلوي للـ 1 , والـ7 هو الحد العلوي للـ 5 , ببساطة لو قمنا بترتيب القائمة فإن الحد العلوي لقيمة ما هو القيمة التي تليها في القائمة ( من أجل قائمة لا تحوي عناصر متكررة )   يعيد لنا التابع std::upper_bound الموجود في المكتبة  algorithm مؤشراً أو iterator للحد العلوي لقيمة ما داخل قائمة مرتّبة, (أي : مؤشراً لأصغر قيمة ممكنة أكبر تماماً من قيمة الوسيط )   لو : بفرض أننا نبحث عن الحد العلوي للقيمة x : لو كانت القيمة x أكبر من أكبر قيمة في القائمة فإن التابع سيعيد مؤشراً إلى ما بعد نهاية القائمة وعندها لا يجوز محاولة الوصول إلى محتوى ما يشير إليه المؤشر لأن ذلك سينتج undefined behavior لو كانت القيمة x  أصغر من أصغر قيمة في القائمة فسيعيد التابع مؤشراً إلى أصغر عنصر في القائمة (حالة طبيعية ) لو كانت القيمة x غير موجودة في القائمة إلا أنها ليست إحدى الحالتين السابقتين فإن التابع يعيد مؤشراً إلى أصغر قيمة موجودة أكبر من x لو كانت القيمة x موجودة فإن التابع يعيد مؤشراً إلى القيمة التي بعدها , مما يعني أنه في حال كانت القيمة x موجودة في نهاية القائمة فسيعيد التابع مؤشراً إلى ما بعد نهاية القائمة   لتلخيص جميع الحالات السابقة في عبارة واحدة نقول أن التابع upper_bound يعيد مؤشراً أو iterator إلى أول عنصر في المجال المعطى يحقق كونه أكبر من القيمة المراد البحث عنها , وإن لم يجد يعيد مؤشراً إلى ما بعد نهاية المجال .   أما أخوه الشقيق التابع std::lower_bound فعلى عكس ما يوحي به الاسم ! إنه لا يعيد مؤشراً لأكبر قيمة أصغر من قيمة معينة . يعيد التابع lower_bound مؤشراً أو iterator لأول عنصر في المجال المعطى ليس أصغر من القيمة المراد البحث عنها ,وإن لم يجد يعيد مؤشراً إلى ما بعد نهاية المجال .   تحذيرات : يجب أن تكون القائمة مرتبة وفقاً لنفس نوع المقارنة الذي سيستخدمه التابع للعثور على الحد العلوي أو السفلي .التابع upper_bound يعيد مؤشراً لعنصر أكبر تماماً من القيمة المحددة بينما يعيد lower_bound يعيد مؤشراً لعنصر أكبر أو يساوي القيمة المحددة (إن وجدت )لنبدأ بالتابع std::upper_bound : تعريف التابع : كما اعتدنا في توابع STL التي تقوم بالمقارنة فإن للتابع upper_bound تعريفان على شكل قوالب , الأول يستخدم عملية المقارنة > لمقارنة العناصر والعثور على الحد العلوي , والثاني يستخدم تابع يمرر كوسيط للمقارنة : الشكل الأول (الافتراضي) : template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);يعيد التابع  ForwardIterator يشير إلى الحد العلوي ويأخذ ثلاثة وسطاء : الوسيط الأول هو  ForwardIterator يشير للعنصر الأول في القائمة المراد البحث بداخلها . الوسيط الثاني هو  ForwardIterator يشير للعنصر الذي يلي العنصر الأخير في القائمة المراد البحث بداخلها . الوسيط الثالث هو العنصر المراد على العثور على الحد العلوي له . أي أن أول وسيطين يحددان المجال المراد البحث فيه من first إلى ما قبل last . الشكل الثاني للتابع (المخصص ) : template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);يضاف له وسيط رابع هو تابع مقارنة (يمكن أن يكون تابعاً عادياً يعيد قيمة bool أو functor كما في greater<int>()l أو تعبير lambda .. يمكنك مراجعة الموضوع التالي للمزيد عن طرق تعريف الوسيط compare )   إن جسم التابع مكافئ للجسم التالي : template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val){ ForwardIterator it; iterator_traits<ForwardIterator>::difference_type count, step; count = std::distance(first,last); while (count>0) { it = first; step=count/2; std::advance (it,step); if (!(val<*it)) // or: if (!comp(val,*it)), for version (2) { first=++it; count-=step+1; } else count=step; } return first;}لاحظ وجود عملية بحث ثنائي داخل القائمة .   هذا مثال على استخدام التابعين من المرجع: // lower_bound/upper_bound example#include <iostream>     // std::cout#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort#include <vector>       // std::vectorint main () {  int myints[] = {10,20,30,30,20,10,10,20};  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30  std::vector<int>::iterator low,up;  low=std::lower_bound (v.begin(), v.end(), 20); //          ^  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^  std::cout << "lower_bound of 20 " << *low << '\n';  std::cout << "upper_bound of 20 " << *up  << '\n';  return 0;}إذا كانت القائمة لا تسمح بالوصول العشوائي non-random-access فإن التابع سيستغرق زمناً (O(N للوصول إلى الحد العلوي أو السفلي , أما إن كانت تدعم الوصول العشوائي فسيتم إجراء مقارنة log2(N)+1 مقارنة .   لننتقل إلى التابع lower_bound : تعريف التابع : مثل سابقه بشكلين , والوسطاء لها نفس الدلالات الشكل الافتراضي : template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);الشكل المخصص : template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);كما ذكرنا سابقاً فهو يعيد مؤشراً لأول عنصر في المجال من first إلى ما قبل last يحقق كونه ليس أصغر من val (لو كانت val أكبر من جميع العناصر سيعيد last )   يمكن أن يكون شكل جسم التابع مكافئ لما يلي : template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val){ ForwardIterator it; iterator_traits<ForwardIterator>::difference_type count, step; count = distance(first,last); while (count>0) { it = first; step=count/2; advance (it,step); if (*it<val) { // or: if (comp(*it,val)), for version (2) first=++it; count-=step+1; } else count=step; } return first;}تحذير : لا يجوز استخدام عملية الـ* للوصول إلى محتوى المؤشر أو الـ iterator إلا إذا كان لا يساوي last (أي يجب التأكد من صلاحية المؤشر أولاً ) والآن لننتقل إلى الجزء الماتع , توظيف التابعين :   1- استخدام lower_bound للبحث الثائي , بل وأفضل : عندما نحتاج البحث عن عنصر ما , فإن البحث الثنائي من أسرع خوارزميات البحث بزمن (log2(N ولكن للأسف , يعيد التابع std::binary_search يعيد فقط true أو false للدلالة على وجود أو عدم وجود القيمة المراد البحث عنها , فكيف يمكننا الوصول للقيمة ؟ أو رقمها في الفهرس ؟ أو القيمة التي قبلها ؟ كل هذا من وظيفة التابع lower_bound تذكرة : يعيد lower_bound مؤشراً لأول عنصر أكبر أو يساوي العنصر الذي نبحث عنه (إن وجد) مثال : // lower_bound/upper_bound example#include <iostream>     // std::cout#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort#include <vector>       // std::vectorint main (){    int myints[] = {4,2,3,5,7,8,9,1};    std::vector<int> v(myints,myints+8);    std::sort (v.begin(), v.end());    for(auto x:v)        std::cout<<x<<" ";    std::cout<<std::endl;    for(int y=0; y<10; y++)    {        int index=lower_bound (v.begin(), v.end(), y) - v.begin();        if(v[index]==y)            std::cout<<y<<" is exist with index : "<<index<<std::endl;        else            std::cout<<"we can't find "<<y<<" but the first bigger is "<<v[index]<<std::endl;    }    return 0;}للتأكيد على أن التابع يستخدم البحث الثنائي , لنقم بما يلي : 1- تعريف تابع مقارنة خاص , يحوي بداخله تابع لطباعة العددين الذين يتم مقارنتهما 2- استدعاء الشكل المخصص للتابع وتمرير تابع المقارنة له . 3- تمرير مصفوفة من 32 عنصرأ والبحث عن العنصر الأخير (الحالة الأسوأ) ويجب ان ينفذ التابع فقط 5 مقارنات .   راقب وافهم عمل الكود التالي : // lower_bound/upper_bound example#include <iostream>     // std::cout#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort#include <vector>       // std::vectorbool comp(const int&a,const int&b){    std::cout<<a<<" "<<b<<std::endl;    return a<b;}int main (){    std::vector<int> v(32);    for(int i=0;i<32;i++)        v[i]=i;    lower_bound (v.begin(), v.end(),31,comp);    return 0;} بالمناسبة :إذا كان العنصر المراد البحث عنه متكرراً عدة مرات في القائمة فإن خوارزمية البحث الثنائي المعتادة لا تفرّق بين العثور على أول وجود له أو آخر وجود له , المهم أن تعثر عليه كيفما كان ولكن lower_bound تضمن لك العثور على أول ظهور له مما يزيد من فائدتها .   2- استخدام الفرق بين نتيجتي  lower_bound وupper_bound  لمعرفة عدد مرات تكرار العنصر :   إن lower_bound تعيد مؤشر لأول ظهور لعنصر ما (إن وجد ) أما upper_bound فتعيد مؤشر لما بعد آخر ظهور لعنصر ما (إن وجد) أما إن كان غير موجود فسيعيدان نفس  المؤشر لأول عنصر أكبر من العنصر المراد . إذا عند طرح قيمة المؤشر الخاص بـ upper_bound من مؤشر lower_bound سيعطينا شيئاً ما :) انظر للقائمة التالية : 6 5 5 5 4 2 1 ببدء الترقيم من الصفر , فإن lower_bound ستعيد 3 و upper_bound ستعيد 6 ( للتسهيل سنعتبر أنها تعيد الـ index إلا أنها تعيد مؤشر وعلينا طرحه من first للحصول على الـ index ) لاحظ أن ناتج upper_bound - ناتج lower_bound = عدد مرات التكرار = 3 // lower_bound/upper_bound example#include <iostream>     // std::cout#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort#include <vector>       // std::vector#include <cstdlib>      // rand,srand#include <ctime>        // timeint main (){    std::vector<int> v;    srand(time(0));    for(int i=0;i<10;i++)        {            int repeat=rand()%10;            for(int j=0;j<repeat;j++)                v.push_back(i);        }        int s=5;//search for 5    std::cout<< upper_bound (v.begin(), v.end(),s) - lower_bound (v.begin(), v.end(),s) << std::endl;    for(auto x:v)        std::cout<<x<<" ";    return 0;}3-هل العنصر موجود ؟   هذه الفقرة فقط لتأكيد فهمك للموضوع , وعليك الإجابة الآن : هل التابع التالي يصلح للاستخدام كـ binary_search في vector ؟ bool binary_search_2(std::vector<int>x,int y){    sort(x.begin(),x.end());    if( upper_bound(x.begin(),x.end(),y) == lower_bound(x.begin(),x.end(),y) )        return false;    return true;}جرب الكود التالي : // lower_bound/upper_bound example#include <iostream>     // std::cout#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort#include <vector>       // std::vector#include <cstdlib>      // rand,srand#include <ctime>        // timebool binary_search_2(std::vector<int>&x,int y){    sort(x.begin(),x.end());    if( upper_bound(x.begin(),x.end(),y) == lower_bound(x.begin(),x.end(),y) )        return false;    return true;}int main (){    std::vector<int> v;    srand(time(0));    for(int i=0;i<100;i++)        v.push_back(rand()%100);    if(binary_search_2(v,23))        std::cout << "By Mostafa 0x36a2"<<std::endl;    else        std::cout << "ArabTeam2000"<<std::endl;    for(int i=0;i<100;i++){        if(i and i%10==0)            std::cout<<std::endl;        std::cout<<v[i]<<" ";    }    return 0;}أخيراً تجدر الإشارة إلى أن التابع lower_bound مفيد جداً في تنفيذ خوارزمية longest increasing sub-sequence حيث يجعل زمن التنفيذ (O(n2المعتاد للخوارزمية أفضل بكثير (O(n log2n   وتجدر الإشارة أيضاً إلى وجود نسخ من التابع تختص بالتعامل مع std::set التي تمثل كشجرة بحث ثنائية تسمح بتنفيذ lower_bound بشكل فعال .   المرجع : cplusplus : lower_bound upper_bound مصادر : stackoverflow فهم القيمة المعادة من التابعين ماذا يحدث عند عدم وجود العنصر lower_bound == upper_bound     خاتمة : أخي الكريم , المقال الذي بين يديك تحت رخصة (اكتب بالقدر الذي تستطيعه , سيتابع أحدهم من بعدك !) لذلك واجبك بعد قراءة المقال الزيادة عليه أو على سواه , بالسؤال عن ما لم تفهمه , او بتطبيق مفيد أو رابط متعلق به , أو بالتنبيه للأخطاء فيه أو تحسينها , كما يحق لك نشره إن وجدت فيه الفائدة , يمكنك جمعه مع مقالات أخرى لنشر كتاب مجاني . ساهم برفع المستوى العلمي العربي , وتجنب الردود الخالية من الفائدة لمن سيأتي من بعدك .     والله ولي التوفيق