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

سلسلة شغل مخك - العودة - 1

بدأه هاني الأتاسي في 31 أكتوبر 2008 · 12 رد · 2,219 مشاهدة · في Microsoft Visual C#.NET
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

معظمكم يعرف سلسلتي شغل مخك في أيام الخوالي .. أحببت أن أعيدها وأقدم أسئلة أقوى وبتحدي أكبر :) الحلول ممكن أن تكون بأي لغة سي ، سي++، سي# ، psuedo code ، ...

أبدأ الجزء الثاني من السلسلة بهذا السؤال ..

مهمتك برمجة جزء من برناج رسم ثنائي الأبعاد .. لنقل smart paint .. يمكنك من خلال البرنامج ان تضع اشكال مثلا مربع دائرة خط نقطة .. الخ .. ووظيفتك أن تصمم الكود المسؤول عن اختيار الأشكال أي الكود داخل mouse click event .. مهمتك كتابة كود للتابع التالي:

Shape Select(int x, int y) {
};

للتسهيل ، يمكنك ان تعتبر أي شكل محاط بمستطيل وبالتالي تسهل عملية فحص إذا كانت الكليك تابعة للشكل ام لا.. أي أن كل shape يحتوي على التالي:

class Shape {
   public int x1, y1, x2, y2;     // boundry
   public bool IsInside(int x, int y);
}

المطلوب منك تصميم ال data structure لحفظ ال shapes ، أي كيف سوف تحفظ الأشكال بالذاكرة وكتابة الكود الذي يحقق أسرع وقت من أجل ملاقاة الشكل ..

:wacko:

تم تعديل هذه المشاركة بواسطة هاني الأتاسي في 31 أكتوبر 2008 في 23:47

Coding on the Cloud and for the Cloud!

My Blog

#2

يعني المطلوب pattern recognition ؟

#3
golden man كتب:
يعني المطلوب pattern recognition ؟

لا.. فقط معرفة اي shape تم الضغط عليه .. مثال لدينا شكل shape1 احداثياته 10,10,100,100 وشكل shape2 احداثياته 200,200,250,250 والمستخدم نقر على الاحداثيات 50,50 فالكود المطلوب يجب ان يرجع shape1 ..

أريد أي حل يحقق المطلوب وكودوز لأسرع خوارزمية :)

Coding on the Cloud and for the Cloud!

My Blog

#4

هذه محاولة أولي :

  1. shape select(int x,int y)
  2. {
  3. vector<shape> shapes;
  4. int i;
  5. for(i=0;i<shapes.size();i++)
  6. {
  7. 	if( shapes[i].IsInside(x,y)) return shapes[i];
  8. }
  9.  
  10. }
  11.  


      
      

      
tvquran_6.gif

    

  

    
    

      
#5
        
        

      
فهدالشلوي كتب:
هذه محاولة أولي :
  1. shape select(int x,int y)
  2. {
  3. vector<shape> shapes;
  4. int i;
  5. for(i=0;i<shapes.size();i++)
  6. {
  7. 	if( shapes[i].IsInside(x,y)) return shapes[i];
  8. }
  9.  
  10. }
  11.  
  12.  

