חידת SQL ולצידה אתגר מתימטי

26/02/2015

אין תגובות

נתחיל מהחידה שהיא רק המתאבן לאתגר:
נתונה טבלה בשם MyTbl ובה עמודת ID מסוג Int.
נריץ את השליפה הבאה:

Select  *

From    MyTbl T1

Inner Join MyTbl T2

        On T1.ID=T2.ID;

כמה שורות יחזרו?

בשלב הזה צריך לעצום את העיניים כדי לא לקלקל את האתגר ולנסות לבד לחשוב,
ומי שמתעצל- יכול להציץ בתשובה ולשכנע את עצמו שהוא היה מגיע לזה לבד..
בכל מקרה- מכיוון שלא נאמר מה טיבה של אותה עמודת ID אזי יכולים להיות בה ערכי Null, ערכים שאינם יחודיים וכו’;
ומספר השורות החוזרות ינוע בין אפס שורות במקרה שכל העמודה היא Nulls (ואז אין אף התאמה כי Null אינו שווה לעצמו) לעשרת אלפים שורות במקרה שבכל השורות אותו ערך ונוצרת מכפלה קרטזית (יש “לצבוע” את מקום המספר בעזרת העכבר כדי לראות את התשובה)..

האתגר המתימטי- האם ניתן לקבל כל מספר שורות כרצוננו כל עוד הוא בין שתי השובות הנ”ל?
למשל- האם ניתן לקבל 4321 שורות למשל?
אם יהיו- 65 שורות בהן הערך הוא 1 ושהן יצרו מכפלה קרטזית של 4225 שורות,
9 שורות בהן הערך הוא 2 ושהן יצרו מכפלה קרטזית של 81 שורות,
3 שורות בהן הערך הוא 3 ושהן יצרו מכפלה קרטזית של 9 שורות,
2 שורות בהן הערך הוא 4 ושהן יצרו מכפלה קרטזית של 4 שורות,
1 שורה בה הערך הוא 5 ושהיא תחזיר שורה 1,
1 שורה בה הערך הוא 6 ושהיא תחזיר שורה 1,
ובכל השאר Null;
אז יחזרו בסה"כ 4321 שורות.
אם לעומת זאת נרצה לקבל 9999 שורות – זו בעייה כי אין דרך לעשות זאת.
בקיצור- נדרשת שליפה שתייצר לי פתרונות על פי הצורך: אני אצור פרמטר אחד שערכו 100, שני שערכו 4321, והמערכת תחזיר לי את הפתרון הנ”ל ואולי עוד כמה; רצוי כמובן – שבזריזות..
הפתרון (רצוי לנסות לבד..):

Declare    @S Int=100,

        @I Int=4321;

With Nm As

(Select    1 N

Union All

Select    N+1

From    Nm

Where    N<100),

T As

(Select    1 Level,

        Nm.N*Nm.N Mahpela,

        Cast(Nm.N As Varchar(Max)) Mahrozet,

        Nm.N Shum,

        Nm.N Ahron

From    Nm

Where    Nm.N<=Sqrt(@I)

        And Nm.N<=@S

Union All

Select    T.Level+1,

        T.Mahpela+Nm.N*Nm.N,

        Cast(Concat(T.Mahrozet,',',Nm.N) As Varchar(Max)),

        T.Shum+Nm.N,

        Nm.N Ahron

From    T

Inner Join Nm

        On Nm.N<=T.Ahron

        And T.Mahpela+Nm.N*Nm.N<=@I

        And T.Shum+Nm.N<=@S

        And (@S-T.Shum-Nm.N)*(@S-T.Shum-Nm.N)>=(@I-T.Mahpela+Nm.N*Nm.N)

Where    T.Mahpela<@I)

Select    *

From    T

Where    Mahpela>=@I;

image

יש כאן שני CTE רקורסיביים- אחד שמייצר את המספרים 1..100 (חבר ותיק כאן בבלוג ולא ארחיב לגביו את הדיבור),
והשני שמייצר את הפתרונות.
למשל במקרה של 4321: הוא ישלוף מטבלת המספרים את כל אלו שהריבוע שלהם קטן מ-4321 (כדי לא לעבור אותו).
לאחר מכן באופן רקורסיבי הוא יקח את אלו שסכום הריבועים אצלם קטן מ-4321 (יש תנאי נוסף שאין לו משמעות מיוחדת בעוגן של ה-CTE),
ויעשה להם Join חדש עם טבלת המספרים, אך עם כאלה שהריבוע שלהם קטן או שווה למה שנשאר עדיין להוסיף כדי להגיע ל-4321.
יש בחלק הרקורסיבי של ה-CTE חמישה תנאים (4 ב-On ו-1  ב-Where):

  1. המספרים קטנים מהאחרון שהתווסף (ל-65 נחבר מספרים שאינם גדולים ממנו). כך נמנע כפילויות.
  2. המספר יהיה כזה שסכום הריבועים עד כה ועוד ריבועו – לא יחרגו מ-4321.
  3. המספר יהיה כזה שיחד עם סכום המספרים עד כה – לא יחרגו מ-100.
  4. ריבוע המספר יהיה כזה שמה שנשאר עד מאה כפול עצמו (=בריבוע) לא יהיה קטן מסכום הריבועים שחסר. למשל- אם אנחנו מנסים להגיע ל-9999 (כזכור- אין לזה פתרון), נתחיל מ-99 בריבוע (שזה 9801) אבל לא נצטרך לחפש יותר מדי מספרים שישלימו את זה ל-9999 כי נשאר הפרש של 1 עד 100, והוא לא יספיק לכך.
  5. סכום המכפלות טרם הגיע ל-4321 וצריך להמשיך ולחפש.

בסה”כ זה רץ מהר, בעיקר בזכות תנאי 4 שקצת קשה להבינו במבט ראשון..

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *