תרגיל בסיסי במערכים - אשמח אם תעברו על הקוד

[AvengersAssemble]

שלום,

ביום שישי התחלתי ללמוד C# מהספר הזה: http://www.corner.co.il/UserImage/BookFiles/8/index.html#/108 (לפני זה למדתי את החלק של המבוא מהמדריך של וובמאסטר, וזה פחות או יותר חופף לעמודים 30 עד 100 בספר הזה רק במידת פירוט יותר נמוכה)

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

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

פתרתי את התרגיל בדרך הבאה:

http://pastebin.com/txQuJMK4

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

תודה לעוזרים !

[שניצל]

לא התייחסת בשום צורה להערות שנתנו לך על הדיון הקודם שפתחת...

[AvengersAssemble]

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

[שניצל]

סבבה.

לגבי הקוד שלך, ההתעסקות שלך עם ה-frequency לא כל כך נכונה. מה מייצג כל תא במערך הזה? למה אתה מאתחל אותם ב-1?

[AvengersAssemble]

frequency הוא מערך שנעזרתי בו בשביל לקבוע כמה פעמים חוזרת כל ספרה במערך arr, וכך לקבוע מה הספרה השכיחה ביותר במערך ומה הספרה הנדירה ביותר. frequency ו-arr הם בעלי אותו אורך מסיבות של חסכון בזכרון (אם הייתי מגדיר את frequency כבעל אורך של length+1000 זה לא היה משנה), אבל האורך של frequency חייב להיות לכל הפחות שווה לאורך של arr כי אני ניעזר באינדקס של כל איבר ב-frequency כך שיחפוך לאינדקס של האיבר ב-arr, בגלל זה הערך של frequencyz מקודם כל פעם שנמצאה ספרה השווה לספרה שמאוחסנת ב-arrz (בלולאה שבין שורות 24 ל-32).

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

אחרי סיום הבדיקה, הערך של כל תא frequencyz הוא מספר המופעים של הספרה שמאוחסנת ב-arrz במערך arr. בלולאה שבין השורות 33-47, יש השוואה בין כל האיברים במערך frequency בכדי למצוא את האיבר הגדול ביותר (שהאינדקס שלו הוא הספרה במערך arr שחוזרת על עצמה הכי הרבה) ואת האיבר הקטן ביותר (שהאינדקס שלו הוא הספרה הנדירה ביותר במערך arr).

אחר כך, יש השוואה בין common לאינדקס של האיבר הגדול ביותר ב-frequency בשביל לשמור את האינדקס של האיבר השכיח ביותר במערך arr. אותו דבר (רק הפוך במטרה) עם המשתנה rare.

בשורה 50, התכנית פולטת את המספר השכיח ביותר במערך arr (והוא האיבר arr[common]z) ואת המספר הנדיר ביותר במערך arr (והוא האיבר arr[rare]z).

[שניצל]

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

תחשוב איך לעשות את זה הרבה יותר יעיל. תחשוב איזה ערכים arr בכלל יכול להחזיק.

[AvengersAssemble]

חשבתי על התרגיל שוב ופתרתי אותו מחדש, הפעם בלי המערך frequency.

http://pastebin.com/wbXQGTsW

אשמח לחוות דעתך

[שניצל]

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

[Gil28]

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

[Amit Shani]

הכי יעיל לדעתי זה לספור כמה פעמים כל מספר מופיע ולאחר מכן לבדוק מי הופיע הכי הרבה (והכי מעט) פעמים:

int[] count=new int[10]; //counts values from 0 to 9
for(int i=0;i<10;i++)//initializing count array
count[i]=0;
for(int i=0;i<l;i++)
count[a[i]]++;
int max=0,min=count[0],maxIndex=0,minIndex=0;
for(int i=0;i<10;i++)
{
if (count[i]>max)
{
max=count[i];
maxIndex=i;
}
if (count[i]<min)
{
min=count[i];
minIndex=i;
}
}
cout<<"the most common number is: "<< maxIndex << endl;
cout<<"the rarest number is: "<< minIndex << endl;

    //assume a is l length and already holds random numbers

[שניצל]

אכן זה הפתרון (אמנם בלבלת כאן קצת ++C ו-#C).

[Amit Shani]

אכן זה הפתרון (אמנם בלבלת כאן קצת ++C ו-#C).

חחחחח אמת.. רציתי להתאים את עצמי אליו אבל לא היה לי כוח לכתוב:

Console.WriteLine