Thread: backtracking problem

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    11

    backtracking problem

    i have to make a program that reads m,n from the keyboard.
    i have :
    Code:
    char letters[]={'A','B','C','D','E','F','G','H','I','J','K'}
    the program is going to make commutations of those letters.
    if n=2 and m=4 the output will look something like this :
    AB,AC,BA,BC ... etc
    so it will take the 4 starting letters and make groups of 2.
    this is the program that i done so far...
    but at the fuction Valid() i am missing something
    i didn't manage to figure what. All help is welcomed.
    Sorry for the bad english.
    Code:
    #include <stdio.h>
    
    int m,n;
    
    int st[11];
    
    char litere[]={'A','B','C','D','E','F','G','H','I','J','K'};
    
    void Init(int st[],int k)
    
      {
    
        st[k]=0;
    
      }
    
    int Am_Succesor(int st[],int k)
    
      {
    
        if(st[k]<n)
    
          {
    
    	st[k]++;
    
    	return 1;
    
          }
    
        else return 0;
    
      }
    
    int Valid(int st[],int k)
    
      {
    
        int i;
    
        for(i=1;i<k;i++)
    
          if(st[k]==st[i]) return 0;
    
          return 1;
    
      }
    
    int Solutie(int k)
    
      {
    
         if(k==n) return 1;
    
         else return 0;
    
      }
    
    void Tipar()
    
      {
    
        int i;
    
        for(i=1;i<=n;i++)
    
          printf("&#37;c",litere[st[i]]);
    
          printf("\n");
    
      }
    
    void back()
    
      {
    
        int k;
    
        int As,Ev;
    
        k=1;
    
        Init(st,k);
    
        while(k>0)
    
          {
    
    	do
    
    	  {
    
    	    As=Am_Succesor(st,k);
    
    	    if(As==1) Ev=Valid(st,k);
    
    
    
    	  }while((As==1)&&(Ev==0));
    
    	if(As)
    
    	  if(Solutie(k)) Tipar();
    
    	  else
    
    	    {
    
    	      k++;
    
    	      Init(st,k);
    
    	    }
    
    	  else k--;
    
          }
    
      }
    
    int main(void)
    
      { 
    
        printf("m="); scanf("%d",&m);
    
        printf("n="); scanf("%d",&n);
    
        back();
    
        return 0;
    
      }
    in the program i done so far if i put m=4 and n=2 i get : BC CB only .
    Last edited by samsung; 05-27-2008 at 02:30 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Several points.
    1. Don't double space all your code. It's basically twice as long as it needs to be.

    2. for(i=1;i<=n;i++)
    Arrays start at 0, not 1.

    3. Don't use global variables.

    4. If you absolutely must have global variables, then don't have locals with the same name.

    5. Look at Tipar(). Is the newline meant to be part of the for loop? By indentation, it sure looks like it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    11
    Quote Originally Posted by Salem View Post
    Several points.
    1. Don't double space all your code. It's basically twice as long as it needs to be.

    2. for(i=1;i<=n;i++)
    Arrays start at 0, not 1.

    3. Don't use global variables.

    4. If you absolutely must have global variables, then don't have locals with the same name.

    5. Look at Tipar(). Is the newline meant to be part of the for loop? By indentation, it sure looks like it.
    1. sorry it happen when i pasted it i have it indented nice in a old Dos IDE
    2. yes but that fuction is only for printing to the screen even if i do start i=0 the outcome is : AB,AC ....
    3. I know is a bad practice but that is how they ask for the project in school
    5. The "\n" it's outside of the for just an indentation typo anyway its not included in the for anyway.

    The problem is at the Valid() function. It needs more conditions.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 05:46 PM