שירשור החידות הגדול
ראה תגובה לtheAman, לפניך.
תרגיעו, אפילו בשרשור הסרטים לא מלחיצים ככה.
אפשר לחשוב שיש לחץ של חידות טובות שיתפרץ בצורה לא מבוקרת אם לא נשחרר מספיק מהר
אולי יותר מאוחר, אולי מחר. אני קצת עסוק. לרשום אותה לא בעיה , אבל לא יהיה לי זמן להגיב ודווקא יש לי אחת טובה - חזרה לחידה מתמטית כמו שצריך. יש מה לחכות.
תרגיעו, אפילו בשרשור הסרטים לא מלחיצים ככה.
אפשר לחשוב שיש לחץ של חידות טובות שיתפרץ בצורה לא מבוקרת אם לא נשחרר מספיק מהר
אולי יותר מאוחר, אולי מחר. אני קצת עסוק. לרשום אותה לא בעיה , אבל לא יהיה לי זמן להגיב ודווקא יש לי אחת טובה - חזרה לחידה מתמטית כמו שצריך. יש מה לחכות.
משה
טוב, נזכרתי בעוד אחת טובה יחסית.
זה מריח ממדעי המחשב, אז אני מתנצל בפני מי שלא מכיר כמה מושגים (אסביר בקצרה) אך אין שום צורך בידע מוקדם.
נתונה לכם סדרת מספרים (יכולים להיות גם שליליים) . תמצאו אלגוריתם (דרך חישוב, לצורך העיניין) למצוא תת הסדרה
בתוך הסדרה הנ"ל אשר סכום המספרים בה מקסימלי. האלגוריתם צריך להיות יעיל.
הסבר מה זה יעיל: טריביאלי להגיד שפשוט עוברים על כל תת-הסדרות (כל הזוגות של איבר ראשון ואיבר אחרון), מסכמים את הסדרה ושומרים את המספר המקסימלי ואת תת הסדרה שיצרה אותו. אם יש לנו N איברים בסדרה נצטרך לזה סדר גודל של N בשלישית גישות לאיברים (בחירת איבר ראשון כפול בחירת אחרון כפול מעבר עליהם לשם סיכומם).
זה נחשב לא יעיל. ניתן פה לפתור בצורה הרבה יותר יעילה.
יש לשאלה הזו פתרונות מסובכים ופתרונות אלגנטיים. הזוכה יהיה מי שייתן פתרון אלגנטי אלא אם כם לא יהיה כזה אך כן יהיה פתרון מסובך.
תשובות במסרים פרטיים.
זה מריח ממדעי המחשב, אז אני מתנצל בפני מי שלא מכיר כמה מושגים (אסביר בקצרה) אך אין שום צורך בידע מוקדם.
נתונה לכם סדרת מספרים (יכולים להיות גם שליליים) . תמצאו אלגוריתם (דרך חישוב, לצורך העיניין) למצוא תת הסדרה
בתוך הסדרה הנ"ל אשר סכום המספרים בה מקסימלי. האלגוריתם צריך להיות יעיל.
הסבר מה זה יעיל: טריביאלי להגיד שפשוט עוברים על כל תת-הסדרות (כל הזוגות של איבר ראשון ואיבר אחרון), מסכמים את הסדרה ושומרים את המספר המקסימלי ואת תת הסדרה שיצרה אותו. אם יש לנו N איברים בסדרה נצטרך לזה סדר גודל של N בשלישית גישות לאיברים (בחירת איבר ראשון כפול בחירת אחרון כפול מעבר עליהם לשם סיכומם).
זה נחשב לא יעיל. ניתן פה לפתור בצורה הרבה יותר יעילה.
יש לשאלה הזו פתרונות מסובכים ופתרונות אלגנטיים. הזוכה יהיה מי שייתן פתרון אלגנטי אלא אם כם לא יהיה כזה אך כן יהיה פתרון מסובך.
תשובות במסרים פרטיים.
משה
)
)
טוב, נגמר הזמן.
amirbd פתר נכונה והשרביט עובר אליו.
כתבתי מקודם שהוא "פתר לא אלגנטי", ואני רוצה לתקן את דברי. הפתרון שלו אלגנטי בפני עצמו, רק שהפתרון שרציתי הוא לדעתי יותר פשוט לתיאור (ולכן יותר אלגנטי). זה סוביקטיבי כמובן.
הפתרון שקיוויתי לו:
עוברים על כל סדרת המספרים ויוצרים סדרה אחרת של סכומים מצטברים מההתחלה. כמו אינטגרל רק שעל פונקציה לא רציפה.
מוצאים את המינימום הגלובלי והמקסימום הגלובלי.
אם המינימום הגלובלי בא לפני המקסימום הגלובלי (תמונה ראשונה) אז תת הסדרה היא פשוט מהאיבר המתאים למינימום עד לאיבר המתאים למקסימום.
אם לא, אז מוצאים גם את המקסימום בין המינימום הגלובלי ועד הסוף, C בתמונה השנייה, וגם את המינימום שבין המקסימום הגלובלי וההתחלה, D.
תת הסדרה היא או DA או BC, זו עם ההפרש הגדול יותר (BC במקרה שבציור המסוים פה)
לכל הפעולות הנ"ל מספיק לעבור על האיברים בסדרה באופן עוקב, כך שזה ליניארי.
amirbd פתר נכונה והשרביט עובר אליו.
כתבתי מקודם שהוא "פתר לא אלגנטי", ואני רוצה לתקן את דברי. הפתרון שלו אלגנטי בפני עצמו, רק שהפתרון שרציתי הוא לדעתי יותר פשוט לתיאור (ולכן יותר אלגנטי). זה סוביקטיבי כמובן.
הפתרון שקיוויתי לו:
עוברים על כל סדרת המספרים ויוצרים סדרה אחרת של סכומים מצטברים מההתחלה. כמו אינטגרל רק שעל פונקציה לא רציפה.
מוצאים את המינימום הגלובלי והמקסימום הגלובלי.
אם המינימום הגלובלי בא לפני המקסימום הגלובלי (תמונה ראשונה) אז תת הסדרה היא פשוט מהאיבר המתאים למינימום עד לאיבר המתאים למקסימום.
אם לא, אז מוצאים גם את המקסימום בין המינימום הגלובלי ועד הסוף, C בתמונה השנייה, וגם את המינימום שבין המקסימום הגלובלי וההתחלה, D.
תת הסדרה היא או DA או BC, זו עם ההפרש הגדול יותר (BC במקרה שבציור המסוים פה)
לכל הפעולות הנ"ל מספיק לעבור על האיברים בסדרה באופן עוקב, כך שזה ליניארי.
משה
amirbd ,
התבלבלתי
לא הסתכלתי על התמונה כשכתבתי.
צ"ל :
מינימום גלובאלי A
מקסימום גלובאלי B
תתי סדרות AC ו DB .
theAman,
תגיד אם עוד צריך לאחר הבלבול שתיקנתי. שיהיה ברור, הגרפים המצוירים הם לא של הסדרה המקורית אלא של סדרת הסכומים המצטברים (האינטרגל).
זה פשוט:
1) צור את סדרת הסכומים
2) מצא נקודות קיצון
אני מציע ש amirbd יפרסם את פתרונו, כי הוא שלח לי אותו בשני נוסחים.
התבלבלתי
לא הסתכלתי על התמונה כשכתבתי.צ"ל :
מינימום גלובאלי A
מקסימום גלובאלי B
תתי סדרות AC ו DB .
theAman,
תגיד אם עוד צריך לאחר הבלבול שתיקנתי. שיהיה ברור, הגרפים המצוירים הם לא של הסדרה המקורית אלא של סדרת הסכומים המצטברים (האינטרגל).
זה פשוט:
1) צור את סדרת הסכומים
2) מצא נקודות קיצון
אני מציע ש amirbd יפרסם את פתרונו, כי הוא שלח לי אותו בשני נוסחים.
משה
משה,moco כתב:amirbd ,
התבלבלתי
צ"ל :
מינימום גלובאלי A
מקסימום גלובאלי B
תתי סדרות AC ו DB .
theAman,
תגיד אם עוד צריך לאחר הבלבול שתיקנתי. שיהיה ברור, הגרפים המצוירים הם לא של הסדרה המקורית אלא של סדרת הסכומים המצטברים (האינטרגל).
זה פשוט:
1) צור את סדרת הסכומים
2) מצא נקודות קיצון
אני מציע ש amirbd יפרסם את פתרונו, כי הוא שלח לי אותו בשני נוסחים....
אני עדיין לא בטוח שהפתרון שלך נכון
נסמן את נקודת המינימום הלוקאלי בין B ל-A ב-E, ואת נקודת המקסימום הלוקאלי בינהם ב-F
תמשוך כעת את E למטה עד שיהיה קצת מעל A (כך ש-A עדיין המינימום הלוקאלי), בצורה דומה תצשוך את F למעלה עד שיהיה קצת מתחת ל-B.
כעת לפי ההסבר שלך DB עדיין יוחזר למרות שהפתרון הנכון יהיה EF
אמיר.
הפתרון - נגדיר ( T( i כסכום תת-הסידרה המקסימאלית שמסתיימת באיבר ה-i
תנאי התחלה -(T(1)=x(1
כעת נבחין כי כדאי לחשב את (T(i+1 מספיק להתבונן בשתי מקרים :
מקרה א - הסדרה הכבדה ביותר שמסתיימת באיבר i+1 היא באורך אחד (דהיינו מכילה רק את (x(i+1
מקרה ב - הסדרה הכבדה ביותר שמסתיימת באיבר i+1 מכילה לפחות שני איברים, ולכן בפרט היא שווה במשקלה לשדרה הכבדה ביותר שמסתיימת באיבר ה-i (בנוסף לאיבר(x(i+1 כמובן.)
כעת ברור שניתן (ע"י ההגדרה הרקורסיבית הבאה) לחשב בזמן לינארי את
(T(1),T(2),...T(n ולהחזיר את הערך המקסימאלי שמצאנו.
ההגדרה המלאה של T :
T(1)=x(1)
T(i+1)=x(i+1) if T( i)<0
T(i+1) = x(i+1)+T( i) otherwise
בנוסף, אם צריך גם למצוא את האינדקסים של תת-הסידרה, שומרים בצד את האינדקסים הכי טובים כל פעם שהמקסימום משתנה.
סיבוכיות הפתרון - זמן לינארי.
דרך אגב - פתרון זה הוא דוגמה לשיטת אופטימיציה כללית שנקראת "תכנון דינאמי".
תנאי התחלה -(T(1)=x(1
כעת נבחין כי כדאי לחשב את (T(i+1 מספיק להתבונן בשתי מקרים :
מקרה א - הסדרה הכבדה ביותר שמסתיימת באיבר i+1 היא באורך אחד (דהיינו מכילה רק את (x(i+1
מקרה ב - הסדרה הכבדה ביותר שמסתיימת באיבר i+1 מכילה לפחות שני איברים, ולכן בפרט היא שווה במשקלה לשדרה הכבדה ביותר שמסתיימת באיבר ה-i (בנוסף לאיבר(x(i+1 כמובן.)
כעת ברור שניתן (ע"י ההגדרה הרקורסיבית הבאה) לחשב בזמן לינארי את
(T(1),T(2),...T(n ולהחזיר את הערך המקסימאלי שמצאנו.
ההגדרה המלאה של T :
T(1)=x(1)
T(i+1)=x(i+1) if T( i)<0
T(i+1) = x(i+1)+T( i) otherwise
בנוסף, אם צריך גם למצוא את האינדקסים של תת-הסידרה, שומרים בצד את האינדקסים הכי טובים כל פעם שהמקסימום משתנה.
סיבוכיות הפתרון - זמן לינארי.
דרך אגב - פתרון זה הוא דוגמה לשיטת אופטימיציה כללית שנקראת "תכנון דינאמי".
אמיר.
חידה קלילה - אפשר לענות בשרשור.
הדולר החסר
=========
3 חברים (ילעדיפים, kaser, ו-dudib) הלכו למסעדה בכפר אבוייה לאכול כונפות. קיבלו חשבון של 30$. נתנו כל אחד 10$. בעל המסעדה tiptip, שמכיר אותם עוד מהמיץ של הזבל החליט לתת להם הנחה של 5 דולר ונתן למלצר efib שטר של 5$ להחזיר להם. efib לא ידע איך לחלק את השטר לשלושה, ולכן החליט לתת לכל אחד דולר אחד, ולשמור את שני הדולרים לעצמו בתור טיפ.
לסיכום, כל אחד מהחברים שילם 9$ (סה"כ 27), וישי שני דולר אצל efib, סה"כ 29 דולר. איפה הדולר החסר?
הדולר החסר
=========
3 חברים (ילעדיפים, kaser, ו-dudib) הלכו למסעדה בכפר אבוייה לאכול כונפות. קיבלו חשבון של 30$. נתנו כל אחד 10$. בעל המסעדה tiptip, שמכיר אותם עוד מהמיץ של הזבל החליט לתת להם הנחה של 5 דולר ונתן למלצר efib שטר של 5$ להחזיר להם. efib לא ידע איך לחלק את השטר לשלושה, ולכן החליט לתת לכל אחד דולר אחד, ולשמור את שני הדולרים לעצמו בתור טיפ.
לסיכום, כל אחד מהחברים שילם 9$ (סה"כ 27), וישי שני דולר אצל efib, סה"כ 29 דולר. איפה הדולר החסר?
אמיר.
אין דולר חסר !!
האנשים (ילעדיפים, kaser, ו-dudib) שילמו 30 דולר אבל הוחזרו להם 3 דולרים ולכן סה"כ הכסף שהם שילמו הוא 27 דולר מתוכם
בעל המסעדה tiptip קיבל 25 דולר
ו efib המלצר קיבל (לקח) 2 דולר טיפ
סה"כ 27 דולר
האנשים (ילעדיפים, kaser, ו-dudib) שילמו 30 דולר אבל הוחזרו להם 3 דולרים ולכן סה"כ הכסף שהם שילמו הוא 27 דולר מתוכם
בעל המסעדה tiptip קיבל 25 דולר
ו efib המלצר קיבל (לקח) 2 דולר טיפ
סה"כ 27 דולר
