|
|
صفحة: 199
כי ב . נתון עבור / ; -ו מסוימים ^[/][/] / בעל ערך , FALSE כלומר לא קייס מסלול / -מ . / -ל שאינו עובר דרך קדקוד כלשהו שמספרו גבוה . # -מ אם קיים מסלול ? X / -מ העובר דרך הקדקוד , K + 1 כלומר קיים מסלול / -מ ( K + 1 ) -ל ( K + 1 ) -ומ , '; -ל ומסלולים אלו אינם עוברים דרך הקדקודים שמספרם גבוה , K-n אזי מה יהיה ערכו של 1 P [!][/] K + i ג . האס /'„ [/][/] שווה למטריצת הסמיכות שמייצגת את הגרף הנתון 1 G ד . כתבו אלגוריתם בעל סיבוביות זמן ריצה 0 ([ V ] ) לקבלת מטריצת המסלולים . ה . כתבו פונקציה / שגרה בשפה עילית לחישוב מטריצת המסלולים , כך שסיבוכיות זמן הריצה של השגרה היא : ([\ ' 1 ) ל . < שאלה 4 . 29 במדינת קום יש N ערים . קיימת מערכת כבישים ישירים המחברת בין הערים . אורכו של כל כביש ישיר הוא . 1 מערכת הכבישים תיקרא זוג-פרד אס קיימות במערכת הכבישים שתי ערים המחוברות על-ידי מסלול באורך זוגי וגם על-ידי מסלול באורך אי-זוגי . כתבו תכנית אשר תקלוט מערכת כבישים ותחזיר : א . את המילה "כן '' אס מערכת הכבישים היא מסוג זוג-פרד . אחרת , תודפס המילה . "לא" ב . אם התשובה לסעיף א' שלילית , אזי התכנית תמצא תת-קבוצה X של מספר מקסימלי של ערים המקיימת את התנאי שלהלן ו בין כל שתי ערים , # -ב קיים מסלול שאורכו זוגי . מבנה הקלט בשורה הראשונה - N מספר הערים ( N < 300 ) לאחר מכן שורות המכילות זוגות של מספרים שלמים i , j המסמנת שיש כביש ישיר בין עיר < לבין עיר , / לדוגמה , עבור הקלט הזה
|
|