שאלה במערך חד מימדי C++

[BAR_PC 0]

היי חבר'ה יש לי שאלה במC++ במערך חד מימדי שאני ממש תקוע עליה אשמח לכיוון ולדעת אם אני בכלל בכיוון קצת "רמזים" 

 

השאלה: (מצטער מראש על האורך)

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

3	6	17	5	4	5	2
6#	5#	4#	3#	2#	1#	0#

התא 0# מצביע על התא 2#, התא 1# מצביע על התא 5#, אך התא 4# אינו מצביע על כל תא במערך (שכן במערך אין תא 17#).

לולאה במערך כנ"ל היא סדרה של תאים כך שהראשון מצביע על השני, השני על השלישי, וכן הלאה, עד לתא האחרון בסדרה שמצביע על התא הראשון בלולאה.לדוגמה: במערך הנ"ל התאים 3#, 5#, 6# מהווים לולאה. שימו לב כי גם התא 1# מצביע על התא 5#, אולם התא 1# אינו נכלל בלולאה, שכן אין עליו הצבעה על-ידי תא אחר בלולאה. כמו כן התא 0# מצביע על התא 2# אשר מצביע על התא 4#, אולם גם סדרת תאים זו אינה מהווה לולאה שכן התא 4# אינו מצביע על התא 0#.

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

 

מה שעשיתי:

 

 

#include <iostream>
#include <cstdlib>

//------std section-----
using std:: cin;
using std:: cout;
using std:: endl;

//------const section
const int N = 7;// The size you want to set


/////-----Main-------
int main()
{
    int nums [N];

    int N_place,
		temp = 0,
		 globalmax ;


    for(N_place = 0; N_place < N ; N_place++)
    {
    cin >> nums[N_place ];
    }

   for(N_place = 0; N_place < N ; N_place++)
    {

    	while (nums[N_place] == nums[nums[N_place]])
    	{
    		temp= nums[nums[N_place]];
    		if(temp = nums[N_place])
    		{
    			globalmax = nums[N_place];
    		break;
    		}
    	}

    	if (nums[N_place ] < 0 || nums[N_place ] > 7)
    	    	 break; // dont loop
    }

    cout << temp << " " << globalmax ;
   return EXIT_SUCCESS ;
}

 

שוב המון תודה אשמח לכיוון

[מודעה]

[Jabberwock 454]

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

• if(temp = nums[N_place])

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

• while (nums[N_place] == nums[nums[N_place]])

  עושה רושם שאתה מצפה שהלולאה תהיה בעלת 2 איטרציות בלבד ? לא רשום בתרגיל שמספר האיטרציות הוא קבוע.

[BAR_PC 0]

ציטוט של Jabberwock

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

• 
  if(temp = nums[N_place])

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

• 
  while (nums[N_place] == nums[nums[N_place]])

  עושה רושם שאתה מצפה שהלולאה תהיה בעלת 2 איטרציות בלבד ? לא רשום בתרגיל שמספר האיטרציות הוא קבוע.

 

הבנתי אז אני שומר לפני הfor  אחרי שאני קולט... תיקנתי את התנאי, לא שמתי לב, תודה

 

נכון הוא לא קבוע... זה לא רץ כל עוד הבא אחריו שווה? לא הבנתי למה זה מגביל ב2? כאילו הלולאה רצה כל עוד התא מצביע על תא,לא?

אם לא אפשר רמז קטן בבקשה למה לשנות את התנאי?

 

המון תודה

[Jabberwock 454]

אני גם חושב איתך... חחח

עשיתי בדיקה קטנה:

int main() {
    int nums[N] = { 2,5,4,5,17,6,3 };
     
    for (int i = 0; i < N; i++) {
      int firstIndex = i;
      int firstValue = nums[firstIndex];
      int value = firstValue;
      
      if (value >= 0 && value < N) {
        for (value = nums[value]; value >= 0 && value < N && value != firstValue; value = nums[value]);
      
          if (value == firstValue) {
            cout << "index " << firstIndex  << endl ;
          }
      }
    }
}

יוצא:

index 1

index 3

index 5

index 6

 

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

מה שלא חשבנו מקודם זה העל המקרה בתא 1, הערך שלו 5 ואחרי שעוקבים אחריו לא חוזרים לתא 1 אלא עוברים בתאים 3, 5 ו-6.

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

[etal 458]

ציטוט של Jabberwock

מה שלא חשבנו מקודם זה העל המקרה בתא 1, הערך שלו 5 ואחרי שעוקבים אחריו לא חוזרים לתא 1 אלא עוברים בתאים 3, 5 ו-6.

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

זאת שגיאה, לפי ההוראות תא #1 אינו נכלל בלולאה ולא היה צריך להופיע בהדפסה.

 

עוד בעיות:

- התוכנה תדפיס את כל הלולאות שיש במערך והדרישה היתה להדפיס רק את הלולאה הראשונה

