עבור לתוכן

מטריצת שכנויות בשפת C

Featured Replies

פורסם

אני צריך לבנות עץ מכוון בעל N צמתים שיהיה מיוצג על ידי מטריצת שכנויות בגודל N*N הבעיה של היא שאני צריך לקבל מהמשתמש שני צמתים ולהחזיר TRUE אם קיימת קשת מכוונת בניהם וFALSE אם לא קיימת(ממש כמו עץ בינארי רק שמיוצג על ידי מטריצת שכנויות) ואני לא מוצא דרך לעשות חיפוש כזה באופן יעיל.

יש רעיונות?

תודה

פורסם

מה מייצג איבר במטריצה? כלומר, מה המשמעות של הערך במקום i,j?

פורסם
  • מחבר

1 ו0 כאשר 1 מייצג שקיים לו בן ו0 שלא קיים

כאשר המשתמש מכניס את i=האבא ו j=הבן

ואני צריך להחזיר אם יש בין האבא לבן קשת מכוונת זאת אמרת אם הוא באמת אבא שלו

פורסם
  • מחבר

עלי לכתוב פונקציה בשם path המקבלת כפרמטר מטריצת שכנויות A ואינדקסים של שני צמתים u ו v ומחזירה TRUE אם ורק אם קייםמסלול מכוון(לפי כיווני החצים) מצומת u לצומת v ,בעץ המיוצג על ידי מטריצה A. אחרת היא מחזירה FALSE

פורסם

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

תבדיל אגב בין בן (child) לצאצא (descendent). בן זה אומר בן ישיר (כלומר יש קשת מכוונת ביניהם), צאצא זה אומר עקיף (כלומר יש מסלול מכוון ביניהם). בדיוק כמו שאתה צאצא של סבא שלך, ולא בן שלו :) . בכיוון ההפוך אגב מבדילים בין "אב" (parent) ל"אב קדמון" (ancestor).

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

אם זה היה סתם גרף מכוון ולא עץ, אז זה גם היה אפשרי באמעות פונקציית סריקה פשוטה (DFS או BFS).

פורסם
  • מחבר

הבעיה שאם מדובר בN ממש גדול ואם יש לצאצא יותר מאבא אחד...

רקורסיה יכולה לעבוד פה באופן טוב או שהזמן ריצה יהיה גדול מדי?

פורסם

לאף צומת בעץ לא יכול להיות יותר מאבא אחד, כי אז זה לא היה עץ. יכול להיות שזה סתם גרף כללי, ואז כמו שאמרתי צריך לעבוד אחרת (DFS). בכל מקרה הסיבוכיות תהיה לא יותר מ-(O(N^2. אם לכל צומת בעץ היה נתון מי האבא שלו (במקום מטריצה השכנויות) אז הסיבוכיות הייתה (O(N.

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

פורסם
  • מחבר

אוקיי...תודה.

פורסם
  • מחבר

יש לי עוד שאלה.

איך אני מקבל קלט מהמשתמש לתוך המטריצה אבל שלא יהיה כל פעם להכניס משתנה אחד אלה שיהיה הכל ביחד? למשל:

{{0,1,1,1,0},{0,0,1,1,0},{0,0,0,0,0}}

כרגע אני פשוט מבקש ממנו להכניס מספר ללחוץ אנטר ולהכניס עוד אחד וכו...

פורסם

תקרא את מחרוזת הקלט בשלמותה ואז תפרסר (parse) אותה בעצמך (באמצעות חיפוש תווים ו/או ביטויים רגולרים).

פורסם
  • מחבר

אין אופציה לעשות שהמערך שווה ל scanf ואז המשתמש ישר מכניס את הערכים?

פורסם

לא. scanf יודעת לקרוא רק מחרוזות ומשתנים פרימיטיביים (int,double וכד').

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

פורסם
  • מחבר

הבנתי...תודה

נראה לי שאני יעשה לולאה ואתן למשתמש למלא את המערכים עם scanf ככה גם אני יכול לשלוט בכמות משתנים שהוא מכניס

למרות שבמערכים ממש גדולים זה לא נוח.

תודה על ההסבר.

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים