זקוק לעזרה בשיעורי בית בג'אווה

[moskitos]

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

התרגיל:

נתאר כמה ממאפייני קבוצה:

- בהינתן קבוצה A ועצם x כלשהו, מתקיימת בדיוק אחת משתי האפשרויות: או x הוא

איבר של A (ובמילים אחרות נאמר: x שייך ל- x ,A נמצא ב- A), או x אינו איבר של .

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

- שתי קבוצות A ו- B נחשבות שוות זו לזו, כאשר לשתיהן יש בדיוק אותם איברים.

- קימות קבוצות סופיות, כגון: קבוצת הפתרונות של המשוואה x2 - 7x + 12 = 0 (הקבוצה

מכילה את המספרים 3 ו- 4). במקרה כזה נגיד כי מספר האיברים בקבוצה הוא 2.

- קיימות קבוצות אינסופיות, כגון: כל המספרים הממשיים בין 0 ל- 1 (כולל קצוות). במקרה

כזה לא נדבר על מספר האיברים בקבוצה.

- קבוצה A תיקרא קבוצה ריקה אם אין בה איברים בכלל (כגון, קבוצת כל המספרים בין 10

ל- 15 המתחלקים ב 9- ). במקרה כזה נגיד כי מספר האיברים הוא 0.

- בהינתן שתי קבוצות A ו- A ,B נקראת תת-קבוצה של B, אם כל איבר של A הוא איבר של

