2016 מועד ב סמסטר ב

2016 מועד ב סמסטר ב

noa davidovitch (guest) 25 Jan 2019 10:16

http://tau-cs1001-py.wdfiles.com/local--files/exams/exam_2016b_moed-b.pdf
בשאלה 5 במבחן המצורף, לא הבנתי איך משפיע השינוי בקוד שביצעו בפונקציה על הקידוד.
את סעיף א' אפשר לעקוף ולתת מחרוזת שאין בה חזרות ואז בטוח הקידוד יהיה שווה
אבל בשביל סעיפים ב וג צריך להבין מה הפונקציה עושה- ולא הבנתי
אשמח אם מישהו הבין ויסביר :)

Re: 2016 מועד ב סמסטר ב

Hagai Shapira 25 Jan 2019 13:34

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

while k<min(max_length,n-p)and T[p-m+k] == T[p+k]:

בפונקציה החדשה אם הפרמטר הוא True אז אנחנו מגבילים את k לפי res והוא המינימום גם עם m.

res = min(m,max_length,n-p) if what else min(max_length,n-p)

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

Last edited on 25 Jan 2019 13:36 by Hagai Shapira Show more

noa davidovitch (guest) 25 Jan 2019 14:36

כן תודה רבה!