DCSIMG
פתרון חידת המשולשים באמצעות TSQL - גרי רשף

פתרון חידת המשולשים באמצעות TSQL

לפני כארבע שנים, אב”ג פרסם בטור שלו את חידת המשולשים (בסוף המאמר), חידה שכדוגמתה ניתן למצוא באינטרנט או בספרי חידות: צורה גיאומטרית המחולקת למשולשים קטנים שמהם נוצרים משולשים גדולים יותר, וצריך למצוא כמה משולשים יש בסה”כ. בדרך כלל מסתבכים, סופרים חלק מהמשולשים פעמיים, משולשים אחרים מפספסים, קשה לסמן את המשולשים, והשמחה רבה..
הפעם נפתור את הבעייה שאב”ג הציג: היא לא המסובכת מכולם, אבל אנחנו הרי בעסקי SQL..

image

ניתן שמות לנקודות השונות בציור, וניצור שלוש טבלאות):
    טבלת נקודות
    טבלת קווים (השם של כל קו יווצר מהנקודה הראשונה והאחרונה שלו)
    טבלת קווים-נקודות (יחס רבים לרבים – N:N – בין שתי הנ”ל).
אפשר להסתפק בטבלה האחרונה, ולקבל במקרה הצורך את הקווים או הנקודות על ידי שליפת Distinct, אבל אנחנו נהיה מסודרים- מפתח ראשי לכל טבלה, ויחס 1:N בין שתי הטבלאות הראשונות לטבלת הקשר:

If Object_ID('T_Nekudot') Is Not Null Drop Table T_Nekudot;
Go
 
Create Table T_Nekudot(Nekuda Char(1) Primary Key);
Go
 
Insert
Into    T_Nekudot
Select    'A' Union All
Select    'B' Union All
Select    'C' Union All
Select    'D' Union All
Select    'E' Union All
Select    'F' Union All
Select    'G' Union All
Select    'H' Union All
Select    'I' Union All
Select    'J' Union All
Select    'K' Union All
Select    'L';
 
If Object_ID('T_Kavim') Is Not Null Drop Table T_Kavim;
Go
 
Create Table T_Kavim(Kav Char(2) Primary Key);
Go
 
Insert
Into    T_Kavim
Select    'AK' Union All
Select    'CE' Union All
Select    'FH' Union All
Select    'IK' Union All
Select    'AL' Union All
Select    'BF' Union All
Select    'EI' Union All
Select    'HL' Union All
Select    'BC' Union All
Select    'EF' Union All
Select    'HI' Union All
Select    'KL';
 
If Object_ID('T_KavimNekudot') Is Not Null Drop Table T_KavimNekudot;
Go
 
Create Table T_KavimNekudot(Kav Char(2) Not Null,
                    Nekuda Char(1) Not Null);
 
Alter Table T_KavimNekudot Add Constraint PK_T_Nekudot Primary Key Clustered (Kav,Nekuda); 
Go 
 
Alter Table T_KavimNekudot
Add Foreign Key (Kav) References T_Kavim(Kav);
Go
 
Alter Table T_KavimNekudot
Add Foreign Key (Nekuda) References T_Nekudot(Nekuda);
Go
 
Insert
Into    T_KavimNekudot
Select    'AK','A' Union All
Select    'AK','B' Union All
Select    'AK','E' Union All
Select    'AK','H' Union All
Select    'AK','K' Union All
Select    'CE','E' Union All
Select    'CE','D' Union All
Select    'CE','C' Union All
Select    'FH','H' Union All
Select    'FH','G' Union All
Select    'FH','F' Union All
Select    'IK','K' Union All
Select    'IK','J' Union All
Select    'IK','I' Union All
Select    'AL','A' Union All
Select    'AL','C' Union All
Select    'AL','F' Union All
Select    'AL','I' Union All
Select    'AL','L' Union All
Select    'BF','B' Union All
Select    'BF','D' Union All
Select    'BF','F' Union All
Select    'EI','E' Union All
Select    'EI','G' Union All
Select    'EI','I' Union All
Select    'HL','H' Union All
Select    'HL','J' Union All
Select    'HL','L' Union All
Select    'BC','B' Union All
Select    'BC','C' Union All
Select    'EF','E' Union All
Select    'EF','F' Union All
Select    'HI','H' Union All
Select    'HI','I' Union All
Select    'KL','K' Union All
Select    'KL','L';

