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

אני צריך לבנות פונקציה שתמצא רק את קבוצת המספרים הנמצאים במקומות עוקבים.
דוגמא:
המחרוזת היא:
"ב 4 מהדקים 44 שח"
אני צריך לבנות פונקציה שהפלט שלה עבור מחרוזת זו היא 44.

במחרוזת:
"מהדק 11 שח", אני צריך לקבל 11.

במחרוזת:
"בגד + 12 כפתורים 34 שח", אני צריך לקבל 1234
וכו'...

אנא - מימוש ב- VB
תודה

BigAssWeb
B. ENG

BigAssWeb
B. ENG

או בקיצור: לא הבנתי באופן כללי

אחזור על הבעיה כדי לוודא שהבנתיה היטב.
יש לנו מחרוזת באורך N שיש בה :
1. מספר בודד שמוקף בתווים אחרים. (לא חייב להיות)
2. קבוצה של 2 או יותר מספרים רצופים (לפחות קבוצה אחת כזאת)
אתה רוצה שרשור של כל המספרים מקבוצה 2.

הסיבוכיות של הבעיה צריכה להיות N,כלומר מעבר אחד בלבד על המחרוזת.
אז מה צריך לעשות :

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

תתחיל מזה,ולא תתקשה לממש גם בVB.

הפתרון שלך נכון באופן עקרוני, הבעיה הקטנה היא ש-VB אין מצביעים...
הדרך לקבל תו ממחרוזת S במיקום N היא השימוש בפונקציה Mid כך:

C = Mid(S, N, 1)

ואנחנו עובדים בתקווה שהסיבוכיות של Mid היא O(1)o, מה שהגיוני
אבל אף-אחד לא מבטיח לנו...

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

זה לא כזה טריוויאלי, למרות שזה נראה ככה

BigAssWeb
B. ENG

למה אם זה הקלט:
"בגד + 12 כפתורים 34 שח"
אז הפלט הוא: 1234

ואם זה הקלט:
"אבג12דהו3456"
אז הפלט הוא: 3456
ולא: 123456?

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

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

הרצף הארוך ביותר אורכו בדיוק 10 ספרות וזה עדיין בתחום ה (O(1 מקום

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