شكرا للمشاركة أخ فهد .. فقط للتوضيح في حلك ال vector يكون في الخارج ويتم اضافه له عند وضع الshapes على لوحة الرسم .. حلك صحيح ولكن:
1- في حال ليدنا المئات من الshapes هل يوجد حل أسرع؟
2- ماذا لو يوجد أشكال فوق بعضها ، أيها سوف تعيد؟

      
      

      
Coding on the Cloud and for the Cloud!
My Blog

    

  

    
    

      
#6
        
        

      
هذا كود بسيط بالمقارنات العادية دون استخدام أى خوارزمية
  1. using System;
  2. using System.Collections;
  3.  
  4. namespace ConsoleApplication1
  5. {
  6.     class Shape
  7.     {
  8.         public string Shapename;
  9.         public int x1, y1, x2, y2;
  10.  
  11.         public bool IsInside(int x, int y)
  12.         {
  13.             if (x >= x1 && x <= x2 && y >= y1 && y <= y2)
  14.                 return true;
  15.  
  16.             return false;
  17.         }
  18.     }
  19.  
  20.     class Program
  21.     {
  22.         public static ArrayList Shapes = new ArrayList();
  23.  
  24.         static void Main(string[] args)
  25.         {
  26.             int x, y;
  27.  
  28.             GetShapes();
  29.  
  30.             if (Shapes.Count > 0)
  31.                 while (GetXY(out x, out y) == true)
  32.                     for (int n = (Shapes.Count - 1); n >= 0; n--)
  33.                         if (((Shape)Shapes[n]).IsInside(x, y) == true)
  34.                         {
  35.                             Console.WriteLine("({0}, {1}) Exist in Shape: {2}", x, y, ((Shape)Shapes[n]).Shapename);
  36.                             break;
  37.                         }
  38.         }
  39.  
  40.         private static void GetShapes()
  41.         {
  42.             string sName = "";
  43.  
  44.             Console.WriteLine("nEnter Shapes... ");
  45.             do
  46.             {
  47.                 Console.Write("nEnter name: ");
  48.                 sName = Console.ReadLine();
  49.                 if (sName.Length > 0)
  50.                 {
  51.                     Shape shape = new Shape();
  52.  
  53.                     shape.Shapename = sName;
  54.  
  55.                     Console.Write("x1: ");
  56.                     shape.x1 = Convert.ToInt32(Console.ReadLine());
  57.                     Console.Write("y1: ");
  58.                     shape.y1 = Convert.ToInt32(Console.ReadLine());
  59.                     Console.Write("x2: ");
  60.                     shape.x2 = Convert.ToInt32(Console.ReadLine());
  61.                     Console.Write("y2: ");
  62.                     shape.y2 = Convert.ToInt32(Console.ReadLine());
  63.  
  64.                     Shapes.Add(shape);
  65.                 }
  66.                 else
  67.                     break;
  68.             }
  69.             while (sName.Length > 0);
  70.         }
  71.  
  72.         private static bool GetXY(out int x, out int y)
  73.         {
  74.             Console.WriteLine("nCoordinates... ");
  75.             Console.Write("Enter x: ");
  76.             x = Convert.ToInt32(Console.ReadLine());
  77.             Console.Write("Enter y: ");
  78.             y = Convert.ToInt32(Console.ReadLine());
  79.  
  80.             if (x >= 0 && y >= 0)
  81.                 return true;
  82.             return false;
  83.         }
  84.     }
  85. }
  86.  
وحيث أن #C تستخدم Short Path فالكود
  1.         public bool IsInside(int x, int y)
  2.         {
  3.             if (x >= x1 && x <= x2 && y >= y1 && y <= y2)
  4.                 return true;
  5.  
  6.             return false;
  7.         }
  8.  
يتماثل اداءة مع الكود
  1.         public bool IsInside(int x, int y)
  2.         {
  3.             if (x >= x1)
  4.                 if (x <= x2)
  5.                     if (y >= y1)
  6.                         if (y <= y2)
  7.                             return true;
  8.  
  9.             return false;
  10.         }
  11.  


      
      

      
    

  

    
    

      
