Re: שאלה בנוגע לבדידה1

[wishcow]

השאלות האלה הן די קשות. 

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

אני אכתוב באנגלית כי אחרת זה יהיה בלאגן גמור:

a0(n) - legal strings beginning with 0

a1(n) - legal strings beginning with 1

a2(n) - legal strings beginning with 2

ברור שכל מחרוזת חוקית חייבת להתחיל ב 0 ב 1 או ב 2 ולכן נקבל:

a(n) = a0(n)+a1(n)+a2(n)

מה ניתן להגיד על הפונקציות הפשוטות יותר? אם מחרוזת מתחילה ב 0, אז ניתן להמשיך אותה בכל דרך, ולכן:

a0(n) = a(n-1)

כלומר מחרוזת חוקית שמתחילה ב 0 זה כמו לקחת מחרוזת חוקית קצרה בתו אחד ולחבר לה 0 בהתחלה.

כעת מה ניתן להגיד על מחרוזות שמתחילות ב 1 או ב 2? ניתן להתאים לכל מחרוזת שמתחילה ב 1 מחרוזת שמתחילה ב 2 ע"י החלפת כל הופעה של 1 בהופעה של 2. 

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

a1(n)=a2(n)

לכן יש לנו:

a(n) = a0(n)+a1(n)+a2(n) = a(n-1)+2a1(n)      *

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

a1(n) = a0(n-1) + a2(n-1)

אבל ניתן כעת להשתמש בזהויות שכבר הוכחנו:

a1(n) = a0(n-1) + a2(n-1) = a(n-2) + a1(n-1)

=> a1(n)-a1(n-1)=a(n-2)

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

*

נכונה לכל ערך

n

ובפרט לערך

n-1.

לאחר הצבה נקבל:

a(n-1)=a(n-2)+2a1(n-1)

כעת נחסר את שתי המשוואות:

a(n)-a(n-1) = a(n-1)-a(n-2)+2(a1(n)-a1(n-1)) = a(n-1)-a(n-2)+2a(n-2) = a(n-1)+a(n-2)

=> a(n) = 2a(n-1)+a(n-2)

בהצלחה

 

2009/4/24 מוריה תנעמי <bsg_...@walla.com>

היי סולי,

אנחנו ניגשות למועד ב' בבדידה 1 ויש לנו שאלה בנוגע לתרגיל 5 שאלה 6.

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

מקוות שזה לא טרחה עבורך.

נודה לך מאוד

 

 

השאלה:

יהי an מספר המילים באורך N על הא"ב {0,1,2} כך שלא מופיעים במילה לא רצף של שני 1'ים ולא רצף של  שני 2'ים.

הוכיחו ש

 a(n)=2a(n-1)+a(n-2)    n>=2

a(1)=3, a(2)=7

 

המון תודה

---

"גם כי אלך בגיא צלמוות לא אירא רע כי אתה עמדי"

---

Walla! Mail - Get your free unlimited mail today