עזרה בקוד, שפת C

19/6/2012 , 20:08

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

כל זה, בסיבוכיות זמן של log(n), סיבוכיות מקום של 1.

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

עזרה מישהו?

tima · שליחה על ידי **tima** » 19/6/2012 , 20:32

מה קורה בתוך התנאי? נראה כאילו חסר שם משהו..

בכל מקרה, למה אתה לא הולך מהתא הראשון קדימה עד שאתה מוצא איבר שגדול מהאיבר הבא אחריו?
משם למיין בסיבוכיות n/1 - משהו כמו להחליף את k הראשונים ב-k האחרונים, להקטין את האורך ב-k, ולעשות שוב, עם טיפה וריאציה.

19/6/2012 , 20:36

הייתי צריך למצוא את k בlog(n) ואז למיין בn*k.

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

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

Soul · שליחה על ידי **Soul** » 19/6/2012 , 22:58

בדקתי ברפרוף קצת ולא בדקתי את ההצעה שלי, אז ייתכן שאני טועה...

הצעת פיתרון ב-PasteBin:

עריכה: עריכה של הקוד

לא ברור לי מה קורה בבלוק של else. הייתי מצפה שזה יהיה רק middle = (middle + max)/2 וזהו.

דבר שני, נדמה שבבדיקה של if else אתה מנסה למצוא את הצד השמאלי של ההזזה (אם האמצע קטן מהסוף --> תמשיך לחפש, ז"א אתה מחפש אמצע שגדול מהסוף) ואילו בבדיקה של do while אתה בודק האם זה הצד הימני של ההזזה (צא כשהמספר הקודם מהאמצע גדול ממנו)

ז"א אם המערך הוא:
[0]7
[1]8
[2]0
[3]1
[4]2
[5]3
[6]4
[7]5
[8]6

ב-if אתה מוצא את המיקום של 8 ([1]) כשאתה בעצם אמור למצוא את המיקום של 0 ([2]). יוצא שב-while אתה בודק שהוא עדיין גדול מקודמו: [1]8 גדול מ-[0]7 ואתה ממשיך שמאלה שלא כשורה.

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

אז אולי תשנה את התנאי ב-if else כדי למצוא את הצד הימני של ההזזה. או שתנסה להחליף את התנאי של do while בבדיקה של המספר העוקב במקום הקודם. בחזרה תתן לו middle + 1. תוודא ש-middle + 1 לא גולש. לצורך זה אפשר לשמור על הערך של length (ונראה שאין צורך לשנות אותו כי אני נעזר ב-max_array בבלוק של ה-else). צריך גם איכשהו לבדוק שזה מחזיר 0 כשאמצע הוא תחילת המערך וה-if עדיין מתקיים...

tima · שליחה על ידי **tima** » 20/6/2012 , 0:00

Sir Psycho Sexy כתב:הייתי צריך למצוא את k בlog(n) ואז למיין בn*k.

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

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

בשביל למצוא את k, תשווה את middle ל- middle+1. ואז תחזור על הפעולה הזו ברקורסיה על חצי המערך הנותן (זה שהאיבר הקריטי נמצא בו). זה עושה את זה בלוג n.

20/6/2012 , 7:10

רקורסיה תוסיף לסיבוכיות מקום, זה למה זה נעשה בdo while.

Antrax · שליחה על ידי **Antrax** » 20/6/2012 , 8:37

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

20/6/2012 , 9:03

אני יכול למצוא מהו k מאד בקלות, הבעייה שלי היא המימוש בlog n.

Antrax · שליחה על ידי **Antrax** » 20/6/2012 , 9:16

אכן, לעשות את זה בO(n) זה קל. אז הרמז שלי לא היה מספיק עבה?

[עריכה] לא לספיילר לך את מבני, אבל למצוא מינימום במערך בO(logn) אפשרי גם במערך בכלל לא ממוין, אז על אחת כמה וכמה בזה.

jamanta · שליחה על ידי **jamanta** » 20/6/2012 , 9:59

לא יודע אם אני מפספס משהו אבל אם מצאת את k אז זה לא פשוט לעשות לולאה אחת נוספת שרצה פעם אחת על המערך ומסדרת אותו מחדש?

tomeriko · שליחה על ידי **tomeriko** » 20/6/2012 , 10:31

jamanta כתב:לא יודע אם אני מפספס משהו אבל אם מצאת את k אז זה לא פשוט לעשות לולאה אחת נוספת שרצה פעם אחת על המערך ומסדרת אותו מחדש?

הוא רק צריך למצוא את k

20/6/2012 , 12:24

דורון, במקום לדבר בחידות, בא לך לעזור?

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

leeron · שליחה על ידי **leeron** » 20/6/2012 , 22:31

אני לא ממש יודע שפת C אבל אולי אני יוכל לעזור..
int k = 0;
int min = Array[0];
for (int i = 1; i < Length; i++)
if (Array < min)
{
k = i;
min = Array;
}
זה השורות קוד למציאת k
עריכה: יש משהו יותר יעיל:
for (int i = 0; i <Length> Array[i + 1])
return i;

20/6/2012 , 22:34

leeron כתב:אני לא ממש יודע שפת C אבל אולי אני יוכל לעזור..
int k = 0;
int min = Array[0];
for (int i = 1; i < Length; i++)
if (Array < min)
{
k = i;
min = Array;
}
זה השורות קוד למציאת k

נכון, הבעייה היחידה היא שזה עובדת בסיבוכיות זמן O(n), כשאני צריך O(logn). ברור שלרוץ על המערך, לבדוק איבר איבר ולבחור את ההכי קטן זה הדרך הכי פשוטה- היא אבל הדרך לא הכי יעילה.

tomeriko · שליחה על ידי **tomeriko** » 20/6/2012 , 22:42

אם אתה ממש צריך פיתרון, לא ממש הסתכלתי, אבל את ה יכול לעשות חיפוש לפי אמצע.
אתה צריך a>a[i+1]
אם זה מתקיים מצאת רק עם a[i+1]<a[2+i]
אם מקיים הראשון אבל לא השני, אתה צריך לחפש מחצי הימיני. אם הראשון לא מתקיים חפש בחצי השמאלי .
אתה צריך בעיקרון רק שני משתנים - קצע ימין וקצה שמאל. זה בעצם חיפוש בינארי ולכן o(logn). במקום זה o(1)

leeron · שליחה על ידי **leeron** » 20/6/2012 , 22:49

מה זה (log(n?

tomeriko · שליחה על ידי **tomeriko** » 20/6/2012 , 22:50

leeron כתב:מה זה (log(n?

לוג היא פונקציה, כדאי לחפש אותה בויקיפדיה - logn=x זה כמו n=e^x

jamanta · שליחה על ידי **jamanta** » 21/6/2012 , 6:30

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

21/6/2012 , 7:43

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

Soul · שליחה על ידי **Soul** » 21/6/2012 , 10:53

Sir Psycho Sexy כתב:אתם כל כך מצחיקים... מישהו בכלל הסתכל על הקוד שפרסמתי? כי כולם אומרים לי לכתוב אותו מחדש.

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

הבנתי שאתה נעזר ב-length כדי לדלג את middle למקום הנכון. אבל משום מה אתה לא עושה בו שימוש בבלוק של ה-if. זה אומר שבבדיקה של צד שמאל אתה עובר לאמצע שבין 0 ל-middle שזה בעיה. היית צריך כמו ב-else להעזר ב-length/2 אבל להפחית במקום להגדיל. אולי אפילו שווה ללכת על בטוח עם משתנה start.