Question

pascal题NIOP普及。只要给个思路和算法

题目描述
将1，2，••••••,9共9个数排成下列形态的三角形。
a
b c
d e
f g h i
其中：a～i分别表示1，2，••••••,9中的一个数字，并要求同时满足下列条件： （1）a < f < i; （2）b < d, g < h, c < e （3）a+b+d+f=f+g+h+i=i+e+c+a=P 程序要求： 根据输入的边长之和P 输出所有满足上述条件的三角形的个数。
输入
一行，一个整数P。
输出
一行，一个整数，即满足条件的三角形的个数。
样例输入
21
样例输出
4
提示

来源

Answer 1

O(9!),暴搜即可
var n,r:longint;
p:array[1..9]of integer;
c:array[1..9]of boolean;
procedure calc;
begin
if p[1]>p[6] then exit;
if p[6]>p[9] then exit;
if p[4]>p[2] then exit;
if p[5]>p[3] then exit;
if p[7]>p[8] then exit;
if p[1]+p[2]+p[4]+p[6]<>n then exit;
if p[1]+p[3]+p[5]+p[9]<>n then exit;
if p[6]+p[7]+p[8]+p[9]<>n then exit;
inc(r);
end;
procedure dfs(k:longint);
var a:longint;
begin
if k>9 then
begin
calc;
exit;
end;
for a:=1 to 9 do
if not c[a] then
begin
p[k]:=a;
c[a]:=true;
dfs(k+1);
c[a]:=false;
end;
p[k]:=0;
end;
begin
read(n);
dfs(1);
write(r);
end.

追问

乖乖！

Answer 2

深搜
注意剪枝就行

Answer 3

同问，求解啊！

追问

姓曹的，是不是要被选上啊？（白日做梦）你要同问就按“同问”别瞎起哄

追答

额，哈哈~求高人指点迷津！