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

נושא: חידה קשה במיוחד - פרס כספי מובטח

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 27 January 2008 בשעה 17:54 | IP רשוּם
ציטוט של

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

הפרס הכספי הוא 2000 ש"ח !!!!!!!!!!!!!!!!!!!!!

לפתרונות שאלות נוספות וכול תגובה אחרת:

sh_lv@netvision.net.il
חזרה לתחילת העמוד הצג את כרטיס החבר של של חפש הודעות אחרות של של בקר בדף הבית של של
 
של
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 27 January 2008 בשעה 17:57 | IP רשוּם
ציטוט של
כמובן שהכוונה שבסוף כול הנורות שקיימות במטריצה יהיו מוארות.
חזרה לתחילת העמוד הצג את כרטיס החבר של של חפש הודעות אחרות של של בקר בדף הבית של של
 
צחי@
משתמש חבר
משתמש חבר


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 28 January 2008 בשעה 23:13 | IP רשוּם
ציטוט צחי@
אני לא יודע אם אתה רציני לגבי הפרס או מה המטרה שלך בתרגיל הנ"ל אבל לתשומת לבך - במונחי סיבוכיות זמן ריצה, הבעיה שתיארת היא שלמה ל-NP, זאת אומרת שמאוד לא סביר שקיים אלגוריתם שזמן ריצתו פולינומיאלי בגודל הקלט והוא תמיד מוצא פתרון אופטימלי.
המקרה הכללי של הבעיה שתיארת נקרא Vertex Cover או כיסוי בקדקודים.

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

אני משאיר לך לנתח את הסיבוכיות של האלגוריתם הנ"ל, אבל שים לב שהוא לינארי ב-N^2 , אם כי ייתכן שמבוצעות קצת יותר מ-12N^2
פעולות אטומיות.

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


הצטרף / הצטרפה: 30 January 2008
משתמש: מנותק/ת
הודעות: 8
נשלח בתאריך: 30 January 2008 בשעה 17:12 | IP רשוּם
ציטוט Poligraf
עלק תביא פרס 2000 שקל מה אתה חושב קודם תכניס את ה 2000 שקל יחרטטן ואחר כך תקבל תתשובה!
חזרה לתחילת העמוד הצג את כרטיס החבר של Poligraf חפש הודעות אחרות של Poligraf
 
orrvaa
משתמש מתחיל
משתמש מתחיל


הצטרף / הצטרפה: 04 January 2008
מדינה: Israel
משתמש: מנותק/ת
הודעות: 16
נשלח בתאריך: 30 January 2008 בשעה 17:30 | IP רשוּם
ציטוט orrvaa
Poligraf כתב:
עלק תביא פרס 2000 שקל מה אתה חושב קודם תכניס את ה 2000 שקל יחרטטן ואחר כך תקבל תתשובה!


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

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

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

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