נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: חידה לא פשוטה במדעי המחשב

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
clocker
משתמש מתחיל
משתמש מתחיל
סמל אישי

הצטרף / הצטרפה: 24 October 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 10
נשלח בתאריך: 04 November 2005 בשעה 01:26 | IP רשוּם
ציטוט clocker
אתם ניצבים מול נוכל שמציע לכם לשחק במשחק הבא:
מונחים n קלפים על השולחן עם הגב למעלה.
על כל קלף רשום מספר שונה בין 1 לn. (לא רואים את המספר)
עליכם לסדר את הקלפים לפי הסדר.
לא ניתן לדעת מה ערך קלף מסוים, אלא רק לשאול את הנוכל
"מי יותר גדול ?" בין 2 קלפים בדיוק.

כל שאלה שאתם שואלים את הנוכל עולה לכם שקל אחד.
ואם תצליחו לסדר את כל הקלפים לפי הסדר, תקבלו 3n ש"ח.

קיימת דרך (שיטה) ודאית להרוויח כסף במשחק הנ"ל.

מהו הערך המקסימלי שיכול להיות לn ?
חזרה לתחילת העמוד הצג את כרטיס החבר של clocker חפש הודעות אחרות של clocker בקר בדף הבית של clocker
 
SBD
פורומיסט על
פורומיסט על
סמל אישי

הצטרף / הצטרפה: 13 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 1194
נשלח בתאריך: 04 November 2005 בשעה 09:45 | IP רשוּם
ציטוט SBD
זה כמו מיון בשיטת הבועות לא?

__________________
~ Nobody Is Perfect, I'm Nobody ~
פורומים
חזרה לתחילת העמוד הצג את כרטיס החבר של SBD חפש הודעות אחרות של SBD בקר בדף הבית של SBD
 
clocker
משתמש מתחיל
משתמש מתחיל
סמל אישי

הצטרף / הצטרפה: 24 October 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 10
נשלח בתאריך: 04 November 2005 בשעה 13:58 | IP רשוּם
ציטוט clocker

שים לב !

נתון: קיימת שיטה ודאית להרוויח כסף.

צ"ל: את הn המקסימלי עבורו קיימת שיטה שכזו.

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

הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
נשלח בתאריך: 04 November 2005 בשעה 14:46 | IP רשוּם
ציטוט ניר
מיון על ידי השוואה פועל באופן אידיאלי ב-nlogn השוואות. (לוג על בסיס 2) אם אנחנו זוכים אנחנו מקבלים 3n אז בעצם צריך לפתור
קוד:
3n > nlogn


ומכאן:
קוד:
3 > logn

ואני רואה שזה נכון עבור n < 8.

לא בטוח 100% אבל זה נראה לי הכיוון


__________________
מספר האייסיקיו שלי ו/או כתובת ה-MSN שלי אינם מהווים מוקד תמיכה
חזרה לתחילת העמוד הצג את כרטיס החבר של ניר חפש הודעות אחרות של ניר בקר בדף הבית של ניר
 
clocker
משתמש מתחיל
משתמש מתחיל
סמל אישי

הצטרף / הצטרפה: 24 October 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 10
נשלח בתאריך: 04 November 2005 בשעה 16:44 | IP רשוּם
ציטוט clocker

תראה, nlogn זה הסדר גודל של הסיבוכיות.

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

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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