שאלה - מיפוי חחע מזוג מספרים לאחד

[kikkler]

שאלה - מיפוי חחע מזוג מספרים לאחד

n הוא שלם בין 0 ל-N-1 m הוא שלם בין 0 ל- M-1. אני רוצה לקחת את הזוג <n.m> ולהחזיר בצורה חח"ע מס' בין 0 ל- NxM - 1. אם N היה שווה ל-M, למשל, התשובה הטריויאלית הייתה n * N + m. הבעיה היא שהם שונים, וכל דבר שאני חושב עליו נכשל במבחן החח"עיות.. יש למישהו רעיון לכיוון?

 

[shirbi]

למה שלא תכניס את האפשרויות לטבלה

שמספר העמודות שלה הוא N ומספר השורות שלה הוא M, ואז להחזיר את האיבר הנמצא בעמודה ה n בשורה הm?

 

[kikkler]

כי זה קצת מכוער מימושית..

הנה עוד רעיון שהיה לי - גם הוא לא הכי יפה..

 

[kikkler]

למען האמת אתה צודק

זה לא מכוער בכלל.. תודה

 

[kikkler]

מצטער על חוסר ההחלטיות שלי

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

 

[vinney]

הN וM ידועים?

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

 

[kikkler]

ידועים

פונקציה הופכית קיימת, אבל בשביל למצוא אותה צריך לסרוק את המערך.. בקיצור הייתי מעדיף O(1) space/time בשני הכיוונים. רעיון שקיבלתי כרגע ואני צריך עוד לחשוב עליו -

i = (N > M) ? m * N + n : n * M + m​

 

[vinney]

ברור שזה O של 1

זה הרעיון שקיבלת הרגע? שיר כתב לך את זה ב22:42

 

[kikkler]

אולי אם מסתכלים על ההודעה

בזווית ועוצמים עין אחת...

העניין עם להכניס מספרים לטבלה קצת בילבל אותי, אבל בדיעבד אני מבין את הנקודה תודה