- This topic has 8 תגובות, 2 משתתפים, and was last updated לפני 22 שנים by
.
-
תגובות
-
המצאתי חידה, וחשבתי לשתף אתכם:
כתבו שתי פונקציות: הפונקציה ה"דוחסת", המקבלת זוג סדור של מספרים שלמים, כאשר ידוע שהראשון אינו קטן מהשני, ומחזירה מספר בגודל 8 ביט. והפונקציה ה"מחלצת", ההופכת את התהליך, מקבלת מספר בגודל 8 ביט ומחזירה את הזוג הסדור (שיצר אותו ע"י הפונקציה הדוחסת).
מטרת החידה היא שהפונקציות יוכלו לעבוד עם מספרים גדולים ככל האפשר (לא רק מ 0 עד 15, אלא מ 0 ועד n, כאשר n מקסימלי).
א. מהו טווח המספרים הגדול ביותר שניתן לדחוס?
ב. כתוב פונקציה דוחסת ופונקציה מכווצת.
ג (החלק הקשה). כתוב את הפונקציות, ללא שימוש בפעולת שורש.אורן.
כותרת: תשובה (מי שרוצה לפתור לבד, שלא יקרא)
שאלה נחמדה. המספר המירבי הוא 21.
תחת ההגדרה Tj = j*(j+1)/2
הדחיסה היא Tj + i
והפתיחה היא
for (j=0; Tj<=x; j++) ; j–; i = x-Tjכותרת: יפה, אבל אפשר גם בסיבוכיות O(1)
את פונקצית הפתיחה אפשר גם לכתוב כך:a = (sqrt(8*p+1)-1)/2;
b = p – a*(a+1)/2.אבל איך אפשר לכתוב את הפונקציות כך שלא יכילו פעולת שורש וסיבוכיותם תהיה O(1) ?
ההנחה היא שסיבוכיותיהן של פקודות שפת מכונה של
80×86
היא O(1)אורן
כותרת: תוכנית אסמבלי קצרה (ללא שורש)
דחיסה:
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:כותרת: בדיוק
זה אפילו טיפה יותר פשוט מהפתרון שניתן לי במקור ע"י מת´יו הנדרי.(לדעתי, יש טעות קטנה בפקודה האחרונה שבפונקציית הדחיסה, שאמורה להיות ADD ולא MOV, אבל זו כנראה טעות הקלדה).
כותרת: ואיך זה עובד?
א. זו לא טעות (צ"ל MOV). אם אתה מוכן שהתוצאה תהיה ב AH, אז אפשר גם לחסוך את הפקודה הזאת.
ב. למה זה עובד? יש בתוכנית כמה "טריקים" נחמדים.כותרת: טעות שלי
כן, טעות שלי, קראתי שוב והבנתי איך זה עובד.אין טעם שאני אסביר איך הפתרון עובד, כי אני ידעתי מראש את הרעיון שעומד מאחוריו. אני אנסה לפרסם את הפורום בסביבה שלי, אולי עוד אנשים יתחילו להשתתף.
אורן.
כותרת: טעות שלי
כן, טעות שלי, קראתי שוב והבנתי איך זה עובד.אין טעם שאני אסביר איך הפתרון עובד, כי אני ידעתי מראש את הרעיון שעומד מאחוריו. אני אנסה לפרסם את הפורום בסביבה שלי, אולי עוד אנשים יתחילו להשתתף.
אורן.
- יש להתחבר למערכת על מנת להגיב.