שאלה במלכוד (שפת C)

[DannyBoyo]

שאלה במלכוד (שפת C)

לפניכם השאלה. לפי ההוראות (כפי שהבנתי) יש לקלוט מספר בינארי בתוך מערך ככה שהMSB יהיה 0 אפס והLSB יהיה בתא length-1. כמו כן יש לקרוא מיד לאחר מכן לפונקציה הרקורסיבית binarr2int מבלי לעשות כל שינוי במערך. לפי הנתונים האלה, ולפי הכותרת של הפונקציה שניתנה, אני מוצא את עצמי במלכוד, מפני שהדבר היחידי שאני יכול לעשות הוא לכתוב פונקציה שמחשבת את הערך העשרוני של המספר הבינארי *ההפוך* מהמספר שנקלט (כלומר מספר שה MSB שלו בתא length-1 ו-LSB בתא 0). מישהו יכול להציע פתרון, או להגיב אם יש בכלל כזה?

 

[אלדד28]

בוודאי שזה אפשרי

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

 

[DannyBoyo]

אני מבין למה אתה מתכוון, אבל---

הבעיה היא שיש לי רק אינדיקטור אחד והוא length. אני בעצם בפונקציה עשיתי ככה

if(length>0) return arr[length-1]*pow(2,length-1)+binarr2int(arr,length-1); else return 0;​

הבעיה היא שאני לא מוצא שום דרך לעשות את הדבר הזה בסדר הפוך, כלומר מ-0 עד length. עזרה בבקשה

 

[אלדד28]

אבל זה בדיוק מה שאתה צריך,

נגיד שיש לך 5 ביטים - 10110. עכשיו אתה בדרך אחורה, ואתה בביט השלישי. אתה יודע שאתה בביט השלישי, כי ה - length שלך הוא בעצם 3 (הפונקציה הנוכחית צריכה לחשב את 110 בלבד...). שניה קודם קראת לפונקציה שחישבה עבורך את 10, וקיבלת ממנה את התוצאה (שזה 2). עכשיו יש לפניך את הביט השלישי (1) ואת האורך (3) ולתוצאה מקודם (2) אתה צריך להוסיף 1 כפול 2 בחזקת 2 (4), סה"כ = 6, שזה באמת 110; זה הערך שתחזיר מהפונקציה, וזה הערך שיגיע לפונקציה שתצטרך לחשב את 0110 (וכן הלאה).

 

[DannyBoyo]

בעיה:

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

 

[DannyBoyo]

תיקון: ערך=משתנה; שערך=משתנה ^_^

 

[אלדד28]

ברור שיש לך.

2 זה 3-1. זה האורך של המחרוזת שלך פחות 1. וגם מה שאייל הציע, אגב, יכול לעזור לך. הוא תקף את זה בכיוון הפוך.

 

[eyalbd]

עוד רמז

תנסה לנסח ברקורסיה את הביטוי הבא:

value = a[4] + 2 * (a[3] + 2 * (a[2] + 2 * (a[1] + 2 * a[0])));​

 

[DannyBoyo]

המממ אני חושב שזה הולך ככה:

if(length==1) return 2*arr[length-1]; else return arr[length-1]+2*binarr2int(arr,length-1);​

אבל לצערי הרב אני לא מבין איך זה מתקשר לתוכנית ^_^ מבקש הנחיה נוספת, אייל ^_^;

 

[eyalbd]

תיקון

קרוב מאד רק שתנאי העצירה שיהיה ב 0 ולא 1. יותר טבעי (ובקוד שאתה נתת יותר נכון) לעצור באורך מערך 0 מאשר ב 1. בפתרון שלך תוריד את ההכפלה ב 2 ואז תקבל תוצאה נכונה.

if(length==0) return 0; /*else*/ return arr[length-1]+2 * binarr2int(arr, length-1);​

 

[DannyBoyo]

כן, אוקי.. טעות שלי. אבל---

---עדיין לא הבנתי למה זה עובד כלומר, אפשר איזה הסבר מתמטי? (הפתרון שלך מזכיר מאוד את נושא האינדוקציות).

 

[eyalbd]

אין הרבה מה להסביר

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

 

[DannyBoyo]

כן עכשיו אני רואה את זה:

זה בעצם הנוסחה לחישוב הבינארי, לאחר כינוס איברים.

a[4]+2^1*a[3]+2^2*a[2]+2^3*a[1]+2^4*a[0]​

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

 

[DannyBoyo]

כן עכשיו אני רואה את זה:

זה בעצם הנוסחה לחישוב הבינארי, לאחר כינוס איברים.

a[4]+2^1*a[3]+2^2*a[2]+2^3*a[1]+2^4*a[0]​

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