sicily 1002 Anti-prime Sequences

debug了好久。。各种犯错。。按照某个学长的思路,终于AC了。。

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int n,m,d;
 6 bool isPrime[10000];                                    // 存储素数表
 7 bool added[1101];                                        // 存储是否已添加到结果数组中
 8 int re[1101];                                            // 结果存储数组
 9 bool hasFoundResult = false;                            // 存储是否已找到答案
10 
11 void buildPrimeDiagram()                                // 构建素数表
12 {
13     memset(isPrime,true,sizeof(isPrime));
14     for (int i = 2; i <= 101; i++)
15     {
16         if (isPrime[i])
17         for (int j = i; j*i <= 10000; j++)
18         {
19             isPrime[j*i] = false;
20         }
21     }
22 }
23 
24 bool passMuster(int numberOfTheNumbersAdded)            // 判断到当前为止符合要求,是返回true,否返回false
25 {
26     int sum = re[numberOfTheNumbersAdded];
27     for (int i = 1, j = numberOfTheNumbersAdded-1; i < d&&j>=0; i++,j--)
28     {
29         sum+=re[j];
30         if (isPrime[sum]) return false;
31     }
32     return true;
33 }
34 
35 void dfs(int numberOfTheNumbersAdded)                    // 一个个的添加符合要求的数到结果数组中
36 {
37     if (numberOfTheNumbersAdded == m-n+1)                // 添加完全时
38     {
39         hasFoundResult = true;
40         return;
41     }
42     for (int i = n; i <= m; i++)
43     {
44         if (!added[i])                        // i还未被添加时
45         {
46             re[numberOfTheNumbersAdded] = i;    // 将i添加到结果数组
47             if (passMuster(numberOfTheNumbersAdded))    // 如果添加i后符合要求
48             {
49                 added[i] = true;
50                 dfs(numberOfTheNumbersAdded+1);            // 添加下一个
51                 if (hasFoundResult) return;                // 如果找到答案直接返回
52                 added[i] = false;                        // 没有找到时, 把i的状态设为未添加
53             }
54         }
55     }
56 }
57 
58 int main()
59 {
60     buildPrimeDiagram();
61     while (cin>>n>>m>>d)
62     {
63         if (n==0&&m==0&&d==0) break;
64         hasFoundResult = false;                    // 设为未找到答案
65         int numberOfTheNumbersAdded = 0;
66         memset(added, false, sizeof(added));
67         dfs(numberOfTheNumbersAdded);            // 寻找答案
68         if (hasFoundResult)
69         {
70             for (int i = 0; i <= m-n; i++)
71             {
72                 if (i!=0) cout<<',';
73                 cout<<re[i];
74             }
75             cout<<endl;
76         }
77         else cout<<"No anti-prime sequence exists."<<endl;
78     }
79     return 0;
80 }
原文地址:https://www.cnblogs.com/zmj97/p/5439146.html