אתגר בפסקל

[rr2u2]

אתגר בפסקל

אתגר משהו נחמד... אוקי זה הולך ככה: כתוב פרוצדורה nice_num המקבלת מספר ממשי כלשהו, ומדפיסה הודעה מתאימה אם המספר הוא מספר "נחמד". מספר "נחמד" הוא מספר ממשי גדול מ0- שהספרות אחרי הנקודה הן תמונת ראי לספרות שלפני הנקודה. דוגמא: 123.321 1.1 5072.2705 הם מספרים "נחמדים" 123.123 1.2 72.6 אינם כאלה.

 

[ilankt]

אתגר, או שיעורי בית?

 

[rr2u2]

אתגר אעלה את הפיתרון אם לא תצליחו

 

[אוֹריארד]

כיוונים...../images/Emo26.gif

בשלב ראשון הייתי מוצא דרך להפוך את המספר הממשי לשתי מחרוזות למשל... אחת בשביל החלק השלם, ואחת בשביל החלק שמימין לנקודה העשרונית. (אגב - למה מחרוזות ולא מספר שלם?... רמז: 123.0321 אינו מספר "נחמד") בשלב שני נבדוק האם שתי המחרוזות הן תמונת-ראי אחת של השניה...

 

[vinney]

למה לעבוד קשה למה?

תעשה השוואה של מספר יחידות מול מספר עשיריות, מספר עשרות מול מספר מאיות וכך הלאה, לולאה אחת על המספר ושתי השוואות, למה מחרוזות וכל הבלגן????

 

[VoodooKid]

אני מסכים

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

 

[אוֹריארד]

מה? מה? מה?...../images/Emo26.gif

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

 

[vinney]

לא במקום

 

[אוֹריארד]

פרס נובל...../images/Emo26.gif

סיבוכיות המקום של הפתרון שהבאתי הוא O של 1... אם יש לך פתרון עם סיבוכיות טובה יותר - אז יש כמה פרופ' בטכניון שכדאי שתדבר איתם...

 

[vinney]

זה לא נכון

סיבוכניות מקום שלך היא o(log n), זאת משום שככל שערך המספר יותר גדול, כך המחרוזת שמייצגת אותו תהיה יותר גדולה, כשקפיצה בתו לכל חזקה של 10 בערך. O של 1 זה במקרה ולכל מספר אתה משתמש בזכרון קבוע, וזה לא נכון, כי 10.01 לוקח 2 מחרוזות של 2 תוים ואילו 100.001 לוקח 2 מחרוזות של 3 תוים. בפתרון שלי אין לך משתני עזר (מעבר למוני הלולאה), לכן בפתרון שלי סיבוכיות מקום באמת O של 1, על חשבון הקריאות.

 

[אוֹריארד]

זה כן נכון...../images/Emo26.gif

מספר real הוא מספר בטווח הבא:

2.9 x 10^-39 ... 1.7 x 10^38​

כלומר לכל היותר מספר בן 38/39 ספרות. לכן אורכם של s1 ו-s2 בהכרח קטן מ-40. מכיוון שיש חסם עליון קבוע לזכרון בו אני משתמש - סיבוכיות המקום היא בהכרח O של 1...

 

[vinney]

אוח נו שוין

שיהיה, O של 1 בכל מקרה, זה פתרון א-לה VB (או JAVA, שיהיה) לא מתוכחם במיוחד

 

[אוֹריארד]

בהחלט מסכים...../images/Emo8.gif

 

[אוֹריארד]

בלגן??../images/Emo26.gif

זה אמור להיות משהו בסגנון:

Str(trunc(num), s1) Str(num-trunc(num), s2) Delete(s2, 1, 2) Reverse(s1) isNice := (s1 = s2)​

בלי לולאות... הרבה יותר קריא... בדיוק אותה סיבוכיות... אני מסכים שהדרך שלך 100% - אבל אני לא רואה את ה"בלגן" שדיברת עליו... (ואם תחשבו איך בדיוק נראית הלולאה שלך - תגלה שברמת הקוד הקריאוּת שלה אפילו פחות אינטואיטיבית... מה תנאי העצירה שלך למשל?...)

 

[vinney]

שכחתי שאתה חי בעולם הJAVA ../images/Emo13.gif

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

 

[אוֹריארד]

ומצד שני...../images/Emo26.gif

למתכנת שיתחזק את הקוד שלך יקח פי 8 זמן להבין מה הולך עם הקוד שלא הוא כתב...

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

 

[vinney]

בהחלט מסכים

 

[אוֹריארד]

../images/Emo45.gif

 

[גל ישראלי]

אפשר יהיה לקבל את הפתרון לתרגיל?

יש לי מחר מתכונת..וזה נראה תרגיל מאוד חביב

 

[ברנדל]

לא יודע פסקל..

אבל יש לזה ריח של steak (לא כזה שאוכלים). עד הנקודה כל ספרה דוחפים ל steak, מהנקודה שולפים מה steak ומשווים עם הספרה שיש אחרי הנקודה. FIFO