| כותב |
|
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 29 January 2006 בשעה 01:13 | | IP רשוּם
|
|
|
|
היי,
טופ רוצה הצעות לבעיה הבאה:
נתונים שני כדורי זכוכית ובניין בעל N קומות,
מה היא הקומה הנמוכה ביותר שממנה כדור זכוכית יישבר?
תודה.
|
| חזרה לתחילת העמוד |
|
| |
ניר
מנהל האתר
הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
|
| נשלח בתאריך: 29 January 2006 בשעה 03:48 | | IP רשוּם
|
|
|
|
מתקדמים מלמטה בצעדים של שורש(n). כשמגיעים לקומה בה הכדור הראשון נשבר ממשיכים מהמקום האחרון בו השני לא נשבר. במקרה הגרוע שני שורש n
__________________
מספר האייסיקיו שלי ו/או כתובת ה-MSN שלי אינם מהווים מוקד תמיכה
|
| חזרה לתחילת העמוד |
|
| |
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 29 January 2006 בשעה 07:11 | | IP רשוּם
|
|
|
|
אני לא מבינה ,
אם התחלתי עם כדור אחד ומצאתי את הקומה הנמוכה - בשביל מה אני צריכה תכדור השני?? הרי לכאורה החידה נפתרה והסיבוכיות היא שורש N
אמממ, בכל אופן בוקר טופ ותודה רבה !
|
| חזרה לתחילת העמוד |
|
| |
ניר
מנהל האתר
הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
|
| נשלח בתאריך: 29 January 2006 בשעה 07:21 | | IP רשוּם
|
|
|
|
בוקר טופ!
את מתקדמת בקפיצות של שורש n כל פעם כשאת מתקדמת בקומות. כאשר הכדור הראשון נשבר, יש לך שורש n קומות שאחת מהן יכולה להיות הקומה המינימלית. בשביל למצוא מי מהן בדיוק יש צורך בכדור השני.
__________________
מספר האייסיקיו שלי ו/או כתובת ה-MSN שלי אינם מהווים מוקד תמיכה
|
| חזרה לתחילת העמוד |
|
| |
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 29 January 2006 בשעה 07:32 | | IP רשוּם
|
|
|
|
אהההההההההה,
נפל האסימון, צלצל הטלכרט, נדנד המסנגר ,
טופ נו בסוף הבנתי חחחח,
תודה רבה !
והמשך יום טופ
|
| חזרה לתחילת העמוד |
|
| |
desig
משתמש מתחיל
הצטרף / הצטרפה: 15 October 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 6
|
| נשלח בתאריך: 31 January 2006 בשעה 01:07 | | IP רשוּם
|
|
|
|
לא כל כך הבנתי את הפתרון - אם יש לך מס' קומות גבוה וכבר בשורש הראשון נשבר הכדור הראשון ואותו דבר לגבי הכדור השני עדיין נשאר שורש של שורש של שורש של N קומות לבדוק ואין יותר כדורים... נראה לי שלא כל כך הבנתי את הבעיה או משהו - אם אפשר לפרט אודה מאוד.
|
| חזרה לתחילת העמוד |
|
| |
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 02 February 2006 בשעה 22:28 | | IP רשוּם
|
|
|
|
נייט ,
עם הכדור הראשון אתה עולה בקפיצות של שורש N עד שהכדור נשבר,
ואז עוברים עם הכדור השני - גם עולה עם הכדור השני - לא בקפיצות , קומה קומה, כאשר מקסימום עולה עד לקומה בה נשבר הכדור הראשון - זאת בכדי לקבל את הקומה הספציפית הנמוכה ביותר בה נשבר הכדור.
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 03 February 2006 בשעה 12:34 | | IP רשוּם
|
|
|
|
מצטער ניר, הפתרון שלך הוא לא האופטימלי 
אם החישוב שלי נכון(והוא נעריך ממש עכשיו, ככה שלך תדע...  ) בשיטה שלך ה-worstcase הוא 2-שורש-N, והממוצע הוא 1+שורש-N.
זה נחמד מאוד, אבל קיים אלגוריתם אחר שנותן במקרה הגרוע שורש-2N, ובמקרה הממוצע....קשה לי לחשב 
בדיקה מספרית:
N=50
אצלך: 13,7.5
אצלי: 12,5
N=100
אצלך: 20,11
אצלי: 15,10
ה-worst-case שלי תמיד יהיה ב-25% טוב משלך(2-שורש-N מול שורש-2N). במקרה
הממוצע נדמה לי ששלי תמיד יהיה עדיף, אבל כרגע אני לא יכול להוכיח את זה,
כי אין לי נוסחה. לא נורא, תוך כמה ימים אסנג'ר מישהו שיפתח אחת... 
|
| חזרה לתחילת העמוד |
|
| |
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 05 February 2006 בשעה 17:58 | | IP רשוּם
|
|
|
|
אממ , מהו האלגוריתם שלך אלצקו?
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 06 February 2006 בשעה 00:35 | | IP רשוּם
|
|
|
|
רוצה הצעות או פתרון?...
הצעות אני נותן. פתרונות לא.
קודם כל, כבר סיפקתי המון רמזים. אמרתי שיש אלגוריתם טוב יותר, והבאתי את סיבוכיות ה-worst case שלו. זה לא מעט.
צריך עוד טיפ? סבבה.
קודם כל, עזבי את המקרה של N איברים, ותעבדי עם מספר קונקרטי, כמו מאה. זה
יהיה הרבה יותר פשוט, ואחרי שמוצאים את הפתרון אפשר לעבור למקרה הכללי
חזרה.
עכשיו תחשבי איך יפעל האלגוריתם של ניר עבור מאה איברים. כמה בדיקות הוא
יעשה אם הקומה המבוקשת היא בין 1 ל-10, וכמה אם היא בין 91 ל-100.
תעברי ל-10000 קומות. כמה בדיקות אם הקומה המבוקשת בין 1 ל-100? כמה אם היא בין 9901 ל-10000? מה זה אומר לך?...
להגיד יותר מזה יהיה כבר לתת את הפתרון, וזה לא כיף. קצת עבודה עצמית, בחייאת...
|
| חזרה לתחילת העמוד |
|
| |
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 06 February 2006 בשעה 09:48 | | IP רשוּם
|
|
|
|
בואנה , לא יפה, קצת עדינות..
אממ מה שאני מבינה בשביל להגיע לסיבוכיות שורש של 2 כפול N אני מחלקת I מקטעים - במקרה הגרוע שלי זה 2I פעולות - I זריקות מכל המקטעים ו I-1 מכל מקטע
והחישוב ( במקרה ש N מספר משולש ) יכול להיות - 1+2+3+....+I =
i(i+1)\2 = (i^2)\2
ומכאן ש I שווה לשורש של 2 כפול N
אמממ אז מה האלגוריתם שלך ?
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 06 February 2006 בשעה 19:53 | | IP רשוּם
|
|
|
|
לא ממש הבנתי מה כתבת(מה זה "מספר משולש"?)
אבל יש קטע אחד שבאמת לא ברור לי:
- אם I = שורש(2N)
- ואתה עושה במקרה הגרוע 2I פעולות
- זה יוצא בסה"כ... 2שורש(2N), לא?
ועכשיו בעדינות 
ניסית לשחק על עניין הסיבוכיות, ויצאו לך תוצאות מעניינות מאוד. מהנחת
הבסיס שסיבוכיות המקרה הגרוע היא שורש(2N) הגעת למסקנה שסיבוכיות המקרה
הגרוע היא 2שורש(2N)...
למה שלא תנסי לעשות מה שהצעתי?
אלצ'קו כתב:
קודם כל, עזבי את המקרה של N איברים, ותעבדי עם מספר קונקרטי, כמו מאה. זה
יהיה הרבה יותר פשוט, ואחרי שמוצאים את הפתרון אפשר לעבור למקרה הכללי
חזרה.
עכשיו תחשבי איך יפעל האלגוריתם של ניר עבור מאה איברים. כמה בדיקות הוא
יעשה אם הקומה המבוקשת היא בין 1 ל-10, וכמה אם היא בין 91 ל-100.
תעברי ל-10000 קומות. כמה בדיקות אם הקומה המבוקשת בין 1 ל-100? כמה אם היא בין 9901 ל-10000? מה זה אומר לך?... |
|
|
למה שלא תעני לעצמך על כמה כמה שאלות פשוטות, ותראי לאן זה מוביל?
מה שבאמת לא יפה הוא שאת די מתעלמת ממה שכתבתי. זה אפילו קצת מעליב.
נערך ע"י שושן ב-06/02/2006
מה שאת מתעלמת ממנו זה שהוא לא רוצה לתת לך את האלגוריתם.
|
| חזרה לתחילת העמוד |
|
| |
חרוזית
משתמש מתחיל
הצטרף / הצטרפה: 29 January 2006
משתמש: מנותק/ת
הודעות: 9
|
| נשלח בתאריך: 06 February 2006 בשעה 22:37 | | IP רשוּם
|
|
|
|
אלצקוווווווו ,
קודם כל לא הייתה התעלמות מדבריך ובטח שלא כוונה להעליב !!!
הסיבוכיות שיוצאת לי :
sqrtN+sqrtN-1=sqrtN
אמממ , מספר משולש- מספר המסכם את כל המספרים לפניו בסדרתיות דוגמאות
1+2=3 - המספר 3 משולש
1+2+3 = 6 המספר 6 משולש , וכן הלאה,
וכן אתה צודק סיבוכיות היא 2*(sqrt(N*2
ולא sqrt(N*2( כפי שציינתי
אממממ טופ אני הולכת לזרוק פה כמה כדורים :-)
לילה טופ ותודה
בידידות
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
מדעי המחשב
