שתי שאלות קשות שהמורה שלי הביא....

[X-BLADE]

בשפת JAVA או C....[לא למדנו יותר מידי חומר רק את החומר של השתי יחידות בגרות...]

א)

נתבונן ברביע הראשון של מערכת צירים על קווים המחברים את הנקודות 1...N על ציר הY עם הנקודות 1....N על ציר הX [נניח שהמרחק קבוע]כל נקודה i על ציר הY מחוברת בקו לשתי נקודות על ציר הX: הנקודה i והנקודה N-i+1.

כתוב תוכנית שהקלט שלה הוא מספר שלם חיובי זוגי N [בין 2 ל10000], והפלט שלה הוא מספר החיתוכים של זוגות קווים מתוך הקווים המתוארים [שני קווים נחתכים אם קוארדינת הY של האחד גדולה מזו של השני וקוארדינת הX של האחד קנה מזו של השני ]

למשל עבור הקלט 2 יהיה הפלט 1.

ב)משחק הקטנת מספרים:

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

למשל עבור הערך ההתחלתי N=4, יקטין השחק הראשון את המספר ל3 (אם יקטינו למספר גדול יותר יפסיד) יריבו שיכול להקטינו ל2 או לאחד יקטינו ל2 והראשון יקטין ל0 וינצח.

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

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

[שניצל]

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

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

הפתרון היותר מעניין (ומהיר) הוא למצוא נוסחה מתמטית לחישוב הזה (מה שהופך את השאלה לתרגיל בקומבינטוריקה...)

[X-BLADE]

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

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

הפתרון היותר מעניין (ומהיר) הוא למצוא נוסחה מתמטית לחישוב הזה (מה שהופך את השאלה לתרגיל בקומבינטוריקה...)

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

כמו לדוגמא אם N=4.......יש הרבה חיתוכי קווים לא רק עם הזוגות הנוחכיים של I,N+1-I.

אני חשבתי על משהו שאין לי מושג איך לבצע אותו....עדיין לא למדנו פונקציות אבל שמעתי עליהם קצת...

להגדיר פונקצייה כזאת שיהיו לה 4 משתנים [או תכונות] X1,X2,Y1,Y2. עכשיו לעשות תוכנית שתגצהיר על מערך חד מימדי מסוג הפונקצייה.

לעשות לולאה שתמלא את המערך בקווים [את כל התכונותשל המערך כמובן] ואז לבדוק מתי התנאי הזה שהבאת [ושהיה כרמז גם כן] מתקיים על כל תאי המערך והתכונות שלו [שזה בעצם הקווים כי כך הגדרנו אותם בלולאה] חוץ מהתא הנוחכי ולמנות כל פעם שהתנאי מתקיים ואז להציג את המונה...

הבעיה שאין לי מושג איך עושים את זה.....

למשהו יש רעיון? שוב ממש תודה על העזרה....

לגבי השאלה השנייה אין לי מושג איך להתחיל זה פשוט ממש קשה....מצד שני אני בטוח שאחד מהגאונים פה יפתור את זה....

[שניצל]

לא הבנת אותי נכון.

התכוונתי לכל הזוגות, כלומר כל שילוב של שניים מ-2N הקווים.

את ב' עדיין לא קראתי

[ofir_yair]

לגבי השאלה השנייה:

אם המחשב מתחיל, אז הבחירה החכמה תהיה לחסר מספר כך ש:

א. אם N מתחלק ב-3 אז לחסר N/3-1

ב. אם N לא מתחלק ב-3 אז לחסר את הערך השלם התחתון של N/3

ואסביר מכאן מדוע נצחונו של המחשב מובטח, באמצעות דוגמה:

נניח N=50. אינו מתחלק ב-3 לכן נחסר את הערך השלם התחתון של 50/3, כלומר נחסר 16.

כעת ליריב האנושי נתון המספר 34. הוא לא יכול לאפס את המספר כי לכל היותר מותר לו לחסר 32,

אולם חייב לחסר לפחות 16, לכן המקסימום שיכול להישאר זה 18, ולכן מכאן ניצחון המחשב מובטח.

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

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

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

לדוגמה עבור אותו N=50, אם השחקן החליט לחסר למשל 10, אז למחשב נתון המספר 40 כך שהערך השלם של 40/3 נמצא בתחום הבחירה של המחשב (כרגע בין 10 ל-20) ולכן יטיב אם יבחר ב13 כדי להבטיח את נצחונו שוב, כפי שהסברתי בטקטיקה למעלה.

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

[X-BLADE]

לגבי השאלה השנייה:

אם המחשב מתחיל, אז הבחירה החכמה תהיה לחסר מספר כך ש:

א. אם N מתחלק ב-3 אז לחסר N/3-1

ב. אם N לא מתחלק ב-3 אז לחסר את הערך השלם התחתון של N/3

ואסביר מכאן מדוע נצחונו של המחשב מובטח, באמצעות דוגמה:

נניח N=50. אינו מתחלק ב-3 לכן נחסר את הערך השלם התחתון של 50/3, כלומר נחסר 16.

כעת ליריב האנושי נתון המספר 34. הוא לא יכול לאפס את המספר כי לכל היותר מותר לו לחסר 32,

אולם חייב לחסר לפחות 16, לכן המקסימום שיכול להישאר זה 18, ולכן מכאן ניצחון המחשב מובטח.

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

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

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

לדוגמה עבור אותו N=50, אם השחקן החליט לחסר למשל 10, אז למחשב נתון המספר 40 כך שהערך השלם של 40/3 נמצא בתחום הבחירה של המחשב (כרגע בין 10 ל-20) ולכן יטיב אם יבחר ב13 כדי להבטיח את נצחונו שוב, כפי שהסברתי בטקטיקה למעלה.

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

התוכנית צריכה לחשב האם כדאי לה להתחיל או לא......למה דווקא לחלק ב3? מה זה הערך התחתון???

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

ואם תוכל לכתוב לי את התוכנית אני אשמח מאוד כי לא כ"כ הבנתי איזה פעולות לעשות...

לא הבנת אותי נכון.

התכוונתי לכל הזוגות, כלומר כל שילוב של שניים מ-2N הקווים.

את ב' עדיין לא קראתי

אוקיי אז איך בדיוק מבצעים את הבדיקה הזאת??? אתה יכול בבקשה לכתוב לי קטע תוכנית או אלגוריתם?

שוב תודה ענקית לשניכם!!!

[שניצל]

הנה האלגוריתם הכי בסיסי:

1. sum = 0

2. עבור i מ-1 עד N בצע:

2.1. עבור j מ-i+1 עד N בצע:

2.1.1. אם j < N-i+1 אז sum = sum+1

2.1.2 אם i > N-j+1 אז sum=sum+1

קפיש?

(שים לב שאפשר לפשט את האלגוריתם הרבה יותר...)

[ofir_yair]

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

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

4) כ,1- 5)ל,0 6)כ,1- 7)כ, 2- 8)ל,0 וכו' (כ-כדאי להתחיל שם, ל- לא כדאי להתחיל שם)

כאשר העיקרון המנחה הוא כזה:

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

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

סיבוכיות הפתרון אמנם גרועה: תשובה להאם כדאי להתחיל במקום N תתקבל בסיבוכיות של( O(N^2, אך אלגוריתם צעדי המחשב למעשה שמור כבר במערך, כי הרי המחשב יבצע את הצעד שכתוב לו לעשות בכל תא ותא (המספר המינימלי שיבטיח ניצחון).

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

תחילה, ממקום 1 לא ניתן כלל לשחק, ולכן נתחיל מ-2:

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

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

אדגים כעת את האלגוריתם על N=5: צריך לבדוק עבור צעדים בגודל 1 עד הערך השלם התחתון של 5/3, לכן 1, אם הצעדים בגודל הנ"ל יבטיחו ניצחון בטוח. כאמור יש צעד אחד בלבד לבדיקה, לכן נבדוק אותו (כי הרי צעד גדול יותר יביא להפסד מיידי, שכן היריב יוכל לאפס מיד לאחר הצעד הנ"ל). נבדוק עבור צעד אחד אחורה ונגלה שהביא אותנו לתא מספר 4 ממנו ניתן לנצח את המשחק בצעד אחד אחורה - כלומר במהלך חוקי ליריב, ולכן הצעד יביא להפסד וודאי (אלא אם כן היריב האנושי סתום).

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

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

שוב, הפתרון די מסורבל, ועומד בסיבוכיות מקום( O(N וזמן ( O(N^2 די גרועות, אבל לא מצאתי עד כה משהו יותר טוב. אשמח לשמוע רעיונות אחרים, שאלה בהחלט מעניינת!

[PhoenixBoy]

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

http://www.tau.ac.il/~cstasks/olympiada/olympiada-2007.html

יש שם גם פתרונות ועוד 2 שאלות שהופיעו באותה בחינה.

[X-BLADE]

הנה האלגוריתם הכי בסיסי:

1. sum = 0

2. עבור i מ-1 עד N בצע:

2.1. עבור j מ-i+1 עד N בצע:

2.1.1. אם j < N-i+1 אז sum = sum+1

2.1.2 אם i > N-j+1 אז sum=sum+1

קפיש?

(שים לב שאפשר לפשט את האלגוריתם הרבה יותר...)

אחי אתה יכול קצת יותר לפרט כי לא הבנתי בדיוק כמה דברים: מה J מסמל? למה הJ הוא מI+1??? ולמה דווקא האיפים האלו???איפה בדיוק התנאי של בדיקת החיתוך???ואיפו נכנסים לתמונה הקווים הרגילים [מI לI]????

עריכה: כתבתי את האלגוריתם והתוכנית לא עושה את העבודה =\ כשאני קולט 2 זה מדפיס לי 0.....

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

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

4) כ,1- 5)ל,0 6)כ,1- 7)כ, 2- 8)ל,0 וכו' (כ-כדאי להתחיל שם, ל- לא כדאי להתחיל שם)

