מערך מסדר N*N נקרא מושלם אם הוא מכיל אך ורק את המספרים 1,2,,n כך שכל מספר מופיע בדיוק פעם אחת בכל שורה ובכל עמודה.

לדוגמא:

1 2 3 4

2 1 4 3

3 4 2 1

4 3 1 2

כתבו פעולה המקבלת מערך דו-מימדי של מספרים ומחזירה "אמת" אם המערך מושלם ו- "שקר" אחרת.

אני לא מצליח לחשוב על דרך למצוא אם יש את כל המספרים מ-1 עד N..

מישהו יכול לתת לי עזרה? רמז?

תודה

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

שים לב שמספיק לך לבדוק שאין מספר שמופיע פעמיים, ושכל המספרים הם בין 1 ל-N (אם מספר חסר, אז בהכרח מספר אחר יופיע פעמיים).

סתם כיוון, לא בטוח בכלל שזה נכון מתמטית-

מה עם למצוא את הסכום של כל המספרים 1 - N והמכפלה שלהם, ואז לעבור שורה שורה ולבדוק שהסכום והמכפלה של כל שורה שווים למספרים הנ"ל?

בנוסף הייתי מוסיף בתחילת הפונקציה בדיקה אם גודל המערך נכון (N * N), כדי לחסוך ריצות מיותרות.

ההצעה שלי היא כזאת:

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

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

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

int [] numbers = new int[n];

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

כך לדוגמא numbers[0] יכיל את מספר הפעמים שהמספר 1 מופיע בשורה, ו- numbers[1] את מספר הפעמים שהמספר 2 מופיע בשורה number[n-1] את מספר הפעמים שהמספר n מופיע במערך.

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

bool checkRowsAndCols(int [ , ] arr, int n)
{
int [] numbers_rows = new int[n];
int [] numbers_cols = new int[n];

for(int i=0; i < n; i++)
{
	for(int k =0; k < n; k++) 
		numbers_cols = numbers_rows[k] = 0; // מאפסים את המערך במעבר משורה לשורה

	for(int j=0; j < n; j++)
	{
		int num_row = arr[i, j];
		int num_col = arr[j, i];
if(num_row > n || num_row < 1 || num_col > n || num_col < 1) return false;
		numbers_rows[ num_row -1 ]++; // הוסף מופע מספר בשורה
		numbers_cols[ num_col -1 ]++; // הוסף מופע מספר בעמודה

		if(numbers_rows[ num -1 ] > 1 || numbers_cols[ num -1 ] > 1) // אם המספר מופיע יותר מפעם אחת - לא טוב
			return false; 
	}
}
return true; // הכל בסדר
}

מספיק לבדוק רק את הסכום של כל טור וכל שורה (אתה אמור לדעת מהו) (אחרי שבשורה אחת בדקת שיש את כל המספרים)

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

המערך מגודל N*N תמיד..

Master Boo,

בעיקרון אני אמור לעשות ככה?

      int[] a = new int[4];
      int i, sum = 0, kefel = 1, tempsum=0, tempkefel=1;
      for (i = 0; i < a.Length; i++)
      {
        sum = sum + (i+1);
        kefel = kefel * (i+1);
      }
      for (i = 0; i < a.Length; i++)
      {
        tempsum = tempsum + a[i];
        tempkefel = tempkefel * a[i];
      }
      if (tempsum == sum && tempkefel == kefel)
        return true;
      else
        return false;

ImFondOfComputers,

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

yigael_o, אי אפשר לבדוק רק את הסכום, בשורה של 4 מקומות לדוגמא יש 1,2,3,4. הסכום הוא 10. אך גם אם יש 2,2,3,3 הסכום הוא 10.

מספיק לבדוק רק את הסכום של כל טור וכל שורה (אתה אמור לדעת מהו) (אחרי שבשורה אחת בדקת שיש את כל המספרים)

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

זה לא נכון, זה לא מבטיח שום דבר

yigael_o, אי אפשר לבדוק רק את הסכום, בשורה של 4 מקומות לדוגמא יש 1,2,3,4. הסכום הוא 10. אך גם אם יש 2,2,3,3 הסכום הוא 10.

כנראה לא הבהרתי את הכוונה שלי. אני אנסה שוב:

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

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

הנחה: הטבלה מכילה רק מספרים שלימים.

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

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

דרך אגב, למה אתם לא משתמשים ב foreach?

בניתי לך פעולה שעושה את זה...

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

    static bool Mushlam(int[,] a, int n)
    {
      int[,] counter = new int[n, n];
      for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
        {
          if (a[i, k] < 1 || a[i, k] > n) return false;
          counter[i, a[i, k]-1]++;
        }
      for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
        {
          if (counter[i, a[i, k]-1] > 1) return false;
        }
      return true;
    }

בניתי לך פעולה שעושה את זה...

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

    static bool Mushlam(int[,] a, int n)
    {
      int[,] counter = new int[n, n];
      for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
        {
          if (a[i, k] < 1 || a[i, k] > n) return false;
          counter[i, a[i, k]-1]++;
        }
      for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
        {
         if (counter[i, a[i, k]-1] > 1) return false;
        }
      return true;
    }

הפתרון שלך יפה אבל הוא חלקי

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

למשל אם יש לך מערך כזה

1234

1234

1234

1234

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

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

        static bool Mushlam(int[,] a, int n)
        {
            int[,] counter = new int[n, n];
            for (int i = 0; i < n; i++)
                for (int k = 0; k < n; k++)
                {
                    if (a[i, k] < 1 || a[i, k] > n) return false;
                    counter[i, a[i, k] - 1]++;
                }
            for (int i = 0; i < n; i++)
                for (int k = 0; k < n; k++)
                {
                    if (counter[i, a[i, k] - 1] > 1)
                    {
                        Console.WriteLine("two in a line");
                        return false;
                    }
                }
            for (int i = 0; i < n; i++)
                for (int k = 0; k < n; k++)
                    counter[i, k] = 0;

            for (int k = 0; k < n; k++)
                for (int i = 0; i < n; i++)
                {
                    counter[a[i, k] - 1,k ]++;
                }
            for (int k = 0; k < n; k++)
                for (int i = 0; i < n; i++)
                {
                    if (counter[a[i, k] - 1, k] > 1)
                    {
                        Console.WriteLine("two in a row");
                        return false;
                    }
                }
            return true;
        }

לקחתי את הקוד שבניתי.. לאחר בדיקת השורות איפסתי את מערך המונים, ואז עשיתי את אותה הפעולה של הבדיקה רק בטורים ( קודם i עולה ורק אז k).