| כותב |
|
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 November 2007 בשעה 20:10 | | IP רשוּם
|
|
|
|
הצלחתי לפתור רק בסיבוכיות של n בריבוע וצריך לפתור בסיבוכיות של n
נתאר את בעיית מציאת "בור" במערך דו-ממדי ריבועי:
קלט: מערך דו-ממדי ריבועי בגודל n´n המלא באפסים ואחדים בלבד.
נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0, ובעמודה ה- k -ית כל הערכים הם 1 (חוץ מהאיבר [k][k] עצמו שהוא 0).
פלט: האם קיים מספר k המהווה בור במערך? אם כן, הדפס את ערכו.
לדוגמא: במערך A 3 הוא "בור", ובמערך B אין בור.
|
|
|
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 |
כתבו שיטה יעילה הפותרת את הבעיה.
חתימת השיטה תהיה:
public static int isSink (int [][] mat)
השיטה תחזיר את המספר k המהווה בור במערך, אם קיים אחד כזה, ו- -1 אם לא קיים בור במערך.
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 15:47 | | IP רשוּם
|
|
|
|
אני מנסה ומנסה ולא מצליח.
מישהו מכיר פורום שבו אוכל לקבל עזרה לגבי בניית אלוגריתם כזה?
תודה!
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 16:39 | | IP רשוּם
|
|
|
|
הממ...הפורום הזה (:
אגב, למה בשניהם 0 הוא לא בור ?
צריך להגזיר מהו n, אם הוא מספר האיברים בשורה או מספר האיברים במטריצה.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 16:51 | | IP רשוּם
|
|
|
|
תודה על התגובה.
רק ב-A יש בור ב-B אין בור(הבור ב-A הוא[3][3]).כדי ש-[0][0] יהיה בור צריך שכל המספרים בשורה 0 יהיו 0 וכל המספרים בתור 0 יהיו 1 חוץ מ-[0][0] שצריך להיות ס.
n הוא הגודל פה הוא שווה ל-6-->לכן יש במטריצה 36 ריבועים
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 17:31 | | IP רשוּם
|
|
|
|
אה אוקיי, הבנתי, לא קראתי נכון את ההגדרה של בור.
שנייה, אני אחשוב על זה.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 18:26 | | IP רשוּם
|
|
|
|
הממ...כתבתי ב-c# אבל הדמיון מאוד מאוד גדול.
קוד:
private static int isSink(int[,] arr)
{
int n = arr.GetLength(0);
bool[ ] check = new bool[n];
for ( int i = 0 ; i < n ; i++ )
check[i] = true;
for ( int i = 0 ; i < n ; i++ )
if ( check[i] )
{
for ( int j = 0 ; j < n ; j++ )
{
if ( arr[i, j] == 0 )
check[j] = false;
else
{
check[i] = false;
break;
}
if ( i == j )
continue;
if ( arr[j, i] == 1 )
check[j] = false;
else
{
check[i] = false;
break;
}
}
if ( check[i] )
return i;
}
return -1;
} |
|
|
נכון זה נראה, לולאה דו מימדית שבסה"כ מבצעת n^2 פעולות.
אבל שם לב שכל פעם שאנחנו לא מבטלים את האינדקס של i אז זה מבטל את
האינדקס של j, ולהפך, למעט מאקסימום פעם אחת, ולכן אנחנו מבטלים n-1
פעמים n צעדים ונשאר לנו n בדיקות.
סה"כ יהיו לנו N בדיקות ולא n^2.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 18:46 | | IP רשוּם
|
|
|
|
שושן תודה על העזרה!
תרגמתי את זה ל-java והרצתי את מערך A והשיטה שכתבת מחזירה 1- במקום 3 ניסיתי על כל מיני מערכים אחר ותמיד השיטה מחזירה 1- אז לצערי היא לא עונה על השאלה.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 20:04 | | IP רשוּם
|
|
|
|
אצלי זה עבר, כנראה לא תירגממת טוב או שלא העתקת את המערך טוב.
אתה מוזמן לדבג
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 20:34 | | IP רשוּם
|
|
|
|
דיבגתי את הקוד בעזרת מהדר והוא עבר קומפילציה אבל שוב הבעיה שהתשובה
שהוא נותן לא נכונה.
קוד:
public static int isSink(int[][] arr)
{
int n = arr[0].length;
boolean[ ] check = new boolean[n];
for ( int i = 0 ; i < n ; i++ )
check[i] = true;
for ( int i = 0 ; i < n ; i++ )
if ( check[i] )
{
for ( int j = 0 ; j < n ; j++ )
{
if ( arr[i][j] == 0 )
check[j] = false;
else
{
check[i] = false;
break;
}
if ( i == j )
continue;
if ( arr[j][i] == 1 )
check[j] = false;
else
{
check[i] = false;
break;
}
}
if ( check[i] )
return i;
}
return -1;
} |
|
|
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 20:43 | | IP רשוּם
|
|
|
|
יש בעיה בהעתקה לאתר! העתקתי את הקוד מקובץ ה-java לאחר שנוצר ועבר קומפילציה לפה ולאחר ששלחתי אני שם לב שמשום מה הוא השמיט את הסימן של המערך.לדוגמה
(if(check צריך להיות if ובסוגריים [check[i
יש דרך להעתיק לפה בצורה תקינה?בכל מקרה זה הקוד שתרגמתי ל-java(חוץ מהבעיות שהאתר משום מה השמיט בשליחה)והוא עבר קומפילציה .אתה יכול לראות שהקוד כמו שלך בול רק ששיניתי את הדברים ל-java למשל במקום bool שכתבת כתבתי boolean ב-java
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 21:03 | | IP רשוּם
|
|
|
|
כן, תשלח וכשאתה שולח תוריד את הבחירה מ-"אפשר שימוש ב- קודי הפורום בכדי
לכתוב את הודעותיך"
אתה מוזמן גם עם debugger לעבור שורה אחרי שורה ולראות מה הבעיה.
אתה יודע,
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 21:15 | | IP רשוּם
|
|
|
|
עברתי עם debugger והכל תקין רק שהשיטה לא עושה את מה שהיא צריכה לעשות לפי התרגיל.
public static int isSink(int[][] arr)
{
int n = arr[0].length;
boolean[ ] check = new boolean[n];
for ( int i = 0 ; i < n ; i++ )
check[i] = true;
for ( int i = 0 ; i < n ; i++ )
if ( check[i] )
{
for ( int j = 0 ; j < n ; j++ )
{
if ( arr[i][ j] == 0 )
check[j] = false;
else
{
check[i] = false;
break;
}
if ( i == j )
continue;
if ( arr[j][ i] == 1 )
check[j] = false;
else
{
check[i] = false;
break;
}
}
if ( check[i] )
return i;
}
return -1;
}
}
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 21:27 | | IP רשוּם
|
|
|
|
אה אוקיי, סורי, טעות לוגית קטנה שלי, שמנעה לגמרי להאלגוריתם לעבוד.
תשנה את check[j] = false; הראשון בלבד ל:
קוד:
if ( i != j )
check[j] = false; |
|
|
my bad
הרעיון שם היה לפסול שורה אחרת, לא את הנוכחית.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
java
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 13 November 2007 בשעה 21:58 | | IP רשוּם
|
|
|
|
פשש כל הכבוד!תודה רבה!זה עובד רק אני מקווה שזה סיבוכיות של N ולא N בריבוע.אני אשב לנסות להבין את זה כי אני מתחיל ב-java ואין לי ממש נסיון...את כל הבסיס של java הבנתי מצויין והבעיות אצלי מתחילות מהנושאים הקשים יותר--> יעילות+רקורסיה+רשימות מקושרות- לא ממש תירגלתי את הנושאים האלו ואין לי ממש נסיון(ברקורסיה אתה גם מבין טוב?).
תודה אחי עזרת לי מאוד.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 13 November 2007 בשעה 23:28 | | IP רשוּם
|
|
|
|
אה הא ואני אפילו אחזור בסופ"ש ונראה אם יהיה כוח לזה...
בכל מקרה, אני די בטוח שזה O של N,
והתפקיד של המורה שלך זה ללמד אותך, שי/תעשה אז העבודה שלהם.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
עדי
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 December 2007 בשעה 02:07 | | IP רשוּם
|
|
|
|
אל תהיה בטוח,
הקוד הזה הוא בסיבוכיות O של N בריבוע, ואני יכול להראות את זה אם תבקשו.
|
| חזרה לתחילת העמוד |
|
| |
מיכאל
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 December 2007 בשעה 03:55 | | IP רשוּם
|
|
|
|
אכן... מסכים עם הצדיק מעליי...
הסיבוכיות במקרה הגרוע היא ריבועית.
|
| חזרה לתחילת העמוד |
|
| |
לוק
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 December 2007 בשעה 13:06 | | IP רשוּם
|
|
|
|
לא מדוייק.
למרות שהניתוח של שושן לסיבוכיות איננו נכון, עדין הסיבוכיות היא לינארית כפונקציה
של הקלט.
|
| חזרה לתחילת העמוד |
|
| |
עדי
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 December 2007 בשעה 14:57 | | IP רשוּם
|
|
|
|
הסיבוכיות היא לא לינארית,
הנה הדוגמא:
ניתן מקרה גרוע לדוגמא:
01111
00111
00011
00001
במקרה הבדיקות נעשות ע"פ כל שורה... שורה ראשונה בדיקה של 2 שורה שניה בדיקה של 3 שורה שלישית בדיקה של 3 וכן הלאה עד שורה n-1.
2+3+4+5+5 (שורה אחרונה אותה מספר של בדיקות כמו לפני אחרונה)
= 19 בדיקות למקרה הזה
עכשיו,
הנוסחא הכללית,
4+3+2 ... n + n =
n+1 * n
--------- -1 + n
2
הנוסחא שהראיתי פה היא כבר O של N בריבוע אם מצמצמים את כל המקדמים.
|
| חזרה לתחילת העמוד |
|
| |
לוק
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 12 December 2007 בשעה 23:21 | | IP רשוּם
|
|
|
|
עדי אין ספק שהסיבוכיות היא ריבועית ביחס ל-N.
אך שים לב שגודל הקלט שלך הוא N^2 כלומר מטריצה מגודל NxN
כיוון שעוברים לכל היותר על כל איבר פעם אחת הסיבוכיות היא לינארית ביחס לגודל הקלט.
לדוגמה:
סיבוכיות מציאת איבר מקסימלי במערך שגודלו N היא לינארית כפונקציה של הקלט ולינארית ביחס ל-N.
סיבוכיות מציאת איבר מקסימלי במטריצה שגודלה NxN גם היא לינארית כפונקציה של הקלט,
אך ריבועית ביחס ל-N.
|
| חזרה לתחילת העמוד |
|
| |
מיכאל
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 16 December 2007 בשעה 02:47 | | IP רשוּם
|
|
|
|
חחח אז זאת לא חוכמה נכון?
הכוונה היתה סיבוכיות N ביחס לקלט של N בריבוע.
|
| חזרה לתחילת העמוד |
|
| |
מיכאל
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 16 December 2007 בשעה 02:51 | | IP רשוּם
|
|
|
|
למען בהירות, בוא ניתן למערך גודל של MXM.
הסיבוכיות של האלגוריתם הנ"ל יהיה N בריבוע. בכי במקרה הגרוע שלו הוא ירוץ כמו שעדי תיאר. לכן התשובה לא עומדת בדרישות התרגיל, מכיוון שכמות העבודה תוגדל כל פעם ביחס ריבועי לגודל המטריצה.
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
