首页 > ACM题库 > 九度OJ > 九度-1033-继续xxx定律[模拟]
2014
01-18

九度-1033-继续xxx定律[模拟]

题目来自九度。2009年浙江大学计算机及软件工程研究生机试真题

题目描述:
    当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
3 8 4
5
3 8 4 7 15
5
3 8 4 15 7
0
样例输出:
3
15 7 3
7 15 3

 

此题重点在于理解题意,不知道是不是出题者叙述的太差了:
对于3 8 4 7 15 ,求出每个数的覆盖数序列,最后组成一个覆盖数集合,然后在其中查找原序列中的数,没找到则为关键数。。。这个思考就差不多能AC了

#include<stdio.h>
#include<set>
using namespace std;
int main()   //用集合实现 
{    //求出每个数的覆盖数序列,最后组成一个覆盖数集合,然后在其中查找原序列中的数,没找到则为关键数 
    int n,a[510],i,x,flag;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)            
            break; 
        i=0;
        while(i<n)
        {
            scanf("%d",&a[i]);
            i++;
        }
        set<int> set_int;
        set_int.insert(1);   //插入数字1 
        for(i=0;i<n;i++)         
        {             
            x=a[i];             
            while(x!=1)            
            {                 
                if(x%2==0)                 
                {                    
                    x/=2;                    
                    set_int.insert(x);     //序列过程中的数字加入集合            
                }                
                else                
                {                    
                    x=(x*3+1)/2;                   
                    set_int.insert(x);       //序列过程中的数字加入集合               
                }            
            }        
        }   
        flag=0;        
        for(i=n-1;i>=0;i--)         
        {                           
            if(set_int.count(a[i])<=0)      //没被覆盖的即为关键字            
            {                 
                if(flag)                     
                    printf(" ");                
                printf("%d",a[i]);                 
                flag=1;            
            }         
        }         
        printf("\n");      
    }
    return 1;
}

 


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”