שאלה במדעי המחשב
- פותח הנושא KO74
- פורסם בתאריך
הסברתי כבר, אבל שוב:
נעקוב אחרי הביצוע עבור המערך 1,2,3,1,2,3,1,2,3 המערך באורך 9 הנה הביצוע: התא הראשון - הערך הוא 1, מוסיפים לתא 1, (לא תא 0) את הערך 9, עכשיו יש בו 11 1,11,3,1,2,3,1,2,3 התא השני - הערך הוא 11, מוסיפים לתא במקום arr[index]%9 שזה 11%9 את הערך 9, עכשיו יש בו 12: 1,11,12,1,2,3,1,2,3 התא השלישי - יש בו 12, מוסיפים לתא ה- 12%9 את הערך 9, עכשיו יש בו 10 1,11,12,10,2,3,1,2,3 וכך הלאה, זה קצת מסובך, אבל זה עובד בדוק. קצת אמונה
נעקוב אחרי הביצוע עבור המערך 1,2,3,1,2,3,1,2,3 המערך באורך 9 הנה הביצוע: התא הראשון - הערך הוא 1, מוסיפים לתא 1, (לא תא 0) את הערך 9, עכשיו יש בו 11 1,11,3,1,2,3,1,2,3 התא השני - הערך הוא 11, מוסיפים לתא במקום arr[index]%9 שזה 11%9 את הערך 9, עכשיו יש בו 12: 1,11,12,1,2,3,1,2,3 התא השלישי - יש בו 12, מוסיפים לתא ה- 12%9 את הערך 9, עכשיו יש בו 10 1,11,12,10,2,3,1,2,3 וכך הלאה, זה קצת מסובך, אבל זה עובד בדוק. קצת אמונה
אני אנסה שוב
הלולאה מבצעת מעבר אחד על המערך, ומשתמשת בו כמערך מונים הבעיה שנוצרת היא שאני לא יכול למנות בצורה רגילה כי אז אני הורס את הערכים הבאים מה הפיתרון, למנות בצורה לא 'קונבנציונלית', זה בדיוק מה שעשיתי הערך הכי גדול שיכול להופיע במערך הוא N-1, לכן כל פעם שאני מונה, במקום להוסיף 1 עבור כל פעם, אני מוסיף N עבור כל פעם זה עדיין לא פותר את הבעיה, לכן, אני לא מסתכל על התא כמו שהוא אלא על התא mod N לדוגמה: N=9, בתא הראשון יש את הערך 3, ובתא השלישי יש לי את הערך 7 כשאני סורק את התא הראשון, אני נתקל בערך 3, ומוסיף לתא ה- 3=3%9 את הערך 9 כלומר בתא השלישי יש לי עכשיו 16 במקום 7 כשאני יגיע לתא השלישי, אני יוסיף לתא ה- 7=16%9 את הערך 9
הלולאה מבצעת מעבר אחד על המערך, ומשתמשת בו כמערך מונים הבעיה שנוצרת היא שאני לא יכול למנות בצורה רגילה כי אז אני הורס את הערכים הבאים מה הפיתרון, למנות בצורה לא 'קונבנציונלית', זה בדיוק מה שעשיתי הערך הכי גדול שיכול להופיע במערך הוא N-1, לכן כל פעם שאני מונה, במקום להוסיף 1 עבור כל פעם, אני מוסיף N עבור כל פעם זה עדיין לא פותר את הבעיה, לכן, אני לא מסתכל על התא כמו שהוא אלא על התא mod N לדוגמה: N=9, בתא הראשון יש את הערך 3, ובתא השלישי יש לי את הערך 7 כשאני סורק את התא הראשון, אני נתקל בערך 3, ומוסיף לתא ה- 3=3%9 את הערך 9 כלומר בתא השלישי יש לי עכשיו 16 במקום 7 כשאני יגיע לתא השלישי, אני יוסיף לתא ה- 7=16%9 את הערך 9
המם.... טוב, אני סתם נכנס לקטנות../images/Emo13.gif
זה דקויות, אבל כדי לייצג מספר עד N, אתה חייב LOG N סיביות, וכדי לבצע כל פעולה חשבונית, אתה חייב לעבור על כל LOG N הסיביות. לא משנה איזו פעולה, לכן כל פעולת חשבון היא LOG N. אבל, כשמדברים על אלגוריתמים שהם לא אלגוריתמי חישוב, בדרך כלל מזניחים את זה, ובהנחה הזאת אפשר לפתור את השאלה הזאת, גם בחישוב מודולרי שהצעת.
זה דקויות, אבל כדי לייצג מספר עד N, אתה חייב LOG N סיביות, וכדי לבצע כל פעולה חשבונית, אתה חייב לעבור על כל LOG N הסיביות. לא משנה איזו פעולה, לכן כל פעולת חשבון היא LOG N. אבל, כשמדברים על אלגוריתמים שהם לא אלגוריתמי חישוב, בדרך כלל מזניחים את זה, ובהנחה הזאת אפשר לפתור את השאלה הזאת, גם בחישוב מודולרי שהצעת.
לא היה לי כח לקרוא את כל השרשור
ואני בטוח שמי שהציג את הבעיה התייחס לפעולות אריתמטיות באל פעולות אטומיות כנהוג אצל אנשי מחשבים בימינו. מה שיכול להיות נכון באופן תיאורתי ומעשי כאשר מביטים על הבעיה שאתה מציג מנקודה מסויימת. בכל מקרה, ניתן לפתור את הבעיה כך c <- N לכל i <- 1 to N בצע c <- c + array - i בסיום אלגוריתם קצר זה יהיה בידך המספר המבוקש.
ואני בטוח שמי שהציג את הבעיה התייחס לפעולות אריתמטיות באל פעולות אטומיות כנהוג אצל אנשי מחשבים בימינו. מה שיכול להיות נכון באופן תיאורתי ומעשי כאשר מביטים על הבעיה שאתה מציג מנקודה מסויימת. בכל מקרה, ניתן לפתור את הבעיה כך c <- N לכל i <- 1 to N בצע c <- c + array - i בסיום אלגוריתם קצר זה יהיה בידך המספר המבוקש.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.