הנפה של ארטוסתנס

יום שישי, אוגוסט 27, 2010

הנפה של ארסטותנס היא אלגוריתם למציאת כל המספרים הראשוניים מ-2 ועד לערך שנקבע מראש: 2 הוא הראשוני הראשון ולכן נמחק את כל המספרים שמתחלקים ב-2 המספר הכי קטן מעל 2 הוא ,3 מכאן שהוא ראשוני, ולכן נמחק את כל המספרים שמתלקים ב-3 המספר הכי קטן מעל 3 הוא 5 (4 כבר נמחק בתור כפולה של 2) ולכן נמחק את כל כפולותיו.. כך ממשיכים עם כל הרשימה, כשלמעשה מספיק להמשיך עד לשורש של הערך המקסימלי ברשימה.. נכין טבלת מספרים מאונדקסת מ-2 ועד 1,000,000: If Object_Id('T_Misparim') Is Not Null Drop Table T_Misparim; Go Declare @N Int=1000000; With T As (Select 2 Mispar Union All Select Mispar+1 From ...

טבלת מספרים ראשוניים בדרך איטרטיבית

יום רביעי, אוגוסט 18, 2010

בפוסט זה הצעתי דרך לחישוב מספרים ראשוניים על ידי שליפה אחת (CTE רקורסיבי כפול – ליתר דיוק). כאן אני מציע דרך איטרטיבית שהיא יותר יעילה, כשהרעיון באופן כללי הוא כזה: כשבודקים אם מספר מסויים הוא ראשוני – יש לנסות ולחלק אותו בכל המספרים הראשוניים שהם קטנים או שווים לשורש הריבועי שלו (או בהיעדר טבלה של מספרים ראשוניים – וזה בדרך כלל המצב – מחלקים אותו בכל המספרים השלמים בין 2 לבין השורש הריבועי שלו). ההיגיון כאן הוא די ברור – אם מספר מתחלק במספר הגדול מהשורש שלו – התוצאה תהיה קטנה מהשורש שלו, ממילא הוא מתחלק גם בה. למשל- 100 מתחלק ב-20...
אין תגובות

פונקציית XIRR לחישוב שיעור תשואה פנימי (שת"פ)

יום שישי, יולי 30, 2010

IRR = Internal Rate Of Return (ובעברית- שת"פ) הוא מדד מקובל לחישוב כדאיות פרוייקט. פרוייקט כלכלי טיפוסי מורכב מהשקעות גדולות בתחילת הדרך וזרם הכנסות בעתיד, ואנחנו מחפשים את שער הריבית התיאורטי הגלום בפרוייקט; כלומר- אם הפרוייקט לא היה אלא תוכנית חסכון בה מפקידים הרבה כסף בהתחלה ונהנים מהכנסות בהמשך – מה היה שער הריבית של אותה תוכנית חסכון שאינה אלא בת דמותו של הפרוייקט הנ"ל. טכנית הכוונה לאותו שער ריבית שעבורו הענ"נ (הערך הנוכחי הנקי, NPV = Net Present Value) הוא 0. משחישבנו את השת"פ – עלינו להשוות אותו לריבית במשק: אם הוא גבוה יותר אזי ההשקעה כדאית (ביחס לאלטרנטיבה), ואם לא-...

מגדלי האנוי

יום חמישי, יולי 15, 2010

אתגר מגדלי האנוי שמוכר לכל מי שעסק ברקורסיה במסגרת מבוא למדעי המחשב: משחק שהומצא במערב וניתן לו שם בעל נופך מזרח אסיאתי מסתורי ולצידו אגדה על נזירים המחשבים את קיצו של העולם לאחור בעוד 64^2 שניות.. באופן מעורר חשד זה מזכיר אגדה אחרת – מופרכת לא פחות – על האיש שהמציא את משחק השחמט וביקש תמורת המצאתו גרגר חיטה כנגד המשבצת הראשונה, 2 גרגרים כנגד השניה, 4 כנגד השלישית וכך הלאה – טור הנדסי של מכפלות של 2, ובמקרה זה מספר גרגרי החיטה הוא 64^2 שזה הרבה מעבר למה שיש + מה שהיה + מה שיהיה.. ולענייננו- נתחיל עם הקוד (למי...

יום π שמח

יום שני, מרץ 15, 2010

אתמול (ארבעה עשר במרץ ציינו את יום ה-π הבינלאומי. לרגל המאורע- שתי וריאציות למציאת שני השלמים שהמנה שלהם מהווה הקירוב הטוב ביותר ל-π (שהוא כידוע מספר לא רציונלי) מבין המספרים עד 1000. בשני המקרים מחלקים את כל אחד מהמספרים ב-π, מעגלים את התוצאה, ומחלקים את המספר מחדש – אך הפעם בעיגול הנ"ל, ולסיכום – מוצאים את ההפרש בערך מוחלט מ-π. השיטה הראשונה האלגנטית יותר- כל שורה מושווית לקודמת וגוררת את הפרמטרים שמחזירים את התוצאה היותר טובה מבין השתיים, ולבסוף רק השורה האחרונה מוצגת: Declare @N Int; Set @N=1000; With Nm As (Select 0 N, ...
אין תגובות

מחולל מספרים ראשוניים

יום רביעי, ינואר 13, 2010

לא הכי שימושי, אבל אתגר נצחי לחובבי הז'אנר: Declare @N Int=1000; With T As (Select 1 Mispar Union All Select Mispar+1 From T Where Mispar<@N) Select T1.Mispar*T2.Mispar Mispar From T T1, T T2 Group By T1.Mispar*T2.Mispar Having Count(*)=2 And T1.Mispar*T2.Mispar<=@N Order By 1 option (MaxRecursion 0); במקרה זה מוכפלים המספרים 1..1000 אלו באלו, ונשלפות המכפלות שמופיעות רק פעמיים: אלו הם המספרים הראשונים שנוצרים רק ממכפלה ב-1. ודרך שונה: Declare @N Int=1000; With T As (Select 2 Mispar Union All Select Mispar+1 From T Where Mispar<@N) Select Mispar From T T1 Where Not Exists (Select * From T T2 Where T2.Mispar<=Sqrt(T1.Mispar) And T1.Mispar%T2.Mispar=0) Order By 1 option (MaxRecursion 0); במקרה זה מחפשים את כל המספרים מ-2 ואילך שאין מספר אחר שהם מתחלקים בו ללא שארית (נבדקים כל המספרים מ-2 ועד שורש המספר - מטעמי יעילות). ולבסוף- הדרך הכי...
אין תגובות

יחס של רבים לרבים ללא טבלת עזר

יום רביעי, ינואר 6, 2010

בדרך כלל יחס של רבים לרבים בין שתי טבלאות ממומש באמצעות טבלת עזר שמקשרת בין שתי הטבלאות, והמפתח הראשי שלה הוא צירוף המפתחות הראשיים של שתיהן. ניתן במקרה הצורך ליצור יחס של רבים לרבים ללא טבלת עזר. אינני יודע מתי זה טוב, אבל זה אפשרי ולהלן שתי דרכים. נניח שבעירנו יש מספר מוסדות תרבות, כל אחד פתוח בימים אחרים במהלך השבוע, ואנחנו מעוניינים להחזיק את המידע הזה. נקים קודם כל את טבלת ימי השבוע: Create Table #T_Yamim(Yom Int,Shem VarChar(Max)) Insert Into #T_Yamim Select 1,'א' Insert Into #T_Yamim Select 2,'ב' Insert Into #T_Yamim Select 3,'ג' Insert Into #T_Yamim Select 4,'ד' Insert Into #T_Yamim Select 5,'ה' Insert Into #T_Yamim Select 6,'ו' Insert Into #T_Yamim...
אין תגובות