- התוכנה תיכנס ללולאה אינסופית במערכים מסויימים:(

 

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

נערך 2020 בנובמבר 17 על-ידי etal

[מודעה]

[BAR_PC 0]

ציטוט של Jabberwock

אני גם חושב איתך... חחח

עשיתי בדיקה קטנה:

int main() {
    int nums[N] = { 2,5,4,5,17,6,3 };
     
    for (int i = 0; i < N; i++) {
      int firstIndex = i;
      int firstValue = nums[firstIndex];
      int value = firstValue;
      
      if (value >= 0 && value < N) {
        for (value = nums[value]; value >= 0 && value < N && value != firstValue; value = nums[value]);
      
          if (value == firstValue) {
            cout << "index " << firstIndex  << endl ;
          }
      }
    }
}

יוצא:

index 1

index 3

index 5

index 6

 

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

מה שלא חשבנו מקודם זה העל המקרה בתא 1, הערך שלו 5 ואחרי שעוקבים אחריו לא חוזרים לתא 1 אלא עוברים בתאים 3, 5 ו-6.

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

 

תודה רבה לך  נכון תא 1 זה הקאצ פה... לדעתי תנאי לפני הfor השני של אם הערך של התא שווה לתא? עם break? הבעיה שזה לא פתר חח זה לא הדפיס כלום.. אני אנסה למצוא משהו תודה רבה מעריך מאוד  

 

ציטוט של etal

זאת שגיאה, לפי ההוראות תא #1 אינו נכלל בלולאה ולא היה צריך להופיע בהדפסה.

 

עוד בעיות:

- התוכנה תדפיס את כל הלולאות שיש במערך והדרישה היתה להדפיס רק את הלולאה הראשונה

- התוכנה תיכנס ללולאה אינסופית במערכים מסויימים:(

 

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

 

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

 

 

תודה רבה  

[Jabberwock 454]

ציטוט של etal

זאת שגיאה, לפי ההוראות תא #1 אינו נכלל בלולאה ולא היה צריך להופיע בהדפסה.

כן, צודק. קראתי שוב את התרגיל ובאמת מצויין זאת.

ציטוט של etal

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

גם כן נכון, כבר ציינתי שהקוד שצירפתי הינו רק לבדיקה.

 

ביגלל המקרה הראשון עם #1, חשבתי שיכול לקרות מצב שכמה תאים אחד אחרי השני ולאו דווקא רק תא אחד שמוביל ללולאה.

 

הנה לעשות שוב ניסוי:

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
const int N = 7;
int nums[N] = { 2,5,4,5,17,6,3 };

struct StackWalk {
    int index;
    int value;
    StackWalk* previous;
};

int findTraversedRoute(StackWalk current) {
    if (current.value < 0 || current.value >= N) return -1;
    
    StackWalk* iterator;
    for (iterator = current.previous; iterator && iterator->index != current.value; iterator = iterator->previous);
    
    if (iterator) {
        cout << "current.index " << current.index << " current.value " << current.value;
        return current.index;
    }
    
    StackWalk newWalk;
    newWalk.index = current.value;
    newWalk.value = nums[current.value];
    newWalk.previous = &current;
    return findTraversedRoute(newWalk);
}

int main() {
    for (int i = 0; i < N; i++) {
      StackWalk walk;
      walk.index = i;
      walk.value = nums[i];
      walk.previous = NULL;
      int foundIndex = findTraversedRoute(walk);
      
      if (foundIndex != -1) {
          cout << " firstIndex " << i << endl;
      }
    }
}

current.index 3 current.value 5 firstIndex 1
current.index 6 current.value 3 firstIndex 3
current.index 3 current.value 5 firstIndex 5
current.index 5 current.value 6 firstIndex 6

 

[etal 458]

 

 

int main() {
    int nums[N] = { 2,5,4,5,17,6,3 };
    int found = -1;
    int value;
  
    for (int i = 0; i < N; i++) {
      value = nums[i];
      
      for (int j = 0; j < N; j++) {
          if(value < 0 || value >= N) break;
          if (value == i) {
            found = i;
            break;
          }
          value = nums[value];
      }
      
      if(found != -1) break;
    }
  
    if(found != -1) {
      cout << "index " << found  << endl;
      value = nums[found];
      while(value != found) {
        cout << "index " << value  << endl;
        value = nums[value];
      }
      cout << "index " << value  << endl;
    } else {
      cout << "cannot find loop" << endl;
    }
}

 

נערך 2020 בנובמבר 17 על-ידי etal

[BAR_PC 0]

ציטוט של etal

 

 

int main() {
    int nums[N] = { 2,5,4,5,17,6,3 };
    int found = -1;
    int value;
  
    for (int i = 0; i < N; i++) {
      value = nums[i];
      
      for (int j = 0; j < N; j++) {
          if(value < 0 || value >= N) break;
          if (value == i) {
            found = i;
            break;
          }
          value = nums[value];
      }
      
      if(found != -1) break;
    }
  
    if(found != -1) {
      cout << "index " << found  << endl;
      value = nums[found];
      while(value != found) {
        cout << "index " << value  << endl;
        value = nums[value];
      }
      cout << "index " << value  << endl;
    } else {
      cout << "cannot find loop" << endl;
    }
}

 

תודה רבה!

[Jabberwock 454]

יפה

[Buck 17]

יש פתרון יותר טוב, הסיבוכיות בזמן של הפתרון הזה היא ריבועית. אם תוסיף עוד מערך שבו אתה מסמן אם עברת כבר בתא אז לא תצטרך לעבור בתאים פעמיים ואז תוכל להוריד את זה לO(2n).

[etal 458]

ציטוט של Buck

יש פתרון יותר טוב, הסיבוכיות בזמן של הפתרון הזה היא ריבועית

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

נערך 2020 בנובמבר 23 על-ידי etal