עבור לתוכן

עזרה בבעיה שקיבלתי ב C.

Featured Replies

פורסם

השאלה שקיבלתי היא כזו

x33i.png

Uploaded with ImageShack.us

אודה מאוד למי שיוכל לעזור לי עם סעיף ב' (הבונוס)

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

תודה רבה למי שיכול לעזור!!!

אהה ואם אפשר אז אני צריך עזרה כמה שיותר מהר :)

פורסם

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

נערך על-ידי karpazi0

פורסם

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

נערך על-ידי א

פורסם

למיין את המערך כבר לא יהיה בסיבוכיות (o(n. כלומר, זה אפשרי למיין את המערך בסיבוכיות כזו אבל זה דורש מערך עזר.

פורסם

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

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

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

נערך על-ידי Zelig

פורסם

פיתרון לינארי עם מערך עזר:

מקצים מערך אפסים בגודל המערך המקורי. רצים על המערך המקורי ואם רואים את המספר i, במקום הi במערך העזר עושים ++. בסוף, אם מערך העזר הוא 1ים - מחזירים 1, אחרת 0.

פיתרון לינארי בלי מערך עזר:

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

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

פורסם

לא כתוב בבעיה שום דבר על מיון באופן כללי...

נערך על-ידי שניצל

פורסם

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

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

פורסם

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

נערך על-ידי WildFire

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים