בעייה באלגוריתם

[g u y c o h e n]

בעייה באלגוריתם

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

void CMainFrame::InitItemsValues() { BOOL flags[SIZE][SIZE] = {FALSE}; int num, pos1_1, pos1_2, pos2_1, pos2_2; srand((unsigned)time(NULL)); // random seed for (int i = 0, times = SIZE * SIZE / 2 ; i < times; i++) // number of couples // lines { while(1) { num = rand() % 9 + 1; pos1_1 = rand() % SIZE; pos1_2 = rand() % SIZE; if (!flags[pos1_1][pos1_2]) { pos2_1 = rand() % SIZE; pos2_2 = rand() % SIZE; if ((!flags[pos2_1][pos2_2]) && (pos1_1 != pos2_1) && (pos1_2 != pos2_2)) { m_Items[pos1_1][pos1_2].value = num; m_Items[pos1_1][pos1_2].hidden = TRUE; // hidden status m_Items[pos1_1][pos1_2].enable = TRUE; m_Items[pos2_1][pos2_2].value = num; m_Items[pos2_1][pos2_2].hidden = TRUE; // hidden status m_Items[pos2_1][pos2_2].enable = TRUE; flags[pos1_1][pos1_2] = TRUE; flags[pos2_1][pos2_2] = TRUE; break; } } } } }​

האם יש אלגורית יעיל יותר ?

 

[Metheny]

קודם כל

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

if ((!flags[pos2_1][pos2_2]) && ((pos1_1 != pos2_1) || (pos1_2 != pos2_2)) )​

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

 

[DNile]

האלגוריתם שלך יכול להיות אינסופי.

בתאוריה לפחות. תאר לך את המצב הבא: הפונקציה rand מחזירה תמיד את המספר 0. לכאורה - לא הגיוני, אבל האמת האמת - אין שום סיבה שלא. הסבירות שתמיד יצא לך 0 זהה לסבירות שתצא לך כל סדרה אחרת. במקום להגריל כל פעם תא במערך ולבדוק האם הוא פנוי, אתה צריך להגריל כל פעם תא אחד מתוך כל התאים שפנויים. לכאורה זה אותו הדבר, אבל זה לא. תאר לך סיטואציה אחרת: אתה אמור למלא מערך של אלף איברים במספרים שהמשתמש מקליד, רק לעשות את זה על פי סדר רנדומלי. גישה אחת תהיה להגריל מספר מאחד עד שלוש, ואם התא במערך במקום זה ריק, לשים בו, אם לא, להגריל מספר חדש. עכשיו תאר לך מצב שבו מילאת את כל המערך מלבד את אחד האחרון, ועכשיו אתה רץ בלולאה עד שrand יחזיר לך 999. ברור שאתה תתמהמה פה הרבה מאוד זמן. השיטה הנכונה תהיה להגריל מספר, שלא מציין את המיקום במערך, אלא מציין את המיקום, ביחס לתאים שאינם מלאים. נניח שרק 5 תאים לא ממולאים, אז אתה מגריל מספר עד 5, שמציין לא את המיקום בתא, אלא את המיקום בין התאים הלא ממולאים. באותה שיטה אתה צריך לנקוט גם כשאתה בוחר תא במערך דו מימדי. בכל מקרה, לא ממש ישבתי להסתכל לך באלגוריתם ולחפש יעילות, אבל הבחירה הרנדומלית הזאת יכולה לגרום הרבה מאוד בעיות, ככל שSIZE גדול יותר.(עד כדי כך שתאורטית, זה יכול לרוץ עד אין סוף).

 

[אינגולמו]

חשבתי על משהו קצת אחר...

שיטה מקובלת (למרות שבד"כ אני משתמש בה עבור מערך חד מימדי): צור מערך עזר T, המכיל את הנתונים הבאים בכל תא: מס' שורה, מס' עמודה במטריצה. אתחל את התאים של T באופן עוקב. נניח והתאים ממוספרים 0 עד N-1. שמור בצד משתנה SIZE = N. האלגוריתם: בחר תא X מתוך המערך T באופן אקראי שלוף את מס' העמודה והשורה מתוך תא X הצב במטריצה, במיקום ששלפת את הערך 1 "דרוס" את התא X ע"י התא האחרון במערך T (התא ה-SIZE-1) הקטן את SIZE ב-1. חזור על התהליך והצב עוד ערך 1 במטריצה. חזור על כל העניין שוב, רק הפעם הצב 2, אח"כ הצב 3 וכו'. יעילות: סדר גודל של N (מספר האיברים במטריצה)

 

[g u y c o h e n]

מממ נשמע רעיון מצויין , אפשר

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

 

[אינגולמו]

???

אף פעם לא יבחר אותו תא פעמיים באלגוריתם הנ"ל. זה כל הרעיון.