מנסה למצוא אלוגריתם יעיל מ-n² לבעיה מסוימת - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

מנסה למצוא אלוגריתם יעיל מ-n² לבעיה מסוימת

gshhary

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

Recommended Posts

gshhary Zone Wannabe

gshhary

פורסם
פורסם

נתאר את בעיית מציאת "בור" במערך דו-ממדי ריבועי:

קלט: מערך דו-ממדי ריבועי בגודל nn המלא באפסים ואחדים בלבד.

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

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

פלט: האם קיים מספר k המהווה בור במערך? אם כן, יש להחזיר את ערכו אחרת יש להחזיר 1 -.

.

לדוגמא: במערך 3 A הוא "בור":

0 1 1 1 1 0

0 0 1 1 0 0

0 0 1 1 0 1

0 0 0 0 0 0

0 0 1 1 0 1

1 1 1 0 1 0

במערך B אין בור:

0 1 0 1 1 0

0 0 1 1 0 0

0 0 1 1 0 1

0 0 0 0 0 0

0 0 1 1 0 1

1 1 1 0 1 0

לצערי לא עולה בדעתי משהו שהוא טוב יותר מ-O(N²)

קישור לתוכן
שתף באתרים אחרים
  • תגובות 90
  • נוצר
  • תגובה אחרונה
שניצל Zone Master

שניצל

פורסם
פורסם

מישהו כבר נתקל בדיוק באותו התרגיל לפני כחודשיים:

http://hwzone.co.il/community/threads/534413-%D7%9E%D7%A0%D7%A1%D7%94-%D7%9C%D7%9E%D7%A6%D7%95%D7%90-%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D-%D7%99%D7%A2%D7%99%D7%9C-%D7%9C%D7%91%D7%A2%D7%99%D7%94-%D7%94%D7%91%D7%90%D7%94?highlight=%D7%91%D7%95%D7%A8#.UrbEMPQW38o

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

gshhary

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

מה נותן לי איבר מסויים ? לא הרבה נראה לי, בסה"כ מספר

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

ארכיון

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

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