דרך ראשונה תחפש שלשות של קווים שיוצרים משולשים ןתהיה בעלת אופי גיאומטרי יותר:

Select    *
From    T_Kavim T1
Inner Join T_Kavim T2
        On T1.Kav>T2.Kav
Inner Join T_Kavim T3
        On T2.Kav>T3.Kav
Where    Exists (Select    1
                From    T_KavimNekudot K1
                Inner Join  T_KavimNekudot K2
                        On K1.Nekuda=K2.Nekuda
                Where    K1.Kav=T1.Kav
                        And K2.Kav=T2.Kav)
        And Exists (Select    1
                From    T_KavimNekudot K2
                Inner Join  T_KavimNekudot K3
                        On K2.Nekuda=K3.Nekuda
                Where    K2.Kav=T2.Kav
                        And K3.Kav=T3.Kav)
        And Exists (Select    1
                From    T_KavimNekudot K1
                Inner Join  T_KavimNekudot K3
                        On K1.Nekuda=K3.Nekuda
                Where    K1.Kav=T1.Kav
                        And K3.Kav=T3.Kav)
        And Not Exists (Select Nekuda
                From    T_KavimNekudot
                Where    Kav In (T1.Kav,T2.Kav,T3.Kav)
                Group By Nekuda
                Having    Count(Kav)=3)
Order By 1,2,3;

image

ניצור Join עצמי כפול של טבלת הקווים כדי לקבל את כל הצירופים של שלושה קווים שונים,
נבדוק אם קיימת נקודה שנמצאת גם על הראשון וגם על השני,
נבדוק אם קיימת נקודה שנמצאת גם על השני וגם על השלישי,
נבדוק אם קיימת נקודה שנמצאת גם על השלישי וגם על הראשון,
ונוודא שלא מדובר בשלושת המקרים באותה נקודה (במקרה כזה לא נוצר משולש).
בסה”כ 38 משולשים (אם מישהו ניסה לפתור ידנית..).

הדרך השנייה תהיה לחפש שלשות של נקודות שנמצאות על שלושה קווים שונים, ומבחינה טכנית- קיימים שלושה קווים שעל כל אחד שתי נקודות מהשלוש. פתרון זה יותר טכני וגם הרבה יותר יעיל:

Select    *
From    T_Nekudot T1
Inner Join T_Nekudot T2
        On T1.Nekuda>T2.Nekuda
Inner Join T_Nekudot T3
        On T2.Nekuda>T3.Nekuda
Where    Exists (Select Count(1)
        From    (Select Kav
                From    T_KavimNekudot KN1
                Where    Nekuda In (T1.Nekuda,T2.Nekuda,T3.Nekuda)
                Group By Kav
                Having    Count(Nekuda)=2) T
        Having    Count(1)=3)
Order By 1,2,3;

התנאי קצת מסובך: יש לחפש קווים ששתיים משלוש הנקודות נמצאות עליהם (השאילתה הפנימית בתנאי),
ושיש שלושה כאלו (השאילתה החיצונית).
גם כאן יש בסה”כ 38 משולשים, רק שכאן מקבלים את הקודקודים שלהם ולא את הצלעות כמו קודם.

הדרך השלישית תשתמש בטכנולוגיה שונה לחלוטין- Spatial – שתחסוך מאיתנו את הצורך “ללכלך את הידיים” בגאומטריה ותעשה זאת בעצמה בעזרת המתודות המובנות בה. הפעם ניצור רק טבלה אחת ונכניס לתוכה את 12 הקווים שבבעייה – כל אחד עם הנקודות לאורכו.
לשם כך נציב את המשולש כולו במערכת צירים כדי שנוכל לתת את הקואורדינטות של כל הנקודות. לא חייבים לדייק “על הקשקש” ואפשר למפות בקירוב:

image

If Object_ID('T_Spatial') Is Not Null Drop Table T_Spatial;
Go
 
Create Table T_Spatial(ID Int Identity,
                      Kav geometry);
Go
 
Insert
Into      T_Spatial(Kav)
Select    geometry::STGeomFromText('LineString (3 6,5 6)', 0) Union All
Select    geometry::STGeomFromText('LineString (2 4,6 4)', 0)    Union All
Select    geometry::STGeomFromText('LineString (1 2,7 2)', 0)    Union All
Select    geometry::STGeomFromText('LineString (0 0,8 0)', 0)    Union All
Select    geometry::STGeomFromText('LineString (0 0,4 1,7 2)', 0)    Union All
Select    geometry::STGeomFromText('LineString (1 2,4 3,6 4)', 0)    Union All
Select    geometry::STGeomFromText('LineString (2 4,4 5,5 6)', 0)    Union All
Select    geometry::STGeomFromText('LineString (0 0,1 2,2 4,3 6,4 7)', 0)    Union All
Select    geometry::STGeomFromText('LineString (4 7,5 6,6 4,7 2,8 0)', 0)    Union All
Select    geometry::STGeomFromText('LineString (3 6,4 5,6 4)', 0)    Union All
Select    geometry::STGeomFromText('LineString (2 4,4 3,7 2)', 0) Union All
Select    geometry::STGeomFromText('LineString (1 2,4 1,8 0)', 0);
 
Select    ID,
        Kav.ToString()
From    T_Spatial;

image

למשל- שורה מספר 8 מייצגת את השוק השמאלית של המשולש כולו החל ממפגש הצירים 0 0 וכלה בקודקוד העליון 7 4 דרך שלוש נקודות נוספות..
ניעזר במתודה STIntersects כדי לבדוק בשלשות הקווים שניצור אם הם נחתכים זה עם זה,
ובמתודה STIntersection לוודא שהם לא נחתכים באותה נקודה (קיימות לפחות שתי נקודות חיתוך שונות):

Select  T1.Kav.STIntersection(T2.Kav).ToString(),
        T2.Kav.STIntersection(T3.Kav).ToString(),
        T3.Kav.STIntersection(T1.Kav).ToString()
From    T_Spatial T1
Inner Join T_Spatial T2
        On T1.ID>T2.ID
Inner Join T_Spatial T3
        On T2.ID>T3.ID
Where   T1.Kav.STIntersects(T2.Kav)=1
        And T2.Kav.STIntersects(T3.Kav)=1
        And T3.Kav.STIntersects(T1.Kav)=1
        And T1.Kav.STIntersection(T2.Kav).ToString()<>T2.Kav.STIntersection(T3.Kav).ToString();
image

גם כאן 38 פתרונות, והפעם אנחנו מקבלים אותם כקואורדינטות.
לפי ה-Execution Plan – פתרון זה הרבה פחות יעיל מהשני.

מהפתרון של אב”ג עולה שהייתה אי הבנה טכנית- בחידה המקורית קו BC לא היה אמור להופיע.. הפתרון של אב”ג – 34 – הוא ללא BC; עם BC נוצרים עוד 4 משולשים (אלו שהוא חלק מהם) ובסה”כ 38.

תוכן התגובה

# ?????????? ???????? ???????????????? ?????????????? TSQL &laquo; ?????????? ???? ?????? ??????

Pingback from  ?????????? ???????? ???????????????? ?????????????? TSQL &laquo; ?????????? ???? ?????? ??????

שלח תגובה

(שדה חובה) 
(שדה חובה) 
(אופציונלי)
(שדה חובה) 

Enter the numbers above: