Question in one-dimensional array C ++ - Programming - HWzone Forums
Skip to content
  • Create an account
  • About Us

    Hello Guest!

     
    Please note - in order to participate in our community, comment and open new discussions, you must join as a registered member.

    Our members enjoy many advantages, including the ability to participate in discussions, enjoy raffles and promotions for members of the site, and receive our weekly content directly by email.

    Do not like being harassed by email? You can register for the site but do not submit your registration to the weekly email updates.

Question in a C ++ one-dimensional array


Recommended Posts

Hi guys I have a question in C ++ in a one dimensional array that I am really stuck on I would love to direction and know if I am at all in the direction of some "hints" 

 

Question: (sorry in advance for the length)

For a one-dimensional array of N-cell integers (for N which is a constant of the scheme) it is said that one cell in the array Indicates a second cell in the array if one cell contains the number of the other cell.
for example: In the next array

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





The cell 0 # indicates the cell 2 #, the cell 1 # indicates the cell 5 #, but the cell 4 # does not point to any cell in the array (since the array does not have cell 17 #).

A loop in the above array is a series of cells so that the first points to the second, the second to the third, and so on, until the last cell in the series points to the first cell in the loop.for example: Note that the cell 3 # also points to the cell 5 #, but the cell 6 # is not included in the loop because it does not have to be indicated by another cell in the loop. The cell 1 # indicates the cell 5 # which points to the cell 1 #, but also this cell series does not constitute a loop since the cell 0 # does not point to cell # 2.

Write a plan that defines an array of eight-cell integers, reads data into it, and presents the description of the first loop in the array, that is, the description of the loop so that there is no other loop containing a cell whose number (i.e. its position when counting starts from zero, not the cell value) is lower The lowest cell contained in the 'first' loop. The loop description, (which must be printed), will include all the cell numbers included in the loop (including of course the lowest cell number included in the loop). The first cell, which is also the last cell, will appear at both the beginning and end of the loop.

 

What I've done:

 

 



#include #include // ------ 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; }

 

Thanks again I would love to head :)

Post Reply Direct Link To This Post
Share on other sites
  • To know if it is a loop, you need to save the cell number before entering the test because you will need it to check "Did you get back to the same cell", i.e. if you traced back to the same start cell then it is a loop.
  • if(temp = nums[N_place])

    Note that you only put one equal so this is not a condition but a placement.

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

    Does it seem like you expect the loop to have only 2 iterations? Not listed in the exercise that the number of iterations is fixed.

Post Reply Direct Link To This Post
Share on other sites
Quote of Jabberwock
  • To know if it is a loop, you need to save the cell number before entering the test because you will need it to check "Did you get back to the same cell", i.e. if you traced back to the same start cell then it is a loop.
  • if(temp = nums[N_place])

    Note that you only put one equal so this is not a condition but a placement.

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

    Does it seem like you expect the loop to have only 2 iterations? Not listed in the exercise that the number of iterations is fixed.

 

I understood then I save before the for after I catch ... I corrected the condition, I did not notice, thanks :)

 

True it is not fixed ... it does not run as long as the next after it is worth? I did not understand why it limits to 2? Like the loop ran as long as the cell points to a cell, no?

If not a small hint please please why change the terms?

 

many thanks :)

Post Reply Direct Link To This Post
Share on other sites

I'm thinking of you too ... lol :)

I did a little test:

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

outgoing:

index 1

index 3

index 5

index 6

 

I.e. these are the cell numbers that are in the loop.

What we did not think before is the super case in cell 1, its value 5 and after being followed it does not return to cell 1 but passes in cells 3, 5 and 6.

So I changed it to check the value of the cell (5) and accordingly it will check if it returns to the above value. There may be other cases where this is not the best solution. Try to check

Post Reply Direct Link To This Post
Share on other sites
Quote of Jabberwock

What we did not think before is the super case in cell 1, its value 5 and after being followed it does not return to cell 1 but passes in cells 3, 5 and 6.

