原題目鏈接

題解和源碼

#include"stdio.h"
/* 最開始拿到這道題想嘗試用結(jié)構(gòu)體求解，結(jié)構(gòu)體中第一個(gè)元素為輸入的數(shù)字，第二個(gè)數(shù)字為
輸入數(shù)字進(jìn)行3n+1猜想分解過程中的每一步，然后如果該數(shù)組中的數(shù)字在原始輸入的哪一組數(shù)中
出現(xiàn)，則該結(jié)構(gòu)體中的數(shù)字不是關(guān)鍵數(shù),然后寫了一堆代碼，發(fā)現(xiàn)太復(fù)雜了，后期還涉及排序，更
復(fù)雜了，題上最大數(shù)字不超過100，且還互不重復(fù)，一個(gè)大小為100的int數(shù)組就可解決，所謂覆蓋，
直接置零就完事
 */
int main()
{
    int K,cur,num[101]={0}; 
    //輸入的過程
    /*只使用num的第2-101個(gè)位置，恰好100個(gè);cur 表示當(dāng)前讀入的數(shù)字*/
    scanf("%d",&K);
  
    for(int i=0;i<K;i++)
    {   scanf("%d",&cur);
        num[cur]=1;
    }

    //覆蓋的過程
    for(int i=1;i<=100;i++)
    {   if(num[i])
        {   for(int j=i;j>1;)
            /*將i的值賦給j,對(duì)j進(jìn)行3n+1猜想*/
            {   if(j%2){ j=(3*j+1)/2 ;}
                else {j/=2;}
                //判斷每操作一步后更新的j值是否被覆蓋
                if(j<=100&&num[j])
                /*這一步比較關(guān)鍵，首先得判斷j是否小于100，否則若直接判斷num[j]可能出現(xiàn)數(shù)組越界
                eg. j=81==》j=122 發(fā)生越界*/
                {   num[j]=0; //用置0的方式表示該數(shù)被覆蓋，最后剩下的數(shù)自然就是關(guān)鍵數(shù)了
                    K--;//表示還剩余的未被覆蓋的數(shù)字，后面會(huì)用K來控制輸出結(jié)構(gòu)
                    if(j<i) { break; } //減小時(shí)間復(fù)雜度的關(guān)鍵一步，不過也比較難以理解
                }
            }

        }
    
    }

    //輸出的過程
    
    for(int i=100;i>=1;i--) //要求按從大到小的順序輸出，將數(shù)組倒過來即可
    {   if(num[i])
        { 
            printf("%d%c", i, --K ? ' ' : '\0');
            /*PTA的輸出格式經(jīng)常是要求數(shù)字與數(shù)字之間以空格隔開，最后一個(gè)輸出不帶空格*/
        }
    }

    return 0;
}