#7
        
        

      
شكرا أخ دحدوح على الكود وعلى توضيح الكود ل IsInShape .. طريقتك هي نفسها طريقة فهد في الكود المطلوب كتابته وهو Select ..
ولكن هل يوجد طريقة أسرع .. الخوارزميات التي كتبتوها هي O(N) .. يجب أن يكون هناك افضل من هذا ..
مساعدة : فكرو بتوزع الأشكال على لوحة الرسم ومواضعها وكيف يمكن تصميم data structure مناسب لها :)

      
      

      
Coding on the Cloud and for the Cloud!
My Blog

    

  

    
    

      
#8
        
        

      
اقتباس
الحلول ممكن أن تكون بأي لغة سي ، سي++، سي# ، psuedo code ، ...
سأختار الـ ...  :lol: 
فكرت -ويحتمل الخطأ بنسبه كبيييييييييره- أن ننشئ Binary Search Tree ، تحتوي على مؤشر لعقده باليمين واليسار ومؤشر للشكل Shape ،ومعروف أن العقده التي في اليسار تحمل قيمه أقل من الأب ، والعقد التي في اليمين تحمل عقده أكبر ..
class Node
{
public :
	Shape* sp;
	Node* leftNode;
	Node* rightNode;
};
الفكره تكون كالتالي :
عند إدخال أي شكل جديد ، نقوم بوضع id له   .. وندخله في الشجره (طبعا سيذهب في المكان الصحيح بناء على القيم الموجوده في الشجره ) .. أي داله الأدخال تكون :
insert(int id,Shape* s);
الأن عند الضغط بالماوس نستطيع الحصول على الشكل الحالي وذلك بالبحث في الشجره عن الid وسيرجع بسرعه كبيره جدا (تقريبا شجره البحث الثنائيه يكون لها تعقيد O(log N) )
المشكله الأن في نوعيه هاid كيف يمكن أختياره ؟
يمكن أن نجمع  أحد الأبعاد في الشكل ، يعني لو لدى البعد : 10.10.100.100 أجمع 10+100 ويصبح لدى 110 .
وهكذا أدخل هذا الشكل في الشجره بالرقم 110 (ويكون هو root) .
أيضا :
200.200.250.250
يكون الId هو 450 وسوف يكون في الجهه اليمني من الشجره ..
الأن في حال ضغط المستخدم في المكان 50.50 ، أجمع الرقمين ويخرج 100 ، وبالتالي البحث سوف يكون مقتصر في الجهه اليسري من الشجره .. واذا ضغط المستخدم على 150.150 يكون 300 وبالتالي البحث في الجهه اليمني ..
وهنا في حال كان شكلين فوق بعض سوف يخرج الشكل الأول :) لأنه الأول في الشجره ..
أخيرا المعذره على هذه الفكره ، ربما تكون بعييييييده جدا عن ما تريد ، لكن حبيت المشاركه :) .
وحمد لله على سلامتك أخ هاني الأتاسي .. وبراحه علينا ، اذا كان هذا أول سؤال ترحيبي كده الباقي بيكون كيف :( ..
بالتوفيق ،

      
تم تعديل هذه المشاركة بواسطة Wajdy Essam في 2 نوفمبر 2008 في 00:36

      

      
http://informatic-ar.com منصة تعليمية عربية في علوم الحاسب والبرمجة
https://moalfat.com  للكتب الالكترونية والكورسات التعليمية
Everything we see now is just an engineering solution based on old science

    

  

    
    

      
#9
        
        

      
عجبني متل ما بقولو تفكيرك خارج الصندوق :)
فكرتك قريبة من الحل بس فيها مشكلة .. الاحداثيات 10,100 غير 100,10 وبالتالي وضعها في الشجرة لا يكون بشكل صحيح ..
المفروض يمكنك استخدام احداثيات x و y على حدا في الشجرة من غير الجمع .. كيف يمكن هذا؟ الأسهل فكر كيف يمكن ان تستخدم x فقط ومن بعدها كيف تستفيد من y ..

      
      

      
Coding on the Cloud and for the Cloud!
My Blog

    

  

    
    

      
#10
        
        

      
أنا كنت قاصد أن 10.10.100.100 وهي تمثل x1,y1,x2,y2 وأقوم جمع x1+y2 ... 
وممكن أيضا أن يكون الid اللى تكلمت عنه هو القيمه الكبيره من هذه الأحداث ، وبالتالي لو المستخدم دق على 20.50 (ناخذ القيمه الكبيره هنا) ونبحث في جهه الشمال ..
لكن يبدوا من حديثك أنك تريد اختبار الx,y مع بعض ،،بالتالى ربما العقد يجب أن تحتوي على أكثر من متغير لحفظ القيمه يعني تصبح 2-3 Tree ..
على العموم نجرب ان شاء الله ونعود ،،
ولو في Hint بسيط بيكون أحسن  :P 

      
      

      
http://informatic-ar.com منصة تعليمية عربية في علوم الحاسب والبرمجة
https://moalfat.com  للكتب الالكترونية والكورسات التعليمية
Everything we see now is just an engineering solution based on old science

    

  

    
    

      
#11
        
        

      
  1. using System;
  2. using System.Collections;
  3.  
  4. namespace ConsoleApplication1
  5. {
  6.     class Shape
  7.     {
  8.         public string Shapename;
  9.         public int x1, y1, x2, y2;
  10.  
  11.         public bool IsInside(int x, int y)
  12.         {
  13.             if (x >= x1 && x <= x2 && y >= y1 && y <= y2)
  14.                 return true;
  15.             return false;
  16.         }
  17.     }
  18.  
  19.     class Screen
  20.     {
  21.         private const int xArr = 10, yArr = 10;
  22.         private const int xLen = 128, yLen = 128;
  23.         private Region[,] Regions = new Region[xArr, yArr];
  24.         public static ArrayList Shapes = new ArrayList();
  25.  
  26.         class Region
  27.         {
  28.             public int left, top, right, bottom;
  29.             public ArrayList ShapeIndexs;
  30.  
  31.             public bool Search(int x, int y)
  32.             {
  33.                 if (ShapeIndexs.Count > 0)
  34.                     for (int n = (ShapeIndexs.Count - 1); n >= 0; n--)
  35.                     {
  36.                         Shape shape = ((Shape)Shapes[(int)ShapeIndexs[n]]);
  37.                         if (shape.IsInside(x, y) == true)
  38.                         {
  39.                             Console.WriteLine("({0}, {1}) Exist in Shape: {2}", x, y, shape.Shapename);
  40.                             return true;
  41.                         }
  42.                     }
  43.  
  44.                 Console.WriteLine("No shapes at ({0}, {1})", x, y);
  45.                 return false;
  46.             }
  47.         }
  48.  
  49.         public Screen()
  50.         {
  51.             for (int x = 0; x < xArr; x++)
  52.                 for (int y = 0; y < yArr; y++)
  53.                 {
  54.                     Regions[x, y] = new Region();
  55.                     Regions[x, y].left = x * xLen;
  56.                     Regions[x, y].right = ((x + 1) * xLen) - 1;
  57.                     Regions[x, y].top = y * yLen;
  58.                     Regions[x, y].bottom = ((y + 1) * yLen) - 1;
  59.  
  60.                     Regions[x, y].ShapeIndexs = new ArrayList();
  61.                 }
  62.         }
  63.  
  64.         public void GetShapes()
  65.         {
  66.             string sName = "";
  67.  
  68.             Console.WriteLine("nEnter Shapes... ");
  69.             do
  70.             {
  71.                 Console.Write("nEnter name: ");
  72.                 sName = Console.ReadLine();
  73.                 if (sName.Length > 0)
  74.                 {
  75.                     Shape shape = new Shape();
  76.  
  77.                     shape.Shapename = sName;
  78.  
  79.                     Console.Write("x1: ");
  80.                     shape.x1 = Convert.ToInt32(Console.ReadLine());
  81.                     Console.Write("y1: ");
  82.                     shape.y1 = Convert.ToInt32(Console.ReadLine());
  83.                     Console.Write("x2: ");
  84.                     shape.x2 = Convert.ToInt32(Console.ReadLine());
  85.                     Console.Write("y2: ");
  86.                     shape.y2 = Convert.ToInt32(Console.ReadLine());
  87.  
  88.                     InsertShape(ref shape);
  89.                 }
  90.                 else
  91.                     break;
  92.             }
  93.             while (sName.Length > 0);
  94.         }
  95.  
  96.         public bool InsertShape(ref Shape shape)
  97.         {
  98.             int x1 = shape.x1 / xLen;
  99.             int y1 = shape.y1 / yLen;
  100.             int x2 = shape.x2 / xLen;
  101.             int y2 = shape.y2 / yLen;
  102.             int ShapeIndex;
  103.  
  104.             if (x2 < xArr && y2 < yArr)
  105.             {
  106.                 ShapeIndex = Shapes.Add(shape);
  107.  
  108.                 for (int x = x1; x <= x2; x++)
  109.                     for (int y = y1; y <= y2; y++)
  110.                     {
  111.                         Regions[x, y].ShapeIndexs.Add(ShapeIndex);
  112.                         Console.WriteLine("Shape inserted at Regions[{0}, {1}]", x, y);
  113.                     }
  114.                 return true;
  115.             }
  116.             return false;
  117.         }
  118.  
  119.         public bool SearchShape(int xPos, int yPos)
  120.         {
  121.             int x = xPos / xLen;
  122.             int y = yPos / yLen;
  123.             if (x < xArr && y < yArr)
  124.             {
  125.                 Console.WriteLine("Searching in Regions[{0}, {1}]", x, y);
  126.                 return Regions[x, y].Search(xPos, yPos);
  127.             }
  128.  
  129.             return false;
  130.         }
  131.     }
  132.  
  133.     class Program
  134.     {
  135.         static void Main(string[] args)
  136.         {
  137.             int x, y;
  138.             Screen scr = new Screen();
  139.  
  140.             scr.GetShapes();
  141.  
  142.             while (GetXY(out x, out y) == true)
  143.                 scr.SearchShape(x, y);
  144.         }
  145.  
  146.         static public bool GetXY(out int x, out int y)
  147.         {
  148.             Console.WriteLine("nCoordinates... ");
  149.             Console.Write("Enter x: ");
  150.             x = Convert.ToInt32(Console.ReadLine());
  151.             Console.Write("Enter y: ");
  152.             y = Convert.ToInt32(Console.ReadLine());
  153.  
  154.             if (x >= 0 && y >= 0)
  155.                 return true;
  156.             return false;
  157.         }
  158.     }
  159. }
  160.  
  161.  
  162.  
  163.  
  164.  
