九度oj 题目1031：xxx定律题目1033：继续xxx定律

题目描述：: 对于一个数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。
请计算需要经过几步才能将n变到1，具体可见样例。

输入：: 测试包含多个用例，每个用例包含一个整数n,当n为0 时表示输入结束。（1<=n<=10000）

输出：: 对于每组测试用例请输出一个数，表示需要经过的步数,每组输出占一行。

样例输入：

3
1
0

样例输出：

5
0

 1 #include <cstdio>
 2 #include <cstdlib>
 3 
 4 int main(int argc, char const *argv[])
 5 {
 6     int n;
 7     scanf("%d",&n);
 8     while(n != 0) {
 9         int ans = 0;
10         while(n != 1) {
11             if(n %2 == 0) {
12                 n = n/2;
13             }
14             else {
15                 n = 3 * n + 1;
16                 n = n/2;
17             }
18             ans++;
19         }
20         printf("%d
",ans);
21         scanf("%d",&n); 
22     }
23     return 0;
24 }

题目描述：: 当n为3时，我们在验证xxx定律的过程中会得到一个序列，3，5，8，4，2，1，将3称为关键数，5，8，4，2称为覆盖数。现在输入n个数字a[i]，根据关键数与覆盖数的理论，我们只需要验证其中部分数就可以确定所有数满足xxx定律，输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。

输入：: 输入数据包含多个用例,每个用例首先包含一个整数n，然后接下来一行有n个整数a[i]，其中: 1<=n<=500, 1<a[i]<=1000

输出：: 请计算并输出数组a中包含的关键数，并按照其输入顺序的逆序输出,每个用例输出占一行。

样例输入：

样例输出：

3
15 7 3
7 15 3
这道题的题面让人难以理解，事实上，它是在给定的输入串上寻找关键数。关键数和覆盖数并不一定是连着的
我第一次WA的代码是这样的

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define MAX 1002
 4  
 5 bool flag[MAX];
 6 int num[MAX];
 7  
 8 int main(int argc, char const *argv[])
 9 {
10     int n;
11      
12     scanf("%d",&n);
13     while(n != 0) {
14         for(int i = 0; i < MAX; i++) {
15             flag[i] = false;
16         }
17         for(int i = 0; i < n; i++) {
18             scanf("%d",&num[i]);
19             int temp = num[i];
20                 while(temp != 1) {
21                     if(temp % 2 == 0) {
22                         temp = temp/2;
23                     }
24                     else {
25                         temp = 3 * temp + 1;
26                         temp = temp/2;
27                     }
28                     if(temp > 1000) {
29                         break;
30                     }
31                     if(flag[temp] == true) {
32                         break;
33                     }
34                     flag[temp] = true;
35                 }
36  
37         }
38         int isOne = 1;
39         for(int i = n-1; i >= 0; i--) {
40             if(flag[num[i]] == false) {
41                 if(isOne == 1) {
42                     printf("%d",num[i]);
43                     isOne = 0;
44                 }
45                 else {
46                     printf(" %d",num[i]);
47                 }
48                  
49             }
50         }
51         printf("
");
52          
53         scanf("%d",&n); 
54     }
55     return 0;
56 }

这段代码犯了两个错误，一是

if(temp > 1000) {
    break;
}

这句话本来是为了防止数组越界，但有时n作为关键字是它的覆盖字会超过1000,这样会导致错误

解决这个问题有两个方案，一是增加MAX，如下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define MAX 130000
 4 
 5 bool flag[MAX];
 6 int num[MAX];
 7 
 8 int main(int argc, char const *argv[])
 9 {
10     int n;
11     
12     scanf("%d",&n);
13     while(n != 0) {
14         for(int i = 0; i < MAX; i++) {
15             flag[i] = false;
16         }
17         for(int i = 0; i < n; i++) {
18             scanf("%d",&num[i]);
19             int temp = num[i];
20                 while(temp != 1) {
21                     if(temp % 2 == 0) {
22                         temp = temp/2;
23                     }
24                     else {
25                         temp = 3 * temp + 1;
26                         temp = temp/2;
27                     }
28                     
29                     if(flag[temp] == true) {
30                         break;
31                     }
32                     flag[temp] = true;
33                     
34 
35                 }
36 
37         }
38         int isOne = 1;
39         for(int i = n-1; i >= 0; i--) {
40             if(flag[num[i]] == false) {
41                 if(isOne == 1) {
42                     printf("%d",num[i]);
43                     isOne = 0;
44                 }
45                 else {
46                     printf(" %d",num[i]);
47                 }
48                 
49             }
50         }
51         printf("
");
52         
53         scanf("%d",&n); 
54     }
55     return 0;
56 }

二是做特殊处理

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define MAX 1002
 4  
 5 bool flag[MAX];
 6 int num[MAX];
 7  
 8 int main(int argc, char const *argv[])
 9 {
10     int n;
11      
12     scanf("%d",&n);
13     while(n != 0) {
14         for(int i = 0; i < MAX; i++) {
15             flag[i] = false;
16         }
17         for(int i = 0; i < n; i++) {
18             scanf("%d",&num[i]);
19             int temp = num[i];
20                 while(temp != 1) {
21                     if(temp % 2 == 0) {
22                         temp = temp/2;
23                     }
24                     else {
25                         temp = 3 * temp + 1;
26                         temp = temp/2;
27                     }
28                     if(temp < 1000) {
29                         flag[temp] = true;
30                     }
31                 }
32  
33         }
34         int isOne = 1;
35         for(int i = n-1; i >= 0; i--) {
36             if(flag[num[i]] == false) {
37                 if(isOne == 1) {
38                     printf("%d",num[i]);
39                     isOne = 0;
40                 }
41                 else {
42                     printf(" %d",num[i]);
43                 }
44                  
45             }
46         }
47         printf("
");
48          
49         scanf("%d",&n); 
50     }
51     return 0;
52 }

九度oj 题目1031：xxx定律 题目1033：继续xxx定律

九度oj 题目1031：xxx定律题目1033：继续xxx定律