הבלוג של גרי רשף

27/02/2010

חלוקה (תורת המספרים)

Filed under: Uncategorized — תגיות: , , , — גרי רשף @ 21:42

בכמה אופנים ניתן לחלק 3 מטבעות?
3
2,1
1,1,1
כלומר- 3 אפשרויות; כאשר ברור ש-2,1 ו-1,2 הן היינו הך.
ובכמה אופנים ניתן לחלק N מטבעות (נוסחה כללית למקרה הפרטי הנ"ל)?
לכאורה בעייה פשוטה מהסוג שפוגשים במבוא להסתברות, אלא שלמרבה הפלא אין לבעייה זו תשובה,
ולהרחבה ניתן לעיין בוויקיפדיה.

את הנוסחה הנכספת אינני מתיימר למצוא, אבל ננסה לטפל במקרים פרטיים- למשל חלוקה של 5 מטבעות.
מה עדיף- פתרון מסובך ואיטי או פתרון אלגנטי ומהיר? דילמה קשה!..
נתחיל מהמסובך והאיטי שהיתרון העיקרי שלו שהוא יגרום לנו להעריך את האלגנטי והמהיר שבעתיים.
ניצור את סדרת המספרים 0..5, נבצע 5 פעמים Join שלה עם עצמה, ונציג את כל הצירופים בהם סכום המספרים המתקבלים הוא 5.
כדי למנוע כפילויות נקפיד שהסדרה תירד משמאל לימין (למשל 2,2,1,0,0 או 5,0,0,0,0 או 1,1,1,1,1),
וכדי להקל על המערכת נקבע שהסדרה הראשונה תנוע בין 0 ל-5, השניה בין 0 ל-5/2, השלישית בין 0 ל-5/3 וכו' (מתחייב מהתנאי שהסדרה יורדת):

With Nm As

(Select 0 N

Union All

Select    N+1

From    Nm

Where    N<5)

Select    --Nm1.N+Nm2.N+Nm3.N+Nm4.N+Nm5.N Nm,

        *

From    Nm Nm1, Nm Nm2, Nm Nm3, Nm Nm4, Nm Nm5

Where    Nm1.N<=5/1 And Nm2.N<=5/2 And Nm3.N<=5/3 And Nm4.N<=5/4 And Nm5.N<=5/5

        And Nm1.N+Nm2.N+Nm3.N+Nm4.N+Nm5.N=5

        And Nm1.N>=Nm2.N And Nm2.N>=Nm3.N And Nm3.N>=Nm4.N And Nm4.N>=Nm5.N

Order By Nm1.N,Nm2.N,Nm3.N,Nm4.N,Nm5.N

נקבל 7 אפשרויות.

מכיוון שלכל מספר לשאילתה יש מבנה שונה, ניצור את משפט ה-SQL באופן דינאמי ונריץ אותו:

Declare    @N Int,

        @SQL Varchar(Max),

        @SQLs Varchar(Max),

        @SQLf Varchar(Max),

        @SQLw0 Varchar(Max),

        @SQLw1 Varchar(Max),

        @SQLw2 Varchar(Max),

        @SQLo Varchar(Max);

Set        @N=5;

Set        @SQLs='';

Set        @SQLf='';

Set        @SQLw0='';

Set        @SQLw1='';

Set        @SQLw2='';

Set        @SQLo='';

With Nm As

(Select 0 N

Union All

Select    N+1

From    Nm

Where    N<@N)

Select    @SQLs=@SQLs+'Nm'+Cast(N As Varchar)+'.N+',

        @SQLf=@SQLf+'Nm Nm'+Cast(N As Varchar)+', ',

        @SQLw0=@SQLw0+'Nm'+Cast(N As Varchar)+'.N<='+Cast(@N As Varchar)+'/'+Cast(N As Varchar)+' And ',

        @SQLw1=@SQLw1+'Nm'+Cast(N As Varchar)+'.N+',

        @SQLw2=@SQLw2+Case When N=@N Then '' Else 'And Nm'+Cast(N As Varchar)+'.N>=Nm'+Cast(N+1 As Varchar)+'.N ' End,

        @SQLo=@SQLo+'Nm'+Cast(N As Varchar)+'.N,'

From    Nm

Where    N>=1;

Set        @SQL='With Nm As'+CHAR(13)+

            '(Select 0 N'+CHAR(13)+

            'Union All'+CHAR(13)+

            'Select    N+1'+CHAR(13)+

            'From    Nm'+CHAR(13)+

            'Where    N<'+Cast(@N As Varchar)+')'+CHAR(13)+

            'Select    --' + Left(@SQLs,Len(@SQLs)-1)+' Nm,'+CHAR(13)+

            '        *'+CHAR(13)+

            'From    '+Left(@SQLf,LEN(@SQLf)-1)+CHAR(13)+

            'Where    '+Left(@SQLw0,LEN(@SQLw0)-4)+CHAR(13)+

            '        And '+Left(@SQLw1,Len(@SQLw1)-1)+'='+CAST(@N As Varchar)+CHAR(13)+

            '        '+@SQLw2+CHAR(13)+

            'Order By '+Left(@SQLo,Len(@SQLo)-1);

Print    @SQL;

Exec(@SQL);

כפי שאפשר לראות- SQLs@ יוצר באופן דינאמי את ה-Select,

SQLf@ את ה-From,

SQLw123 את תנאי ה-Where (שלוש סדרות של תנאים),

SQLo@ את ה-Order By,

ו-SQL@ את המשפט כולו.

ה-CTE המתחיל ב-With יוצר את המספרים 0..5, ובנוסף גם ב-SQL הדינאמי נוצר CTE דומה.

בדוגמה זו N=5@, אך ניתן להציב איזה מספר שרוצים.

ועכשיו לפתרון הפשוט: למספרים 1..5 נשרשר מספרים שאינם גדולים מהם כל עוד הסכום של כולם אינו גדול מ-5, כל זאת על ידי CTE רקורסיבי כפול (הראשון עבור המספרים 1..5 והשני עבור החלוקות השונות):

Declare    @N Int;

Set        @N=5;

With Nm As

(Select 1 N

Union All

Select    N+1

From    Nm

Where    N<@N),

Haluka As

(Select    CAST(N As Varchar(Max)) Haluka,

        N As Ahron,

        N As Total

From    Nm

Union All

Select    H.Haluka+','+CAST(Nm.N As Varchar(Max)),

        Nm.N,

        H.Total+Nm.N

From    Haluka H

Inner Join Nm

        On H.Ahron>=Nm.N

        And H.Total+Nm.N<=@N)

Select    Haluka

From    Haluka

Where    Total=@N;

גם בדוגמה זו N=5@, אך ניתן להציב איזה מספר שרוצים.

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: