שאלה במערך חד מימדי C++ - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

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


BAR_PC
 Share

Recommended Posts

היי חבר'ה יש לי שאלה במ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 ;
}

 

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

קישור לתוכן
שתף באתרים אחרים

  • בשביל לדעת האם זאת לולאה, אתה צריך לשמור את מספר התא לפני שאתה נכנס לבדיקה מכיוון שתצרך אותו בשביל לבדוק "האם הגעת  חזרה לאותו תא", כלומר אם עקבת בחזרה לאותו תא ההתחלה אז זוהי לולאה.
  • if(temp = nums[N_place])

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

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

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

קישור לתוכן
שתף באתרים אחרים

ציטוט של Jabberwock
  • בשביל לדעת האם זאת לולאה, אתה צריך לשמור את מספר התא לפני שאתה נכנס לבדיקה מכיוון שתצרך אותו בשביל לבדוק "האם הגעת  חזרה לאותו תא", כלומר אם עקבת בחזרה לאותו תא ההתחלה אז זוהי לולאה.
  • 
    if(temp = nums[N_place])

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

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

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

 

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

 

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

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

 

המון תודה :)

קישור לתוכן
שתף באתרים אחרים

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

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

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) ולפי זה יעקוב אם חוזר לערך הנ"ל. אולי יש עוד מקרים בהם זה לא הפתרון המיטבי. תנסה לבדוק

קישור לתוכן
שתף באתרים אחרים

ציטוט של Jabberwock

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

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

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

 

עוד בעיות:

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

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

 

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

נערך על-ידי etal
קישור לתוכן
שתף באתרים אחרים

ציטוט של 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 אבל זה לא פתר..אפשר בבקשה כיוון קטן? אני מנסה לחשוב..

 

 

תודה רבה :) 

קישור לתוכן
שתף באתרים אחרים

ציטוט של 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

 

קישור לתוכן
שתף באתרים אחרים

 

 

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;
    }
}

 

נערך על-ידי etal
קישור לתוכן
שתף באתרים אחרים

ציטוט של 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;
    }
}

 

תודה רבה!

קישור לתוכן
שתף באתרים אחרים

ציטוט של Buck

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

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

נערך על-ידי etal
קישור לתוכן
שתף באתרים אחרים

הצטרפ/י לדיון

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

אורח
הוסף תגובה

×   התוכן שהודבק הוא עם עיצוב.   הסר עיצוב

  Only 75 emoji are allowed.

×   הקישור שלך הוטמע אוטומטית.   הצג כקישור רגיל

×   התוכן הקודם שלך שוחזר אוטומטית.   נקה הכל

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
  • צור חדש...