广州市公园景点:求助拆分n

如有不懂的地方清联系我QQ: 378468086
program baidu(input,output);
const
p:array[1..5]of longint
=(2,3,5,7,13);
var
a,pa:array[0..1000]of longint;
b,pb:array[0..1000]of char;
i,n,max:longint;
bo:boolean;
procedure try(ceng,tot:longint);
var
i:integer;
begin
if abs(tot)>1e8
then exit;
if ceng>max
then begin
if tot=n
then begin
bo:=true;
pa:=a;
pb:=b;
end
end
else for i:=1 to 5 do
if not bo then
begin
a[ceng]:=p[i];
if ceng=1
then try(ceng+1,p[i])
else begin
b[ceng]:='+';
try(ceng+1,tot+p[i]);
b[ceng]:='-';
try(ceng+1,tot-p[i]);
b[ceng]:='*';
try(ceng+1,tot*p[i]);
end;
end;
end;
begin
readln(n);
max:=0;
bo:=false;
repeat
inc(max);
try(1,0);
until bo;
for i:=1 to max-1 do
write(pa[i],pb[i+1]);
writeln(pa[max],'=',n);
readln
end.

算法说明：
采取回溯法遍历所有可能出现的n步运算的式子，n=1，2，...，当找到第一个解时就是运算步数最少的解了。
当然在遍历过程中会去除明显不可能是最优解的分支，以提高速度。

运行示例：
./split_n 22

运行结果：
2+7+13=22

#include <stdio.h>
#include <hash_map>
#include <deque>

using namespace std;

#define MAX_STEP 100

hash_map<int, int> hmap;

int num[5] = {2,3,5,7,13};
char op[3] = {'*','+','-'};
bool is_num[14] = {0,0,1,1,0,1,0,1,0,0,0,0,0,1};

int n;

int max_step;
char op_arr[MAX_STEP];
int num_arr[MAX_STEP];

bool try_num(int cur, int step);

bool try_op(int cur, int step)
{
if (step > 0 && cur == n)
{
printf("%d", num_arr[0]);
for (int i = 1; i < step; i++)
printf("%c%d", op_arr[i], num_arr[i]);
printf("=%d\n", n);
return true;
}
if (step >= 2 && 2 <= cur && cur <= 13 && is_num[cur])
return false;
hash_map<int,int>::iterator it = hmap.find(cur);
if (it == hmap.end())
{
hmap[cur] = step;
}
else if (it->second <= step)
{
return false;
}
else
{
it->second = step;
}
for (int i = 0; i < 3; i++)
{
op_arr[step] = op[i];
if (try_num(cur, step))
return true;
}
return false;
}

bool try_num(int cur, int step)
{
if (step == max_step)
return false;
for (int i = 0; i < 5; i++)
{
num_arr[step] = num[i];
int total = 0;
int k = step;
while (k >= 0 && (op_arr[k] == '+' || op_arr[k] == '-'))
{
if (op_arr[k] == '+')
total += num_arr[k];
else
total -= num_arr[k];
if (k != step && 2 <= total && total <= 13 && is_num[total])
break;
if (k != step && -2 >= total && total >= -13 && is_num[-total])
break;
k--;
}
if (k >= 0 && (op_arr[k] == '+' || op_arr[k] == '-'))
{
continue;
}
switch (op_arr[step])
{
case '+':
if (try_op(cur + num_arr[step], step + 1))
return true;
break;
case '-':
if (try_op(cur - num_arr[step], step + 1))
return true;
break;
case '*':
if (try_op(cur * num_arr[step], step + 1))
return true;
break;
}
}
return false;
}

int main(int argc, char **argv)
{
if (argc < 2)
{
fprintf(stderr, "Usage: %s <n>\n", argv[0]);
return 1;
}
n = atoi(argv[1]);
max_step = 1;
op_arr[0] = '+';
while (!try_num(0, 0))
{
max_step++;
op_arr[0] = '+';
hmap.clear();
}

return 0;
}

产生出什么?