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

נושא: ריבוע לטיני

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 08 October 2007 בשעה 16:10 | IP רשוּם
ציטוט אורח

מישהו יודע איך לבדוק אם ריבוע מסוים הוא ריבוע לטיני בC?

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 08 October 2007 בשעה 16:25 | IP רשוּם
ציטוט ששש

הממ...למה לא פשוט לשמור מערך של ביטים באורך N (הריבוע בגודל NXN) ואז לכל
שורה וכל עמודה לאפס אותו, וכל מספר בשורה / בעמודה, אם הוא לא בין 1 ל-N
להחזיר שקר, אם הביט במקום שלו במערך הוא 0 לשין בביט שלו 1, ואם הביט שלו 1
אז המספר חזר על עצמו והריבוע לא טוב (להחזיר שקר).
חזרה לתחילת העמוד הצג את כרטיס החבר של ששש חפש הודעות אחרות של ששש בקר בדף הבית של ששש
 
צחי@
משתמש חבר
משתמש חבר


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 08 October 2007 בשעה 17:00 | IP רשוּם
ציטוט צחי@

מימוש באמצעות std::set (נותן יתרון בכך שלא מוגבל למספרים):

קוד:

bool IsLatinSquare(int** mat, int size)
{
 set<int> hitMapRows;
 set<int> hitMapCols;
 int i, j;

 for ( i = 0; i < size; ++i)
 {
  hitMapRows.clear();
  hitMapCols.clear();
  for ( j = 0; j < size; ++j)
  {
   if (hitMapRows.find(mat[i][j]) != hitMapRows.end())
   {
    return false;
   }
   if (hitMapCols.find(mat[j][i]) != hitMapCols.end())
   {
    return false;
   }

   hitMapRows.insert(mat[i][j]);
   hitMapCols.insert(mat[j][i]);
  }
 }

 return true;
}

כמובן שצריך גם לבדוק שאין בריבוע יותר מ-N סמלים (הריבוע בגודל NxN).

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


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

:
תודה שעזרת לי
אבל אני לא יודע באיזה שפה זה נכתב, אני יודע רק C
והhitMapRows.find
או hitMapRows.insert

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


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 09 October 2007 בשעה 00:10 | IP רשוּם
ציטוט צחי@

זה נכתב ב-c++ כמובן. set הוא template class השייך לחבילת STL.
כדי להשתמש בו צריך להוסיף בתחילת הקוד:
קוד:

#include <set>

using namespace std;

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


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

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 09 October 2007 בשעה 02:40 | IP רשוּם
ציטוט לוק

לריבוע לטיני חוקיות די ברורה האומרת כי בכל שורה ובכל עמודה חייב להופיע מס' בתחום N..0 (לא כולל N), בדיוק פעם אחת.
לכן אפשר לבנות תוכנית שבנויה בדיוק על עיקרון זה.

קוד:

#define SIZE 4

 

void restoreArray(bool A[], int size)

{

      int i = 0;

      for(i = 0; i < size; ++i)

      {

            A[i] = false;

      }

}

 

bool CheckLatinSquare(int A[][SIZE],int size)

{

      bool a[SIZE];

      int i = 0, j = 0;

 

      restoreArray(a,size);

 

      for(i = 0; i < size; ++i)

      {

            for (j = 0; j < size; ++j)

                  if (a[A[i][j]] < 0 || a[A[j][i]] >= size)

                         return false;

                  else if (a[A[i][j]] == true)

                         return false;

                  else

                         a[A[i][j]] = true;

            restoreArray(a,size);

      }

 

      for(i = 0; i < size; ++i)

      {

            for (j = 0; j < size; ++j)

                  if (a[A[j][i]] < 0 || a[A[j][i]] >= size)

                         return false;

                  else if (a[A[j][i]] == true)

                         return false;

                  else

                         a[A[j][i]] = true;

            restoreArray(a,size);

      }

      return true;

}

