تداخل بين اثنين من فترات:المنطق / خوارزمية لإيجاد مجموعة منفصلة و تداخل فترات

Question

النظر في الاعداد الصحيحه الايجابية {1, 2, 3, 4, ...} وما يقابلها من عدد صحيح خط.

لنفترض أن لدينا أربعة أرقام صحيحة ، A ، B ، C و D.

على سبيل المثال:

_________________A___________________________ب__________________ ___________________________ج__________D_________________________

أو

_________________A___________________________ب__________________ ___________________________ج____________________________D_______

النظر في تدوين AB مجموعة من أرقام متتالية،...., ب ، و الفاصل الزمني المضغوط باعتبارها مجموعة من أرقام متتالية C, ..., D.

أود أن أعرف بسيطة لكنها مجردة generalizaed resoning (الرياضية مظاهرة سيكون حقا apreciated) أننا يمكن أن تنطبق إذا كنا نريد أن نجد جميع فترات تتكون من "منفصلة" أرقام "متداخلة" الأرقام بين كل مجموعة من الأرقام, AB و CD.

مثال 1: إذا AB = {2, 3, 4, 5, 6, 7, 8, 9} و CD = {4, 5, 6, 7}, لدينا ما يلي فرعية لكل مجموعة AB و CD:

• AB:{2, 3}, {4, 5, 6, 7} و {8, 9}
• القرص المضغوط:{4, 5, 6, 7}

مثال 2: إذا AB = {2, 3, 4, 5, 6, 7, 8, 9} و CD = {4, 5, 6, 7, 8, 9, 10, 11, 12}, لدينا ما يلي فرعية لكل مجموعة AB و CD:

• AB:{2, 3}, {4, 5, 6, 7, 8, 9}
• القرص المضغوط:{4, 5, 6, 7, 8, 9} و {10, 11, 12}

ولكن أي واحد من شأنه أن يكون كبيرا و لكنها بسيطة المنطق وراء منفصلة ومتداخلة مجموعات من الأرقام بين اثنين من مجموعة معينة من عدد الأرقام ؟

شكرا جزيلا على أي دليل!!

Answer 1

عن اثنين من الاعداد الصحيحه $A$ و $B$ حيث $A\le B$, اسمحوا $[A,B)$ للدلالة على نصف مغلقة ونصف مفتوحة الفاصل الذي يتألف من الأرقام $A, A+1, \cdots ، ب-1$.ولا سيما إذا كان $A, ثم هناك $B-A$ الأرقام في $[A,B)$.إذا $A=B$, ، ثم لا يوجد أي أرقام في $[A,B)$.على سبيل المثال ،

• $[0,1)$ يعني الرقم 0.
• سواء $[0,0)$ و $[3, 3)$ يعني لا توجد أرقام.
• $[5,11)$ يعني الأرقام $5,6,7,8,9,10.$
• للدلالة على الأرقام $-2, -1, 0, 1, 2$, يمكننا استخدام $[-2, 3)$.

---

خاصية جميلة من نصف مغلقة ونصف مفتوحة الفاصل: إذا $L\le M \le R$, ثم $[L,R) = [L,M) \sqcup [M,R)$.

برهان: وأخشى هو واضح من التعريف.القيام به.

---

لنفترض أننا تعطى $[A, B)$ و $[C, D)$, حيث $A\lt B$ و $ج\lt D$.ثم $[A,B)$ التداخل $[C,D)$ إذا و فقط $\max(A,C)\lt \مين(ب ، د)$.

برهان:

"$ ightarrow$":السماح $n$ يكون عدد في كل $[A,B)$ و $[C,D)$, أي $A\le n\lt B$ و $ج\le n \lt D$.ثم $\max(A,C)\le n\lt \مين(ب ، د)$.

"$\Leftarrow$": $A\لو \max(A,C)\lt \مين(B,D)\le B$, أي $\max(A,C)\في [أ ، ب)$.وبالمثل ، $\max(A,C)\في [C,D)$.لذلك $[A,B)$ التداخل $[C,D)$.

القيام به.

---

لنفترض $[A,C)$ و $[B ، D)$ التداخل.ثم لدينا ما يلي مجموعة التفسخ.

• $[A,B) = [A, \max(A,C))\sqcup[\ماكس(أ ، ج) ، \مين(ب ، د)]\sqcup[\مين(ب ، د) ب)$
• $[C,D) = [C \max(A,C))\sqcup[\ماكس(أ ، ج) ، \مين(ب ، د)]\sqcup[\مين(ب ، د) ، د)$

برهان:

لدينا $A\لو \max(A,C) \لو \مين(B,D)\le B$.لذلك ،

$$\begin{align} [A,B) &= [A, \max(A,C))\sqcup[\max(A,C) B)\\ &= [A, \max(A,C))\sqcup[\ماكس(أ ، ج) ، \مين(ب ، د)]\sqcup[\مين(ب ، د) ب).\end{align}$$

---

مثال 1: إذا $I = \{2, 3, 4, 5, 6, 7, 8, 9\}$ و $J = \{4, 5, 6, 7\}$, ثم $I=[2,10)$ و $J=[4,8)$.لدينا ما يلي مجموعة التفسخ.

• $[2,10) = [2, 4)\sqcup [4, 8) \sqcup [8,10)$.
• $[4,8) = [4, 4)\sqcup [4, 8) \sqcup [8,8) = [4,8)$.

مثال 2: إذا $I = {2, 3, 4, 5, 6, 7, 8, 9}$ و $J = {4, 5, 6, 7, 8, 9, 10, 11, 12}$, ثم $I=[2,10)$ و $J=[4,13)$.لدينا ما يلي مجموعة التفسخ.

• $[2,10) = [2, 4)\sqcup [4, 10) \sqcup [10,10)= [2, 4)\sqcup [4, 10)$.
• $[4,13) = [4, 4)\sqcup [4, 10) \sqcup [10,13)= [4, 10) \sqcup [10,13)$.

الأمثلة المذكورة أعلاه ينبغي أن تبين بوضوح كاف الخوارزمية التي تتحلل اثنين من تداخل فترات في فترات منفصلة.