إذا كنت تريد أن يعرض لك أسماء جميع الاشكال أسفل النقطة مع الحفاظ على ترتيب ظهورهم على الشاشة (الأعلى أولاً، بأعتبار أن ما يدخل أولاً هو الاسفل وما يدخل بعده هو الأعلى)، أستبدل الكلاس Region الى:
  1.         class Region
  2.         {
  3.             public int left, top, right, bottom;
  4.             public ArrayList ShapeIndexs;
  5.  
  6.             public bool Search(int x, int y)
  7.             {
  8.                 bool bFound = false;
  9.                 if (ShapeIndexs.Count > 0)
  10.                     for (int n = (ShapeIndexs.Count - 1); n >= 0; n--)
  11.                     {
  12.                         Shape shape = ((Shape)Shapes[(int)ShapeIndexs[n]]);
  13.                         if (shape.IsInside(x, y) == true)
  14.                         {
  15.                             Console.WriteLine("({0}, {1}) Exist in Shape: {2}", x, y, shape.Sha
    pename);
  16.                             bFound = true;
  17.                         }
  18.                     }
  19.  
  20.                 if (bFound == false)
  21.                     Console.WriteLine("No shapes at ({0}, {1})", x, y);
  22.                 return bFound;
  23.             }
  24.         }
  25.  
  26.  
  27.  
  28.  

