כותב |
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 28 December 2007 בשעה 21:27 | | IP רשוּם
|
|
|
|
קוד:
public class IntVector { private int []_arr;
/** * Constructor for objects of class IntVector */ public IntVector(int size) { _arr= new int[size]; }
public void addInt(int num, int index) { _arr[index] = num; }
public boolean what (int[] other) { if (_arr.length != other.length) return false; for (int i=0; i<_arr.length; i++) { boolean f = false; for (int j=0; j<other.length && !f; j++) if (_arr == other[j]) f= true; if (!f) return false; } for (int i=0; i<other.length; i++) { boolean f = false; for (int j=0; j<_arr.length && !f; j++) if (other == _arr[j]) f= true; if (!f) return false; } return true; }
}
|
|
|
אני צריך לשנות את השיטה what ליעילה יותר מבחינת סיבוכיות זמן הריצה
הבנתי שניתן לעשות זאת על ידי מיון בועות וחיפוש בינארי
הנה השיטות למיון והחיפוש אבל לא יודע כיצד למזג אותם לגבי התרגיל
קוד:
private void bubble (int[ ] _arr) { int last, current, temp; for (last = _arr.length-1; last > 0; last--) { for (current = 0; current < last; current++) {
if ( _arr[current] < _arr[current + 1] ) {
temp = _arr[current];
_arr[current] = _arr[current + 1];
_arr[current + 1] = temp;
}
} }
private int binary (int[ ] _arr, int num) { int middle, lower = 0, upper = (_arr.length - 1); do { middle = ((lower + upper) / 2); if (num < _arr[middle]) upper = middle - 1;
else lower = middle + 1; } while ( (_arr[middle] != num) && (lower <= upper) );
if (_arr[middle] == num) return middle;
else return -1; }
} |
|
|
מישהו יכול לעזור בנוסף??
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 28 December 2007 בשעה 21:34 | | IP רשוּם
|
|
|
|
את הבינארי לא צריך, תמיין כל מערך ואז תעבור על שניהם עם שני אינדקסים שמתחילים מ-0, בערך כמו שהולך מיזוג, רק שאל תעשה מיזוג אלא תחפש כפילויות.
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 28 December 2007 בשעה 22:15 | | IP רשוּם
|
|
|
|
shoshan כתב:
את הבינארי לא צריך, תמיין כל מערך ואז תעבור על שניהם עם שני אינדקסים שמתחילים מ-0, בערך כמו שהולך מיזוג, רק שאל תעשה מיזוג אלא תחפש כפילויות. |
|
|
כך?
קוד:
public boolean what (int[] other) {
bubble(_arr);
bubble(other);
כאן צריכה לבוא ההשוואה..
}
private void bubble (int[ ] _arr) { int last, current, temp; for (last = _arr.length-1; last > 0; last--) { for (current = 0; current < last; current++) {
if ( _arr[current] < _arr[current + 1] ) {
temp = _arr[current];
_arr[current] = _arr[current + 1];
_arr[current + 1] = temp;
}
} }
|
|
|
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 29 December 2007 בשעה 10:58 | | IP רשוּם
|
|
|
|
כן
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 29 December 2007 בשעה 11:17 | | IP רשוּם
|
|
|
|
אוקיי ואיך אני מבצע את ההשוואה
ניסיתי משהו כזה
קוד:
public boolean what (int[] other) { int index = 0 ;
bubble(_arr);
bubble(other);
if ( (binary (other, _arr[index])!=-1) ) return true; else return false; } |
|
|
יש לי אבל שאלה הbubble הסיבוכיות שלו היא O(n^2)ddd לא?אז בעצם לא יעלתי את השיטה?
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 29 December 2007 בשעה 11:51 | | IP רשוּם
|
|
|
|
אהממ..קודם כל במימוש הראשון שלך לא צריך לחפש גם את כל האיברים של המערך השני בראשון.
חוץ מזה, במימוש עם המיון לא צריך חיוש בינארי, כמו שכבר אמרתי.
ואחרו חביב, יש מיונים יותר יעילים ממיון בועות.=, שיהיו ב-O של n*log(n)
ובאותה יעילות של n*logN אפשר גם לעשות את מה שהציעו לך: למיין מערך אחד (עדיף את הקטן מבינהם) ולחפש את כל האיברים של המערך השני בחיפוש בינארי במערך הזה.
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 29 December 2007 בשעה 12:20 | | IP רשוּם
|
|
|
|
shoshan כתב:
אהממ..קודם כל במימוש הראשון שלך לא צריך לחפש גם את כל האיברים של המערך השני בראשון.
חוץ מזה, במימוש עם המיון לא צריך חיוש בינארי, כמו שכבר אמרתי.
ואחרו חביב, יש מיונים יותר יעילים ממיון בועות.=, שיהיו ב-O של n*log(n)
ובאותה יעילות של n*logN אפשר גם לעשות את מה שהציעו לך: למיין מערך אחד (עדיף את הקטן מבינהם) ולחפש את כל האיברים של המערך השני בחיפוש בינארי במערך הזה.
|
|
|
כן יש את quicksort
הנה זה מה שעשיתי עכשיו בהנחה שזה נכון ועשיתי לשני המערכים את המיון איך אני יכול לבצע את הבדיקה עליהם כעת אמרת שלא צריך את החיפוש הבינארי תוכל להראות לי אם כך בלעדיו?
קוד:
public boolean what (int[] other) { int index = 0 ; quicksort(_arr, 0, _arr.length-1); quicksort(other, 0, other.length-1); }
private void quicksort(int[] a, int lo, int hi) { int m;
if (hi > lo+1) { // there are at least 3 elements // so sort recursively m = partition(a,lo, hi); quicksort(a, lo, m-1); quicksort(a, m+1, hi); } else // 0, 1, or 2 elements, so sort directly if (hi == lo+1 && a[lo] > a[hi]) swap(a,lo, hi); }
private int medianLocation(int[] a, int i, int j, int k) { if (a[i] <= a[j]) if (a[j] <= a[k]) return j; else if (a[i] <= a[k]) return k; else return i; else // _arr[j] < _arr[i] if (a[i] <= a[k]) return i; else if (a[j] <= a[k]) return k; else return j; }
private int partition(int[] a, int lo, int hi) { swap(a, lo, medianLocation(a, lo+1, hi, (lo+hi)/2)); int m = partition(a, lo+1, hi, a[lo]); swap(a, lo, m); return m; }
private int partition(int[] a,int lo, int hi, int pivot) { if (hi == lo) if (a[lo] < pivot) return lo; else return lo-1; else if (a[lo] <= pivot) // a[lo] in correct half return partition(a, lo+1, hi, pivot); else { // a[lo] in wrong half swap(a, lo, hi); return partition(a, lo, hi-1, pivot); } }
private void swap(int[] a, int first, int second) { //swaps between the contents of the array cells in //indexes first and second int temp; temp = a[first]; a[first] = a[second]; a[second] = temp; }
|
|
|
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 29 December 2007 בשעה 12:38 | | IP רשוּם
|
|
|
|
כמו שאמרתי, זה קצת מזכיר איחוד (merge)
קוד:
// arr1 is sorted // arr2 is sorted
int n1 = arr1.length int n2 = arr2.length int i = 0 , j = 0; while (i < n1 && j < n2) { if (arr[i] == arr[j]) return false; if (arr[i] > arr[j]) ++j; else ++i; }
return true; |
|
|
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 29 December 2007 בשעה 13:00 | | IP רשוּם
|
|
|
|
רגע אם יש לי _arr
והמערך השני הוא other
אז מה זה arr בלולאה עצמה?
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 29 December 2007 בשעה 15:04 | | IP רשוּם
|
|
|
|
אופס, בכל מקום שיש arr[i] הכוונה למערך הראשון במקום ה-I ובכל מקום שיש J הכוונה למערך השני במקום ה-J.
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 29 December 2007 בשעה 16:08 | | IP רשוּם
|
|
|
|
shoshan כתב:
אופס, בכל מקום שיש arr[i] הכוונה למערך הראשון במקום ה-I ובכל מקום שיש J הכוונה למערך השני במקום ה-J. |
|
|
אוקי הבנתי כך?
קוד:
public boolean what (int[] other) { int n1 = other.length; int n2 = _arr.length; int i = 0 , j = 0; quicksort(_arr, 0, _arr.length-1); quicksort(other, 0, other.length-1); while (i < n1 && j < n2) { if (_arr[i] == other[j]) return false; if (_arr[i] > other[j]) ++j; else ++i; }
return true; }
|
|
|
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 29 December 2007 בשעה 16:59 | | IP רשוּם
|
|
|
|
looking good
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 29 December 2007 בשעה 17:20 | | IP רשוּם
|
|
|
|
תודה רבה
תוכל בבקשה לומר לי רק אם עשיתי נכון את ה quiksort כי הקומפיילר לא צעק על שגיאה כלשהי
קוד:
private void quicksort(int[] a, int lo, int hi) { int m;
if (hi > lo+1) { // there are at least 3 elements // so sort recursively m = partition(a,lo, hi); quicksort(a, lo, m-1); quicksort(a, m+1, hi); } else // 0, 1, or 2 elements, so sort directly if (hi == lo+1 && a[lo] > a[hi]) swap(a,lo, hi); }
private int medianLocation(int[] a, int i, int j, int k) { if (a[i] <= a[j]) if (a[j] <= a[k]) return j; else if (a[i] <= a[k]) return k; else return i; else // a[j] < a[i] if (a[i] <= a[k]) return i; else if (a[j] <= a[k]) return k; else return j; }
private int partition(int[] a, int lo, int hi) { swap(a, lo, medianLocation(a, lo+1, hi, (lo+hi)/2)); int m = partition(a, lo+1, hi, a[lo]); swap(a, lo, m); return m; }
private int partition(int[] a,int lo, int hi, int pivot) { if (hi == lo) if (a[lo] < pivot) return lo; else return lo-1; else if (a[lo] <= pivot) // a[lo] in correct half return partition(a, lo+1, hi, pivot); else { // a[lo] in wrong half swap(a, lo, hi); return partition(a, lo, hi-1, pivot); } }
private void swap(int[] a, int first, int second) { //swaps between the contents of the array cells in //indexes first and second int temp; temp = a[first]; a[first] = a[second]; a[second] = temp; }
|
|
|
|
חזרה לתחילת העמוד |
|
|
shoshan מנהל האתר
הצטרף / הצטרפה: 16 July 2005 מדינה: Israel
משתמש: מנותק/ת הודעות: 4637
|
נשלח בתאריך: 29 December 2007 בשעה 18:22 | | IP רשוּם
|
|
|
|
א. הקומפיילר לא צועק, שונא את הביטוי הזה.
ב. למה שלא תכתוב קוד שמשתמש במחלקה שלך ותראה אם הוא עובד ??
|
חזרה לתחילת העמוד |
|
|
זיו1 משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת הודעות: 66
|
נשלח בתאריך: 29 December 2007 בשעה 18:54 | | IP רשוּם
|
|
|
|
shoshan כתב:
א. הקומפיילר לא צועק, שונא את הביטוי הזה.
ב. למה שלא תכתוב קוד שמשתמש במחלקה שלך ותראה אם הוא עובד ??
|
|
|
אוקיי לא אשתמש בביטוי
ואני מנסה לכתוב רק יש לי בעיה בחלק של לראות האם השיטה פועלת נכון
אני רוצה שיוצג true or false
קוד:
import java.util.Scanner; public class Tester { public static void main ( String[] args) {
// _data = the array int [] _arr; // MAX = the length of the array final int MAX = 6; _arr = new int [MAX];
/** * enterNumbers is a method that fills the array with data from * the user */ Scanner scan = new Scanner (System.in); for (int i=0; i<_arr.length; i++) { System.out.print("enter an integer "); _arr[i] = scan.nextInt(); } /** * printArray prints the array content */ System.out.print("The array is: "); for (int i=0; i<_arr.length; i++) System.out.print("\t"+ _arr[i]); System.out.println(); System.out.println(what(_arr)); ?????? } }
|
|
|
|
חזרה לתחילת העמוד |
|
|
|
|