void main()

{

      int a[SIZE][SIZE] = {{1,3,0,2},

                           {3,2,1,0},

                            {2,0,3,1},

                            {0,1,2,3},};

 

      int b[SIZE][SIZE] = {{1,3,0,2},

                           {3,2,1,0},

                            {3,0,2,1},

                            {0,1,2,3},};

 

      if (CheckLatinSquare(a,SIZE) == true)

            printf("a is a latin square.\n");

      else

            printf("a is NOT a latin square.\n");

 

      if (CheckLatinSquare(b,SIZE) == true)

            printf("b is a latin square.\n");

      else

            printf("b is NOT a latin square.\n");

}

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 09 October 2007 בשעה 02:46 | IP רשוּם
ציטוט לוק

ישנה טעות והבדיקה של התחום צריכה להעשות כך כמובן:

if (A[i][j] < 0 || A[i][j] >= size)

     return false;

                 

if (A[j][i] < 0 || A[j][i] >= size)

     return false;


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


הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
נשלח בתאריך: 09 October 2007 בשעה 09:44 | IP רשוּם
ציטוט צחי@

ציטוט:

אבל זה לא יעזור לי אם אני לא אבין מה המשמעויות שלהם
יש לך איזה דף שמסביר כל אחד ?

בגדול - set הוא קבוצה במובן של תורת הקבוצות - כלומר הוא יכול להכיל איברים מטיפוס כלשהו (שמוגדר בתוך < >) ומוגדרות עליו פעולות של הכנסה, הוצאה וחיפוש. המימוש של set יכול להיות שונה בהתאם לצרכים - זה אפשרי עם מערך או רשימה או hash table או עץ חיפוש ועוד. נדמה לי שב-STL זה ממומש בתור עץ בינארי.

חוץ מזה, JFGI  !!!

(Just F***'n Google It)

אתה תמצא בקלות המון מקורות דוגמאות והסברים לשימוש.

לגבי הפתרון שהוצע ע"י לוק - הוא פתרון טוב כל עוד מניחים שהאיברים הם מספרים מהתחום 0..N

אבל עד כמה שאני זוכר, ריבוע לטיני מוגדר עבור N סמלים כלשהם - זה יכול להיות אותיות א"ב או כל סוג סמל אחר.

http://en.wikipedia.org/wiki/Latin_square

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 09 October 2007 בשעה 15:29 | IP רשוּם
ציטוט לוק

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

בכל מקרה שים לב לכמה דברים בפתרון שלך:

1.כיוון ששפת התיכנות היא C אי אפשר להשתמש ב-STL, כלומר כל מבנה צריך
לממש מכף רגל עד ראש או להשתמש בחבילות בשפת C בלבד. 

2.הפתרון שלך אינו תקף על כל קבוצה N. ניתן אומנם להשתמש בו (בעזרת Casting)
לטובת סמלים כיוון שלכל סמל בטבלת ה-ASCII יש מס' טיבעי כלשהו.
אבל מצד שני לקבוצה מעל שדה הרציונלים, או קבוצה מעל שדה הטיבעיים והא"ב ביחד,
הפתרון לא תקף.

3.לא בדקת אם מס' מסויים בכלל שייך לקבוצה N.
כלומר מקרה של ריבוע: 1 2 3  הפונקציה שכתבת תחזיר אמת.
                         4 5 6
                         7 8 9   


בכל אופן הרעיון הוא אותו רעיון והאלגוריתם נבנה בפתרון מחוקיות של ריבוע לטיני כך:

1.בעבור כל שורה וכל עמודה
  1.1 אם נמצא איבר המופיע יותר מפעם אחת או אינו שייך לקבוצה N החזר שקר.
2.החזר אמת.
חזרה לתחילת העמוד הצג את כרטיס החבר של לוק חפש הודעות אחרות של לוק בקר בדף הבית של לוק
 

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

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

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