כאשר העיקרון המנחה הוא כזה:

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

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

סיבוכיות הפתרון אמנם גרועה: תשובה להאם כדאי להתחיל במקום N תתקבל בסיבוכיות של( O(N^2, אך אלגוריתם צעדי המחשב למעשה שמור כבר במערך, כי הרי המחשב יבצע את הצעד שכתוב לו לעשות בכל תא ותא (המספר המינימלי שיבטיח ניצחון).

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

תחילה, ממקום 1 לא ניתן כלל לשחק, ולכן נתחיל מ-2:

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

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

אדגים כעת את האלגוריתם על N=5: צריך לבדוק עבור צעדים בגודל 1 עד הערך השלם התחתון של 5/3, לכן 1, אם הצעדים בגודל הנ"ל יבטיחו ניצחון בטוח. כאמור יש צעד אחד בלבד לבדיקה, לכן נבדוק אותו (כי הרי צעד גדול יותר יביא להפסד מיידי, שכן היריב יוכל לאפס מיד לאחר הצעד הנ"ל). נבדוק עבור צעד אחד אחורה ונגלה שהביא אותנו לתא מספר 4 ממנו ניתן לנצח את המשחק בצעד אחד אחורה - כלומר במהלך חוקי ליריב, ולכן הצעד יביא להפסד וודאי (אלא אם כן היריב האנושי סתום).

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

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

שוב, הפתרון די מסורבל, ועומד בסיבוכיות מקום( O(N וזמן ( O(N^2 די גרועות, אבל לא מצאתי עד כה משהו יותר טוב. אשמח לשמוע רעיונות אחרים, שאלה בהחלט מעניינת!

וואי אחי ממש ממש תודה אני רואה שהשקעת אבל זה באמת מסובך ולא בדיוק הצלחתי להבין איך זה יעבוד....

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

[שניצל]

עבור כל i מ-1 עד N קיימים לך 2 קווים, נכון? הקו שמחבר בין i ל-i, והקו שמחבר בין i ל-N-i+1.

האלגוריתם צריך לעבור על כל זוגות הקווים שייתכן שחותכים זה את זה.

איך עוברים על זוגות? באמצעות שתי לולאות מקוננות. ה-i "בוחר" את הקו הראשון בזוג, ה-j "בוחר" את הקו השני בזוג.

למה j רץ רק מ-i+1? כי אם הוא היה רץ על הכל, אז היית בודק כל זוג פעמיים (כי הסדר של הקווים בזוג לא משנה).

לגבי ה-ifים:

תיאורטית, עבור כל i ו-j יש לך 4 קווים - (i,i), (j,j), (i,N-i+1), (j,N-j+1). אתה צריך לבדוק כל זוג מהם אם הם חותכים זה את זה (סה"כ 6 בדיקות).

אבל מה? חלק מהבדיקות לא צריך לבדוק - לדוגמה, הקווים (i,i) ו-(j,j) הם מקבילים, ולכן בטוח לא חותכים זה את זה...

בסופו של דבר, אתה צריך לבדוק רק:

אם i<j וגם i>N-j+1, או i>j וגם i<N-j+1

ואם j<i וגם j>N-i+1 או j>i וגם j<N-i+1

שים לב שכיוון שאתה כבר יודע ש-i<j (זה נובע מהלולאה שלך), אז ה"ביטוי" הנ"ל הרבה יותר פשוט:

אם i>N-j+1,

ואם j<N-i+1.

עכשיו יותר מובן?

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

[X-BLADE]

עבור כל i מ-1 עד N קיימים לך 2 קווים, נכון? הקו שמחבר בין i ל-i, והקו שמחבר בין i ל-N-i+1.

האלגוריתם צריך לעבור על כל זוגות הקווים שייתכן שחותכים זה את זה.

איך עוברים על זוגות? באמצעות שתי לולאות מקוננות. ה-i "בוחר" את הקו הראשון בזוג, ה-j "בוחר" את הקו השני בזוג.

למה j רץ רק מ-i+1? כי אם הוא היה רץ על הכל, אז היית בודק כל זוג פעמיים (כי הסדר של הקווים בזוג לא משנה).

לגבי ה-ifים:

תיאורטית, עבור כל i ו-j יש לך 4 קווים - (i,i), (j,j), (i,N-i+1), (j,N-j+1). אתה צריך לבדוק כל זוג מהם אם הם חותכים זה את זה (סה"כ 6 בדיקות).

אבל מה? חלק מהבדיקות לא צריך לבדוק - לדוגמה, הקווים (i,i) ו-(j,j) הם מקבילים, ולכן בטוח לא חותכים זה את זה...

בסופו של דבר, אתה צריך לבדוק רק:

אם i<j וגם i>N-j+1, או i>j וגם i<N-j+1

ואם j<i וגם j>N-i+1 או j>i וגם j<N-i+1

שים לב שכיוון שאתה כבר יודע ש-i<j (זה נובע מהלולאה שלך), אז ה"ביטוי" הנ"ל הרבה יותר פשוט:

אם i>N-j+1,

ואם j<N-i+1.

עכשיו יותר מובן?

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

בשאלה כתוב שעבור הקלט 2 יהיה הפלט 1....[זאת השאלה הראשונה כאן http://www.tau.ac.il/~cstasks/olympiada/olympiada-2007.html].

וציירתי את זה וזה חותך פעם אחת הנה:

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

[שניצל]

אופס, צודק, זה באמת אמור להיות 1 (וגם יוצא 1 לפי האלגוריתם שלי).

תעלה לכאן את הפתרון שלך ונראה.

[X-BLADE]

אופס, צודק, זה באמת אמור להיות 1 (וגם יוצא 1 לפי האלגוריתם שלי).

תעלה לכאן את הפתרון שלך ונראה.

יוצא 0 =\

import java.util.Scanner;
public class Targil {

  public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n,mone=0,i=0,j=0;
n=in.nextInt();
for (i=1;i<=n;i++)
{
	for (j=i+1;j<=n;j++)
	{
		if (n-i+1>j)
		mone++;
		if (n-j+1<i)
		mone++;
	}
}
 System.out.println(mone);
 }
}

עריכה מצאתי קצת מידע על הפתרונות לשאלון הזה:

"לא-מעט פתרו נכון ואלגנטי את שאלה 1, ובסיבוכיות זמן O(1). מעטים פתרו את השאלות האחרות נכון ויעיל. פתרון שאלה 2 מבוסס על מספרי פיבונצ'י, פתרון שאלה 3א בסיבוכיות זמן O(N), ופתרונות שאלות 3ב ו-4 בסיבוכיות זמן O(NlogN). בקרוב תפורסם התייחסות יותר מפורטת לתשובות. אנו שמחים מאד על העניין וההשתתפות של כולם, ומקווים שתמשיכו להיות פעילים בפורום (גם מי שלא עבר לשלב הבא). נשתדל להמשיך להציג שם בעיות אתגר מעניינות, אשר מהן ניתן ללמוד לעתיד."

מקור http://www.tau.ac.il/~cstasks/luach-modaot_2007.html

[שניצל]

צודק, יש טעות בחישוב שלי.

אתה צריך לבדוק גם אם N-i+1 > N-j+1. שים לב שכיוון ש-i<j, אז הביטוי הזה תמיד נכון, כלומר אין צורך באמת לבדוק אותו (אלא רק להעלות את mone ב-1).

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