עזרה בשאלה מראיון עבודה

ע"י: משחזר999

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

ע"י: 1_אורח_כללי

לכל המעוניינים, להלן הפתרון הכי טוב עד כה שאני מצאתי. Void int roll(int a, int jump) { int size=x.length; Int i1=0; Jump %= size; Int i2 = size-jump; While (i1<i2) { a = a+a; a = a-a; a=a-a; i1++; i2++; if (i2==size) i2=size-jump; } } 3 השורות הראשונות בלולאה הן בעצם החלפה של הערכים בשני התאים המתאימים.

ע"י: 1_אורח_כללי

כן נראה לי שזה פתרון טוב. יש גם פתרון יפה נוסף: http://stackoverflow.com/questions/8762 ... m-position צריך פונקציה reverseArray(array, start end) ואז להשתמש בה 3 פעמים: reverseArray(arr, 0, size-1) reverse(arr, 0, k-1) reverse(arr, k, size-1)

ע"י: יוסי ד

החלפות יתבצעו כמובן בעזרת altswap(A1,A2 } A1=A1+A2 A2=A1-A2 A1=A1-A2 {

ע"י: יוסי ד

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

ע"י: 1_אורח_כללי

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