PAT-B] 1005. 继续(3n+1)猜想 [查找]

链接：1005. 继续(3n+1)猜想 (25)

题意

(3n+1)猜想的衍生题目。
给你一串数字，对每个数字进行猜想的验证，如果其中的某些数字并没有在验证其他数字的时候被验证过，那这些数字就是关键数字。并以从大到小的顺序输出他们。

分析

这道题目的话不需要想太多，就依次验证每一个数字就可以了。在验证数字的过程中，把每一个中间数字都保存下来就可以了。
所以我们需要一个保存数字的数组f[]，然后对中间数字进行标记（比如验证5的时候，就能得到中间数字8, 4, 2, 1，分别将f[8], f[4], f[2], f[1]都置为1就可以了）
值得一提的是，在递归验证思想的时候如果发现某个中间数字已经被置为1了，那么就不需要再递归下去了，因为下面的数字都已经被算过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[ 100000 ];    //标记这个数字是否已经查找过了
int in[ 105 ];      //输入
void solve( int n, int i ){ //n为由猜想递归计算得到的数 i为输入的当前数字
    if( f[ n ] || n == 1 )  return; //得到的n已经查找过了或者已经查找到1满足猜想了就结束程序
    if( n != i )    f[ n ] = 1; //将递归计算到的数都置为 1 表明这些数字都已经在验证猜想时被覆盖了
    if( n % 2 )     solve( ( 3 * n + 1 ) / 2, i );
    else    solve( n / 2, i );
}
int main()
{
    int k;
    while( ~scanf( "%d", &k ) ){
        memset( f, 0, sizeof f );
        memset( in, 0, sizeof in );
        f[ 1 ] = 1;
        for( int i = 0; i < k; i++ ){
            scanf( "%d", in + i );
        }
        for( int i = 0; i < k; i++ ){
            solve( in[ i ], in[ i ] );
        }
        sort( in, in + k ); //排序方便降序输出
        int flag = 1;
        for( int i = k - 1; i >= 0; i-- ){
            if( f[ in[ i ] ] == 0 ){    //f为0表示该数没在递归中被查找到，则输出
                if( flag )  flag = 0;
                else        printf( " " );  //空格规范
                printf( "%d", in[ i ] );
            }
        }
        puts( "" );
    }
    return 0;
}

小结

就慢慢做就好了..

查找
PAT-B, 查找