רוטר - שאלה נחמדה שהייתה לי במבחן היום

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

"שאלה נחמדה שהייתה לי במבחן היום"

גירסת הדפסה

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

אשכול מספר 14961

sHuMpI

17:04 17.09.08

שאלה נחמדה שהייתה לי במבחן היום

איך לבדוק מה הפולינדרום הכי גדול במילה מסויימת ב- O(N) כאשר N הוא אורך המילה...
לדוגמא- mississipi
אז הפולינדרום הוא ississi
בהצלחה לכולם...אם לא תצליחו אני אפרסם פיתרון...
אם לא מצליחים אז תפרסמו את הפתרון הכי קרוב שהצלחתם...או כיוון שלכם

הפותר נכונה יקבל ח"ח חח

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
לעשות רוורס למילה ולמצוא המחרוזת התואמת הכי ארוכה? :\|	DLN	17.09.08 18:38	1
זה לא פיתרון...זה כיוון	sHuMpI	17.09.08 22:56	7
הפותר נכונה יקבל וינר מבריק ונוצץ	Nesher	17.09.08 19:25	2
אממ זה אפשרי ביכלל בגודל של N? =/	ronen333	17.09.08 19:35	3
אפשרי	sHuMpI	17.09.08 22:54	5
שהפולינדרום יהיה כבר מורכב בסדר הנכון במילה (ל''ת)	MiP	17.09.08 21:58	4
אתה צריך למצוא את ההכי ארוכה...	sHuMpI	17.09.08 22:54	6
ד''א...חשבתי עכשיו על עוד פיתרון...שונה לגמרי	sHuMpI	17.09.08 22:57	8
טוב קיבלתי איזה הברקה	DLN	18.09.08 03:07	9
אין דבר שאי אפשר לעשות בלולאה רגילה...לא צריך	sHuMpI	18.09.08 13:49	12
אבל רקורסיה זה הכי אלגנטי	DLN	19.09.08 03:02	13
לדעתי זה אקספוננציאלי בכלל...ורקורסיה זה רחוק מלהיות	sHuMpI	19.09.08 11:14	14
תלוי מה ההגדרה שלך למשתלם	DLN	07.10.08 14:50	20
לא הבנתי, מה סיבוכיות הזמן והמקום או שאין הגבלה?	ldan192	18.09.08 12:39	10
סיבוכיות זמן o(N)	sHuMpI	18.09.08 13:48	11
התיאשתם? רמז...זה קשור בעצים	sHuMpI	20.09.08 21:58	15
ירד לי במיקוד	ronen333	21.09.08 09:53	16
חח...אני מקווה שאתה צוחק כי אתה לא צריך לדעת לתכנת	sHuMpI	21.09.08 17:08	17
לא ראית את כל הסמיילים הצוחקים? XD	ronen333	18.10.08 11:55	22
בינתיים לא הצלחתי בסיבוכיות ליניארית	warez_man	02.10.08 00:33	18
היית לי גם את השאלה הזאת במבחן :\| איפה אתה לומד?	By-king	07.10.08 10:59	19
אוניברסיטת חיפה	sHuMpI	17.10.08 15:44	21

DLN
חבר מתאריך 20.4.07
15884 הודעות

18:38 17.09.08

1. לעשות רוורס למילה ולמצוא המחרוזת התואמת הכי ארוכה? :|
בתגובה להודעה מספר 0

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

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

sHuMpI

22:56 17.09.08

7. זה לא פיתרון...זה כיוון
בתגובה להודעה מספר 1

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

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

Nesher

חבר מתאריך 2.7.02
2 הודעות, 24 פידבק

19:25 17.09.08

2. הפותר נכונה יקבל וינר מבריק ונוצץ
בתגובה להודעה מספר 0

בהצלחה

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

19:35 17.09.08

3. אממ זה אפשרי ביכלל בגודל של N? =/
בתגובה להודעה מספר 0

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

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

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

sHuMpI

22:54 17.09.08

5. אפשרי
בתגובה להודעה מספר 3

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

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

