עזרתכם בכתיבת מתודה ב-C#

[gshhar]

יש לי שיעורי בית ואלי לרשום מתודה יעילה שעושה את הדבר הבא:

כתבו שיטה שחתימה היא:

public static int subStrMaxC(String s, char c, int k)

המקבלת מחרוזת s, תו c ומספר שלם חיובי k, ומחזירה כמה תת- מחרוזות יש ב- s שמתחילות

ומסתיימות בתו c ויש בתוכן מקסימום k פעמים את התו .c

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

דוגמאות:

אם המחרוזת היא " s = "abcbcabcacab , התו ' c = 'c והמספר k=2 התוצאה היא 6. (התת-

מחרוזות הן " ("cbc", "cabc", "cac", "cbcabc", "cabcac", "cbcabcac

מה שכתבתי עד כה לא ממש הוביל אותי לפיתרון:

    public static int subStrMaxC(String s, char c, int k)
    {
      int count = 0;
      int totalCount = 0;


      for (int i = 0; i < s.Length; i++)
      {
        if (s[i] == c)
        {
          count++;
        }
      }


      return totalCount;


    }

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

[שניצל]

הכיוון שלך נכון, כי אכן ברגע שאתה יודע כמה פעמים התו c מופיע אז כבר לא צריך בכלל את המחרוזת.

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

[gshhar]

אוקיי אז זה פשוט יותר, אם אני רוצה למשל שהתו יופיע פעמיים אז אני סופר 4 פעמים עם הקצוות.

אבל משהו לא מסתדר לי פה באלוגריתם של זה ואשמח לעזרה

אגב האם גם בכדי שזה יהיה יעיל לעשות את זה בפעם אחת או לרוץ שוב ושוב על המחזורת.

[Gil28]

תכתוב לך מחרוזת כזאת על דף ותבחר פרמטרים (תו ומספר מופעים).

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

[שניצל]

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

[Gil28]

אתה צודק אבל זה עוזר להבין את העיקרון וככה קל יותר להסיק את הנוסחה.

[gshhar]

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

הבעיה שלי היא האלוגריתם שמחשב את זה

[Gil28]

בשביל זה תעשה את מה שאמרתי לך. קח מחרוזת באורך 6-8 בערך (אפילו רק של תו אחד, זה שאנחנו צריכים), ותתחיל לחשב ידנית עבור k=2.

ואז עבור k=3 ותראה אם אתה מצליח לגבש נוסחה. אח"כ תבדוק שהיא אכן נכונה.

[שניצל]

בדיוק. זה אפילו לא שאלה בתכנות, אלא מתמטיקה פשוטה (ליתר דיוק קומבינטוריקה).

[Gil28]

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

[שניצל]

ייתכן, אבל זו קומבינטוריקה מאוד בסיסית.

[gshhar]

אני אנסה את זה תודה רבה.

[gshhar]

אני רואה שאני יכול לעשות דבר כזה:

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

עכשיו אם K = 2 למשל אני יכול להשתמש במספר הפעמים שהתו הופיע פחות (k +1) וככה אני מקבל את מספר הפעמים וכמובן שאני צריך את מספר הפעמים המקסימלי אז במקרה של k =2 להשתמש בנוסא גם עם k = 1 ו-k = 0.

זה הכי יעיל שאפשר למצוא ?

[שניצל]

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

נ.ב. נשמח לדעת איזה ידע מתמטי יש לך (תיכון? בגרות? אוניברסיטה?)

[Rin]

תשמתש ב regex שמחזיר את כל תתי המילים שמתחילות באות המסוימת הזאת , ואז תחזיר את הגודל של אותו מערך\רשימה\whatever