שרשור שעורי בית 29/12/2002

[איגור קרסיק]

....

זויותיו של המחומש הנ"ל ידועות לך [כל אחת 105 מעלות]. ולכן בעזרת a ניתן למצא את הגובה ל-AC במשולש ABC וכך ניתן למצא את שטחו. בשביל למצא אתשטח המחומש יש להוריד את AD וכך תקבלי עוד שני משולשים שו"ש: ADE שווה בשטחו ל-ACB מטעמי חפיפה. את שטח ADC קל למצא [שכן קל צלע היתהת לחישוב כביטוי של a וכל זווית ניתנת לחישוב מספרית].

 

[M o o s h i t]

שאלה על תוחלת - דחוף!

בוחרים באופן אקראי 2 סדרות: P באורך m, ו-T באורך n, מתוך קבוצה בת 2<=d איברים (ניתן לבחור את אותו איבר פעמיים). כעת משווים את הסדרה P לתחילת הסדרה T. (n>=m). מנסים לבדוק את הסדרה P שווה לתחילת הסדרה T, כאשר ברגע שמתגלה אי-שיוויון ראשון, עוצצרים את פעולת ההשוואה. (לכל היותר נצטרך להשוות m איברים). מהי תוחלת מספר ההשוואות בין איברים בודדים שמבצעת לולאת ההשוואה? ובעיקר, איך הגעתם לתשובה?

 

[freedom rider]

אפשר לקבל הבהרות?

1) האם זה שיעורי בית או משהו אחר? 2) האם ניתן לבחור כל איבר של הקבוצה לכל אחת מהסדרות לכל מקום בסדרה? כלומר, אם נניח הקבוצה היא {1,2,3,4,5}, האם הסדרה 5,5,5,5,5,5 היא סדרה אפשרית?

 

[M o o s h i t]

תשובה

לשאלה 2, כן, הכל מותר. לשאלה 1, זה לא בדיוק ש.ב

 

[Fingertip]

ובכן....

האינטואיציה שלי די גרועה, אבל התשובה שקיבלתי היא שהתוחלת היא d/d-1 שזה טיפה יותר מ-1. כלומר, במקרה הממוצע יתבצעו 2 השוואות... מקווה שעזרתי. אהד.

 

[Fingertip]

אופס!

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

 

[freedom rider]

לא בדיוק שעורי בית? בערך?

אוקיי ההסתברות ששני איברים מקבילים בסדרות (שני הראשונים, שני השניים, וכו´) יהיו זהים היא אחד חלקי d. נסמן p=1/d. נסמן גם q=1-p. ההסתברות שהלולאה תעצור אחרי השוואה אחת היא לכן q. ההסתברות שהלולאה תעצור אחרי שתי השוואות היא p*q (שוויון באיברים הראשונים, אי שוויון בשניים). ההסתברות שהלולאה תעצור אחרי שתי השוואות היא p^2)*q). וכך הלאה. לכן התוחלת היא:

1*q+2*p*q+3*(p^2)*q+....+m*(p^(m-1))*q​

 

[M o o s h i t]

אבל מה הסכום?

 

[Fingertip]

הסכום יוצא מגעיל, אני חושב...

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

 

[M o o s h i t]

עוד שאלה דחופה - גיאומטריה חישובית

נתונה סדרה של נקודות: <p0,p1,p2......p(n-1)> כלומר מ-0 עד n-1. רוצים לבדוק אם הסדרה היא סדרת קודקודים עוקבים של מצולע קמור. האלגו המוצע: בודקים כל זוית : >Pi Pi+1 Pi+2 (חיבור האינדקסים מתבצע מודולו n). אם קבוצת כל הזויות אינה מכילה גם פניות שמאלה וגם פניות ימינה, אז האלגו מחזיר "כן", אחרת מחזיר "לא". יש להראות שהאלגו לא תמיד מחזיר את התשובה הנכונה, ואיך ניתן לתקנו?

 

[טלמון סילבר]

אולי

לבדוק גם, שהצלעות לא חותכות זו את זו? אחרת יכולים להתקבל "כוכבים" למיניהם.

 

[M o o s h i t]

וזה לא מספיק שמניחים שאלה הקודקודים

של המצולע?

 

[zimes]

אם מניחים...

אפשר להניח גם שאלה קודקודים עוקבים של מצולע קמור, לא?

 

[zimes]

ושהנקודה הראשונה היא גם האחרונה

(ז"א - להכניס לבדיקה גם את הצלע בין נקודה 0 לנקודה n-1)

 

[M o o s h i t]

זה לא נכון

אני אתקן: נתונה סדרת נקודות המהווה קודקודים של מצולע! רוצים לדעת האם המוצלע הוא קמור

 

[M o o s h i t]

אולי בגלל - מה אתם אומרים על הפתרון

אולי בגלל שקבוצה שאינה מכילה פניות שמלאה וגם ימינה, יכולה להכיל רק פניות שמאלה, או רק פניות ימינה, או שלא להכיל פניות כלל, כלומר שכל הנקודות על ישר אחד

 

[טלמון סילבר]

תחליטי סוף סוף, אם נתונה קבוצת

קודקודים עוקבים, ואז אולי יש משמעות ל"פניות ימינה-שמאלה", או קבוצת נקודות המהוות קודקודי מצולע, מבלי לקבוע את הסדר שלהן?

 

[M o o s h i t]

כתבתי תיקון...

נתונה קבוצה המהווה קודקודי מצולע, צריך להחליט האם המצולע הוא קמור!

 

[Shiberia]

צריך לכל פרמוטציה לעשות את זה

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

 

[M o o s h i t]

אה, כן...

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