שלום לכם!

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

איפה תוכל כיפה אדומה למצוא תפוח טוב לסבתא בלי ללכת אחורה?

עקב חול המועד סוכות תתפרסם החידה הבאה רק בעוד שבועיים.

חג שמח,

סקובידו


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

54 תגובות

  • קובי

    היכן פורסם הפתרון...?

    היי, היכן פורסם הפתרון לחידה? לא הצלחתי למצוא...

  • יגאל

  • אלון

    חידה שגיליתי במקרה (רק לאנשים חכמים מאוד)

    http://www.milki-fun.com/file.php?f=4256
    כדי לפתור תחידה הנ"ל יש לפחות שתי תשובות נכונות
    אולי שלוש 11 (עוד לא מצאתי)

    OOXXO
    OOOOX
    XXOXO
    OOOOO
    OOOXO

    OXOOO
    XOXOO
    OOOOX
    XOXOX
    OXXOO

    תופעה נדירה מאוד בחידות כאלה (פעם ראשונה שאני רואה)
    למה זה יצא בחידה הזו כך

    אני לא יודע עוד למישהו יש רעיון

  • אלון

    יש לי רעיון - רציני

    בגלל שיש לאדומה "סלסלה שמתאימה לתפוח אחד "
    ובגלל שכולם נראים אותו דבר

    מה שיש לעשות זה לאסוף חלקי תפוח
    למשל עם יש לנו 127657281231145

    נשמור את 1 שלם
    נמצא את 2 אז נחתוך את 1ו 2 לחצי (משקל)
    נשווה חצי 7 (משקל) ל לחצי 2 (משקל)
    7 יותר כבד נחלק את כל התפוחים ל1/3 (משקל)
    וכולי....

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

    עם זה לא ברור או יש בעיה - תגידו לי

  • רמי

    רעיון יפה

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

    אפשר להשוות זאת לשאלה הבסיסית עם סל ל 3 תפוחים וצריך בסוף להביא 3 תפוחים טובים לסבתא (בלי לחזור לאחור)

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

  • אלון

    המשך על אותו בסיס של הרעיון

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

    אבל יש סיכוי של 1/2 שנחזור אחורה כדי לאסוף את אותו תפוח.
    אז אני צריך לחשוב עוד, כי בטוח יש שיטה יותר טובה.

  • רמי

    פתרון טוב יותר עבור תפוחים לא טובים רבי משקל שונים מהטובים

    מצאתי מספר מיקרים שהתהליך (אלגוריתם) הקודם לא פתר כהלכה. התהליך הבא , לעת עתה, פותר את כל מה שניסיתי עליו.

    תהליך חיפוש תפוח טוב עבור סבתא של כיפה אדומה:
    =================================
    נסמן את מספר התפוחים השווים שאספנו באות E, את מספר התפוחים הכבדים יותר באות H ואת מספר התפוחים הקלים יותר באות L.
    1) אסוף תפוח ראשון ושים בסל. סמן E=1 .
    2) אסוף התפוח הבא והשווה אותו לתפוח שבסל.
    _A.אם התפוחים שווים במשקלם:
    ___i.הוסף 1 ל E (השאר את התפוח שבסל)
    _B.אחרת אם התפוח האסוף כבד ממשקל התפוח שבסל:
    ___i. הוסף 1 ל H
    ___ii. אם H > L+E אז
    _____1. הנח בסל את התפוח הכבד
    _____2. הוסף ל L את E (את ערך השווים)
    _____3. סמן E=1 (ספירה מחדש)
    _____4. הורד 1 מ H
    ___iii. אחרת השאר את התפוח שבסל
    _C. אחרת אם משקל התפוח האסוף קטן ממשקל התפוח שבסל :
    ____i. הוסף 1 ל L
    ____ii. אם L > H+E אז
    _____1. הנח בסל את התפוח הקל
    _____2. הוסף ל H את E (את ערך השווים)
    _____3. סמן E=1 (ספירה מחדש)
    _____4. הורד 1 מ L
    ___ii. אחרת השאר את התפוח שבסל
    3) אם לא נשארו תפוחים המשך לביתה של סבתא , התפוח שבסל הוא תפוח טוב.הגש אותו לסבתא.
    4) אחרת עבור לסעיף 2) .

  • סקובי

    האם תוכל להוכיח שזוהי האסטרטגיה הנכונה?

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

  • רמי

    ההוכחה בראשי פרקים

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

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

    ניסוח טענה ראשית לשם הוכחת האלגוריתם באינדוקציה:
    1. נוכיח באינדוקציה על מספר ההחלפות של תפוחים בתהליך.
    2. כלומר נניח כי אם יהיו N-1 חילופי תפוח במהלך חיפוש תפוח לסבתא, כל החלפה מחזירה אותנו למצב ההתחלתי בו בשאר התפוחים שיאספו בעתיד, יישאר רוב לתפוחים טובים. ורישום מצב התפוחים יהיה כמו בהתחלה (0,1,0). ובהחלפה האחרונה התפוח שיונח בסל הוא תפוח טוב.
    3. כלומר נניח נכונות ל N-1 החלפות ונוכיח עבור מצב בו נדרש ל N החלפות .
    4. כבסיס לאינדוקציה נוכיח כי עבור מצב של 1 או 2 החלפות הטענה נכונה.

    נדרשתי לטענת העזר הבאה :
    טענת עזר:

    בכל שלב סטטי באלגוריתם, אם מצב הערכים הנוכחי הוא (H,E,L), ומתקיים H>0 וגם L>0 אזי אם נגדיר Minimum(H,L)=d , אזי אפשר לשנות את מצב הערכים ל (H-d,E,L-d) וזה לא ישנה כלל את התהליך למציאת תפוח טוב.
    1. דוגמא : אם מצב הערכים הוא (H=10,E=3,L=8) אזי ניתן לעבור ל (H=2,E=3,L=0) והתהליך לא ישתנה

    ולבסוף : תאור כללי של תהליך הוכחת הטענה הראשית :
    1. הוכחת הטענה עבור החלפה אחת בלבד.
    2. הוכחת הטענה עבור שתי החלפות בלבד
    3. הנחה עבור N-1 החלפות והוכחה עבור המקרה בו יש N החלפות תפוח.

    (*) ההוכחה תוצג בקרוב.

  • רמי

    הוכחת טענת העזר

    טענת עזר:

    בכל שלב סטטי באלגוריתם, אם מצב הערכים הנוכחי הוא (H,E,L), ומתקיים H>0 וגם L>0 אזי אם נגדיר Minimum(H,L)=d , אזי אפשר לשנות את מצב הערכים ל (H-d,E,L-d) וזה לא ישנה כלל את התהליך למציאת תפוח טוב.
    1. דוגמא : אם מצב הערכים הוא (H=10,E=3,L=8) אזי ניתן לעבור ל (H=2,E=3,L=0) והתהליך לא ישתנה

    הוכחת טענת העזר :

    החישובים לאורך האלגוריתם הם הוספת 1 ל H או 1 ל L. אך ההשוואות שגורמות להחלטות, מתייחסות להפרש ביניהם :
    למשל אם H > L+E או L > H+E , ברור כי מה שקובע כאן הוא לא הערכים המוחלטים של H או L אלה ההפרש ביניהם. ולכן אין משמעות לערכים H או L עצמם אלה להפרש ביניהם.
    מ.ש.ל.

  • רמי

    הוכחה עבור N כשהאינדוקציה מאשרת שעבור N-1 האלגוריתם נכון

    בהנחה שהוכחה הטענה עבור N=1 (הוכחה יחסית ארוכה מאוד ותופיע בהמשך) ועבור N=2,
    נניח את הנחת האינדוקציה כי עבור N-1 החלפות הטענה נכונה, ונוכיח עבור המקרה בו יש N החלפות תפוח :

    1. נניח כי יש ביער M תפוחים עם רוב לטובים כמובן (G – מספר התפוחים הטובים, G>M-G).
    2. יש N החלפות, תפוח כל שהוא בסל ומצב הערכים בהתחלה : (H=0,E=1,L=0)
    החלפה אומרת אחת מהשתיים או נבחר תפוח כבד יותר או נבחר תפוח קל יותר. בה"ה נבחר תפוח כבד שגורם להחלפת התפוח שבסל בתפוח זה. כלומר היה H=L+E וכעת עם היאסף תפוח כבד נקבל H+1>L+E.
    נסמן ב g את מספר התפוחים הטובים שנאספו עד עתה.
    אם התפוח הטוב הוא בין הכבדים יותר אזי אספנו עד רגע זה L+E תפוחים לא טובים ו H תפוחים שחלקם (או כולם) טובים , להלן g .
    לכן g=G-L-E>M-G-L-E כלומר מספר התפוחים הטובים שנשארו ביער לאיסוף גדול ממש ממספר התפוחים הלא טובים שנשארו ביער. מ.ש.ל.

    אם התפוח הטוב הוא בין הקלים יותר אזי אספנו עד רגע זה H+E תפוחים לא טובים ו L תפוחים שחלקם (או כולם) טובים , להלן g .
    לכן g=G-H-E>M-G-H-E כלומר מספר התפוחים הטובים שנשארו ביער לאיסוף גדול ממש ממספר התפוחים הלא טובים שנשארו ביער.

    והגענו למצב בו יש רק N-1 החלפות . מכאן , על פי האינדוקציה, כל שלב מביא אותנו למצב זהה למצב ההתחלתי ובפרט בשלב האחרון שבו נכנס תפוח טוב לסל ונמסר אחר כבוד לסבתא (עבור N=1 שיוסבר בהמשך) .
    מ.ש.ל.

  • רמי

    הוכחת האלגוריתם עבור N=1

    הוכחת הטענה עבור החלפה אחת בלבד :
    - צריך להראות שבכל מקרה שכזה, מספיק שמספר התפוחים הטובים גדול ממש ממספר התפוחים הלא טובים, כדי להגיע לבסוף לסבתא עם תפוח טוב (החלק הקשה מכל להוכחה)
    - נניח M תפוחים ביער, G טובים ולכן M-G לא טובים, ומתקיים G>M-G
    - בהתחלה נאסף תפוח כל שהוא והערכים יהיו : (H=0,E=1,L=0)
    - לאחר איסוף של מספר תפוחים מגיעים לנקודה בה מתחלף תפוח (אחרון מבחינתנו). צריך להראות כי זהו תפוח טוב.
    o אם הגיע תפוח כבד יותר, אזי מתקיים H+1>E+L , ולכן מתקיים גם H=E+L , ולכן הערכים משתנים ל (H, 1, E+L)
    o נסמן ב g את מספר התפוחים הטובים שאספנו עד נקודת ההחלפה (לא כולל תפוח אחרון שנאסף אל הסל)
    o אם תפוח טוב באמת כבד יותר מהתפוח שהיה בסל קודם, מתקיים g=G-H , ולכן היות ו G>M-G , יתקיים G-g>=G-H>M-G-H=M-G-E-L , כלומר G-g>M-G-E-L , שזה אומר שמספר התפוחים הטובים שנשארו גדול ממש ממספר התפוחים הלא טובים שנשארו.
    o אם תפוח טוב באמת קל יותר מהתפוח שהיה בסל קודם, מתקיים g=G-L , ולכן היות ו G>M-G , יתקיים G-g>=G-L>M-G-L=M-G-E-H , כלומר G-g>M-G-E-H , שזה אומר שמספר התפוחים הטובים שנשארו גדול ממש ממספר התפוחים הלא טובים שנשארו.
    o כלומר בשני המקרים האפשריים של החלפת תפוח המצב ההתחלתי לא משתנה. יש רוב לתפוחים הטובים.
    o נשאר להראות שהתפוח האחרון חייב להיות טוב על מנת שזו תהיה ההחלפה האחרונה.
    o היות ולא תהיה החלפה, כל תפוח שייאסף יגרום לאחת מהאפשרויות הבאות בלבד:
     תפוח זהה משקל : (H,E,L) => (H,E+1,L)
     תפוח כבד : (H+1,E,L) ומתקיים H+1  תפוח קל : (H,E,L+1) ומתקיים L+1 o המצב ההתחלתי לאחר ההחלפה האחרונה הוא (0,1,0) (על פי טענת העזר)
    o אם מגיע תפוח שווה משקל עולה ערכו של E, וזה לא משנה את המצב. נניח (0,E,0), נניח כי E>=1
    o אם מגיע תפוח כבד יותר, יתקיים (1,E,0)
     כעת יכול לבוא תפוח כבד שוב רק כל עוד H o אם מגיע תפוח קל יותר נעבור ל (0,E,1)
     כעת יכול לבוא תפוח קל שוב רק כל עוד L o הבה ונספור את התפוחים שאספנו עד סוף התהליך :
     בכל שלב מתקיים E>H וגם E>L, כמו כן H+1  צריך להראות כי E>H+L, כלומר רוב התפוחים שנאספו לאחר ההחלפה האחרונה הם השווים ולכן הם הטובים (כי הם הרוב על פי ההגדרה)
     יש אפשרות שנקבל תפוח כבד ותפוח קל לסירוגין עם מעט תפוחים שווים (ברור כי E>=1 , ונניח כי E • (X,E,X+1) - כאן אין רוב מוחלט כי X+1>=E+X ולא גדול ממש וסתירה לרוב לתפוחים הטובים.
    • (X+1,E,X) כאן אין רוב מוחלט כי X+1>=E+X ולא גדול ממש וסתירה לרוב לתפוחים הטובים.
    • (X,E,X) – כאן סתירה לקיום רוב לטובים. יש שני מועמדים זהים להיות תפוחים טובים : הקלים והכבדים
     לכן תהליך כזה לא סביר אם יש רק החלפה אחת.
     ולכן האפשרות היחידה שיהיה רוב ממש היא ע"י זה שהרבה תפוחים שווים יגיעו ויתקיים בסוף E>H+L וזה בדיוק התפוח הטוב שיימסר לסבתא. מ.ש.ל.

  • רמי

    הוכחת האלגוריתם עבור N=2

    הוכחת הטענה עבור שתי החלפות בלבד :
    1. נניח כי יש ביער M תפוחים עם רוב לטובים כמובן (G – מספר התפוחים הטובים, G>M-G).
    2. 2 החלפות אומר כי החלפה אחרונה הביאה לסל את התפוח הטוב ומצב הערכים : (H=0,E=1,L=0) (לאחר החסרה זהה ב L וב Hשלא משנה את ההפרש בין L ל H) . ונדון בהחלפה אחת לפניה.
    החלפה אומרת אחת מהשתיים או נבחר תפוח כבד יותר או נבחר תפוח קל יותר. בה"ה נבחר תפוח כבד שגורם להחלפת התפוח שבסל בתפוח זה. כלומר היה H=L+E וכעת עם היאסף תפוח כבד נקבל H+1>L+E.
    נסמן ב g את מספר התפוחים הטובים שנאספו עד עתה.
    אם התפוח הטוב הוא בין הכבדים יותר אזי אספנו עד רגע זה L+E תפוחים לא טובים ו H תפוחים שחלקם (או כולם) טובים , להלן g .
    לכן g=G-L-E>M-G-L-E כלומר מספר התפוחים הטובים שנשארו ביער לאיסוף גדול ממש ממספר התפוחים הלא טובים שנשארו ביער. מ.ש.ל.
    אם התפוח הטוב הוא בין הקלים יותר אזי אספנו עד רגע זה H+E תפוחים לא טובים ו L תפוחים שחלקם (או כולם) טובים , להלן g .
    לכן g=G-H-E>M-G-H-E כלומר מספר התפוחים הטובים שנשארו ביער לאיסוף גדול ממש ממספר התפוחים הלא טובים שנשארו ביער.
    לכן מגיעים להחלפה האחרונה כשיש רוב של תפוחים טובים ועל פי הסעיף הקודם לגבי החלפה אחת, מתחייב כי תפוח זה יהיה תפוח טוב. מ.ש.ל.

  • סקובידו

    הרעיון הוא טוב, הביצוע ארוך...

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

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

  • רמי

    בסיס האינדוקציה

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

  • סקובידו

    בסיס האינדוקציה

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

  • רמי

    יפה.

    הבנתי את הטיעון. תודה!
    כעת באמת נראה שההוכחה יכולה להיות קצרה יותר.

  • סקובידו

    ההוכחה שלך

    בהוכחה שלך יש קטעים מאוד טובים, למשל המעבר מ-(H,E,L) ל-(L-d, E, H-d). אולם אפשר לפשט עוד קצת. כאשר מחליפים תפוח, המצב החדש הוא תמיד

    H= e+h

    E = 1

    L = e+h

    (מדוע?). האומדן בסוף ההודעה מה-9.11., 18:08 גם כן טוב וחשוב עבור ההוכחה.

  • אלון

    רמי תכתוב את זה אחרת

    וסבינה תשנו כבר ת'צבע האופר
    אי-אפשר לקרוא שחור על אפור.

    האתר החדש מלא טעויות

  • מומחה מצוות מכון דוידסוןסבינה

    צבע

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

  • אלון

    לבנות אתר זה דבר קשה מאוד

    משלושה סיבות
    1. הכתיבה
    2. אדרכילות
    3. פסיכולוגיה

    באתר הזה הכתיבה טובה (לא בדקתי) השאר לא ואני יסביר

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

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

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

    אין נגישות נוחה דומה לסופר
    שצריך ללכת לסופו בשביל לקנות חלב

    בכלל כל הבלגן מצד שמואל לא ברור למה זה שם בכלל

    הכתב מחוק בתחילתו בקצה הימני ואנחנו צריכים לנחש מה המילה הראשונה

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

    בטח יש עוד...

  • מומחה מצוות מכון דוידסוןסבינה

    עיצוב האתר

    הי אלון,

    תודה על תגובתך ועל הביקורת הקונסטרוקטיבית.

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

    אני מסכימה איתך שעיצוב נעים ומושך חשוב.

    אעביר את הודעתך ל-
    Webmaster
    ולגרפיקאית.

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

    דרך אגב: ניתן להעלות קבצים לדרופבוקס (http://www.dropbox.com/) או לגוגלדוקס (docs.google.com) ולהעלות את הקישור לטוקבק.

  • מומחה מצוות מכון דוידסוןלירון שטרן

    עיצוב האתר

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

  • רמי

    תהליך חיפוש תפוח טוב - תרשים זרימה

    יצרתי תרשים זרימה של התהליך כדי להקל על הבנתו.
    כתובתו :
    https://docs.google.com/leaf?id=0B51WVmclKl_zMzBmN2ViYTEtMDBjZi00Mzc0LWE...

  • רמי

    תהליך חיפוש תפוח טוב (כתוב אחרת)

    תהליך חיפוש תפוח טוב:
    0) התחלה : אסוף תפוח ראשון וסמן שמספר התפוחים השווים הוא 1, מספר התפוחים הכבדים הוא 0 , ומספר התפוחים הקלים הוא 0 .
    1) אסוף תפוח.
    2) אם שווה במשקלו לתפוח שבסל, הוסף 1 למספר התפוחים השווים.
    3) אחרת, אם כבד יותר מהתפוח שבסל, הוסף 1 למספר התפוחים הכבדים, בדוק אם מספר התפוחים הכבדים גדול ממש מסכום התפוחים השווים והקלים. אם כן, הנח התפוח הכבד בסל, הוסף למספר התפוחים הקלים את מספר התפוחים השווים, סמן שמספר התפוחים השווים כרגע הוא 1, הורד 1 ממספר התפוחים הכבדים.
    4) אחרת, אם קל יותר מהתפוח בסל, הוסף 1 למספר התפוחים הקלים, בדוק אם מספר התפוחים הקלים גדול ממש מסכום התפוחים השווים והכבדים. אם כן, הנח התפוח הקל בסל, הוסף למספר התפוחים הכבדים את מספר התפוחים השווים, סמן שמספר התפוחים השווים כרגע הוא 1, הורד 1 ממספר התפוחים הקלים.
    5) אם לא נשארו תפוחים המשך לביתה של סבתא , התפוח שבסל הוא תפוח טוב.הגש אותו לסבתא.
    6) אחרת עבור לסעיף 1)

  • אלון

    הבנתי - תודה

    אבל אני חושב שיש טעות, אני יבדוק יותר מאוחר
    ניראה לי שלא חיבים את שלב 6

  • אלון

    לפי דעתי רק בתפוח הלפני האחרון

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

    יש מצב לרמז...

  • רמי

    פתרון עבור תפוחים לא טובים שונים במשקלם רק ממשקל תפוח טוב

    תהליך חיפוש תפוח טוב עבור סבתא של כיפה אדומה:
    =================================
    נסמן את מספר התפוחים השווים שאספנו באות E, את מספר התפוחים הכבדים יותר באות H ואת מספר התפוחים הקלים יותר באות L.
    1) אסוף תפוח ראשון ושים בסל.
    2) אסוף תפוח והשווה אותו לתפוח שבסל.
    _A.אם התפוחים שווים במשקלם:
    ___i.הוסף 1 ל E (השאר את התפוח שבסל)
    _B.אחרת אם התפוח האסוף כבד ממשקל התפוח שבסל:
    ___i. אם H > L+E אז
    _____1. הנח בסל את התפוח הכבד
    _____2. הוסף ל L את E (את ערך השווים)
    _____3. סמן E=1 (ספירה מחדש)
    ___ii. אחרת הוסף 1 ל H (השאר את התפוח שבסל)
    _C. אחרת אם משקל התפוח האסוף קטן ממשקל התפוח שבסל :
    ____i. אם L > H+E אז
    _____1. הנח בסל את התפוח הקל
    _____2. הוסף ל H את E (את ערך השווים)
    _____3. סמן E=1 (ספירה מחדש)
    ___ii. אחרת הוסף 1 ל L (השאר את התפוח שבסל)
    3) אם לא נשארו תפוחים וגם הגענו לביתה של סבתא, התפוח שבסל הוא תפוח טוב. אחרת, עבור לסעיף 2) .

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

  • אלון

    לא ממש הבנתי

    אבל זה לא ניראה לי נכון

  • רמי

    אני הבנתי שלא הבנת

    אך לא הבנתי איך כשלא הבנת, הבנת שזה לא נראה לך?

    ראשית תנסה את האלגוריתם שלי.
    תקח למשל 6 פעמים 6 , פעמיים 10, 9 אחד ו 5 אחד (או כל קבוצת מספרים מתאימה אחרת).
    תפעיל את האלגוריתם על כל מיני מצבים של 10 המספרים האלו ותנסה למצוא תצורה שלא מובילה ל 6. זה יוכיח שהאלגוריתם שלי לא תקין.
    אם לא תצליח להפריח בדרך זו, תנסה לבדוק את התהליך עם מחשב ולחפש טעות.
    אם לא תצליח להפריח, תנסה להוכיח שהתהליך נכון.
    ואם תצליח בזאת אשמח מאוד!!!

  • אלון

    למה אתרוג?

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

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

    אז בגלל שיש יותר מחצי במשקל מסוים

    אז נניח יש 33344444455555555
    אז אתה אומר שזה לא 3
    וחוזר להתחלה
    אז אתה אומר שזה לא 4

    ובגלל שיש רק 3,4,5 אז המסכנה שלך ש5 הוא טוב?

    זה הרעיון?

  • רמי

    הרעיון

    בשורת התפוחים שלך צריך שמספר הטובים יהיה גדול ממספר שאר התפוחים, למשל
    5335344444455555555 .
    כאן 5 - טובים בכמות 10
    3,4 - לא טובים בכמות כוללת של 9.
    10 > 9 ולכן עונה לדרישות.
    אני אוסף את 5 הראשון בהתחלה ולא מחשב דבר.
    אוסף את 3 , התפוח השני, שהוא קל יותר, אך היות וכל המשתנים שווים עדין ל 0, אני אסמן L=1 ויישאר בסל תפוח 5.
    אוסף 3 שני , קל יותר מ 5 שבסל, מתקיים L>E+H ולכן שם בסל את 3 , ומוסיף את E ל H ומסמן E=1 . יותר הגיוני ל 3 להיות התפוח הטוב בהתאם לנתונים העכשוויים. H=0 E=1 L=1
    אוסף את 5 , היות והוא כבד יותר, אך לא מתקיים H>E+L , לכן רק אסמן שיש כבד ממה שאספתי עד עתה ע"י הוספת 1 ל H . , תפוח 3 ישאר, וערכי המשתנים H=1 E=1 L=1
    כך אמשיך עד התפוח האחרון.

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

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

  • רמי

    ולמה ערבה?

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

  • סקובי

    מה אומרים האחרים?

    נשמע טוב :-). מה אומרים האחרים? האם ניתן להוכיח שאלגוריתם זה הינו נכון?

  • סקובידו

    משקל התפוחים הלא טובים

    זה בכלל לא חשוב האם התפוחים הלא טובים שוני-משקל או שווי-משקל. חשוב שהמשקל (או המשקלים השונים) שלהם יהיה שונה מהמשקל של התפוחים הטובים ושהם פחות ממחצית התפוחים.

  • אלון

    לא הבנתי

    עם התשובה של רמי נכונה והתפוחים הלא טובים הם שווי-משקל

    אז נניח שיש 10 תפוחים 4 לא טובים
    תפוח 0 משקל 9 גרם (לא טוב)
    תפוח 1 משקל 10 גרם ( טוב)
    תפוח 2 משקל 8 גרם (לא טוב)

    נרשום 0001211111

    1) יאסף תפוח ראשון = 0
    2) יאסף תפוח שני (0). יושווה במשקלו לראשון. אם זהים, הסתיים החיפוש כי נמצא תפוח טוב לסבתא. אחרת, תפוח האחרון שנאסף נשאר בסל והתפוח הישן יוחזר אחר כבוד ליער (יושלך לאחור ולא יבדק שנית).

    זהים נימצא תפוח לא טוב 0

    ועם התפוחים הלא טובים שוני-משקל
    1. זה לא נתון 2. יש שיטות יותר טובות לפתור את זה

  • רמי

    הערות

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

  • סקובי

    ...יש שיטות יותר טובות

    רוצים רמז?

  • רועי

  • רמי

    הפתרון

    יחד עם נתוני השאלה ובהנחה שכל התפוחים הטובים שווי משקל וכל התפוחים הלא טובים שוני משקל (גם מהטובים). להלן הפתרון:
    כיפה אדומה תבדוק את כל התפוחים אחד אחד עד שתמצא זוג תפוחים שווי משקל שהם תפוחים טובים. אחד מהם תתן מתנה לסבתא.
    האלגוריתם:
    1) יאסף תפוח ראשון
    2) יאסף תפוח שני. יושווה במשקלו לראשון. אם זהים, הסתיים החיפוש כי נמצא תפוח טוב לסבתא. אחרת, תפוח האחרון שנאסף נשאר בסל והתפוח הישן יוחזר אחר כבוד ליער (יושלך לאחור ולא יבדק שנית).
    3) חזור לסעיף 2)

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

  • אלון

    הבנתי ש..

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

    ובגלל שיש יותר תפוחים טובים
    אז חיב להיות לפחות זוג אחד של תפוחים באותו משקל בדיוק.

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

  • רמי

    השלמה לפתרון

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

  • אלון

    רעיון -

    עם יש תפוח אחד ברור שהוא טוב

    כיפה אדומה תיקח תתפוח האחרון שתמצא
    ואת כל שאר התפוחים תזורק מהדרך.- ולא צריך לשקול.

  • סקובידו

    להזכירכם...

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

  • רמי

    להבנתי

    אם למשל נתייחס לתפוחים שנפלו (שאינם תלויים על העצים), ונניח כי כמותם 100, אזי יכול להיות מצב שבו 51 מתוכם טובים ובעלי משקל זהה, ושאר ה 49 כל אחד מהם בעל משקל שונה!!
    במקרה זה נצטרך לאסוף הרבה תפוחים שוני משקל ולהחזיקם עד נקודת ההחלטה.
    אם הכוונה שמשקלם של כל אחד מהתפוחים הלא טובים זהה, אך לא ידוע לנו מראש אם גדול או קטן ממשקל תפוח טוב, אז נאלץ להחזיק 2 תפוחים שוני משקל עד נקודת ההחלטה.

  • סקובידו

    מה שכתבת בקטע הראשון זה נכון...

    מה שכתבת בקטע הראשון זה נכון, אבל מה שכתבת בהמשך איננו נכון.

  • רמי

    התהליך במקרה של תפוחים לא טובים שוני משקל

    יש להגדיל את הסל של כיפה אדומה לרב סל או עגלה עם מקום לכל K סוגי משקלות התפוחים.

    התהליך למציאת תפוח טוב:
    1) איסוף תפוח והשוואתו לכל K התפוחים הקיימים ברב סל (לתפוחים שישנם). אם קיים תפוח זהה משקל ברב סל להשאיר התפוח שנאסף ביער, אחרת יש

    להוסיפו לרב סל. להוסיף 1 לספירה של כמות התפוחים עם משקל זה.
    2) אם הגענו לביתה של הסבתא וגם נגמרו התפוחים לאיסוף, התפוח בעל הספירה המקסימלית הוא תפוח טוב. אחרת חזור לסעיף 1).

  • סקובי

    סל אחד קטן

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

  • רמי

    התהליך במקרה של תפוחים לא טובים זהי משקל :

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

    הסיבה : היות ויש יותר תפוחים טובים, התפוח שישאר בידיה בסופו של דבר יהיה תפוח טוב.

  • אלון

    זה נכון רק עם התפוח הראשון הוא תפוח טוב

    כי "לתפוחים הלא טובים יש משקל אחר"...

    כאשר תפוח טוב ישקול 13 גרם
    אז תפוח לא טוב ישקול 10 גרם 11 גרם או 12 גרם.
    או כאשר תפוח טוב ישקול 9 גרם
    תפוח לא טוב ישקול 10 גרם
    וכולי.... אז החישוב לא יעבוד.

    גם אם תימצא שלושה תפוחים במשקל זה יש מצב שהם ישקלו 11 גרם
    וישארו לא טובים.

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

    שאלה קשה!!

    • עמודים