Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 19 kết quả

Đề tài: Điền dấu +/- vào giữa các chữ số để có Tổng = n bằng phương pháp Quay lui?

  1. #1
    Ngày gia nhập
    04 2010
    Bài viết
    7

    Angry Điền dấu +/- vào giữa các chữ số để có Tổng = n bằng phương pháp Quay lui?

    điền dấu +/- vào giữa các chữ số: 123456789 (theo đúng thứ tự) để tạo thành 1 biểu thức có giá trị =n.
    Với n là 1 số nguyên dương cho trước.

    VD: với n=12 một trong những đáp án là: 123+ 45- 67- 89
    Ai giúp mình ý tưởng để giải quyết bài này với, code mình sẽ cố gắng tự làm.

  2. #2
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi teaser Xem bài viết
    điền dấu +/- vào giữa các chữ số: 123456789 (theo đúng thứ tự) để tạo thành 1 biểu thức có giá trị =n.
    Với n là 1 số nguyên dương cho trước.

    VD: với n=12 một trong những đáp án là: 123+ 45- 67- 89
    Ai giúp mình ý tưởng để giải quyết bài này với, code mình sẽ cố gắng tự làm.
    Chơi bài khó thế này, mất buổi chiều của mình. Mình trình bày giải thuật nhé:
    PHP Code:
    1. Hàm insert() đưa xâu "123456789" về xâu "1*2*3*4*5*6*7*8*9"
    2. Vị trí các dấu có thể
         - 
    giữ nguyên dấu *: hiểu là các số được viết liền nhau1*12.
         
    Thay bởi dấu +: hiểu là phép trừ1-= -1.
         
    Thay bởi dấu +: hiểu là phép cộng1+2=3. 
         Việc hiểu này dành cho hàm 
    eval().
    3. Hàm Try() được cài đặt đệ quy phù hợp với giải thuật quay lui
    Nó lần lượt thử các vị trí có dấu bởi 3 khả năng trên.
     
    Với mỗi phép thử của nóhàm eval() được gọi để evaluate giá trị của xâu,
     
    tương ứng với biểu thức do hàm removemultsign() trả về.
     
    Nếu khớp với giá trị sum mong muốn thì printf ra thôi.
     
    Thực chất của quay lui được thực hiện bởi câu lệnh str[k] = chđó
    Mình đưa code ra để tham khảo nhé. Mình sử dụng nhiều con trỏ char để các new members tham khảo về kỹ thuật này.
    Nhớ phản hồi lại nhé. Chú ý đừng có space trong xâu nhé, mình chưa nghĩ ra cách bỏ chúng đi đâu, hix.
    C++ Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #define max 100
    4.  
    5. int isdigit(char ch) {return '0' <= ch && ch <= '9';}
    6. int isoperator(char ch) {return ch == '+' ? 1: -1;}
    7. int ismultsign(char ch) {return ch == '*';}
    8.  
    9. long eval(char *str)
    10. {
    11.     long val = 0;
    12.     char sign = '+';
    13.     long temp = 0;
    14.     int k = 0;
    15.     char *ptr = str;
    16.     while (*ptr)
    17.         {
    18.             if (isdigit(*ptr))
    19.                 temp = temp*10 + *ptr - '0';
    20.             else if(!ismultsign(*ptr))
    21.                 {
    22.                     val = val + isoperator(sign)*temp;
    23.                     temp = 0;
    24.                     sign = *ptr;
    25.                 }
    26.             ptr ++;
    27.         }
    28.    
    29.     return val + isoperator(sign)*temp;
    30. }
    31.  
    32. char *insert(char *str)
    33. {
    34.     char *temp = (char *) malloc(2*max);
    35.     char *ptr = str;
    36.     int k = 0;
    37.     while (*ptr)
    38.         {
    39.             k+=2;
    40.             temp[k-2] = *ptr;
    41.             temp[k-1] = '*';
    42.             ptr ++;
    43.         }
    44.     temp[k-1] = 0;
    45.     return temp;
    46. }
    47.  
    48. char *removemultsign(char *str)
    49. {
    50.     char *temp = (char *) malloc (max);
    51.     char *ptr = temp;
    52.     while (*str)
    53.         {
    54.             if(!ismultsign(*str))
    55.                 {
    56.                     *ptr = *str;
    57.                     ptr++;
    58.                 }
    59.             str++;
    60.         }
    61.     *ptr = 0;
    62.     return temp;
    63. }
    64.  
    65.  
    66. void Try(char *str, int k, int sum)
    67. {  
    68.     if (*(str+k))
    69.         for (int j = 0; j < 3; j++)
    70.             {
    71.                 char ch = str[k];
    72.                 if (j==1) str[k] = '-';
    73.                 else if (j==2) str[k] = '+';
    74.                 long num = eval(str);
    75.                 if (num == sum)
    76.                     {
    77.                         char *temp = removemultsign(str);
    78.                         printf("\n%s = %d\n",temp, sum);
    79.                         free (temp);
    80.                     }
    81.                 Try(str,k+2,sum);
    82.                 str[k] = ch;
    83.             }
    84. }
    85.  
    86. void main()
    87. {
    88.     char str[] = "123456789";
    89.     char *ptr = insert(str);
    90.     Try(ptr,1,12);
    91.     free (ptr);
    92. }
    Đã được chỉnh sửa lần cuối bởi onminh : 13-04-2010 lúc 06:19 PM. Lý do: Thêm: Chú ý...

  3. #3
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,007

    em đọc hoa hết cả mắt mới tắm được tư tưởng, về quay lui thì e hiểu nhưng cũng chưa sâu lắm,


    Chú ý đừng có space trong xâu nhé, mình chưa nghĩ ra cách bỏ chúng đi đâu, hix. << chỗ này e ko hiểu ý anh, xóa space đi thì có gì khó đâu
    ^_,^

    Facebook : https://www.facebook.com/langmaninternet

    Bùi Tấn Quang

  4. #4
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi langman Xem bài viết
    em đọc hoa hết cả mắt mới tắm được tư tưởng, về quay lui thì e hiểu nhưng cũng chưa sâu lắm,


    Chú ý đừng có space trong xâu nhé, mình chưa nghĩ ra cách bỏ chúng đi đâu, hix. << chỗ này e ko hiểu ý anh, xóa space đi thì có gì khó đâu
    Chủ topic đâu mà không thấy phản hồi nhỉ, chán ghê. Langman này, mình nghĩ xóa space trong xâu cũng khó đấy chứ, member nào biết mách giùm với.
    Tối nay đọc code của tnglinh mới hoa cả mắt, lại code luôn cho rồi, về hậu tố trong ký pháp Ba Lan. Cũng mệt, nhưng vui phết.
    Đã được chỉnh sửa lần cuối bởi onminh : 14-04-2010 lúc 12:43 AM.

  5. #5
    Ngày gia nhập
    10 2009
    Nơi ở
    Close All
    Bài viết
    993

    Em có code bài xóa space trong chuỗi,làm hồi năm nhất cho nên dài và chưa tối ưu nhìn là thấy oải rồi vì hồi đó còn gà gà.
    Mà giờ lười code lại nên cứ vứt lên đây :
    PHP Code:
    void xoatrang(char s[])
    {
        
    int i,j,n;
        
    n=strlen(s);
        if(
    n==0);
        else
        {
            
    i=0;
            while(
    s[0]==' '&&i<n)
            {
                for(
    j=0;j<n;j++)
                 
    s[j]=s[j+1];
                 
    n=n-1;
            }
            for(
    i=0;i<n;i++)
            {
                if(
    s[i]==' '&&s[i+1]==' '&&i<n)
                {
                     for(
    j=i;j<n;j++)
                       
    s[j]=s[j+1];
                       
    n=n-1;
                       
    i=i-1;
                }
                
            }
            
    i=n-1;
            while(
    s[n-1]==' '&&i<n)
            {
                for(
    j=i;j<n;j++)
                 
    s[j]=s[j+1];
                 
    n=n-1;
            }
        }


  6. #6
    Ngày gia nhập
    04 2010
    Bài viết
    7

    Mặc định Điền dấu +/- vào giữa các chữ số để có Tổng = n bằng phương pháp Quay lui?

    Hic, đi học sáng chiều giờ mới on dc
    thx bạn đã hỗ trợ

    Nhưng mình vẫn chưa hiểu hàm Try()
    biến k để làm gì vậy bạn?

  7. #7
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi teaser Xem bài viết
    Hic, đi học sáng chiều giờ mới on dc
    thx bạn đã hỗ trợ

    Nhưng mình vẫn chưa hiểu hàm Try()
    biến k để làm gì vậy bạn?
    Lời hỏi không rõ @, nhưng cũng trả lời luôn: Trong giải thuật quay lui, người ta xây dựng dần dần từng thành phần của phương án bằng cách thử mọi able. Biến k là xét đến mọi khả năng có thể của thành phần thứ k. Biến này phải ở dạng tham trị, nếu tham biến thì vứt đi luôn.

  8. #8
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,007

    Trích dẫn Nguyên bản được gửi bởi onminh Xem bài viết
    Chủ topic đâu mà không thấy phản hồi nhỉ, chán ghê. Langman này, mình nghĩ xóa space trong xâu cũng khó đấy chứ, member nào biết mách giùm với.
    Tối nay đọc code của tnglinh mới hoa cả mắt, lại code luôn cho rồi, về hậu tố trong ký pháp Ba Lan. Cũng mệt, nhưng vui phết.
    em hiểu ý thầy rồi, xóa và loại bỏ , có thể và ko thể, .....................






    Về việc loại bỏ :

    nếu như này :
    PHP Code:
    char *xau="lang man" 
    thì việc loại bỏ dấu cách là ko thể , nhất là đối với các trình biên dịch chuẩn như VS2008 và VS2010 chẳng hạn

    nhưng nếu
    PHP Code:
    char xau[]="lang man" 
    thì có thể loại bỏ









    ví dụ

    PHP Code:
    #include "iostream"
    using namespace std;


    void bkitu(char *xau,int v,int s=1)   //v là vị trí tính từ 0, s là số lượng các kí tự bị xóa , bkitu : bỏ kí tự ko cần thiết trong 1 xâu
    {
        
    v+s-1>strlen(xau)?*xau=NULL:xau[v]=xau[v+s],v+s<strlen(xau)?bkitu(xau,v+1,s):0;
    }
    void bc(char *xau,int i=0// bỏ cách
    {
        
    i<strlen(xau)?bc(xau,i+1),xau[i]==0x20?bkitu(xau,i):0:0;
    }
    void main()
    {
        
    char xau[]="lang man";
        
    bc(xau);
        
    cout<<xau;

        
    system("pause");

    Đã được chỉnh sửa lần cuối bởi langman : 15-04-2010 lúc 12:59 AM.
    ^_,^

    Facebook : https://www.facebook.com/langmaninternet

    Bùi Tấn Quang

  9. #9
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi langman Xem bài viết
    em hiểu ý thầy rồi, xóa và loại bỏ , có thể và ko thể, .....................






    Về việc loại bỏ :

    nếu như này :
    PHP Code:
    char *xau="lang man" 
    thì việc loại bỏ dấu cách là ko thể , nhất là đối với các trình biên dịch chuẩn như VS2008 và VS2010 chẳng hạn

    nhưng nếu
    PHP Code:
    char xau[]="lang man" 
    thì có thể loại bỏ









    ví dụ

    PHP Code:
    #include "iostream"
    using namespace std;


    void bkitu(char *xau,int v,int s=1)   //v là vị trí tính từ 0, s là số lượng các kí tự bị xóa
    {
        
    v+s-1>strlen(xau)?*xau=NULL:xau[v]=xau[v+s],v+s<strlen(xau)?bkitu(xau,v+1,s):0;
    }
    void bc(char *xau,int i=0)
    {
        
    i<strlen(xau)?bc(xau,i+1),xau[i]==0x20?bkitu(xau,i):0:0;
    }
    void main()
    {
        
    char xau[]="lang man";
        
    bc(xau);
        
    cout<<xau;

        
    system("pause");

    Langman này, em hiểu rồi đó, char *str = "ba ba beo" khác với char str[] = "ba ba beo". Trong các hàm không phải main(), sự truy cập là như nhau, nhưng lời gọi chúng thì có thể và không thể. Có một cậu đưa code về delete space cho mình, kể cũng hay nhỉ, nhờ cậu đó mà mình hiểu thêm một điều nữa.

  10. #10
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,007

    em phát hiện ra thêm 2 trường hợp mà trước giờ ko để ý :



    PHP Code:
    void bc(void)
    {
        
    char *xau="AAAAAA"// do chuỗi "AAAAA"
        
    xau[0]=NULL// lỗi tại đây, ko báo lỗi nhưng khi chạy thì lỗi
    }
    void main()
    {
        
    bc();

        
    system("pause");




    PHP Code:
    void bc(char *xau="lang man")
    {
        
        
    xau[0]=NULL// vẫn lỗi tại đây
    }
    void main()
    {
        
    bc();

        
    system("pause");

    ^_,^

    Facebook : https://www.facebook.com/langmaninternet

    Bùi Tấn Quang

Các đề tài tương tự

  1. Lò quay vịt, lu quay vịt Bắc kinh dùng than giá rẻ tại đây - 0975512038 - www.thanglongco.vn
    Gửi bởi thanglongco.vn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 23-09-2013, 12:53 PM
  2. Máy Quay HD Sony, máy quay sony Handycam, máy quay kỹ thuật số, máy quay phim mới tinh Mo
    Gửi bởi dientuthaithang trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 472
    Bài viết cuối: 03-08-2012, 05:16 PM
  3. Đồ chơi công nghệ thế kỷ 21:Bút quay,đồng hồ quay,móc quay,máy nghe lén qua sim
    Gửi bởi bigphonevn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 06-08-2011, 10:47 PM
  4. Thiết bị thám tử: Bút quay,đồng hồ quay,móc quay,máy nghe lén qua sim
    Gửi bởi bigphonevn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 17-07-2011, 08:23 AM
  5. Quay mũi tên quanh một điểm với góc quay 45 độ?
    Gửi bởi salinh trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 4
    Bài viết cuối: 28-11-2008, 01:39 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn