נושא: שאלה באלגוריתמים

נשלח בתאריך: 07 August 2007 בשעה 10:54 | IP רשוּם

יש לי מספר שאלות באלגוריתמים למי שיש תשובה זה ממש יעזור

1. יש מערך שמכיל N-2 מספרים טבעיים שונים זה מזה מקבוצה 1,2,3...n

כלומר 2 מספרים חסרים. לתת אלגוריתם  שמוצא את 2 המספרים החסרים במעבר יחיד על המערך מותר להשתמש במקום נוסף של O(LOGN) BITS

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

נשלח בתאריך: 07 August 2007 בשעה 11:01 | IP רשוּם

עוד שאלה

1. נתון מערך ובו מספרים ממשייים  כל מספר שמופיע במערך מופיע בדיוק LOGN פעמים

יש למיין את המערך שלא יופיעו בו מספרים עם חזרות ב O(N(ׁ

שימו לב אלו מספרים ממשיים

נשלח בתאריך: 07 August 2007 בשעה 12:47 | IP רשוּם

תודה

יש למישהו רעיונות לשאר השאלות

נשלח בתאריך: 22 August 2007 בשעה 15:37 | IP רשוּם

שושן?

איך פותרים 2 משוואות ב-2 נעלמים בשפת תיכנות (שהיא לא מטלב)?
אפשר קוד?

נשלח בתאריך: 22 August 2007 בשעה 15:39 | IP רשוּם

"מותר להשתמש במקום נוסף של O(LOGN) BITS"

מה זה אומר???
תפרט בבקשה.

נשלח בתאריך: 22 August 2007 בשעה 21:18 | IP רשוּם

השאלה היא שאלה בגרפים.

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

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

נשלח בתאריך: 22 August 2007 בשעה 21:50 | IP רשוּם

סליחה...

ניתן להסתכל על שאלה כשאלה בייצוג של גרף מכוון ע"י מטריצת סמיכויות.

אלגוריתם:

תירגום של במטריצה למבנה של רשימת סמיכויות - o(n^2
הרצת DFS למציאת קשת אחורית - o(e+v
אם נמצאה יש מעגל החזר שקר
אחרת אין מעגל החזר אמת.

סה"כ אלגוריתם בזמן o(n^2

נשלח בתאריך: 25 August 2007 בשעה 17:49 | IP רשוּם

אפשר להוסיף אלמנט לשאלה:

מצא את ערכה של החזקה בזמן שלא יעלה על (O(n^2, בתנאי שהמטריצה מתאפסת.