שאלה במדעי המחשב

[KO74]

שאלה במדעי המחשב

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

 

[vinney]

ומקור השאלה הוא?

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

 

[KO74]

תשובה

מצטער שלא קראתי את מכתב הפתיחה

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

 

[vinney]

היה לנו פעם דיון ארוך על זה

בשפות תכנות, תחפש שם בארכיון. הבעיה היא שאתה יכול לעשות את זה בO של N, אם אתה לא מתחשב בסיבוכיות של פעולות חשבוניות, אבל הן עצמן זה LOG N, לכן אתה מגיע תכל'ס לNLOGN, ואז כבר פשוט תמיין וזהו

זה לפחות המסקנה שאני זוכר מהדיון

 

[sagima]

NLogN ???

כנראה שאני מפספס משהו אבל... יש לנו מערך A בגודל N-1, מה אם נגדיר מערך B בגודל N, ונאתחל את כל הערכים בו ל0, ואז נעבור על כל A ונעשה :

B[A]++​

ואז עוברים על B ומדפיסים את האינדקס של כל מה שהערך שלו גדול מ 1. איפה יש פה משהו שהוא NLogN ?

 

[DNile]

בכמה זכרון נוסף אתה משתמש?

 

[KO74]

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

שגודל מבני הנתונים לא יכול להיות תלוי ב- N אני לא יודע בדיוק מה הכוונה, אבל זו אחת ההגבלות

 

[Isildur]

מיון מנייה זה יפה

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

 

[vinney]

זה סיבוכיות O של N במקום.

ועלות כל פעולה חשבונית היא LOG N לפחות, דיברנו על זה

 

[Isildur]

אבל במקרה כזה

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

 

[KO74]

תחת מה לחפש?

 

[vinney]

חיפשתי בשבילך

כי זכרתי שזה לא היה מזמן, וזה היה בדיוק השאלה הזאת

זה פה.

 

[KO74]

תודה ../images/Emo13.gif

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

 

[vinney]

המם..

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

 

[Yoava333]

אפשר לעשות את הרעיון של סדרה

חשבונית ועצרת, לשניהם יש סיבוכיות של O אם לא הבנת המימוש ב-C הוא משהו כזה:

int iSumArr = 0, iSumSidra = 0, iAzzeret = 1, iAzzeretSidra = 1; for (int i=0;i<ArrayLength;i++){ iSumArr += aArr; iSumSidra += i; iAzzeretSidra *= aArr; iAzzeret *= i; } if ((iSumArr == iSumSidra)&&(iAzzeret == iAzzeretSidra)){ printf('yay!'); } else{ printf('not!'); {​

 

[Yoava333]

לא משנה, אני חייב להתחיל לקרוא את

כל ההודעות לפני שאני מגיב...

 

[KO74]

הגעתי למשהו

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

 

[KO74]

פתרתי!!! ../images/Emo13.gif

אבל, אם המספר לא נמצא יותר מפעם אחת או לא נמצא כלל, הוא מדפיס 0 ואם המספר נמצא יותר מפעם אחת הוא מדפיס את המספר כלומר, עבור המערך: 1 2 3 1 5 2 יודפס: 0 0 0 2 1

 

[vinney]

המם

איך בדיוק?

 

[KO74]

הפיתרון

קודם כל עשיתי לולאה שהופכת את המערך למערך מונים. החל מתא 1 (לא 0 כי אין ערך 0 במערך) ועד תא N יהיה מצוין בתא 1 כמה פעמים הופיע הערך 1 וכך הלאה.. עשיתי את זה כך: (++for (index=0; index<N; index } ;arr[arr[index]%N]+=N { הפעולה היא כזאת: אם מצאתי בתא הראשון את הערך 8 למשל, אז אני אוסיף לתא 8 את הערך N כשאני יגיע בסריקה לתא 8, אני יראה שיש בו את הערך 8+N, בשביל זה השתמשתי בביטוי: arr[index]%9 עכשיו כל מה שנותר הוא להדפיס את האינדקסים של התאים במערך בהם הופיע המספר יותר מפעם אחת עוד סריקה: (++for (index=0; index<N; index } arr[index]/=N arr[index]/=2 {arr[index]=!arr[index {arr[index]=!arr[index ([printf("%d ",index*arr[index { הפקודה הראשונה בלולאה הופכת כל ערך למספר הפעמים שהוא הופיע, 9+N+N יהפוך ל- 2 3+N יהפוך ל-1, וכו' הפקודה השניה מחלקת כל תא ב-2, זה גורם לכל ה-1-ים במערך להפוך ל-0 פעמים NOT על כל תא במערך, זה גורם לכל תא שערכו היה 0 להישאר 0 ןערך שהיה גדול מ-0 יהפוך ל-1 ןלבסוף, הדפסה של {index*arr[index, כפילה ב-0 ידפיס 0, וכפילה ב-1 תדפיס רק את האינדקס של התא