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

השאלה היא לא ממש תכנותית אלא יותר שאלת חשיבה אבל זה נראה לי הפורום המתאים ביותר

קוד:

EXAMPLE:
Consider these assignment scores:
* 41 points out of 42
* 22 out of 64
* 2 out of 26
* 11 out of 44
* 24 out of 27
* 26 out of 70
* 4 out of 30

The grade percentage when dropping zero assignments is:
(41+22+2+11+24+26+4) / (42+64+26+44+27+70+30) = 42.9%

But, you could improve that percentage, by choosing 3 scores to drop.
What is the maximum percentage possible, by dropping 3 scores?


INPUT:
Input to your program is:
* The number of assignments. (This is at least 4, and at most 30.)
* The student's scores, one at a time, for each of the assignments.
(Scores are at least 0, and at most the maximum.)
* The maximum scores, one at a time, for each assignment.
(These are at least 1, and at most 100.)

OUTPUT:
* The best possible final assignment percentage, from dropping 3 scores.

תודה לכל המנסים

אם תוריד את האחוזים הכי קטנים.
42/41 זה כמעט 1 - לכן חובה להשאיר.
2/26 זה כבר פחות מעשירית, ברור שאת זה תוריד.
כנ"ל לגבי 4/30.
פשוט תמצא את היחסים הכי שונים כמו 4/30 שזה יחס של 4 ל-30: בקירוב לשביעית.

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

זה ממש לא נכון, אף אחד משני אלה שאמרת להוריד לא יביאו אותך לממוצע הגבוה ביותר...

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

קוד:

for (i=0;i<N-2;++i) {
        for (k=i+1;k<N-1;++k) {
            for (j=k+1;j<N;++j) {
                sumGrades=0;
                sumMax=0;
                for (q=0;q<N;++q) {
                    if ((q!=i)&&(q!=k)&&(q!=j)) {
                        sumGrades=sumGrades+array[q][0];
                        sumMax=sumMax+array[q][1];
                    }
                }
                average=(sumGrades/sumMax)*100;
           }
        }
    }

לצורך העניין זה מערך דו מימדי כאשר הציון של התלמיד נמצא בתא 0 והציון המקס' נמצא בתא 1.

ציטוט:

במקור נכתב על ידי RP. זה ממש לא נכון, אף אחד משני אלה שאמרת להוריד לא יביאו אותך לממוצע הגבוה ביותר...

למה לא נכון?
אם מורידים את 2 מתוך 44 (2/44) מקבלים 49.4% - כבר 6.5% יותר.
אם אני מוריד גם את 3/40 אני מקבל 54.9%.
אם אתה באמת צריך שאני אאכיל אותך בכפית, אז 22 מתוך 64 מותן את היחס הכי רחוק ומקבלים:
(41+11+24+26) / (42+26+27+70) = 61.8%.
מצאת אחוז יותר גדול?

יכול להיות שפשוט לא הבנת אותי - בשאלה כתוב שצריך למצוא את האחוז הגבוה ביותר בכך שמורידים 3 תוצאות. נתתי רק את ה-2 הראשונות שראיתי בשביל ההסבר.

לא יודע מאיפה המצאת את הציונים האלה, הם לא מופיעים בשאלה...בכל אופן אם מורידים את 4/30, את 2/26 ואת 22/64 מקבלים ממוצע 55.73 שהוא נק' פחות מהממוצע הגבוה ביותר...

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

החישוב שאתה עושה זה לא אחוזים

אתה סוכם את המונה ואחרכך מחלק בסכימה של המכנה.
אם אתה רוצה לחשב ממוצע של אחוזים אז אתה צריך לסכום את השברים ולחלק במספר השברים
למשל:
ניקח 15/20 ו1/4 (רבע ו3 רבעים - אין ספק שהממוצע שלהם הוא חצי).
אם נשתמש בשיטה שלך - נקבל 16/24 שזה 2/3 - ממש לא הממוצע של האחוזים..

לעומת זאת, אם תסכום את השברים - 1/4 + 15/20 = 20/20 = 1
ותחלק במספר השברים - תקבל 1/2

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

!!אזהרה!!

ההודעה עלולה להכיל שברי אגוזים ו/או איברי דגים כלשהם

!!אזהרה!!

משום מה הבעיה הזאת מזכירה לי בטירוף את בעיית הגנב (אני משער שיש לה עוד שמות).
מבחינה אלגוריתמית הבעיה הזאת היא NP-Complete, כלומר אי אפשר לכתוב אלגוריתם (ולכן גם לתת קוד יעיל) שייפתור את הבעיה הזאת גם נכון וגם מהר.

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

בברכה,

Uninstall

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://www.stopie6.org/img/badges/120_60black.gif]