שרשור חידות

[ron369]

שרשור חידות

למישהו בא?

 

[yossiea]

משהו קל בתור התחלה...

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

 

[ron369]

לא כזה קל, אבל נחמד ../images/Emo58.gif

נניח: איש 1 עם איש 2, איש 2 (1) חוזר לבד, איש 4 עם איש 5, איש 1 (2) חוזר לבד, איש 1 ואיש 2 ביחד. 2+2+5+1+2 = 12 אולי לא קשה כמו מבחן של פרידה, אבל בטח לא עד כדי כך קל. נחמד

 

[p k a k]

זו חידה קלה...

כי אין יותר מדי אופציות - ניתן לפתור אותה באופן ברוטלי. תנסה את אותה חידה על (1) דקה. (2) שתי דקות. (3) חמש דקות. (4) עשר דקות. כאשר מוקצב לך 17 דקות.

 

[yossiea]

זה לא אותו דבר?

זה נראה די דומה לחידה הקודמת איפה פה הקושי? אם 5,10 הולכים יחד אחרי ש-1 העביר את 2 עברו 13 דקות. נשאר לך להחזיר את 2 ואז לשלוח את 1 עם 2 הרי 17. לא? איפה פה הקטש?

 

[p k a k]

אותה חידה...

נסיתי לומר לו פה, שזה אפילו קל...

 

[ron369]

עוד אחת ש,כנראה, יחסית קלה

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

 

[yuvalmadar]

ועוד אחת, קשה עוד יותר לדעתי ../images/Emo13.gif

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

 

[גיל14]

חשבתי שצריך nlgn בשביל זה :-|

 

[ron369]

אתה מתכוון, *או* של nlgn ../images/Emo13.gif

 

[גיל14]

אה נכון ../images/Emo163.gif

 

[yuvalmadar]

והביטוי המקורי היה lg(n!) zz

(והוכח שהוא שקול אסימפטוטית לnlgn) וההערכה שלו מתאימה. אם תציב n=5, תקבל -

lg(5!)=lg(120)<lg(128)=7​

כרצוי.

 

[גיל14]

יאי, סטירלינג.

 

[p k a k]

גם כן יחסית פשוטה ../images/Emo3.gif

 

[ron369]

ועוד אחת קשה יחסית

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

 

[yossiea]

מיחזור??? (זה כבר היה פה)

אבל אני לא יכתוב תשובה. שמי שטרם ראה ינסה. למה לקלקל...

 

[ron369]

אה ../images/Emo10.gif

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

 

[ron369]

ואם כבר, ננצל"ש לעצמי

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

 

[vinney]

אם התחום לא חסום לא נראה לי

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

)

 

[ron369]

ועוד חידה

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