שאלות באלגוריתמים

[p i o n e e r]

שאלות באלגוריתמים

יש לי מספר שאלות באלגוריתמים למי שיש תשובה זה ממש יעזור 1. יש מערך שמכיל N-2 מספרים טבעיים שונים זה מזה מקבוצה 1,2,3...n כלומר 2 מספרים חסרים. לתת אלגוריתם שמוצא את 2 המספרים החסרים במעבר יחיד על המערך מותר להשתמש במקום נוסף של O(LOGN) BITS 2. ישנה מטריצה ריבועית שיש בה רק אפסים ואחדים. צריך למצוא אלגוריתם שבודק האם קיימת חזקה כלשהי כך שנעלה את המטריצה והיא תתאפס כולה. הזמן הנדרש הוא O(n^2) עוד שאלה 1. נתון מערך בגודל N ובו מספרים ממשייים כל מספר שמופיע במערך מופיע בדיוק LOGN פעמים יש למיין את המערך שלא יופיעו בו מספרים עם חזרות ב O(N(ׁ שימו לב אלו מספרים ממשיים

 

[yaeerk]

עבור השאלה הראשונה

תבדוק את זה: 1. אתה יודע את סכום הסדרה החשבונית 1..n כלומר אם תסכום את אברי המערך שלך (sigma) אתה יכול לבנות משוואה אחת 2. אתה יודע שמכפלת n האיברים היא !n, כלומר אם תכפיל את איברי המערך (pi) תוכל לבנות משוואה שניה כלומר אם תסמן את a ו- b כנעלמים שלך אזי: a+b=(n+1)*n/2-Sigma a*b=n!/pi ואת זה אין בעיה לפתור ואפילו בלי שימוש בעוד זיכרון. אבל יכול להיות שאני טועה כאן במשהו. לגבי העוד שאלה שלך, כמה פעמים חוזר כל מספר במערך?

 

[p i o n e e r]

מספר מופעים

LOGN פעמים כש N זה גודל המערך

 

[yaeerk]

לפי ההגדרה שלך

כל מספר (שונה) במערך שלך חוזר אותו מספר פעמים במערך, יתרה על כך logn הוא מספר טבעי ומספר האיברים השונים במערך m מקיים mlogn=n האומנם?

 

[p i o n e e r]

כנראה

כך קיבלתי את השאלה

 

[HaifaMan]

לגבי שאלה 2

תסתכל על המטריצה כיצוג של גרף. תחפש את אורך המסלול המכסימלי בגרף ותחזיר אותו + 1.