רוטר - מחפש אלגוריתם לתרגיל על מערך דו מימדי בשפת C

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"מחפש אלגוריתם לתרגיל על מערך דו מימדי בשפת C"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15938	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15938

tomash

18:15 09.06.10

מחפש אלגוריתם לתרגיל על מערך דו מימדי בשפת C

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

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
מבלי להתחכם, האלגוריתם הפרמטיבי ביותר	ldan192	10.06.10 21:37	1
לא הבנתי את הפתרון שלך	ronen333	10.06.10 23:11	2
גם אני לא הבנתי ממש את הפתרון...	tomash	12.06.10 10:24	5
אוקיי, במילים אחרות אתה בוחר כל קומבינציה אפשרית	ldan192	12.06.10 13:27	6
פתרון (סיבוכיות נוראית)	TuShY	11.06.10 00:05	3
העברתי את ההצעה לחבר שלי, והוא אמר שזה גם מה שעלה לו	tomash	12.06.10 10:23	4
אמממ אני דווקא הייתי חושב לכיוון UNION FIND...	פאביו ג'וניור	12.06.10 16:07	7
רעיון נחמד, השאלה מה עושים אח''כ.	Deuce	12.06.10 17:55	8

ldan192
חבר מתאריך 14.9.08
95119 הודעות

21:37 10.06.10

1. מבלי להתחכם, האלגוריתם הפרמטיבי ביותר
בתגובה להודעה מספר 0

של לרוץ עם i, j על המערך ולכן מ-i, j לרוץ עם a, b עד m, n על הקו האנכי-אופקי שמאליים-עליוניים לקבלת חצי מסגרת שמאלית עליונה, ובמקביל עם c, d מ-m, n ועד i, j לרוץ מהכיוון השני על חצי המסגרת הימנית התחתונה (לוודא חוקיות של מסגרת של 1-ם) תתן בקלות את התשובה.

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

23:11 10.06.10

2. לא הבנתי את הפתרון שלך
בתגובה להודעה מספר 1

ניסתי והצלחתי לפתור את זה אבל בסיבוכיות כל כך מגעילה שאני מתבייש להציג את הפתרון.
ואשמח אם תרחיב על הייצוג עם העץ.

שאלה מעניינת..

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

tomash

10:24 12.06.10

5. גם אני לא הבנתי ממש את הפתרון...
בתגובה להודעה מספר 1

אשמח להסבר ברור יותר...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

13:27 12.06.10

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

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

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

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TuShY
חבר מתאריך 20.1.07
196 הודעות

00:05 11.06.10

3. פתרון (סיבוכיות נוראית)
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 11.06.10 בשעה 00:19 בברכה, TuShY

עוברים על כל תא במערך - אם יש 0 ממשיכים, אם יש 1 בתא אז עומדים על התא הזה ומשתמשים באינדקס Z שיבדוק צלעות של כל המלבנים שמתחילים בנקודה הזאת.
מתחילים עם אורך מלבן 1 ורוחב 1 ובודקים אם זה מלבן,אם כן תדפיס את פרטי המלבן ואז עוברים למלבן אורך 2 רוחב 1 ושוב בודקים ואז מבצעים SWAP, בודקים שוב ובסוף מגיעים לריבוע 2X2 ושוב בודקים וממשיכים עד שמגיעים לגודל המקסימלי שהמלבן יכול להיות מהתא הזה! לאחר שסיימת לבדוק את כל האפשרויות של המלבנים שיכולים להתחיל מהתא הזה עבור לתא הבאה וכו...
בעצם זה 4 לולאות שבודקות כל צלע של במלבן, עם יש צלע לא תקין אז לא תדפיס את פרטי המלבן הזה כמובן.
פתרון נוראי אבל זה הדבר היחיד שעלה לי לראש...

ד"א: כתבתי את זה בC אם אתה רוצה שאשלח לך, תיצור איתי קשר בפרטי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

tomash

10:23 12.06.10

4. העברתי את ההצעה לחבר שלי, והוא אמר שזה גם מה שעלה לו
בתגובה להודעה מספר 3

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

פאביו ג'וניור

16:07 12.06.10

7. אמממ אני דווקא הייתי חושב לכיוון UNION FIND...
בתגובה להודעה מספר 0

מה ז"א?
בהתחלה כל "1" כזה הוא סט משל עצמו... ואתה מאחד אותו עם כל האחדים שלידו לאט לאט... ושומר ריבועים בצד..
זה הכיוון שאני חושב עליו... (פשוט אני עשיתי משהו דומה אבל לא זהה...)
פיתרון מפורש עוד אין לי אבל תחשוב לכיוון הזה ותיראה לאן אתה מגיע..

אם תמשש את זה עם עץ הפוך ועם היעול של FIND רקורסיבי שגורם שכולם יציביעו לאב זה הופך להיות מאד יעיל...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

17:55 12.06.10

8. רעיון נחמד, השאלה מה עושים אח''כ.
בתגובה להודעה מספר 7

לבסוף אתה מקבל קבוצות של אחדות כאשר בהנתן קבוצה - x,y משבצות שייכות לקבוצה אמ"ם יש מסלול מ-x ל-y כאשר אפשר כל פעם להתקדם ממשבצת דרך משבצת אחדות.

בירוק מסומן המסלול, במקרה הזה הקבוצה תכיל בפרט את כל המשבצות דרכן עובר המסלול הירוק.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד