1000 Lockers Problem

This is a discussion on 1000 Lockers Problem within the C Programming forums, part of the General Programming Boards category; Hey, I have a question to solve. There are 1000 lockers all in a row, all closed at first. Starting ...

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    104

    Post 1000 Lockers Problem

    Hey, I have a question to solve.
    There are 1000 lockers all in a row, all closed at first.
    Starting at the second locker and going to all even no. lockers, open it if closed (and close it if open).
    Then start at the 3rd locker (opening if closed, closing if open) and going to the 6th...9th...
    Then starting at the 4th locker and going on. (4th, 8th, 12th...)
    Then the 5th...going...

    I'm suppose to know how many lockers are open and closed after going through all the recursions.

    This is what I have so far
    btw, what is "unreachable code?"

    Code:
    #include <stdio.h>
    #include <conio.h>
    #define OPEN 1
    #define CLOSE 0
    #define LAST 1000
    void main (void) {
    
    int locker[1001];
    int close_count=0, open_count=0;
    int i, a, start, j, n, p, z=1;
    
    locker[0]=-1;
    
    for (i=1; i<=LAST; i++) locker[1]=0;
    
    
    for (start=2; start<=LAST; start++) {
    
    	for (j=start; j<=LAST; j=((z++)*j)) {
    		if (LAST%j==0) {
    			for (n=j; j<=LAST; j++) {
    				if (locker[j]==CLOSE) locker[j]=OPEN;
    				if (locker[j]==OPEN) locker[j]=CLOSE;}
    				}
    		else
    			{for (n=j; j<=((LAST%j)*j); j++) {
    				if (locker[j]==CLOSE) locker[j]=OPEN;
    				if (locker[j]==OPEN) locker[j]=CLOSE;}
    		 }
    	}
    }
    
    for (a=1; a<=LAST; a++) {
    	if (locker[a]==0) close_count++;
    	if (locker[a]==1) open_count++;
    	}
    printf ("Number of open lockers are %d", open_count);
    printf ("Number of close lockers are %d", close_count);
    }
    Last edited by Hexxx; 11-20-2003 at 08:57 PM.

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    >btw, what is "unreachable code?"
    Code:
    for (i=1; 1<=LAST; i++) locker[1]=0;
    When is one not less than 1000?
    Last edited by Dave_Sinkula; 11-20-2003 at 08:35 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    104
    darn! ok, I changed that 1 to a i, but still doesn't work.

  4. #4
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    This might work I don't have a compiler on me to test but here is the gerneral algorythm. Maybe atleast i probably have a major flaw.
    Code:
    #inlcude <stdio.h>
    
    int main(void){
    	int x, locker[1000];
    	int shift=2;
    	do{
    		for(x=0;x<1000;x++)
    			locker[x]=0;
    		for(x=shift;x<1000;x+=shift){
    			if(locker[x]==1)
    				locker[x]=0;
    			else
    				locker[x]=1;
    		}
    		shift++;
    	while(shift!=1000);
    	return 0;
    }
    This is also the first time I found a use for the do while loop:-)

  5. #5
    Registered User
    Join Date
    Oct 2003
    Posts
    104
    what does

    int shift=2;


    do?

  6. #6
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    that is the variable that tells where to start and how much to increment. You start on 2 and increment by 2 everytime then you start on 3 and increment by 3 everytime.

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,659
    Code:
    #define OPEN 1
    #define CLOSED 0
    
    int
     main()
    {
     const int total = 1000;
     
     int lockers[total] = { CLOSED };
     
     int index, inc;
    
     int opened = 0, closed = 0;
     
        for(inc = 2; inc != total; ++inc)
       {
           for(index = inc - 1;  index + inc < total;  index += inc)
          {
              if(lockers[index] == CLOSED)
               lockers[index] = OPEN;
    
              else
               lockers[index] = CLOSED;
          }
    
       }
        for(index = 0; index < total; ++index)
       {
           if(lockers[index] == OPEN)
            ++opened;
            
           else
            ++closed;
       }
       
     printf("There are %d lockers open and %d closed.\n", opened, closed);
    
     return EXIT_SUCCESS;
    }



    ITSA
    Socket Library!

  8. #8
    Registered User
    Join Date
    Oct 2003
    Posts
    104
    how come my logic doesn't work?

    btw, when I use the code above for 2 lockers, shouldn't I get 1 closed and 1 opened? I get both closed...
    Last edited by Hexxx; 11-20-2003 at 11:04 PM.

  9. #9
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    There are a number of reasons for your code not working, but one of the main reasons is here:
    Code:
      // if locker[j] is closed, we open it,
      // if locker[j] is already open we leave it that way ...
      if (locker[j]==CLOSE) locker[j]=OPEN;
    
      // ... either way when we get to this line locker[j] is
      // always open so we close it.
      if (locker[j]==OPEN) locker[j]=CLOSE;}
    The result is that we always end up with all the lockers closed.

    Here is a corrected C version of Sebastiani's code:
    Code:
    #define OPEN 1
    #define CLOSED 0
    #define N_LOCKERS 1000
    
    int main(void)
    { 
      int lockers[N_LOCKERS] = { CLOSED };
      int index, inc;
      int opened = 0, closed = 0;
     
      for(inc = 2; inc <= N_LOCKERS; ++inc) {
        for(index = inc - 1; index < N_LOCKERS; index += inc) {
          if (lockers[index] == OPEN)
            lockers[index] = CLOSED;
          else
            lockers[index] = OPEN;
        }
      }
    
      for(index = 0; index < N_LOCKERS; ++index) {
        if(lockers[index] == OPEN)
          ++opened;
        else
          ++closed;
      }
       
      printf("There are %d lockers open and %d closed.\n", opened, closed);
    
      return 0;
    }
    HTH,
    DavT
    -----------------------------------------------

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  3. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 05:24 PM
  4. Replies: 5
    Last Post: 11-07-2005, 10:34 PM
  5. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21