类型:递推求解

代码附下：

 1 

//

wrong1  产生的和有两个相同的

 2 

//

wrong2  visti标记数组标记错误

 3 #include <iostream>

 4 #include <cstring>

 5 

using 

namespace std;

 6 

int N, nN, sum[

10010], num[

110];

 7 

bool visit[

10010];

 8 

bool ok(){   

//

num[1], num[2], num[3]假设已经确定,

 9 

            

//

则num[1] + num[4]必定在区间sum(3, nN)中未被标记的第一个数

10     

int i, j = 

3, k, t;

11     

for(i = 

4; i <= N; ++i){

12         

while(visit[j]) j++;

13         

if(j > nN) 

break;

14         num[i] = sum[j] - num[

1]; 

//

find num[i] (3 < i <= N)

15         visit[j] = 

true;          

//

标记sum[j];

16         

for(k = 

2; k < i; ++k){   

//

标记num[i] 与 num[2, i-1]的和,并判断和是否存在,若不存在,结束

17             

for(t = j + 

1; t <= nN; ++t)

18                 

if(!visit[t] && num[i] + num[k] == sum[t]){

19                     visit[t] = 

true;　

break;

20                 }

21             

if(t > nN) 

return 

false;

//

若不存在,结束

22         }

23     }

24     

return 

true;

25 }

26 

27 

int main()

28 {

29     

while(cin>>N){

30         

if(!N) 

break;

31         nN = N * (N - 

1) / 

2;

32         

for(

int i = 

1; i <= nN; ++i) cin>>sum[i];

33         

for(

int i = 

3; i <= nN; ++i){

34             

//

枚举出num[2]:

35 

            

//

because sum[1] = num[1] + num[2];

36 

            

//

sum[2] = num[1] + num[3]; num[2] + num[3] = sum[k]( 3 <= k <= nN)

37             num[

2] = (sum[

1] - sum[

2] + sum[i]) / 

2;

38             num[

1] = sum[

1] - num[

2];

39             num[

3] = sum[

2] - num[

1];

40             memset(visit, 

false, 

sizeof(visit));

41             

if(num[

2] + num[

3] == sum[i]){

42                 visit[i] = 

true;

43                 

if( ok() ){     

//

检查是否符合条件，若符合，则输出

44                     

for(

int j = 

1; j < N; ++j) cout<<num[j]<<

"

 

";

45                     cout<<num[N]<<endl; 

break;

46                 }

47             }

48         }

49     }

50     

return 

0;

51 }