חידת דחיסה

עמוד
מוצגות 9 תגובות – 1 עד 9 (מתוך 9 סה״כ)
  • מאת
    תגובות
  • #77359
    אורן בקר
    משתתף

    המצאתי חידה, וחשבתי לשתף אתכם:

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

    מטרת החידה היא שהפונקציות יוכלו לעבוד עם מספרים גדולים ככל האפשר (לא רק מ 0 עד 15, אלא מ 0 ועד n, כאשר n מקסימלי).

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

    אורן.

    #79081
    CodeGuru
    מנהל בפורום

    כותרת: תשובה (מי שרוצה לפתור לבד, שלא יקרא)
    שאלה נחמדה. המספר המירבי הוא 21.
    תחת ההגדרה Tj = j*(j+1)/2
    הדחיסה היא Tj + i
    והפתיחה היא
    for (j=0; Tj<=x; j++) ; j–; i = x-Tj

    #79082
    אורן בקר
    משתתף

    כותרת: יפה, אבל אפשר גם בסיבוכיות O(1)
    את פונקצית הפתיחה אפשר גם לכתוב כך:

    a = (sqrt(8*p+1)-1)/2;
    b = p – a*(a+1)/2.

    אבל איך אפשר לכתוב את הפונקציות כך שלא יכילו פעולת שורש וסיבוכיותם תהיה O(1) ?

    ההנחה היא שסיבוכיותיהן של פקודות שפת מכונה של
    80×86
    היא O(1)

    אורן

    #79084
    CodeGuru
    מנהל בפורום

    כותרת: תוכנית אסמבלי קצרה (ללא שורש)
    דחיסה:
    CMP AL,0A
    JLE SMALL
    SUB AX,1716
    NEG AX
    SMALL:
    MOV BX,1701
    MUL BX
    MOV AL,AH

    פתיחה:
    XOR AH,AH
    MOV BH,17
    DIV BH
    CMP AL,AH
    JGE SMALL
    SUB AX,1716
    NEG AX
    SMALL:

    #79085
    אורן בקר
    משתתף

    כותרת: בדיוק
    זה אפילו טיפה יותר פשוט מהפתרון שניתן לי במקור ע"י מת´יו הנדרי.

    (לדעתי, יש טעות קטנה בפקודה האחרונה שבפונקציית הדחיסה, שאמורה להיות ADD ולא MOV, אבל זו כנראה טעות הקלדה).

    #79086
    CodeGuru
    מנהל בפורום

    כותרת: ואיך זה עובד?
    א. זו לא טעות (צ"ל MOV). אם אתה מוכן שהתוצאה תהיה ב AH, אז אפשר גם לחסוך את הפקודה הזאת.
    ב. למה זה עובד? יש בתוכנית כמה "טריקים" נחמדים.

    #79087
    אורן בקר
    משתתף

    כותרת: טעות שלי
    כן, טעות שלי, קראתי שוב והבנתי איך זה עובד.

    אין טעם שאני אסביר איך הפתרון עובד, כי אני ידעתי מראש את הרעיון שעומד מאחוריו. אני אנסה לפרסם את הפורום בסביבה שלי, אולי עוד אנשים יתחילו להשתתף.

    אורן.

    #79088
    אורן בקר
    משתתף

    כותרת: טעות שלי
    כן, טעות שלי, קראתי שוב והבנתי איך זה עובד.

    אין טעם שאני אסביר איך הפתרון עובד, כי אני ידעתי מראש את הרעיון שעומד מאחוריו. אני אנסה לפרסם את הפורום בסביבה שלי, אולי עוד אנשים יתחילו להשתתף.

    אורן.

    #79089
    אורן בקר
    משתתף

    כותרת: טעות שלי
    כן, טעות שלי, קראתי שוב והבנתי איך זה עובד.

    אין טעם שאני אסביר איך הפתרון עובד, כי אני ידעתי מראש את הרעיון שעומד מאחוריו. אני אנסה לפרסם את הפורום בסביבה שלי, אולי עוד אנשים יתחילו להשתתף.

    אורן.

מוצגות 9 תגובות – 1 עד 9 (מתוך 9 סה״כ)
  • יש להתחבר למערכת על מנת להגיב.