עזרה ב C

[InfectedM]

עזרה ב C

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

#include <Stdio.h> #define n 10 void main(void) { int moo[n]; int i,lrg,slrg,tlrg; printf("Enter a number\n"); scanf("%d",&moo[0]); lrg=moo[0]; printf("Enter a number\n"); scanf("%d",&moo[1]); slrg=moo[1]; printf("Enter a number\n"); scanf("%d",&moo[2]); tlrg=moo[2]; for(i=3;i<=n-1;i++){ printf("Enter a number\n"); scanf("%d",&moo); }//for for(i=0;i<=n-1;i++){ if((moo > lrg) && (moo > slrg) && (moo > tlrg)) lrg=moo; if((moo < lrg) && (moo > slrg) && (moo > tlrg)) slrg=moo; if((moo < lrg) && (moo < slrg) && (moo > tlrg)) tlrg=moo; }//for printf("\n%d\n%d\n%d",lrg,slrg,tlrg); }//main​

בקטע הראשון קלטתי שלושה מספרים לאיברים הראשונים, כדי לא להציב 0. אח"כ עברתי על כל המערך מההתחלה והצבתי תנאים, שככל הנראה לא פועלים. אם אני מכניס את המספרים 1,2,3,4,5,6,7,8,9,10(בסדר הזה) הפלט המתקבל הוא 10,2,3. איפה אני שוגה? תוכלו להציע לי תנאים אחרים להציב? תודה

 

[vinney]

כמה תהיות

א. למה אתה קולט את שלושת המספרים בהתחלה? תאתחל את שלושתם עם המספר הראשון במערך, הרי כל עוד אתה לא מכיר שום מספר אחר - הראשון הוא גם הכי גדול, גם שני בגודלו וגם השלישי בגודלו. משם תמשיך בהשוואות. ב. שמעת על המושג "If... Else"? אתה עושה 3 ifים בלתי תלויים, אבל הם תלויים.

 

[InfectedM]

א. בהתחלה ניסיתי דרך אחרת אז זה

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

 

[vinney]

תחשוב הפוך

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

 

[InfectedM]

צודק! תודה על התיקון. עכשיו זה נראה

כך:

for(i=0;i<=n-1;i++){ if((moo > lrg) && (moo > slrg) && (moo > tlrg)) lrg=moo; else if((moo < lrg) && (moo > slrg) && (moo > tlrg)) slrg=moo; else if((moo < lrg) && (moo < slrg) && (moo > tlrg)) tlrg=moo; }//for​

וזה עדיין לא פועל עכשיו מוחזר הפלט :10,1,1.

 

[vinney]

כי לא עשית את מה שאמרתי

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

הוא הופך להיות השני בגודל

ואת זה שכחת לעשות.

 

[InfectedM]

אאוריקה!

#include <Stdio.h> #define n 10 void main(void) { int moo[n]; int i,lrg,slrg,tlrg,temp; printf("Enter a number\n"); scanf("%d",&moo[0]); lrg=moo[0]; slrg=moo[0]; tlrg=moo[0]; for(i=1;i<=n-1;i++){ printf("Enter a number\n"); scanf("%d",&moo); }//for for(i=0;i<=n-1;i++){ if((moo > lrg) && (moo > slrg) && (moo > tlrg)) { lrg=moo; slrg=temp; }//if else if(moo>slrg) { slrg=moo; tlrg=temp; }//if else if(moo>tlrg) tlrg=moo; temp=moo; }//for printf("\n%d\n%d\n%d",lrg,slrg,tlrg); }//main​

זה פועל!

 

[vinney]

עוד הערה

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

 

[eyalamado]

אני יכול להמליץ לך 2 אופציות:

1) לבצע חיפוש גרידי על המערך למציאת האיבר הגדול ביותר ובמקביל לחפש את השני והשלישי. 2) למין את המערך באחד מ-1001 המיונים שיש בעולם (שלא תעיז להשתמש במיון בועות-Bubble sort) ואז לשלוף את ה3 האחרונים או הראשונים תלוי במיון-סדר עולה או יורד...

 

[InfectedM]

דווקא מיון בועות זה מה שלימדו אותנו

בבה"ס המורה אמרה שזה לא יעיל, אבל מפיך זה נשמע נוראי! מה כלכך בעייתי בו?

 

[eyalamado]

שתלמד סיבוכיות תבין...

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

bubble_sort quick_sort straight_selection {max_value} simple_insertion_sort shell_sort merge_sort radix_sort​

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

הסיבוכיות של מיון בועות הינו:

O(N^2)​

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

 

[neko]

האנליזה שלכם לוקה בחסר.

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

 

[vinney]

היי, זה סיבוכיות תיאורטית

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

 

[vinney]

בלי יותר מדי ברברה ../images/Emo13.gif

מיון בועות זה מה שנקרא "אלגוריתם טריויאלי" - הכי פשוט למימוש והבנה, אבל הוא גם הכי פחות מהיר מבין כל הקיימים (כמו שאתה יכול להווכח מההדגמה של אייל

)

 

[vinney]

למה לעשות מיון?

מיון, הכי יעיל שיהיה, זה NLOGN, השאלה הזאת לינארית.

 

[eyalamado]

צודק לא אמרתי שמיון יעיל יותר

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

 

[InfectedM]

עוד קצת סי, ברשותכם

הפעם ניסיתי להפוך את המערך! ככה:

#include <Stdio.h> #define n 10 void main(void) { int moo[n]; int i,temp; for(i=0;i<=n-1;i++){ printf("Enter a number\n"); scanf("%d",&moo); }//for for(i=0;i<=n/2;i++){ temp=moo[n-1-i]; moo[n-i]=moo; moo=temp; }//for for(i=0;i<=n-1;i++){ printf("\n%d",moo); }//for }//main​

זה ממיין לי כמו שצריך חוץ מהחלק הראשון והאחרון. הם הולכים לאיבוד משום מה. אם אני מקליד את המספרים 1,2,3,4,5,6,7,8,9,10. הפלט המתקבל הוא זה: 1 9 8 7 6 5 4 3 2 מה הבעיה בקוד? שוב תודה

 

[vinney]

הבעיה ב moo[n-i]=moo;

והפעם תחשוב קצת לבד

 

[InfectedM]

ידעתי שברח לי שם איזה "1" ../images/Emo13.gif