מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תוצאה ב"לוח כפל"/שאלה

נתונה פעולת ה"כפל" $\displaystyle \cdot$ הנתונה ע"י "לוח הכפל" הבא:

דוגמה: אם "מכפילים" את $\displaystyle a$ ב$\displaystyle b$, מקבלים $\displaystyle a\cdot b=b$. אם "מכפילים" את $\displaystyle b$ ב$\displaystyle a$, מקבלים $\displaystyle b\cdot a=c$.

שימו לב: פעולת ה"כפל" $\displaystyle \cdot$ איננה אסוציטבית או קומוטטיבית: $\displaystyle \forall _{x,y,z}x\cdot (y\cdot z)=(x\cdot y)\cdot z$ אינה נכונה בהכרח. $\displaystyle \forall _{x,y}x\cdot y=y\cdot x$ אינה נכונה בהכרח.

נתונה מחרוזת שכל אחד מאיבריה הוא $\displaystyle a$,‏ $\displaystyle b$,‏ או $\displaystyle c$. אנא מצא האם אפשר לקבוע סוגריים כך שפעולת ה"כפל" $\displaystyle \cdot$ תניב על איברי המחרוזת את $\displaystyle a$. במידה שאפשר, אנא הדפס גם היכן לקבוע את הסוגריים.

דוגמה: נניח שהמחרוזת היא $\displaystyle bbbbac$. על תכניתך לזהות שאכן $\displaystyle \left(b\cdot (b\cdot b)\right)\cdot \left((b\cdot a)\cdot c\right)=a$. נניח שהמחרוזת היא $\displaystyle bab$. על תכניתך לזהות שאין אפשרות לקבל את $\displaystyle a$, שכן $\displaystyle \left(b\cdot a\right)\cdot b=c\neq a$, ו$\displaystyle b\cdot \left(a\cdot b\right)=b\neq a$.