חידה
- פותח הנושא M486
- פורסם בתאריך
כן
נניח ש-N=16. נבדוק את M(2,4 למשל. אם הוא 1, אז לא נוכל להחזיר 2. אם הוא 0, לא נוכל להחזיר 4 (תחשוב על זה...). כך נעשה 8 השוואות בשלב הראשון, ונישאר עם 8 אפשרויות. נחזור על אותו שלב עד שנישאר עם איבר אחד אפשרי להחזרה. סה"כ נעשה 8+4+2+1=15=N-1 השוואות, ועוד N השוואות לבדוק שאותה עמודה עמודת 1-ים.
נניח ש-N=16. נבדוק את M(2,4 למשל. אם הוא 1, אז לא נוכל להחזיר 2. אם הוא 0, לא נוכל להחזיר 4 (תחשוב על זה...). כך נעשה 8 השוואות בשלב הראשון, ונישאר עם 8 אפשרויות. נחזור על אותו שלב עד שנישאר עם איבר אחד אפשרי להחזרה. סה"כ נעשה 8+4+2+1=15=N-1 השוואות, ועוד N השוואות לבדוק שאותה עמודה עמודת 1-ים.
אולי פספסתי משהו
כי זה באמת נראה פשוט
1. עבור על כל שורה ובדוק אם היא שורת אפסים. אם כן שמור את האינדקס שלה (נניח במערך בגודל n נסמן האם כל שורה היא שורת אפסים או לא.) 2. עבור על כל עמודה ובדוק אם היא עמודת אחדות (פרט לאיבר האלכסון). אם כן - בדוק במערך שיצרנו בסעיף 1 האם השורה שבאותו אינדקס של העמודה היא שורת אפסים. אם כן - מצאנו. אם עברנו על כל העמודות ולא מצאנו - אז אין.
כי זה באמת נראה פשוט
פתרון אפשרי
בוחרים 3 מספרים באופן אקראי (לא תלוי ב-N) 1. לכל אחד משלושת המספרים: 1.1. עוברים על העמודה שלו, ופוסלים כל שורה שהתא המתאים שלה אינו 0, למעט כמובן השורה שמספרה כמספר העמודה. 1.2. עוברים על השורה שלו ועושים את אותו הדבר לגבי העמודות, כמובן שהפעם בודקים אם התא אינו 1. 4. כעת יש לנו רשימת עמודות תקינות, ורשימת שורות תקינות. נמזג את שתי הרשימות, כי שורת אפסים תענה על תנאי השאלה רק אם השורה שלה תקינה וגם העמודה שלה תקינה. כל מעבר על שורה/עמודה הוא N, ובסה"כ 6N. שלב ניקוי הרשימות גם הוא נעשה ב-N, ולכן בסה"כ N צעדים. מספר השורות שישרדו את התהליך הזה יהיה קטן, ובסה"כ התהליך יהיה יעיל יותר מזה שהציע המנגו. אפשר גם להגדיל (מראש כמובן) את מספר השורות/עמודות שנבדקו - כל עוד זה מספר קבוע, התהליך יהיה ליניארי. אגב, לא הצלחתי לקשר את זה לדרגות כניסה ויציאה, מכיוון שלא אמרת שהמטריצה היא סימטרית. אם יש N קודקודים בגרף, והמטריצה היא למעשה מטריצת קשתות, היא צריכה להיות סימטרית. אם היא לא סימטרית אני לא רואה קשר לדרגות כניסה ויציאה. אם היא כן צריכה להיות סימטרית, זה משנה את השאלה.
בוחרים 3 מספרים באופן אקראי (לא תלוי ב-N) 1. לכל אחד משלושת המספרים: 1.1. עוברים על העמודה שלו, ופוסלים כל שורה שהתא המתאים שלה אינו 0, למעט כמובן השורה שמספרה כמספר העמודה. 1.2. עוברים על השורה שלו ועושים את אותו הדבר לגבי העמודות, כמובן שהפעם בודקים אם התא אינו 1. 4. כעת יש לנו רשימת עמודות תקינות, ורשימת שורות תקינות. נמזג את שתי הרשימות, כי שורת אפסים תענה על תנאי השאלה רק אם השורה שלה תקינה וגם העמודה שלה תקינה. כל מעבר על שורה/עמודה הוא N, ובסה"כ 6N. שלב ניקוי הרשימות גם הוא נעשה ב-N, ולכן בסה"כ N צעדים. מספר השורות שישרדו את התהליך הזה יהיה קטן, ובסה"כ התהליך יהיה יעיל יותר מזה שהציע המנגו. אפשר גם להגדיל (מראש כמובן) את מספר השורות/עמודות שנבדקו - כל עוד זה מספר קבוע, התהליך יהיה ליניארי. אגב, לא הצלחתי לקשר את זה לדרגות כניסה ויציאה, מכיוון שלא אמרת שהמטריצה היא סימטרית. אם יש N קודקודים בגרף, והמטריצה היא למעשה מטריצת קשתות, היא צריכה להיות סימטרית. אם היא לא סימטרית אני לא רואה קשר לדרגות כניסה ויציאה. אם היא כן צריכה להיות סימטרית, זה משנה את השאלה.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.