יום רביעי, 15 באפריל 2009

קומבינה לינארית


עכשיו עליתי מדרגה עברתי למשוואה מסוג .
לעין בלתי מזוינת זו נראית משוואה פשוטה להכנה, לא שונה בהרבה מסוג המשוואות הקודם שעבדתי עליו – אבל למעשה יש פה קפיצת מדרגה גדולה מבחינה אלגוריתמית.
אחרי שנפתר מהמכנים ע"י מכפלה ב 90- נקבל ועכשיו אנחנו צריכים לקבוע את המקדמים הפנימיים של X כך שאחרי פתיחת הסוגריים נקבל 2x (או כל ביטוי אחר שבחרנו). ולכן אנחנו צריכים למצוא a, b, c כך ש . לשם כך נהוג להשתמש בקומבינציה לינארית בדידה.
אבל האלגוריתם הזה יכול לתת גם קומבינציות קצת מוגזמות, למשל, פתרון הקומבינציה יהיה מה שאומר שהמשוואה תהיה . תודו שזה כבר מוגזם. אז הוספתי אלגוריתם חמדן איזון שלמעשה מוריד את הערכים של המקדמים ע"י החלפות מבלי לשנות את תוצאת הקומבינציה.
כך אם נוסיף ל a 56 (המקדם של b) ול b נוסיף 40 (המקדם של a) נקבל . נחזור על התהליך הזה עד שלא נוכל לשפר יותר ונגיע ל , ואם נחזור על אותו תהליך גם למקדמים החופשיים נקבל את הנוסחא . וזה כבר נראה יותר אנושי.
בעיה נוספת שיכולה לצוץ היא ניוון של פרמטרים. למשל, הפיתרון של , יהיה מה שאומר שהמשוואה תהיה , וזה די משעמם. אז הוספתי במקרה של שני מקדמים שהם אפס (a ו c בדוגמא שלנו), לעשות החלפה ביניהם. וכך מקבלים .
כמובן שכדי לסדר את הסימנים הייתי צריך להשקיע בערך שעתיים של ניסוי וטעיה – הרבה מאוד טעיה.
לצערי הרב התוכנה עדיין סובלת מבעיות יציבות ויש בה עדיין דליפות זיכרון והיא נופלת מדי פעם, אני אצטרך להשקיע עוד כשעה שעתיים כדי לייצב אותה אבל כרגע אין לי זמן מכיוון שאני צריך להמשיך הלאה, אני מניח שמתישהו אני אתפנה לזה.

2 comments:

  1. You ought to publish the code; I fail to imagine how inheritance fits into all this, and in general we know too little about the code from your description (the only thing we know for sure is the implementation language - surely it's the memory-leaking and the core-dumping one.)

    -- yosefk

    השבמחק
  2. קודם כל אף אחד לא אמר שצריך ירושות כדי להשתמש בהן.
    :-)
    חוץ מזה, בירושה וברקורסיה השתמשתי בחלק שמתאר את הביטוי ומדפיס אותו ללא יתירות. כולם יורשים מ"איבר" ויש "ערך", "משתנה", "חיבור", "כפל", "שבר" ו "משוואה". יש הרבה לוגיקה ספציפית כדי למנוע יתירות כמו להחליף 1x ב x.
    בהתחלה ניסיתי לעשות זאת ברמת הסטרינגים אבל זה מסובך מדי, עכשיו גם הייתי צריך להתחיל עם הקצאות דינמיות וזה ברדק.

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

    השבמחק