Đ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 nhau, 1*2 = 12.
- Thay bởi dấu +: hiểu là phép trừ, 1-2 = -1.
- Thay bởi dấu +: hiểu là phép cộng, 1+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; đó.
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);
}
Tags:
DevC