למישהו יש רעיון לאלגוריתם עבור השאלה הבאה:

[lalal6]

למישהו יש רעיון לאלגוריתם עבור השאלה הבאה:

נתונה סדרה של מספרים שלמים במערך zz A[1...n] zz כך שמתקיים: zz | A - A[i+1] | <=1 zz לכל zz 1<= i <n zz.

נתון ש-A[1]=a ו-A[n]=b, ומתקיים a<b.

סעיף א':

לכתוב אלגוריתם כך שבהינתן מספר שלם x כך ש-zz a<=x<=b zz מוצא אינדקס i כך ש-A=x.

רעיונות?

 

[lalal6]

ניסיון

המרחק בין x לבין a, הוא לפחות |x-a| .

זו השערה שהגעתי אליה לאחר מספר בדיקות בדוגמאות קונקרטיות. אני די בטוח שהיא נכונה.

לכן אפשר לעבור על איברי המערך החל מאינדקס |x-a|.ואז חסכתי מעבר על |x-a| איברים.

מקווה שאני לא טועה.

בכל מקרה אני לא חושב שזה באמת שיפור משמעותי ושזה מה שהתכוון המשורר.

 

[FineSilverMan]

פשוט ללכת על איברי הסדרה

i=1
אם A=x אז החזר i
אחרת i+1

הסדרה יכולה להיות:
|הקוד|
a=1
b=4
x=3
A={1,2,1,2,1,2,3,4}
|סקוד|

יש דרכים לקיצור דרכים, למשל ללכת לאיבר האמצעי ולבדוק אותו ביחס ל-x וכך להסתכל רק על חצי מהמערך ואז רבע וכך הלאה, אבל הסדרה יכולה להיות:

|הקוד|
a=1
b=4
x=3
A={1,2,3,2,1,2,1,2,1,2,3,4}
|סקוד|
כך שהתשובה נמצאת בהתחלה. אם כי גם לקראת הסוף.

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

 

[lalal6]

לעבור רגיל על המערך!? זה פתרון נאיבי

קשה לי להאמין שזה מה שמצפים. בכל זאת..זו שאלה ממבחן.

 

[cookie man1]

אפשר חיפוש בינארי

למרות שהמערך לא ממוין, מובטח לנו שאם
zz A[n]>x zz ו- zz A[m]<x zz אז קיים בין m ו-n אינדקס שבו הערך הוא x.

 

[lalal6]

מי האינדקסים m,n ואיפה אתה עושה חיפוש בינארי

מה בדיוק אתה מציע לעשות?

איך אתה מוצא את m ו-n, ואחרי שמצאת, איפה אתה עושה חיפוש בינארי?

חיפוש בינארי רלוונטי למערך ממויין.

 

[cookie man1]

בכוונה ציינתי כי המערך לא ממויין

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

 

[cookie man1]

וראוי לתת קרדיט ל-FineSilverMan

שכבר ציין פתרון זה (רק עכשיו שמתי לב)

 

[FineSilverMan]

אולי זו שאלה מכשילה

התלמיד שלא יודע היטב את החומר ילך על שיטה מתוחכמת יותר שלא עובדת במקרה הזה...

אם הערך גבוה, נניח x=50 כאשר a=1 ו-b=100 ומתקיים A[i+1]=A+{-1,0,1} zzz
אז אנחנו יכולים להתחיל לחפש את x החל מהאיבר ה-50
במקרה כזה, אנחנו יודעים שיש לפחות 100 איברים במערך.
אם יש 1,000 איברים, למשל, אז המקסימום הוא 550.
כלומר האלגוריתם יכול לדלג על חלק מהאיברים, בהתאם ל-x.
ניתן גם לחשב את האיבר המינימלי.

 

[אורי769]

כמה הערות

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

 

[FineSilverMan]

אבל במערך של 10 איברים

מ-1 עד 10, אין x=20.
כלומר הערך המבוקש לא חייב להיות בסדרה.

 

[אורי769]

לכן נקרא שמו "משפט ערך הביניים"

הוא תקף רק לערכי ביניים ו-20 אינו ערך בין 1 ל-10.

 

[FineSilverMan]

השאלה היא האם מדברים על ערך בציר ה-X

או ה-Y

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

כלומר בין (1,1) לבין (10,10), הפונקציה הרציפה תחזיר את כל הערכים 2-9, אבל היא יכולה להחזיר גם את 20.

אין כאן חובה של מונוטוניות, למשל.

 

[אורי769]

לא הבנתי מה אתה מנסה להגיד

מפשט ערך הביניים:
אם f רציפה בקטע [a,b] ונניח ש-f(a)<f(b) q אז לכל y המקיים f(a) =< y =< f(b) q קיים x בקטע כך ש-f(x)=y.

מפשט ערך הביניים הבדיד (הטענה בשאלה):
אם a q סדרה "רציפה" (במובן שהמרחק בין ערכים סמוכים הוא לכל היותר 1) ונניח a[1]<a[N] q אז לכל y המקיים a[1] =< y =< a[N] q קיים q 1 =< i =< N כך ש-a = y.

בשני המקרים אף אחד לא טען שערכים שמחוץ לתחום לא מתקבלים.

 

[FineSilverMan]

טוב, רק חזרתי מיום ארוך במרכז...

וכאשר לחצתי על "שלח", עבר בי הרצון להמנע מכך ולהתנסח מחדש.

חשבתי שכאשר כתבת ש-20 אינו ערך בין 1 ל-10, אז המערך לא יכול להכיל אותו.

המקסימום התיאורטי של המערך תלוי ב-n, זה כל מה שאני רוצה להגיד, אני חושב.