שאלה בתוכנה

[12344]

בכל שלב, האלגוריתם יחלק את הרשימה שלו ל- 3 חלקים במקום 2: בערך שליש האיברים השמאליים, בערך
שליש האמצעיים, ובערך שליש הימניים. האלגוריתם יחליט עם איזה שליש יש להמשיך באמצעות בדיקת שני
הגבולות בין החלקים. "בערך" – מותר שהחלקים יהיו בגדלים ששונים לכל היותר ב- 1 זה מזה.
א. ממשו פונקציה בשם (ternary_search(key, lst המקבלת מספר key ורשימה ממוינת lst של מספרים,
ופועלת בשיטה הנ"ל להחזרת אינדקס בו נמצא key ב- lst, או None אם הוא לא נמצא. אם key נמצא
ביותר מאינדקס אחד, יוחזר אחד האינדקסים, שרירותית. אין צורך לבדוק תקינות הקלט. הפונקציה
לא מדפיסה דבר. לדוגמה:
>>> ternary_search(3,[1,2,3,4,5])
2
>>> ternary_search(1,[2,3,4,5])
>>>
הנחיה: על המימוש שלכם להיות איטרטיבי ולא רקורסיבי


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


הקוד לא צריך להיות בשפה מיוחדת או משהו, אני כבר אתרגם אותו למה שאני צריך (אני מקווה שאצליח).

 

[idoamsallem]

השאלה לא ברורה במיוחד זה מחזיר את המיקום של key ברשימה ?
זה בדומה לחיפוש בינארי רק בשלשות ?

 

[12344]

השאלה לא ברורה במיוחד זה מחזיר את המיקום של key ברשימה ?
זה בדומה לחיפוש בינארי רק בשלשות ?

כן, את האינדקס של המיקום שלו.
וכן, בדיוק.

 

[idoamsallem]

כן, את האינדקס של המיקום שלו.
וכן, בדיוק.

אז זה אומר שהרשימה ממוינת ?

 

[sus]

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

מקווה שהבנת אותי

 

[12344]

אז זה אומר שהרשימה ממוינת ?

כן, הרשימה ממוינת.

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

מקווה שהבנת אותי

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

 

[-=ALX=-]

זה אמור להיות מאוד דומה לחיפוש בינארי רגיל רק שכאן תחזיק 2 אינדקסים.
ז"א כל פעם תחלק את המערך ל3 חלקים(במקום לחצות את N ל0.5N כמו בחיפוש בינארי תחלק ל3 , ז"א N/3 ו N\3 כפול 2 ועוד 1.
ואז בשלב הבדיקה תבדוק את האיבר במקום הN/3 , ואם הוא קטן מהאיבר שאתה מחפש אז את האיבר במקום הN\3 כפול 2 ועוד 1. ותעדכן אינדקסים בהתאם.