עזרה מכל המתכנתים!

[אילה9]

כנראה שכן... זו האפשרות היחידה שהסיבוכיות תהיה O של 1
(ואז בכלל לא צריך לעבור על המערך...)

ואם המערך יהיה [8,8,8]?

 

[(:1234]

ואם המערך יהיה [8,8,8]?

אהממ נכון...

 

[דאון]

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

 

[משחזר מידע]

אלא אם כן האיבר הראשון יכול להקרא "עמק"

מבחינה תכנותית מן הסתם לא
כי arr[0]-1 יחזיר 0 ולכן הוא עדיין קטן מ1

 

[(:1234]

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

ובאמת גם הקצוות נקראים עמק?

 

[אילה9]

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

 

[אילה9]

ובאמת גם הקצוות נקראים עמק?

כנראה...
אחרת אין אופציה לענות על השאלה ב o(1)

 

[(:1234]

זה ממש שאלה חמודה אם זה התשובה שלה.. אהבתי

 

[מתכנתת+]

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

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

 

[this my name]

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

כמובן בהנחה שאברי המערך שונים.
כי במערך של [1,1,1], אין אברי עומק.

 

[מתכנתת+]

כמובן בהנחה שאברי המערך שונים.
כי במערך של [1,1,1], אין אברי עומק.

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

 

[מתכנתת+]

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

רק מוסיפה שבמערך יש לפחות איבר עומק 1 ובLOGN נמצא את אחד מהאיברים האלו

 

[מתכנתת+]

מהשאלה מובן שמערך לא ממוין, ולכן חיפוש בינארי לא יעזור

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

 

[דאון]

זה ממש שאלה חמודה אם זה התשובה שלה.. אהבתי

אני דווקא לא אהבתי.
זה סוג שאלה מבלבלת ולא ממש הוגן כשהיא במבחן.
סגנון של קמאטק

 

[תודה לפרוג]

טוב
סליחה
כל מערך יכיל איבר עמק אם לא כל האיברים אותו דבר
לכן זה o(1)

 

[מתכנתת+]

טוב
סליחה
כל מערך יכיל איבר עמק אם לא כל האיברים אותו דבר
לכן זה o(1)

כל מערך שכול איבריו שונים יכיל איבר עמק
לדוגמא 11311 גם לא מכיל איבר עמק למרות שלא כל האיברים אותו דבר

 

[Sara Rivka]

if (arr[i-1]> arr && arr[i+1]>arr)

לא צריך לכתוב: if (arr[i-1]> arr && arr[i+1]>arr) ?

עריכה:
כוונתי שבמקום הarr המודגש יהיה כתוב arr במקום ה-i
אבל זה כשאני מפרסמת את ההודעה זה מופיע בלי המקום ה-i

 

[מתכנתת+]

לא צריך לכתוב: if (arr[i-1]> arr && arr[i+1]>arr) ?

עריכה:
כוונתי שבמקום הarr המודגש יהיה כתוב arr במקום ה-i
אבל זה כשאני מפרסמת את ההודעה זה מופיע בלי המקום ה-i

לא הבנתי

 

[אא-אסתר]

לא צריך לכתוב: if (arr[i-1]> arr && arr[i+1]>arr) ?

עריכה:
כוונתי שבמקום הarr המודגש יהיה כתוב arr במקום ה-i
אבל זה כשאני מפרסמת את ההודעה זה מופיע בלי המקום ה-i

צודקת

 

[מתכנתת+]

לא צריך לכתוב: if (arr[i-1]> arr && arr[i+1]>arr) ?

עריכה:
כוונתי שבמקום הarr המודגש יהיה כתוב arr במקום ה-i
אבל זה כשאני מפרסמת את ההודעה זה מופיע בלי המקום ה-i

זה בדרך הארוכה של On^2 יש דרך הרבה יותר קצרה של LOGn