בעיה עם תרגיל ב- C#

[שניצל]

דרך אגב, זו וריאציה על אלגוריתם מוכר בשם "הרו של פולרד":

http://en.wikipedia.org/wiki/Pollard's_rho_algorithm

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

[NJorl]

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

אני חשבתי על פתרון כזה

public class Class2
{
  public Class2 previous = null;
  public string data = string.Empty;
  public Class2 next = null;
}

public class p1
{
  protected void Test1()
  {
    Class2[] items = new Class2[3];

    items[0] = new Class2();
    items[0].previous = null;
    items[0].data = "aaa";
    items[0].next = null;

    items[1] = new Class2();
    items[1].previous = null;
    items[1].data = "bbb";
    items[1].next = null;

    items[2] = new Class2();
    items[2].previous = null;
    items[2].data = "ccc";
    items[2].next = null;

    items[0].next = items[1];
    items[1].previous = items[0];
    items[1].next = items[2];
    items[2].previous = items[1];
//    items[2].next = items[0]; //Uncomment this line to make the linked list a circular linked list

    Class2 c1 = items[0];
    Class2 c2 = items[0];
    bool thisIsACircledLinkedList = false;
    while (c1 != null && thisIsACircledLinkedList == false)
    {
      c1 = c1.next;
      if (c1 != null)
      {
        if (c1.Equals(c2))
          thisIsACircledLinkedList = true;
      }
    }
//        here you check the value of thisIsACircledLinkedList if its true then it is a cirlce linked list
  }
}

[Ghosthunter]

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

[NJorl]

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

זה לא משנה ,

בדוגמית שכתבתי במקרה השתמשתי במערך והתחלתי לסרוק מהאיבר הראשון אבל זה רק להמחשה

אני יכול לקבל מבחוץ ref לכל אובייקט מסוג Class2 אני לא יודע אם הוא ראשון וזה גם לא מעניין אותי

החלק החשוב של הקטע שכתבתי זה רק איפה שמתחיל לולאת ה- while

אין שום בעיה לזהות בתוך האיטרציה אם אתה ניגש לאובייקט שכבר עברת עליו לפני כן.

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

public bool IsCircle(Class2 cx1)
{
    Class2 c1 = cx1;
    Class2 c2 = cx1;
    bool thisIsACircledLinkedList = false;
    while (c1 != null && thisIsACircledLinkedList == false)
    {
      c1 = c1.next;
      if (c1 != null)
      {
        if (c1.Equals(c2))
          thisIsACircledLinkedList = true;
      }
    }
return thisIsACircledLinkedList ;
  }

[שניצל]

התכנית שלך יכולה להתקע בלולאה אינסופית:

נניח שיש שהרשימה שלך בנויה ככה - א -> ב -> ג -> ד -> ב (כאן המעגל מתחיל)

ואתה מעביר לפונקציה את א בתור פרמטר.

[adamshar]

האלגוריתם פשוט עונה על כל המקרים.

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

ofir_yair תצייר לך כמה רשימות מקושרות כדי להשתכנע.

[ofir_yair]

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

ובלי קשר, אלגוריתם ממש נחמד.

[ktbnus]

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

שרשרת חוליות מעגלית היא שרשרת שאין לה חוליה אחרונה, כלומר כל חוליה מפנה לחוליה אחרת בשרשרת.

להפך, אתה הסקת שמדובר ברשימה מעגלית. לא נאמר שיש הפניה מהחוליה האחרונה לראשונה.

[ofir_yair]

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

[NJorl]

התכנית שלך יכולה להתקע בלולאה אינסופית:

נניח שיש שהרשימה שלך בנויה ככה - א -> ב -> ג -> ד -> ב (כאן המעגל מתחיל)

ואתה מעביר לפונקציה את א בתור פרמטר.

צודק , חשדתי שזה קל מדי

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
  public class Class2
  {
    public Class2 previous = null;
    public string data = string.Empty;
    public Class2 next = null;

    public Class2()
    {
    }
  }

  class Program
  {
    private static Class2 FindNode(Class2 item1)
    {
      Class2 x1 = null;
      System.Collections.Hashtable ht1 = new System.Collections.Hashtable();
      while (item1 != null)
      {
        if (ht1.Contains(item1))
        {
          x1 = item1;
          break;
        }
        else
        {
          ht1.Add(item1, "1");
          item1 = item1.next;
        }
      }
      return x1;
    }

    static void Main(string[] args)
    {
      Class2 item1 = new Class2();
      Class2 item2 = new Class2();
      Class2 item3 = new Class2();
      Class2 item4 = new Class2();

      item1.data = "1";
      item1.previous = null;
      item1.next = item2;

      item2.data = "2";
      item2.previous = item1;
      item2.next = item3;

      item3.data = "3";
      item3.previous = item2;
      item3.next = item4;

      item4.data = "4";
      item4.previous = item3;
      item4.next = item2;

      Class2 node = FindNode(item1);

      if (node == null)
        Console.WriteLine("Found no circular linked items");
      else
        Console.WriteLine("Found circular linked items at " + node.data);
      Console.ReadLine();
    }
  }
}

[Ghosthunter]

כאן אתה משתמש במבנה נתונים נוסף(וזה חצי ניקוד, אם סופרים).