Announcement

Collapse
No announcement yet.

[Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 6

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • [Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 6

    Chủ đề: backtracking
    Attached Files
    Last edited by toannv; 21-07-2015, 17:23.

  • #2
    Draft code nè các bạn

    PHP Code:
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    char** letterCombinations(chardigitsintreturnSize) {
        
    strcpy(digits,"23");
        
    char tel[9][3] = {{' ',' ',' '},{' ',' ',' '},{'a','b','c'},{'d','e','f'},{'g','h','i'}};
        
    int i,j,S1,S2;
        
        
    S1 digits[0] - '0';
        
    S2 digits[1] - '0';
        
    /* Do chỉ có 23 nên dùng 2 vòng lặp , nếu là 873 thì sẽ 3 vòng lặp in ra tel[0][i], tel[1][j], tel[2][k] */
        
    for (i=0i<3i++)
            for (
    j=0j<;j++)
                
    printf("%c%c ",tel[S1][j],tel[S2][j]);
        
        
        return 
    NULL;

    Comment


    • #3
      Minh họa chuyển qua đệ qui
      PHP Code:
      #include <stdio.h>
      #include <string.h>
      char tel[9][3] = {{' ',' ',' '},{' ',' ',' '},{'a','b','c'},{'d','e','f'},{'g','h','i'}};
      char result[3];
      void DeQui(chardigits,int n)
      {
          
      int i,j,S;
          
          if (
      n<0
          {
              
      printf("%s\n",result);
              return;
          }
          
      digits[n] - '0';
          for (
      i=0i<3i++)
          {    
              
      result[n]=tel[S][i];
              
      DeQui(digits,n-1);
          }
          
      }

      main()
      {
          
      DeQui("23",1);

      Comment


      • #4
        Accepted
        PHP Code:
        class Solution {
        public:
            
        vector <stringres;
            
        char l[100];
            
        string t[8]= {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            
        string d;
            
        int n;
            
        vector<stringletterCombinations(string digits) {
                
        d=digits;
                
        n=digits.length();
                if (
        digits!=""
                
        back(0);
                return 
        res;
            }
           
        void save(string l)
            { 
                
        res.push_back(l);
            }
           
        void back(int i)
            {
               
                    for (
        int k=0k<t[d[i]-50].size(); k++)
                    {
                        
        l[i]=t[d[i]-50][k];
                        if (
        i<n-1back (i+1);
                        else 
        save(l);
                    }
            }


        }; 

        Comment


        • #5
          Code chưa submit, ae xem hộ

          PHP Code:
          #include <stdio.h>
          #include <stdlib.h>
          #include <string.h>

          int slip_num(int num)
          {
              
          int temp 0;
              while (
          num/10!=0)
              {
                  
          temp+=num%10;
                  
          temp*=10;
                  
          num num/10;
              }
              
          temp+=num;
              return 
          temp;
          }

          void Try(int num,int sizechar *result)
          {
              
          int letter [] = {97,100,103,106,109112,116,119};
              
          int temp num%10;
              
          temp-=2;
              
              for (
          int i 0i<letter[temp+1]- letter[temp]; i++)
              {
                  
          result[size] = letter[temp]+i;
                  if(
          num/10!=0)
                      Try(
          num/10size+1result);
                  else
                  {
                      for (
          int  k 0k<= size;k++)
                          
          printf("%c"result[k]);
                      
          printf("\n");    
                  }        
              }
          }

          int main()
          {
              
          char digits[] = "\"456\"";
              
          char *pch;
              
          pch digits+1;
              
          strncpy(pchdigits+1,strlen(digits+1)-1);
              
          pch[strlen(pch) ] = '\0';
              
          int num atoi(pch);
              
          num slip_num(num);
              
          char result [10];
              Try(
          num,0result);


          PHP Code:
          input456
          output

          gjm
          gjn
          gjo
          gkm
          gkn
          gko
          glm
          gln
          glo
          hjm
          hjn
          hjo
          hkm
          hkn
          hko
          hlm
          hln
          hlo
          ijm
          ijn
          ijo
          ikm
          ikn
          iko
          ilm
          iln
          ilo

          --------------------------------
          Process exited after 0.01157 seconds with return value 0
          Press any key to 
          continue . . . 
          :beauty:
          Last edited by 14520981; 22-07-2015, 09:42.
          Share to be shared !
          http://thientoan.info

          Comment


          • #6
            Bài N-Queens viết theo 2 cách

            PHP Code:
            #include <stdio.h>
            #include <string.h>
            #define MAX 6

            main()
            {
                
            int D[MAX],C1[MAX*2],C2[MAX*2];
                
            int i0,i1,i2,i3,i4,i5;

                for (
            i0=0i0<MAXi0++) 
                {
                    
            D[i0]=0;
                    
            C1[i0*2]=0;C1[i0*2+1]=0;
                    
            C2[i0*2]=0;C2[i0*2+1]=0;
                }
                
                for (
            i0=0i0<MAXi0++)
                    if ((
            D[i0]==0) && (C1[i0+0]==0) && (C2[i0-0+MAX]==0))        
                    {
                        
            D[i0]=1C1[i0+0]=1C2[i0-0+MAX]=1;
                        for (
            i1=0i1<MAXi1++)
                            if ((
            D[i1]==0) && (C1[i1+1]==0) && (C2[i1-1+MAX]==0))        
                            {
                                
            D[i1]=1C1[i1+1]=1C2[i1-1+MAX]=1;
                                for (
            i2=0i2<MAXi2++)
                                    if ((
            D[i2]==0) && (C1[i2+2]==0) && (C2[i2-2+MAX]==0))        
                                    {
                                        
            D[i2]=1C1[i2+2]=1C2[i2-2+MAX]=1;
                                        for (
            i3=0i3<MAXi3++)
                                            if ((
            D[i3]==0) && (C1[i3+3]==0) && (C2[i3-3+MAX]==0))        
                                                {
                                                    
            D[i3]=1C1[i3+3]=1C2[i3-3+MAX]=1;
                                                    for (
            i4=0i4<MAXi4++)
                                                        if ((
            D[i4]==0) && (C1[i4+4]==0) && (C2[i4-4+MAX]==0))        
                                                            {
                                                                
            D[i4]=1C1[i4+4]=1C2[i4-4+MAX]=1;
                                                                for (
            i5=0i5<MAXi5++)
                                                                    if ((
            D[i5]==0) && (C1[i5+5]==0) && (C2[i5-5+MAX]==0))        
                                                                        {
                                                                            
            D[i5]=1C1[i5+5]=1C2[i5-5+MAX]=1;
                                                                            
            printf("%d %d %d %d %d %d\n",i0,i1,i2,i3,i4,i5);
                                                                            
            D[i5]=0C1[i5+5]=0C2[i5-5+MAX]=0;
                                                                        }
                                                                
            D[i4]=0C1[i4+4]=0C2[i4-4+MAX]=0;
                                                            }
                                                    
            D[i3]=0C1[i3+3]=0C2[i3-3+MAX]=0;
                                                }
                                        
            D[i2]=0C1[i2+2]=0C2[i2-2+MAX]=0;
                                    }
                                
            D[i1]=0C1[i1+1]=0C2[i1-1+MAX]=0;
                            }
                        
            D[i0]=0C1[i0+0]=0C2[i0-0+MAX]=0;
                    }    
                

            PHP Code:
            #include <stdio.h>
            #include <string.h>
            #define MAX 8

            int D[MAX],C1[MAX*2],C2[MAX*2];
            int result[MAX];
            void DeQui(int n)
            {
                
            int i;
                if (
            n==MAX)
                {
                    for (
            i=0i<MAXi++) printf("%d ",result[i]);
                    
            printf("\n");
                    return;
                }
                
                for (
            i=0i<MAXi++)
                    if ((
            D[i]==0) && (C1[i+n]==0) && (C2[i-n+MAX]==0))        
                    {
                        
            D[i]=1C1[i+n]=1C2[i-n+MAX]=1;
                        
            result[n]=i;    
                        
            DeQui(n+1);
                        
            D[i]=0C1[i+n]=0C2[i-n+MAX]=0;
                    }    
                
            }

            main()
            {
                
            int i0,i1,i2,i3,i4,i5;

                for (
            i0=0i0<MAXi0++) 
                {
                    
            D[i0]=0;
                    
            C1[i0*2]=0;C1[i0*2+1]=0;
                    
            C2[i0*2]=0;C2[i0*2+1]=0;
                }
                
                
            DeQui(0);

            Attached Files

            Comment


            • #7
              không hiểu sao chỉ đổi biến res từ char thành string thì lại không ra đúng kết quả :cry:

              PHP Code:
              string tel[8] = {"abc""def""ghi""jkl""mno""pqrs""tuv""wxyz"};
              class 
              Solution {

              public:
                  
              vector<stringresult;
                  
              string res;
                  
              vector<stringletterCombinations(string digits
                  {
                      
              int k 0;
                      
              int n digits[0] - '0' 2;
                      if (
              >= && <= 7)
                      {
                          if (
              == || == 7)
                              
              4;
                          else 
              3;
                      }
                      for (
              int i 0ki++)
                      {
                          
              res[res.length()] = tel[n][i];
                          if (
              digits.length() > 1)
                              
              letterCombinations(&digits[1]);
                          else
                              
              result.push_back(res);
                          
              res[res.length() - 1] = '\0';
                      }
                      return 
              result;
                  }
              };
              /*Input:
              "2"
              Output:
              ["","",""]
              Expected:
              ["a","b","c"]*/ 
              PHP Code:
              string tel[8] = {"abc""def""ghi""jkl""mno""pqrs""tuv""wxyz"};
              class 
              Solution {

              public:
                  
              vector<stringresult;
                  
              char res[100];
                  
              vector<stringletterCombinations(string digits
                  {
                      
              int k 0;
                      
              int n digits[0] - '0' 2;
                      if (
              >= && <= 7)
                      {
                          if (
              == || == 7)
                              
              4;
                          else 
              3;
                      }
                      for (
              int i 0ki++)
                      {
                          
              res[strlen(res)] = tel[n][i];
                          if (
              digits.length() > 1)
                              
              letterCombinations(&digits[1]);
                          else
                              
              result.push_back(res);
                          
              res[strlen(res) - 1] = '\0';
                      }
                      return 
              result;
                  }
              };
              //Accepted 

              Comment

              LHQC

              Collapse
              Working...
              X