רוטר - | שאלה | לא מצליח לפתור את התרגיל הבא

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"| שאלה | לא מצליח לפתור את התרגיל הבא"

גירסת הדפסה

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

אשכול מספר 15160

פנסלווניה
חבר מתאריך 3.11.04
1403 הודעות

14:50 23.01.09

| שאלה | לא מצליח לפתור את התרגיל הבא

http://www.ilshare.net/files/368984073.jpg
O(1) זה אומר לי שאסור לי להגדיר שום משתנה חדש ?!?
עכשיו פיתחתי את האלגוריתם לשאלה רק שאין לי מושג איך לממש אותו.
למשל לדוגמא הנ"ל
a = {3-4 , 4-3+4 , 12-4+3-4, 9-12+4-3+4 }
גם פיתחתי את הנוסחא עבור n זוגי ו n א"ז
כאשר b = a1;
עכשיו הנוסחאות הן:
עבור n זוגי
http://www.ilshare.net/files/601665584.gif
ועבור n א"ז
פשוט ה 1- רק בחזקת K
איך אני מממש את זה?

תודה לעוזרים

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
O(1) אומר שאתה צריך להשתמש במשתנים בדידים	Net_Boy	23.01.09 15:00	1
לא פיתחת כאלה נוסחאות אבל בקטנה ...	Deuce	23.01.09 16:14	2
אני לא מבין למה לפתח נוסחאות.	Heat_M	23.01.09 20:40	3
זה לא נכון .. תצייר לך.	Deuce	23.01.09 21:14	4
היי, זה משהו שממש ממש דומה (ויותר פשוט) מבמחן שהיה לי במבוא למדמ''ח	ldan192	23.01.09 21:32	5
מותר לי לעשות לולאה בתוך לולאה או שזה נקרא O(K^2) ??	פנסלווניה	24.01.09 18:32	6
כן זה יהיה O(n^2).	akoka	24.01.09 19:21	7
מכתב	DOWNTOWN	24.01.09 20:20	8
מה עם תודה? :\|	Deuce	26.01.09 01:48	9
תודה בשמו P:	Sn00py	26.01.09 10:11	10
תודה בשמו ,תודה רבה לך איש יקר ,אלוהים יהיה איתך	akoka	26.01.09 15:00	11

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

15:00 23.01.09

1. O(1) אומר שאתה צריך להשתמש במשתנים בדידים
בתגובה להודעה מספר 0

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

16:14 23.01.09

2. לא פיתחת כאלה נוסחאות אבל בקטנה ...
בתגובה להודעה מספר 0

שים לב אגב לדימיון הרב לסדרת פיבונצ'י, כך שאם ממש מתעקשים אפשר למצוא נוסחת איבר כללי ולפתור את זה ב-O(1) הן בזמן והן במקום.
בכל מקרה,
סיבוכיות זמן אתה יודע.
סיבוכיות מקום O של 1 אומר בסה"כ שאתה צריך להשתמש במספר קבוע (אפילו 100) של משתנים בזכרון - זה הכל.
ANYWAY:
אני לא אבדוק את הפיתוחים שלך אבל בסה"כ אתה עושה שם פלוס מינוס פלוס מינוס ורואה מה קורה.

B = A + A
B = A + A
B = A + A
--->
B - B = A - A
B - B + B = A + A

תקבל בסוף משהו בסגנון

B - ... + ... = A

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Heat_M

20:40 23.01.09

3. אני לא מבין למה לפתח נוסחאות.
בתגובה להודעה מספר 0

למה לא פשוט לרוץ במערך B ולעשות
a = b - a
ככה לרוץ על כל המערך B
ונגמר הסיפור... לא?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

21:14 23.01.09

4. זה לא נכון .. תצייר לך.
בתגובה להודעה מספר 3

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

21:32 23.01.09

5. היי, זה משהו שממש ממש דומה (ויותר פשוט) מבמחן שהיה לי במבוא למדמ''ח
בתגובה להודעה מספר 0

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

פנסלווניה
חבר מתאריך 3.11.04
1403 הודעות

18:32 24.01.09

6. מותר לי לעשות לולאה בתוך לולאה או שזה נקרא O(K^2) ??
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

akoka

19:21 24.01.09

7. כן זה יהיה O(n^2).
בתגובה להודעה מספר 6

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DOWNTOWN
חבר מתאריך 28.5.02
5388 הודעות

20:20 24.01.09

8. מכתב
בתגובה להודעה מספר 0

a[0] = b[0]
a[1] = b[1] - a[0]
a[2] = b[2] - a[1]
a[n] = b[n] - a[n-1]

ברקורסיה פשוטה
מימוש בסי שארפ

static int get(int[] b, int k)
{
if(k == 0)
return b[0];
return b[k] - get(b, k - 1);
}

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

01:48 26.01.09

9. מה עם תודה? :|
בתגובה להודעה מספר 0

פעם שנייה שאני עוזר לך ואין תגובה ...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Sn00py
חבר מתאריך 1.8.02
2954 הודעות

10:11 26.01.09

10. תודה בשמו P:
בתגובה להודעה מספר 9

\x6C\x65\x65\x74\x68\x61\x78\x30
\x72\x3A\x2D\x29
tresp4sser

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

akoka

15:00 26.01.09

11. תודה בשמו ,תודה רבה לך איש יקר ,אלוהים יהיה איתך
בתגובה להודעה מספר 9

צדיק ירא שמים.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד