מציג תוצאות 1 עד 1 מתוך 1

אשכול: מבני נתונים - שובך היונים

  1. #1
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל מבני נתונים - שובך היונים

    שלום חברים.

    מישהו יכול להסביר את מה שמיסגרתי?
    לא הבנתי איך ההנחה בשלילה הזאת, גוררת שקיים בהכרח t באותו טווח? למה t לא בטווח כולו? כלומר כולל n*m?
    אולי כי אני לא מבין את זה אני גם לא מבין איך חל כאן שובך היונים.

    אשמח להסבר.

    תודה רבה.
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: png עלה.png‏ (777.8 ק"ב , 6 צפיות) Find_2D_Local_Peak_Naivelarr)1. (i,j) = (1, 1)2. While (i,j) is not a local 2D peaka. (i,j) +- argmaxije {(i, j-1),(i-1{,}),(1+1,}),(i,j+1)}{arr[7.J13. Return (i,j) טענה: האלגוריתםFind _2D _Local _Peak _Naive תמיד עוצר אחרי לכל יותר n •m פעמים של הלולאה הוכחה: לפי התנאי לכניסה ללולאה (2), אם הרצת האלגוריתם נכנסת ללולאה (2) יש לפחות שכן אחד למיקום (i,j) עם ערך גדול ממש מהערך במיקום (i,j) עבור האינדקסים i ו-j באותו הזמן. במקרה כזה אחרי שורה (a) עבור האינדקסים החדשים i ו-j המיקום (i,j) החדש הוא בעל ערך גדול ממש מהערך במיקום הקודם (כלומר לפני העדכון בשורה (a)). לכן בכל פעם שהרצת האלגוריתם נכנסת ללולאה (2) הערך במיקום (i,j) גדל ממש (מה שמשתנה אלה האינדקסים ולא הערכים במערך). נסמן ב- 4 את הערך במיקום (i,j) אחרי שהרצת האלגוריתם נכנסה ללולאה (2) t פעמים (למשל [1 ,1] a)=arr ). אז אנחנו יודעים שאם t ,4. במערך יש n •m ערכים שונים לכל היותר. אז נוכל לומר שלא יתכן שקיים -an (כלומר לא יתכן שהרצת האלגוריתם נכנסה n •m פעמים ללולאה (2)) כי אם נניח בשלילה שקיים כזה, אז מעקרון שובך היונים קיים t בין 1 - t 0 עבורו a,=dn-m אבל t


מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 0

There are no members to list at the moment.

הרשאות

  • אתה לא יכול לפרסם אשכולות חדשים
  • אתה לא יכול לפרסם תגובות
  • אתה לא יכול לצרף קבצים להודעותיך
  • אתה לא יכול לערוך את הודעותיך
  •  
אודות Emath
האתר Emath הינו יוזמה פרטית והוקם בתחילת שנת 2008 .
מטרתנו הינה למנף את הישגי התלמידים למתמטיקה ופיסיקה בארץ בכלל ובפרט בקרב תלמידי התיכון .
אנו מספקים מספר שירותים לתלמיד, ביניהם גישה למאות אלפי פתרונות איכותיים לתרגילים, פורום עזרה במתמטיקה ופיסיקה הגדול מסוגו בארץ, מאגר סיכומים, מרתונים בוידאו, פתרונות לבגרויות ועוד.
כלים אלו, מאפשרים לכל אחד, ללא תלות במיקומו, ללמוד, לתרגל ולהתמקצע על-מנת להתכונן בצורה מיטבית לבגרות במתמטיקה או פיסיקה .

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו