שאלה מעניינת...

NightMaster

New member
שאלה מעניינת...

יצא לי להיתקל בשאלה די מעניינת (מהחיים): נניח שבקורס מסוים יש n סטודנטים, והממוצע שלהם הוא x. צריך לחלק אותם לm קבוצות (לאו דווקא שוות), ככה שהממוצע של כל קבוצה רחוק במקסימום a נקודות (מספר שנקבע מראש) מהממוצע הכללי של הקורס. לדוגמה: נניח שהציונים הם 10,20,50,50,80. הממוצע הוא 42. צריך לחלק ל-2 קבוצות שהממוצע שלהם רחוק במקסימום 5 נק' מהממוצע הכללי. במקרה הזה פלט אפשרי יהיה: {20,50,50} - ממוצע 40, ו{10,80} - ממוצע 45.
השאלה היא אם יש אלגוריתם יעיל שיקבל את n,m,x,a והציונים של כל סטודנט, ויחזיר את הסידור הזה (אם יש) או שאין כזה סידור.
 

גיל14

New member
שאלה יפה והערה

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

Calius

New member
לא בטוח. אינטואיציה. אבל נראה לי

שאפשר לעשות רדוקציה לבעיית "Knapsack problem" בשלמים.
 
למעלה