עזרה בשפת סי

[medula]

עזרה בשפת סי

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

 

[vinney]

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

זה הסיבוכיות הכי טובה שתשיג ממילא

 

[DNile]

מה פתאום?

אפשר בסיבוכיות זמן ליניארית.

 

[DNile]

תחשוב איך אתה כבן אדם היית עושה

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

 

[medula]

זו דרך ממש טובה לגשת לזה

עובר על המערך פעם אחת, ובכל פעם שאני נתקל במספר שלילי, אני כותב אותו בשורה חדשה עד אשר אין מספרים שליליים. אח"כ אני צריך "לעבור שוב על המערך" כדי בעצם להעתיק את המספרים החיוביים שנותרו לשאר האינדקסים. עד שאחשוב איך למשש את הרעיון החדש, אודה לכם אם תעזרו עם מה שכבר התחלתי עפ"י הרעיון הקודם- איך להדפיס את המספרים החיוביים שנותרו, היכן לשים את פונקציית ההדפסה? ======================== void sort(int *a, int n){ int i, num; n=N; while(n>0){ n--; if(a[n]<0){ for(i=0; i<n; i++) if(a[n]>=0) a[n] = a; num=a[n]; a=num; printf("%d", a); } else if(a==n){ break; } } }

 

[DNile]

יפה, זה כבר פתרון.

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

 

[medula]

קח בחשבון שאני חולה ../images/Emo13.gif

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

 

[DNile]

תמיד יש איזה שהוא trade off

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

 

[medula]

תשמע

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

 

[vinney]

אתה תזדקק ועוד איך

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

 

[medula]

לא, אני לא.

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

 

[galh]

אתה עדיין לא מדען, אתה סטודנט.

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

 

[vinney]

לא הבנת

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

 

[DadleFish]

../images/Emo32.gif זה לא תמיד נכון,

הרי לפעמים אלגוריתם טוב ייתן לנו סיבוכיות זמן ומקום יותר טובה מאלגוריתם רע.

 

[ה עוד אחד]

../images/Emo12.gif

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

אלא אם כן האלגוריתם הרע לא נותן תמיד תשובה/תשובה נכונה ואז אני מבטל את השאלה

 

[ה עוד אחד]

אופס. קבל ביטול על ה../images/Emo12.gif

לא קראתי טוב.

 

[DadleFish]

../images/Emo13.gif

 

[sneaker1]

linear time

All u need to do is keep to pointer to the first negtive from the right and a pointer to the first postive from the left. Then iterate over the array from the left(or right) and swap the the positive with the negtive then refresh the pointer meaning find the first negtive from the legt and the first positive from the right.

 

[selalerer]

זה בדיוק הרעיון שהוא הציע.