Điền dấu +/- vào giữa các chữ số để có Tổng = n

Đ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. 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 luiNó 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đó.  




Demo:

#include <stdio.h>
#include <stdlib.h>
#define max 100
int isdigit(char ch) {return '0' <= ch && ch <= '9';}
int isoperator(char ch) {return ch == '+' ? 1: -1;}
int ismultsign(char ch) {return ch == '*';}
long eval(char *str)
{
    long val = 0;
    char sign = '+';
    long temp = 0;
    int k = 0;
    char *ptr = str;
    while (*ptr)
        {
            if (isdigit(*ptr))
                temp = temp*10 + *ptr - '0';
            else if(!ismultsign(*ptr))
                {
                    val = val + isoperator(sign)*temp;
                    temp = 0;
                    sign = *ptr;
                }
            ptr ++;
        }
   
    return val + isoperator(sign)*temp;
}
char *insert(char *str)
{
    char *temp = (char *) malloc(2*max);
    char *ptr = str;
    int k = 0;
    while (*ptr)
        {
            k+=2;
            temp[k-2] = *ptr;
            temp[k-1] = '*';
            ptr ++;
        }
    temp[k-1] = 0;
    return temp;
}
char *removemultsign(char *str)
{
    char *temp = (char *) malloc (max);
    char *ptr = temp;
    while (*str)
        {
            if(!ismultsign(*str))
                {
                    *ptr = *str;
                    ptr++;
                }
            str++;
        }
    *ptr = 0;
    return temp;
}
void Try(char *str, int k, int sum)
{  
    if (*(str+k))
        for (int j = 0; j < 3; j++)
            {
                char ch = str[k];
                if (j==1) str[k] = '-';
                else if (j==2) str[k] = '+';
                long num = eval(str);
                if (num == sum)
                    {
                        char *temp = removemultsign(str);
                        printf("\n%s = %d\n",temp, sum);
                        free (temp);
                    }
                Try(str,k+2,sum);
                str[k] = ch;
            }
}
void main()
{
    char str[] = "123456789";
    char *ptr = insert(str);
    Try(ptr,1,12);
    free (ptr);
}
Ntech Developers

Programs must be written for people to read, and only incidentally for machines to execute.

Post a Comment

Previous Post Next Post