MiP
חבר מתאריך 24.5.05
782 הודעות

21:58 17.09.08

4. שהפולינדרום יהיה כבר מורכב בסדר הנכון במילה (ל''ת)
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 17.09.08 בשעה 22:01 בברכה, MiP

כלומר האם כל הווריאציות הבאות נכונות:
ississi
ssiss
sis
ss
ipi
issi
ssiss

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

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

sHuMpI

22:54 17.09.08

6. אתה צריך למצוא את ההכי ארוכה...
בתגובה להודעה מספר 4

פולינדרום זה גם אות אחת ד"א

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

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

sHuMpI

22:57 17.09.08

8. ד''א...חשבתי עכשיו על עוד פיתרון...שונה לגמרי
בתגובה להודעה מספר 0

ככה שיש כמה אפשרויות...תהיו יצירתיים

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

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

DLN
חבר מתאריך 20.4.07
15884 הודעות

03:07 18.09.08

9. טוב קיבלתי איזה הברקה
בתגובה להודעה מספר 0

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

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

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

sHuMpI

13:49 18.09.08

12. אין דבר שאי אפשר לעשות בלולאה רגילה...לא צריך
בתגובה להודעה מספר 9

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

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

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

DLN
חבר מתאריך 20.4.07
15884 הודעות

03:02 19.09.08

13. אבל רקורסיה זה הכי אלגנטי
בתגובה להודעה מספר 12

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

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

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

sHuMpI

11:14 19.09.08

14. לדעתי זה אקספוננציאלי בכלל...ורקורסיה זה רחוק מלהיות
בתגובה להודעה מספר 13

אלגנטי אין תוכנית שבה רקורסיה יותר משתלמת מלולאה רגילה

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

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

DLN
חבר מתאריך 20.4.07
15884 הודעות

14:50 07.10.08

20. תלוי מה ההגדרה שלך למשתלם
בתגובה להודעה מספר 14

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

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

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

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

12:39 18.09.08

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

בברכה,
עידן

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

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

sHuMpI

13:48 18.09.08

11. סיבוכיות זמן o(N)
בתגובה להודעה מספר 10

על סיבוכיות מקום תתפרע חח

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

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

sHuMpI

21:58 20.09.08

15. התיאשתם? רמז...זה קשור בעצים
בתגובה להודעה מספר 0

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

09:53 21.09.08

16. ירד לי במיקוד
בתגובה להודעה מספר 15

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

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

sHuMpI

17:08 21.09.08

17. חח...אני מקווה שאתה צוחק כי אתה לא צריך לדעת לתכנת
בתגובה להודעה מספר 16

עצים...רק לתת אלגוריתם

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

11:55 18.10.08

22. לא ראית את כל הסמיילים הצוחקים? XD
בתגובה להודעה מספר 17

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

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

warez_man

חבר מתאריך 1.8.02
3992 הודעות, 2 פידבק

00:33 02.10.08

18. בינתיים לא הצלחתי בסיבוכיות ליניארית
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 02.10.08 בשעה 00:35 בברכה, warez_man

בסיבוכיות ריבועית:
לולאה אחת עוברת על כל התווים מהתחלה ועד הסוף.
עוד לולאה שרצה מהסוף של המילה בודקת האם האות ה-I זהה לאות ה-N-I, אם כן היא ממשיכה ובודקת האם האות ה-I+1 זהה לאות ה-N-I-1 וכך הלאה. במידה ולא, הלולאה השנייה נשברת, ואנו חוזרים ללולאה הראשונה וממשיכים לסרוק את המילה מהתחלה עד לסוף.

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

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

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

By-king

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

10:59 07.10.08

19. היית לי גם את השאלה הזאת במבחן :| איפה אתה לומד?
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 07.10.08 בשעה 10:59 בברכה, By-king

לפני איזה שנתיים ככה :|

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

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

sHuMpI

15:44 17.10.08

21. אוניברסיטת חיפה
בתגובה להודעה מספר 19

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

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