עזרה דחופה בשערים לוגיים!!

[yosefar]

עזרה דחופה בשערים לוגיים!!

שלום לכולם, יש לי שני תרגילים בשערים לוגיים שאני לא מצליח לפתור, כי אני חושב שאני מפספס את דרך החשיבה. אודה מאוד מאוד אם תעזרו לי! 1. בנה מעגל המקבל כקלט 8 כניסות, כל כניסה ברוחב 3 סיביות. המעגל יוציא כפלט את האיבר השני בגודלו. 2. בנה מעגל המקבל כקלט 8 סיביות ומוציא כפלט את מספר ההתחלפויו בין 0 ו-1 ברצף הארוך ביותר של 01-ים. במילים אחרות: בקטע באורך מקסימלי שבו מופיעים 0 ו-1 שמתחלפים זה עם זה (ללא מופע של שני 0 או 1 צמודים) מתקבל מספר ההחלפותץ למשל עבור הקלט 11010100 הפלט יהיה 5. תודה מראש...

 

[vinney]

ומה עשית עד עכשיו?

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

 

[yosefar]

אכן..

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

 

[ron369]

האם הוא מוציא רק את המקסימום,

או גם את המינימום?

 

[yosefar]

רק מקסימום...אבל לא בעיה לבנות רכיב

שמוציא מינימום.

 

[yuvalmadar]

אוקיי

אז, משני אלה תוכל לבנות בקלות שער שממיין שני איברים? מחזיר את הגדול מביניהם מיציאה אחת, ואת הקטן מהשנייה? אז תשתמש בשניים כאלה ותמצא את המספר הגדול ביותר מבין השלושה. (תשווה את השניים הראשונים + תשוואה את השלישי ואת זה שיצא מהMAX) ועכשיו, אתה רק צריך למצוא את הגדול ביותר מבין 2 אלה שנותרו. (אלה שיצאו מיציאות הMIN) אגב, ניתן להרחיב בקלות את הרעיון הזה למיון של n מספרים כלשהם עם (O(n^2 שערים לוגיים. 1. מצא את הגדול ביותר, ושים אותו בתא הראשון. 2. מיין את כל המספרים שנפלטו מיציאות הMIN בשלב 1. (רקורסיבית) כיוון ששלב 1 דורש n שערים (Max בין 1 ל2, בין הגדול מביניהם ו3, הגדול ו4 וכו') מספר השערים הכולל הוא (n+n-1+...+1= O(n^2.

 

[yosefar]

תודה רבה!!

אמנם בשאלה הקלט הוא 8 איברים, אבל הרעיון ברור. שוב תודה!

 

[yuvalmadar]

בבקשה ../images/Emo13.gif