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

למשל, אם הוקטור 10-,2,4-,5,3-,1

אז תת הוקטור שסכומו הגדול ביותר הוא 2,4-,3 שזה שווה ל 5

כתבתי 2 רקורסיות, שפועלות בשתי דרכים.

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

מצורפים 2 הרקוקסיות בקבצי ++C

https://2005-uploaded.fresh.co.il/2...29/20550925.cpp
https://2005-uploaded.fresh.co.il/2...29/18708079.cpp

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

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

יש הסבר בויקיפדיה: http://he.wikipedia.org/wiki/נוסחת_נסיגה

בכל מקרה, לגבי התרגיל שאני קיבלתי

פה כתובים ההוראות לתרגיל: http://info4u.yosh.ac.il/michlol200...0/ALG1_04_2.doc

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

http://info4u.yosh.ac.il/michlol200...0/ALG1_04_1.doc

הבעיה שאני גם יודע תיכנות, אבל לא מבין כלום בצד המתמטי של זה

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


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

T(n)=2T(n/2)+O(n)

זה במקרה הגרוע...
ה(2T(n/2 אתה בטח יודע (אתה עושה פעמיים את הפונקצייה המסויימת הזאת על n/2 איברים)
ה(O(n הוא בגלל שכל פעם אתה עושה סדר גודל של n פעולות
סה"כ לפי נוסחאת האב יוצא שכל הפונקצייה היא סדר גודל של (O(n*log n

בכל מקרה להבא, אני לא חושב שזה פורום שפותרים בו שיעורי בית, יש פורום מיוחד בשביל זה.
אם אתה מראה למישהו קוד, תעד אותו! אחרת אף אחד לא יבין אותו! (כמו שבעוד שבוע אם לא תגע בו גם אתה לא תבין אותו).

מקווה שעזרתי

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

עזרת המון

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

בכל מקרה, תודה רבה !

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

וצריך כמובן לבחור את המקסימום מבין 1 ו2.

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

ועל כן,האלגוריתם הרקורסיבי יראה ככה :

קוד:

  
f(arr,i,j)
{
if (i==j) return(arr[i]);
else
{
current_max=f(arr,i+1, j);
for(itertor=i;itertor<=j;++itertor)
{
if (check_sum=sum(i,itertor)>current_max) current_max=check_sum;
}//for
return(current_max);
}//else
}//f
 

אבל ניראה לי שזה סיבוכיות גבוהה יותר ממה שהוא עשה (למרות שלא הבנתי בדיוק מה שהוא עשה והבנתי מה אתה עשית)
זה יוצא

T(n)=T(n-1)+O(n)
=O(n)+O(n-1)+O(n-2)+...+O(2)+O(1)
=O((n(n+1)/2)=O(n^2)

שזה סיבוכיות של (O(n^2 והוא עשה את זה ב (O(n log n

או שאני מתבלבל O_o' ?

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

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

it is a classic question that i was asked in several jobs interviews (about 6 years ago).
the best method to solve it is thinking about the sum set - perform an "integration" on the set and look at the set . the solution is immediate.

אתה יכול להרחיב טיפה?
למה אתה מתכוון כשאתה אומר לעשות "אינטגרציה"?

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

האם gilgr יכול להרחיב ולהסביר לנו איך אפשר לעשות את זה בסיבוכית של n?
אם אני מסתכלת על הבעייה בצורה תיאורתית,הרי מספר הווקטורים שאנחנו צריכים לבדוק הוא n בריבוע :
n וקטורים בגודל 1
n-1 וקטורים בגודל 2
n-2 וקטורים בגודל 3
...
...
...
1 וקטור בגודל n

סה"כ : n+....+3+2+1 =n*n/2

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

Assuming the sequence contanis only positive numbers it is no problem - we choose all the sequence.


The negative numbers are the ones we should look for..
As long as we met no negative number we can add the numbers to the vector and maintain its sum.
when we first meet a negative number we record the maximal sum and the vectors starting and ending indices (excluding that negative number - of course..).
yet- we continue summing the numbers - if the total sum in a certain index is negative we can stop and start a new vector.
the maximal vector is the one we recorded,

Notice that I went over the all sequence only once and mainitaing a constant number of integers :
Max sum recorded
Starting index recorded
Ending index recorded
Current Sum
Current starting index
Current ending index


Sorry - for not writing in hebrew - my os does not support it ,,,

עכשיו הבנתי, בעצם כל עוד הסכום ממקודם לא שלילי כדאי להוסיף אותו לסכום הבא!
איך לא חשבתי על זה בעצמי?!
תודה על הפיתרון היפה

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

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