חייב חומר על יעילות - עמוד 2 - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

חייב חומר על יעילות

Yehudaa

נוצר על ידי Yehudaa
ב תכנות

Recommended Posts

שניצל Zone Master

שניצל

פורסם
פורסם

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

ה-k בדוגמה הוא 3 (הספירה מתחילה מימין, לא משמאל... זה כנראה מה שבלבל אותך).

אלכסון מוכלל זה אוסף התאים [mat[k][(k+c)%n כאשר c הוא קבוע כלשהו.

קישור לתוכן
שתף באתרים אחרים
ofir_yair Zone Wannabe

ofir_yair

פורסם
פורסם
נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0,

ובעמודה ה- k -ית כל הערכים הם 1

הרי על פי ההגדרה שנתת בגוף השאלה לבור, השורה ה-k היא 0 והעמודה ה-k היא 1, (מלבד k,k) ובמטריצה A הבור הוא ב-k=3. והצומת בין השורה לעמודת הבור (מה שכינית בתור בור) באינדקס 3,3.

ועוד משהו של לא הבנתי איך אני אשמור את כל [k][k]

איפה ראית שאתה צריך לשמור אותם?

גם באלגוריתם שאני הצעתי וגם בזה של שניצל, צריך לשמור מערך חד ממדי באורך k, כדי לשמור חשודים בתור בור, ולצמצם את רשימת החשודים לחשוד יחיד (צמצום החשודים היא הנקודה בה שני האלגוריתמים נבדלים).

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

קישור לתוכן
שתף באתרים אחרים
Jaman Zone Freak

Jaman

פורסם
פורסם

udii, ע"פ הניסוח של השאלה שלך הבורות יכולים ליהיות רק על האלכסון הראשי ("נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0, ובעמודה ה- k -ית כל הערכים הם 1 (חוץ מהאיבר [k][k] עצמו שהוא 0).")

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

[עריכה]

טעות שלי, תשכחו ממה שאמרתי.

קישור לתוכן
שתף באתרים אחרים
Yehudaa Zone Master

Yehudaa

פורסם
  • מחבר
פורסם

אני לא מבין את השאלה (חשד לחוסר דיוק בניסוח השאלה )

נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0,

ובעמודה ה- k -ית כל הערכים הם 1 (חוץ מהאיבר [k][k] עצמו שהוא 0).

פלט: האם קיים מספר k המהווה בור במערך? אם כן, הדפס את ערכו.

לדוגמא: במערך במערך B אין בור במערך A יש בור

A B

0 1 1 0 1 0 1 0 0 0 1 0

0 0 1 1 0 1 1 1 1 0 0 1

1 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1

0 0 1 1 0 1 1 0 1 0 1 0

1 1 1 0 1 0 0 1 0 0 0 1

נאמר [k][k] צריך להיות 0

תביטו על מערך A השורה של הבור היא 3 והעמודה היא 2 ( מתחילים מ 0 )

לכן במקרה שלנו הנקודה K,K היא 3,2 לפי ניסוח השאלה היית מצפה שהנקודה תיהיה 3,3 :nixweiss:

איזה מצחיק אני ;D הקופי פסט יצא הפוך למעשה הנקודה היא באמת 3,3

קישור לתוכן
שתף באתרים אחרים
Jaman Zone Freak

Jaman

פורסם
פורסם

קראת את הת'רד לפני שהגבת?

הפתרון שנתת הוא הפתרון הפשוט ולא יעיל. אנחנו דיברנו על פתרון יעיל ב-(O(n.

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

קישור לתוכן
שתף באתרים אחרים
Jaman Zone Freak

Jaman

פורסם
פורסם

כמו שאמרתי, המספור מתחיל מימין ולא משמאל.

העמודה שמלאה ב-1 הוא עמודה 3, לא 2.

עריכה: גרר, די לערוך ולתקן את עצמכם אחרי שאני כבר מספיק להגיב להודעה הקודמת! :)

התחלתי לערוך לפני ששלחת את ההודעה שלך, לא הייתי עורך אם הייתי רואה את התגובה שלך.

קישור לתוכן
שתף באתרים אחרים
ofir_yair Zone Wannabe

ofir_yair

פורסם
פורסם

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

לכן החלטתי להשקיע מעט ולהסביר את זה במצגת. קבלו:

אם ישנה בעיה בתאימות התצוגה תודיעו לי כדי שאוכל לתקן (2 גרסאות, אחת לאופיס 2007 ואחת ל-2003).

[attachment deleted by admin]

קישור לתוכן
שתף באתרים אחרים

ארכיון

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

עבור לרשימת הדיונים
×
  • צור חדש...