B. (ובמילים אחרות נאמר: A חלקית ל- B, או A מוכלת ב- .(B

- בהינתן שתי קבוצות A ו- B, קבוצת החיתוך של שתי הקבוצות היא אוסף האיברים

שנמצאים גם בקבוצה A וגם בקבוצה B. מסומן .AB

לדוגמא, אם { A = {6, 2, 4 ו- { B = {2, 3, 8, 6 אז { AB = {2,

- בהינתן שתי קבוצות A ו- B, קבוצת האיחוד של שתי הקבוצות היא אוסף האיברים

שנמצאים לפחות באחת הקבוצות A או B. מסומן .AB

לדוגמא, אם { A = {6, 2, 4 ו- { B = {2, 3, 8, 6 אז { AB = {2, 3, 4, 6,

- בהינתן שתי קבוצות A ו- B, קבוצת ההפרש A\B היא אוסף האיברים שנמצאים בקבוצה

A ולא נמצאים בקבוצה .B

לדוגמא, אם { A = {6, 2, 4 ו- { B = {2, 3, 8, 6 אז { A\B = {

עליכם להגדיר מחלקה בשם Set המייצגת את קבוצת המספרים הטבעיים האי-זוגיים (טבעיים =

שלמים חיוביים). כלומר {…, 7 , 5 , 3 , 1} (עד אינסוף).

שימו לב, כל אחד מהאובייקטים שייוצרו מהמחלקה Set שתכתבו יוכל להחזיק קבוצה סופית

משלו. לדוגמא, אובייקט אחד ייצג את הקבוצה { 3 , 25 , 1}, אובייקט אחר ייצג למשל את

הקבוצה { 17 , 25 , 5 , 9} ואובייקט שלישי ייצג את קבוצת כל המספרים האי-זוגיים מ- 100 עד

.1000

מימוש קבוצה צריך להיות באמצעות רשימה מקושרת.

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

הרשימה שתחזיק את המספרים שבקבוצה, כך שלפחות חלק מהפעולות המוזכרות לעיל ייעשו

באופן היעיל ביותר.

עליכם לכתוב את הגדרת המחלקה: תכונות ( instance variables ) - לפי בחירתכם

כאן יש לי רשימה של מתודות שעלי לממש כמו למשל isEmpty, numOfElements וכו'.

[domiel]

דורשים ממך לממש רשימה מקושרת, זה הכל.

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

המטרה היא שתממש את המחלקה ככה שהפונקציות שדורשים ממך יהיו יעילות.

[moskitos]

איך אני למשל ביצירת האובייקט מכניס איברים לרשימה ?

[moskitos]

אוקיי אז התחלתי לכתוב אבל יש לי בעיה.

זה ה-CLASS שמייצג קודקוד ברשימה מקושרת:

public class IntNode
{
  private int _value;
  private IntNode _next;

  public IntNode(int v, IntNode n)
  {
   _value = v;
   _next = n;

  }
  public int getValue()
  {
   return _value;
  }

  public IntNode getNext()
  {
   return _next;
  }

  public void setValue(int v)  
  {
   _value = v;
  }

  public void setNext(IntNode n) 
  {
   _next = n;
  }
}

וזה ה-CLASS שלי:

public class Set
{
  private IntNode _head;
  private IntNode _current;

  //public Set()
  //{
   //_head = null;
   //_current = null;
  //}

  /**
  * add number to Set object
  * @param x - the number to be add 
  */
  public void addToSet (int x)
  {
   _head = new IntNode(x, _current);
   _head = _current;  
  }

  /**
  * return a string representation of this Set 
  */
  public String toString()
  {   
   String temp = "";

   for (IntNode currentNode = _head; currentNode != null; currentNode.getNext())
   {
     temp += currentNode.getValue() + ",";
   }

   return temp;
  }

מה שלא כ"כ מסתדר לי זה באיזה Menbers לבחור כשאני כותב את ה-Class והכנסה של איבר טיפה בעייתית ולא עובדת לי (addToSet)

[domiel]

members? בהתאם למה שאתה צריך.

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

מעבר לזה המימוש שלך לaddtoset לא נכון, שים לב שאתה משנה את ראש הרשימה (בעצם הערך הראשון) לסוף הרשימה, למה?

אתה רק צריך לשנות את _current.

[moskitos]

אוקיי תודה רבה הסתדרתי, זה בעיקרון ב-Class שלי:

import java.awt.HeadlessException;


import javax.print.attribute.standard.PresentationDirection;


public class Set
{
	private IntNode _head;
	private IntNode _current;
	private IntNode _lastNode;
	private int _numberOfElements;

	/**
	 * create a new empty Set object
	 */
	public Set()
	{
		_head = null;
		_current = null;
		_lastNode = null;
		_numberOfElements = 0;
	}

	/**
	 * check if the object empty
	 * @return true if Set object contain elements, false otherwise
	 */
	public boolean isEmpty()
	{
		return (_head == null);
	}

  /**
   * chekc if value exist insude the object
   * @param num - the value the be check
   * @return true if the number in the Set, false otherwise
   */
  public boolean isMember(int num)
  {
  	boolean isFind = false;


    if (_head == null)
    {
      return isFind;      
    }


    IntNode temp = _head;

    while (temp != null)
    {
      if (temp.getValue() == num)
      {
        isFind = true;
      }

      temp = temp.getNext();
    }


    return isFind;
  }

  /**
   * check if 2 Set object are equals
   * @param other - the object to be compare with
   * @return true if the object to be compare with equals to this, false otherwise
   */
  public boolean equals(Set other)
  {
  	boolean isEquals = true;

  	if (this.numOfElements() != other.numOfElements())
		{
			return false;
		}
  	else
  	{
  		IntNode temp = _head;
  		IntNode temp2 = other._head;

  		while (temp != null)
			{				
  			if (temp.getValue() != temp2.getValue())
				{
  				isEquals = false;
					break;
				}

  			temp = temp.getNext();
  			temp2 = temp2.getNext();
			}

  		return isEquals;
		}
  }

  /**
   * calculate number of elements in the object
   * @return number of elements in the object
   */
  public int numOfElements()
  {
  	return _numberOfElements;
  }

  /**
   * check if other is sub set
   * @param other - other Set object to compare with
   * @return true if other is sub set, false otherwise
   */
  public boolean subSet(Set other)
  {
  	boolean isSubSet = true;
  	IntNode temp = other._head;

  	while (temp != null)
		{
  		if (!this.isMember(temp.getValue()))
			{
  			isSubSet = false;
  			break;
			}

  		temp = temp.getNext();
		}

  	return isSubSet;
  }

	/**
	 * add number to Set object
	 * @param x - the number to be add 
	 */
	public void addToSet (int x)
	{
    if (isEmpty())
    {
      _head = new IntNode(x, null);
      _lastNode = _head;
      _numberOfElements++;
    }
    else
    {
      _current = new IntNode(x, null);
      _lastNode.setNext(_current);
      _lastNode = _current;
      _numberOfElements++;
    }
	}

	/**
	 * remove number from list
	 * @param x - the number to remove
	 */
	public void removeFromSet(int x)
	{
		IntNode prev = null;
		IntNode current = _head;

		while (current != null && current.getValue() != x)
		{
			prev = current;
			current = current.getNext();
		}

		if (current != null)
		{
			if (prev == null)
			{
				_head = current.getNext();
				_numberOfElements--;
			}
			else
			{
				prev.setNext(current.getNext());
				_numberOfElements--;
			}
		}
	}

	/**
	 * return a string representation of this Set 
	 */
  public String toString()
  {
  	int count = 0;
    String stTemp = "{";
    IntNode temp = _head;


    while (temp != null)
    {
      stTemp += temp.getValue();

      if (count < this._numberOfElements - 1)
			{
				stTemp += ",";
				count++;
			}

      temp = temp.getNext();
    }

    return stTemp + "}";
  }

  /**
   * find the intersection between 2 Set objects
   * @param other - the other object to compare with
   * @return the intersection group
   */
  public Set intersection(Set other)
  {
  	Set mySet = new Set();
		IntNode temp2 = other._head;

		while (temp2 != null)
		{				
			if (this.isMember(temp2.getValue()))
			{				
				mySet.addToSet(temp2.getValue());
				temp2 = temp2.getNext();
			}			
		}

		return mySet;
  }

  /**
   * find all the elements who exist in both Sets objects 
   * @param other - the other object to compare with
   * @return the union elements who exist in both Set objects
   */
  public Set union(Set other)
  {
  	Set setToReturn = new Set();
  	IntNode temp = this._head;
		IntNode temp2 = other._head;

		while (temp != null) //put all the elements from this object to the new Set
		{
			setToReturn.addToSet(temp.getValue());
			temp = temp.getNext();
		}

		while (temp2 != null) //check if other object elements already exist in the new Set object 
		{
			if (!setToReturn.isMember(temp2.getValue()))
			{
				setToReturn.addToSet(temp2.getValue());					
			}

			temp2 = temp2.getNext();
		}


		return setToReturn;
  }

  /**
   * all the elements who exist in the Set object and missing in the other Set object
   * @param other - the other object to compare with
   * @return - the Set object minus the other Set object elements
   */
  public Set difference (Set other)
  {
  	Set setToReturn = new Set();
  	IntNode temp = this._head;

  	while (temp != null)
		{
			if (this.isMember(temp.getValue()) && !other.isMember(temp.getValue()))
			{
				setToReturn.addToSet(temp.getValue());			
			}

			temp = temp.getNext();
		}

  	return setToReturn;
  }


	public static void main(String[] args)
	{


	}


}

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

[שניצל]

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

חוץ מזה, שים לב ש-equals דורשת שהאיברים בקבוצות יהיו בדיוק באותו סדר, למרות שבקבוצות אין משמעות לסדר האיברים.

בנוסף, ב-addToSet הייתי מוודא קודם שהאיבר לא נמצא כבר בקבוצה, כדי לא להוסיף אותו פעמיים בטעות.

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

נ.ב. למה ה-importים בהתחלה, ולמה יש לך פונקציית main?

[moskitos]

לגבי ה-import'ים בהתחלה אני לא ממש יודע למה, זה מה שנוצר אחרי שיצרתי את ה-Class ולגבי ה-Main אני כמובן בודק את ה- Class אז זה נוח לי שהוא קיים שם ולא ממש משנה, לגבי ההערות שלך אני יבדוק את זה ומה לגבי מה ששאלתי לגבי איך מחשבים סיבוכיות מקום וזמן לכל פונקציה ?

[שניצל]

סיבוכיות זמן, פשוט תנסה לספור כמה "פקודות" כל פונקציה מבצעת. כמובן תמיד צריך לדאוג להסתכל על ה-worst case.

לדוגמה, נסתכל על isMember: היא עוברת על כל איברי הרשימה, ולכל אחד היא משווה אותו לערך הנתון. אז כמה זמן זה ייקח? לכל איבר ברשימה נצטרך לבצע מספר קבוע של פעולות (להשוות אותו לערך הנתון ולעבור לאיבר הבא). כלומר, אם יש n איברים ברשימה אז סה"כ הפעולות הוא n כפול קבוע כלשהו (+ קבוע כלשהו של עלות הפעולות מחוץ ללולאה), שזה סה"כ (O(n. אם ההסבר לא היה ברור לך, אז כדאי שתחזור על החומר של סיבוכיות ואיך מחשבים אותה (בעצם, בכל מקרה כדאי שתחזור על זה).

איך בא לידי ביטוי ה-worst case? ייתכן שהרי הפונקציה isMember תסתיים אחרי שתי איטרציות, כי האיבר שאנחנו מחפשים נמצא במקום השני ברשימה (האמת היא שבמימוש הספציפי שלך אתה תמשיך לרוץ עד סוף הרשימה בלי שום סיבה, אבל נניח לרגע שכן מימשת בצורה יעילה יותר). לכן תמיד צריך להניח את המקרה הגרוע ביותר - במקרה הזה, שהאיבר לא נמצא ברשימה בכלל, ולכן יש לעבור על כולה. בגדול צריך לחשוב על כל המקרים האפשריים ולחשוב מי מהם הוא הגרוע ביותר, ולחשב את זמן הריצה לפיו.

מבחינת סיבוכיות זכרון, פשוט צריך לחשוב כמה זכרון אתה "מקצה" במהלך הריצה של הפונקציה.

[moskitos]

אוקיי בדוגמא שנתת לי עם הפונקציה isMember קודם כל הוספתי break אם האיבר נמצא וככה אין לי צורך לרוץ עד סוף הרשימה במקרה שהאיבר נמצא (אם הוא כמובן לא בסוף הרשימה) והסיבוכיות זמן היא n אבל לא ממש הבנתי איך אני מחשב את הסיבוכיות מקום, האם אני צריך לחשב את זה בנפרד או שגם פה זה n ?

[שניצל]

שוב, תחשוב כמה זכרון הפונקציה שלך צריכה בכל רגע נתון. איזה זכרון אתה "מקצה" במהלך הריצה? (מקצה - זכרון שאתה עושה לו new, בצורה ישירה או ע"י קריאה לפונקציה אחרת שעושה new).

למה לשים break ולא פשוט return כמו שהצעתי קודם?

[moskitos]

מה בדיוק ההבדלים בין ה-2 ? (אני יודע מה כל אחד עושה, אני פשוט מתכוון האם זה משנה משהו)

[שניצל]

return חוסך לך את המשתנה isFind, והקוד יותר ברור ככה למי שקורא אותו.

[moskitos]

אוקיי, תודה רבה ואגב לגבי המתודה union: פה אני רץ פעמיים על על הרשימה - האם פה אפשר להגיד שהסיבוכיות היא פעמיים n ?

[שניצל]

א. תחזור על החומר של סיבוכיות. אתה אמור לדעת מה הקשר בין n ל-2n.

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