كلاس Shape تحتوى بيانات شكل واحد
الدالة IsInside: تحدد ما اذا كان الاحداثى داخل الشكل ام لا (t/f)
----------
كلاس Region تحتوى اشكال كل منطقة
الدالة Search تبحث عن النقطة (x, y) فى الاشكال داخل هذه المنطقة
المصفوفة ShapeIndexs وهى التى تحتفظ برقم (Index) الشكل فى داخل هذه المنطقة، وهذا الرقم يشير الى الشكل فى المصفوفة Shapes
left, top, right, bottom ، حدود المنطقة، يمكن الاستغناء عن (right, bottom) حالياً، ولكن يمكن ان يظهر لهم استخدام مستقبلى
----------
كلاس Screen تحتوى على الاشكال فى الشاشة، وتقسم الشاشة الى عدد من المناطق Regions فى بعدين
دالة Constractor يقوم بتجهيز المناطق
الدالة GetShapes استقبال بيانات شكل من لوحة المفاتيح، وارساله للدالة InsertShape
الدالة InsertShape تضيف الشكل الى المصفوفة Shapes وتحصل على رقمه Index، ثم تحدد المناطق التى يغطيها الشكل، ثم تضيف رقمه فى مصفوفة الرقام ShapeIndexs الخاصه بهذه المنطقة
عدد المناطق الافقية هو xArr وعرض كل منطقة هو xLen
عدد المناطق الرئيسة هو yArr وارتفاع كل منطقة هو yLen
المصفوفة ذات البعدين التى تحتفظ بهذه المناطق هى Regions 
المصفوفة Shapes تحتوى على جميع الاشكال المدخلة (مصفوفة من كائنات كلاس Shape)

      
تم تعديل هذه المشاركة بواسطة دحدوح في 2 نوفمبر 2008 في 21:20

      

      
    

  

    
    

      
#12
        
        

      
دحدوح :) .. حلك كمان قريب .. بس في مشكلة أنا فرضا احب أضح آلاف الأشكال في قسم من الشاشاة .. وفرضا أيضا ممكن أعمل زوم على قسم معين وأرسم فيه كأنه الشاشة كلها ..
هل ممكن أن يكون تقسيمك للشاشة ديناميكي مثل binary search ... 
أعتقد إذا لقيتو طريقة تدمجو طريقة بين حل دحدوح وحل وجدي يكون أفضل :)

      
تم تعديل هذه المشاركة بواسطة هاني الأتاسي في 2 نوفمبر 2008 في 22:26

      

      
Coding on the Cloud and for the Cloud!
My Blog

    

  

    
    

      
#13
        
        

      
الحل بسيط اخي هاني
يمكنك وضع معرف لكل شكل 
وكل ما أضفت شكل جديد يعيه رقم المعرف السابق +1 
واذا تقاطع شكلان في نقطة تعطي الأولوية للذي معرفة رقم أعلى 
وهذا بكون الموضوع أُغلق
والمخ شُغِّل

      
      

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

    

  

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