我的PAT系列文章更新重心已移至Github，歡迎來看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容。此處文章目前已更新至與Github Pages同步律姨。歡迎star我的repo隶垮。
題目
卡拉茲(Callatz)猜想已經(jīng)在1001中給出了描述稚字。在這個(gè)題目里泼橘，情況稍微有些復(fù)雜涝动。
當(dāng)我們驗(yàn)證卡拉茲猜想的時(shí)候，為了避免重復(fù)計(jì)算炬灭，可以記錄下遞推過程中遇到的每一個(gè)數(shù)醋粟。例如對(duì) 進(jìn)行驗(yàn)證的時(shí)候，我們需要計(jì)算
3重归、5米愿、8、4鼻吮、2育苟、1，則當(dāng)我們對(duì) 椎木、8违柏、4、2 進(jìn)行驗(yàn)證的時(shí)候拓哺，就可以直接判定卡拉茲猜想的真?zhèn)斡露猓恍枰貜?fù)計(jì)算，因?yàn)檫@ 4
個(gè)數(shù)已經(jīng)在驗(yàn)證3的時(shí)候遇到過了士鸥，我們稱 5闲孤、8、4烤礁、2 是被 3“覆蓋”的數(shù)讼积。我們稱一個(gè)數(shù)列中的某個(gè)數(shù) 為“關(guān)鍵數(shù)”，如果
不能被數(shù)列中的其他數(shù)字所覆蓋脚仔。
現(xiàn)在給定一系列待驗(yàn)證的數(shù)字勤众，我們只需要驗(yàn)證其中的幾個(gè)關(guān)鍵數(shù)，就可以不必再重復(fù)驗(yàn)證余下的數(shù)字鲤脏。你的任務(wù)就是找出這些關(guān)鍵數(shù)字们颜，并按從大到小的順序輸出它們。
輸入格式：
每個(gè)測試輸入包含 1 個(gè)測試用例猎醇，第 1 行給出一個(gè)正整數(shù) (
)窥突，第 2 行給出
個(gè)互不相同的待驗(yàn)證的正整數(shù)
(
)的值，數(shù)字間用空格隔開硫嘶。
輸出格式：
每個(gè)測試用例的輸出占一行阻问，按從大到小的順序輸出關(guān)鍵數(shù)字。數(shù)字間用 1 個(gè)空格隔開沦疾，但一行中最后一個(gè)數(shù)字后沒有空格称近。
輸入樣例：
6
3 5 6 7 8 11
輸出樣例：
7 6
思路
最簡單的思路：
記錄初始給出的關(guān)鍵數(shù)字第队，對(duì)每一個(gè)數(shù)字進(jìn)行驗(yàn)證計(jì)算，每遇到初始給出的數(shù)字時(shí)刨秆，對(duì)其進(jìn)行標(biāo)記凳谦。標(biāo)記過的數(shù)字便不再進(jìn)行驗(yàn)證。
思路優(yōu)化：
如果（也是一般）進(jìn)行從小到大的遍歷坛善，驗(yàn)證一個(gè)較大數(shù)字時(shí)晾蜘，某一步計(jì)算得到一個(gè)較小數(shù)字（并且在初始給出的數(shù)字中），即可斷定無須繼續(xù)驗(yàn)證眠屎，因?yàn)榻酉聛淼尿?yàn)證過程和這個(gè)較小數(shù)字的驗(yàn)證過程是重復(fù)的。
代碼實(shí)現(xiàn)：
所給數(shù)字范圍是1-100肆饶，可以使用長度為100（或101改衩，方便數(shù)字和索引對(duì)應(yīng)）的數(shù)組記錄需驗(yàn)證的數(shù)字，數(shù)字即為索引驯镊。這樣無須查找排序等操作葫督。初始給出的數(shù)字相應(yīng)記為1，其他置0板惑。
驗(yàn)證過程中會(huì)遇到大于100的數(shù)橄镜，注意條件判斷，避免數(shù)組越界冯乘。
代碼
最新代碼@github洽胶，歡迎交流
#include <stdio.h>
int main()
{
int K, n, table[101] = {0};
scanf("%d", &K);
for(int i = 0; i < K; i++)
{
scanf("%d", &n);
table[n] = 1;
}
/* find numbers needed to test */
for(int i = 1; i <= 100; i++)
if(table[i])
for(int j = i; j > 1; )
{
/* calculate for one step */
if(j % 2) j = (3 * j + 1) / 2;
else j /= 2;
/* see if the new number is in given numbers */
if(j <= 100 && table[j])
{
table[j] = 0; /* 'covered' this number */
K--; /* one less number not 'covered' */
if(j < i) break; /* did this before, no need going on */
}
}
for(int i = 100; i >= 1; i--)
if(table[i] == 1)
printf("%d%c", i, --K ? ' ' : '\0');
return 0;
}
