אני צריכה עזרה בפתרון שאלות תכנות

[ron369]

אבל למה שהוא יהיה חסום?

 

[vinney]

למה לא?

כשאתה פותר בעיה מעשית אתה תמיד מוגבל לטוות כלשהו, אין לך מספרים אינסופיים. זה בדיוק ההתפלספות של יוני בשרשור אחר פה - כשנתון לך מערך בגודל 26, מה הסיבוכיות של לעבור על המערך? O של N או O של 1?

 

[ron369]

O(1)

אבל בשאלה לא מוזכר ש-M חסום, ומבחינה אלגוריתמית לא מעניין אותי יותר מזה. כל אחד מאתנו הבין את השאלה, כנראה, אחרת, ולכן להמשיך לדבר על זה די חסר טעם. נרד מהנושא?

 

[vinney]

לגבי ההערה שלי לMegaMango

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

 

[ron369]

לפי איך שאני מבין את זה,

הסיבוכיות של עיבוד מספר היא לוגריתמית, ולכן אפשר "להתעלם" ממנה. האם אני טועה? האם פה מופיע הלוגריתם של M, או M עצמו, בחישוב הסיבוכיות? (אני פשוט מכיר את החידה, ולא שמעתי על פתרון שלה ב-O(1), אלא בO(m))

 

[ron369]

מצטער על הדאבל

 

[DNile]

זה לא יותר מדי קשה

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

 

[ש ב ו ז]

תשובות

בקשר ל1 הפתרון שלך נכון ויפה. זה בזיכרון של o(1). בקשר ל3 אני מניח שכשאת אומרת O)N( את מתכוונת ביחס לM אחרת זה בלתי אפשרי... אם ככה את יודעת כמה אותיות יש באנגלית את יכולה לפתור את השאלה באמצעות מערך מונים עבור כל אות. כל מילה שהיא פרמוטציה תקיים מערך זהה.

 

[ש ב ו ז]

ז"ת אחרת הסיבוכיות היא M*N או N^2

 

[ש ב ו ז]

אופס לא ראיתי שכתבת סיבוכיות זמןo(1

זה בלתי אפשרי...חחח...

 

[MegaMango]

למה בלתי אפשרי? זה פשוט מאוד מאוד

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