נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: חישוב שטח מצולע

שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
נבט
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 02 July 2008 בשעה 11:04 | IP רשוּם
ציטוט נבט

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 17 February 2010 בשעה 19:09 | IP רשוּם
ציטוט טלי

מה אני אישית לא הבנתי כלום

חזרה לתחילת העמוד הצג את כרטיס החבר של טלי חפש הודעות אחרות של טלי בקר בדף הבית של טלי
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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