מצולעים

[JDOE]

מצולעים ../images/Emo35.gif

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

 

[liornei]

מה הכוונה סופרת מצולעים, מחשבת שטח?

 

[JDOE]

הכוונה ל

סופרת כמה מצולעים שונים יש כמה מרובעים כמה משושים כמה מתומנים וכן הלאה

 

[עריסטו]

יש לי אלגוריתם לא יעיל

עוברים על כל הנקודות ברשת לפי הסדר. סופרים כמה טיולים ניתן לבצע מכל נקודה כנקודת התחלה, כך שהטיול יסתיים בנקודת ההתחלה ולא יחתוך את עצמו (לא קשה לעשות את זה ברקורסיה). כך נספר כל מצולע מספר פעמים: אם היקף המצולע הוא n הוא נספר 2n פעמים (כי ניתן להתחיל מכל נקודה על ההיקף ולנוע בשני כיוונים). לכן ברגע שגלינו מצולע לא נוסיף למונה 1 אלא נוסיף למונה 1/2n, כאשר n הוא היקף המצולע.

 

[JDOE]

לא כל טיול

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

 

[עריסטו]

ודאי שלא, אבל אני סופר רק את

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

 

[JDOE]

הבנתי, רעיון יפה

אם כי כמו שאמרת לא יעיל בכלל הרי שיש אלפי מצולעים כבר ב nים קטנים ולא שכל חלק הולך חלק כל חלק בעצמו אצלך היא איזושהי לולאה אבל אני התכוונתי תיאורטית אז זה לא כל כך משנה אלא אם כן יש לך משהו יעיל?