Therefore I changed it to check the value of the cell (5) and accordingly it will check if it returns to the above value.

This is an error, according to the instructions Cell # 1 is not included in the loop and should not have appeared in print.

 

More problems:

- The software will print all the loops in the array and the requirement was to print only the first loop

- The software will enter an infinite loop in certain arrays :(

 

But it's definitely in the right direction in my opinion, just needs some small fixes

Edited By etal
Post Reply Direct Link To This Post
Share on other sites
Quote of Jabberwock

I'm thinking of you too ... lol :)

I did a little test:

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

outgoing:

index 1

index 3

index 5

index 6

 

I.e. these are the cell numbers that are in the loop.

What we did not think before is the super case in cell 1, its value 5 and after being followed it does not return to cell 1 but passes in cells 3, 5 and 6.

So I changed it to check the value of the cell (5) and accordingly it will check if it returns to the above value. There may be other cases where this is not the best solution. Try to check

 

Thank you very much :) True cell 1 is the catch here ... in my opinion a condition before the second for of if the value of the cell is equal to the cell? With break? The problem is that it did not solve hah it did not print anything .. I will try to find something thank you very much appreciate very much :) 

 

Quote of etal

This is an error, according to the instructions Cell # 1 is not included in the loop and should not have appeared in print.

 

More problems:

- The software will print all the loops in the array and the requirement was to print only the first loop

- The software will enter an infinite loop in certain arrays :(

 

But it's definitely in the right direction in my opinion, just needs some small fixes

 

I was thinking about a condition at the entrance to the second for that if the value of the cell is equal to the cell and at the end break but it did not solve..possible please a small direction? I'm trying to think.

 

 

Thank you :) 

Post Reply Direct Link To This Post
Share on other sites
Quote of etal

This is an error, according to the instructions Cell # 1 is not included in the loop and should not have appeared in print.

Yes you are right. I read the exercise again and it's really great.

Quote of etal

The software will print all the loops in the array and the requirement was to print only the first loop

Also true, I have already mentioned that the code I attached is for testing only.

 

Because of the first case with # 1, I thought a situation could happen where several cells one after the other and not necessarily just one cell leading to a loop.

 

Here is an experiment again:

#include 
#include 
using std::China;
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

 

Post Reply Direct Link To This Post
Share on other sites

 

 

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

 

Edited By etal
Post Reply Direct Link To This Post
Share on other sites
Quote of 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;
    }
}

 

Thank you!

Post Reply Direct Link To This Post
Share on other sites

There is a better solution, the time complexity of this solution is quadratic. If you add another array where you mark if you have already moved in the cell then you will not have to go through the cells twice and then you can lower it to O (2n).

Post Reply Direct Link To This Post
Share on other sites
Quote of Buck

There is a better solution, the time complexity of this solution is quadratic

This is true, with the help of an auxiliary array it is probably possible to arrive at a more efficient solution although it seems to me that the algorithm will be more complex than you describe.

Edited By etal
Post Reply Direct Link To This Post
Share on other sites

Join the discussion

You can then join the discussion and then join our community. If you already have an account with us, please Log in now To comment under your username.
Note that: The comment will appear to the surfers after approval by the board management team.

guest
Add a comment

×   The content pasted is with formatting.   Remove formatting

  Only 75 emoji are allowed.

×   Your link has been automatically assimilated.   Show as regular link

×   Your previous content has been automatically restored.   Clear all

×   You can not paste images directly. Upload or insert images from URL.

×
  • Create new ...

At the top of the news:

New: NVIDIA's Ampere Small

Three different manufacturers are adopting a particularly compact Mini-ITX configuration for the GeForce RTX 3060, so that even miniature computer systems can enjoy the benefits of the new generation - in case the availability does not disappoint once again

new on the site

You have an update

You have an update

Buzz Zone: The Instagram spaces #buzzzone You have an update A photo posted by HWzone.co.il (@ hwzone.co.il) on 2021-01-20 16:09:29 You have an update