how to solve this problem?

This is a discussion on how to solve this problem? within the C++ Programming forums, part of the General Programming Boards category; If k is known before running the program, then it is easy to write codes to do the following (paragraph ...

  1. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    14

    how to solve this problem?

    If k is known before running the program, then it is easy to write codes to do the following (paragraph 2). But now k is input from keyboard. It is difficult to write codes. Are there some nice way to do this? Thank you very much.
    Code:
    while(1)
    {
    part 1. lambda=...;
    part 2. some codes relates to lambda; when lambda satisfies some conditions; break;
    }
    I would like lambda take following values (in lexicographic order, a value each time, for example, lambda=lambda, then do part 2 above, and then lambda=lambda-2a[1], then do part 2 above, and so on):
    lambda,
    lambda-a[1], lambda-a[2], ..., lambda-a[k-1], (the sum of coefficients of a[i] is -1)
    lambda-2a[1], lambda-a[1]-a[2], lambda-a[1]-a[3], ..., lambda-a[1]-a[k-1], lambda-2a[2], lambda-a[2]-a[3], ..., lambda-a[2]-a[k-1], ..., lambda-a[k-2]-a[k-1], lambda-2a[k-1], (the sum of coefficients of a[i] is -2)
    lamdba-3a[1], ... (the sum of coefficients of a[i] is -3)
    ...

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So that's two loops then, one for the index variable inside the a[], and the other for the multiplier out front.

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    14
    Thank you. But it does not work, since k is unknown before we input it.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote Originally Posted by lijr07
    But it does not work, since k is unknown before we input it.
    Once there is input, its value is known, so what is the problem?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I kind of see what you mean, maybe -- for some reason I thought you were going down columns not across. I don't know why I thought that.

    You _almost_ have a combination-generation problem (since you can have duplicates), but I suspect you can easily adapt a combination-generation algorithm (like the traditional odometer-style algorithm: increment the last number until you get to the max, then add one to the previous and "roll over" the new number).

    Note that you can make a vector that will resize itself as you go, so you can, at the beginning of the loop, push_back another number and now you've got 4 coefficients to play with instead of 3 (for instance).

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    14
    Thank you very much.

    we have to write the code before we know exact value of k. If we know k=2 for example, it is easy to write the code as:

    Code:
    int c[2]; //k=2
    int n;
    
    // n, a[i] are known
    
    while(1)
    {
    
    
    
    for(c[0]=0; c[0]<n; c[0]++)
    {
    
    for(c[1]=0; c[1]<n-c[0]; c[1]++) //c[0] + c[1] = n
    {
    for(i=0; i<2; i++)
    {
    lambda=lambda-c[i]*a[i]; //this loop computes lambda-c[0]*a[0]-...-c[k-1]*a[k-1]
    }
    
    
    {this part have some other codes relates to lambda}
    
    if lambda satisfies some conditions, break;
    
    
    }
    
    if lambda satisfies some conditions, break;
    
    }
    
    if lambda satisfies some conditions, break;
    
    }

    but now k is unknown (if k is known, we can write k loops), so I don't know how to write the codes with arbitrary k.

  7. #7
    Registered User
    Join Date
    Jun 2011
    Posts
    14
    Thank you very much. But the problem is not about resize a vector. It is resize the number of loops. This is difficult. Do you have some method to solve this problems?

  8. #8
    Registered User
    Join Date
    Jun 2011
    Posts
    14
    Quote Originally Posted by tabstop View Post
    I kind of see what you mean, maybe -- for some reason I thought you were going down columns not across. I don't know why I thought that.

    You _almost_ have a combination-generation problem (since you can have duplicates), but I suspect you can easily adapt a combination-generation algorithm (like the traditional odometer-style algorithm: increment the last number until you get to the max, then add one to the previous and "roll over" the new number).

    Note that you can make a vector that will resize itself as you go, so you can, at the beginning of the loop, push_back another number and now you've got 4 coefficients to play with instead of 3 (for instance).
    Thank you very much. But the problem is not about resize a vector. It is resize the number of loops. This is difficult. Do you have some method to solve this problems?

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Perhaps this?
    Code:
    a[0]=0;
    for(int i=0;i<max;++i)
      for(int j=0;j<max;++j)
        for(int k=1;k<max;++k)
          lambda-a[i]-a[j]-a[k];
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by lijr07 View Post
    Thank you very much. But the problem is not about resize a vector. It is resize the number of loops. This is difficult. Do you have some method to solve this problems?
    Since there are always and forever two loops, there is no resizing the number of loops problem.

    ETA: Just to be clear about where the loops start and stop: The code to generate
    lambda-a[1], lambda-a[2], ..., lambda-a[k-1], (the sum of coefficients of a[i] is -1)
    and to generate
    lambda-2a[1], lambda-a[1]-a[2], lambda-a[1]-a[3], ..., lambda-a[1]-a[k-1], lambda-2a[2], lambda-a[2]-a[3], ..., lambda-a[2]-a[k-1], ..., lambda-a[k-2]-a[k-1], lambda-2a[k-1], (the sum of coefficients of a[i] is -2)
    and to generate
    lamdba-3a[1], ... (the sum of coefficients of a[i] is -3)

    is exactly the same code (except for one character difference, where 1 changes to 2 changes to 3). If you are using different code for each of these (for example, extra for loops), then your code is b0rken.
    Last edited by tabstop; 07-29-2011 at 10:26 PM.

  11. #11
    Registered User
    Join Date
    Jun 2011
    Posts
    14
    I have an idea to solve this problem. But it is not successful. I use d[l] to record some value (the other values are obtained from d[l]). Could you help me?

    Code:
    #include <stdio.h>
    
    
    #define max_rank 100
    #define max_length 1000
    
    void copy(int c[max_rank], int e[max_rank], int rank) {
        int i;
    
        
        for (i=0;i<rank;i++) {
            e[i]=c[i];
        }
    }
    int main() {
        int i, j, l, n=4, rank=4;
        
      struct vector
        {
          int a[max_rank];
          int i;  
        };
     typedef struct vector vector; 
     vector d[max_length];
     vector c; 
    
            
    
        for(i=0; i<rank; i++){
             if(i==0){
                 c.a[i]=n;
             }
             else{
                 c.a[i]=0;
    
             }
               
        }
    
        c.i=0;
    
          l=0;
    
           printf("c=");
                        for(j=0; j<rank; j++){
    		        printf("%d, ", c.a[j]);
    		   }
    		   printf("\n"); 
    
           
           while(1){
    
              
           
                for(i=c.i; i<rank-1; i++){
    
                     
    
                      
                       
                         if(c.a[i-1]>0 && i>0){
                             
                              for(j=0; j<rank; j++){
                                    d[l].a[j]=c.a[j];
                              }
                              d[l].i=i;
                            printf("d=");
                                for(j=0; j<rank; j++){
    		        printf("%d, ", d[l].a[j]);
    		   }
    		   printf("\n"); 
                              
    
                              l++;  printf("d[%d].i=%d, l=%d\n",l-1, d[l-1].i,l);            
                         }
                       
                       
                        c.a[i]=c.a[i]-1;
                        c.a[i+1]=c.a[i+1]+1;
    /*
                          if(i==rank-2 && c[rank-2] != 0){
                           i=rank-3;                     
                           
                       } 
    
    */
                       printf("c=");
                        for(j=0; j<rank; j++){
    		        printf("%d, ", c.a[j]);
    		   }
    		   printf("\n");
    
                     
    
                }
    
                           
    
                for(j=0; j<rank; j++){
                                    c.a[j]=d[l-1].a[j];
                }
                c.i=d[l-1].i;
                
                l--;
    
              
                if(l==-1){
                    break;
                }
    
    
           }
             
           
        return 0;
     
    
    }

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    1. Look at what you posted. Single-letter variable names, white space everywhere, inconsistent indentation. If you are actually expecting us to read this code, then please make some attempt at making it readable. (Yes, I've got auto-indenting tools, and I'll use them on your code as soon as I'm done typing, but.)

    2. You have posted in the C++ forum. Are you not intending to use C++? (This is not C++ code.)

    EDIT after reading:
    Okay, these seem like the only two lines that change your values:
    Code:
                        c.a[i]=c.a[i]-1;
                        c.a[i+1]=c.a[i+1]+1;
    All this appears to be doing is switching 0,1 to 1,0; it certainly isn't moving you around anywhere else. Remember your goal: you want to generate all the numbers (I'm using n=4 and k=4 since that's what you appear to have in your program)
    0000,0001,0002,0003,0011,0012,0013,0022,0023,0033, 0111,0112,0113,0122, etc., in that order (or at least that seemed important to you earlier). So you need to repetitively add 1 to the last number, and when that goes over the limit "carry" that overflow back to the left as far as necessary, filling forward with the new number. It's odometer-like, if you remember odometers.
    Last edited by tabstop; 07-29-2011 at 11:01 PM.

  13. #13
    Registered User
    Join Date
    Jun 2011
    Posts
    14
    This is C code. I am sorry I made a mistake to put it here. But I think that C and C++ are similar. The sum of each set of numbers should be 4. But 0000, 0001, 0002, ... do not have this property. I need 4000, 3100, 3010, 3001, 2200, 2110, 2101, 2020, 2011, 2002, 1300, 1210, 1111, 1102, 1021, 1012, 1003, 0400, 0310, 0301, 0220, 0211, 0202, 0130, 0121, 0112, 0103, 0040, 0031, 0022, 0013, 0004. So I use d[l] to record some values. d is a stack.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    No, you want 0000, 0001, 0002, etc. Perhaps to make it clearer, here would be the values for the loop when n = 3:
    000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, .... Notice the numbers still go up to 3 because k=4. The first one (000) represents lambda -a[0]-a[0]-a[0] (or lambda-3a[0]); the next one represents lambda-a[0]-a[0]-a[1] (or lambda-2a[0]-a[1]); the next one represents lambda-a[0]-a[0]-a[2] (or lambda-2a[0]-a[2]), and so on.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please help me to solve this IO problem.
    By nichya88 in forum C++ Programming
    Replies: 2
    Last Post: 01-19-2010, 12:15 PM
  2. Problem I Can't solve...
    By ferniture in forum C Programming
    Replies: 3
    Last Post: 07-15-2008, 03:51 AM
  3. Plz solve my problem !
    By pankaj8096 in forum C Programming
    Replies: 12
    Last Post: 01-16-2003, 12:59 AM
  4. how to solve this problem???
    By moon in forum C++ Programming
    Replies: 3
    Last Post: 01-21-2002, 03:19 AM
  5. problem cant solve please help.
    By sarah in forum C Programming
    Replies: 6
    Last Post: 09-03-2001, 02:32 PM

Tags for this Thread


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