第十三屆全國信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題普及組-資料下載頁
2025-01-14 03:17本頁面
【正文】 30%的數(shù)據(jù)滿足: 1 = T= 10， 1 =S= 100 50%的數(shù)據(jù)滿足: 1 = T = 1000， 1 = S = 10000100%的數(shù)據(jù)滿足: 1 = T = 300000， 0 = M=1000 1 =S = 10^8 【問題描述】 給定A,B,C三根足夠長的細(xì)柱，在A柱上放有2n個中間有空的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的(下圖為n=3的情形）?，F(xiàn)要將 這些國盤移到C柱上，在移動過程中可放在B柱上暫存。要求: (1)每次只能移動一個圓盤；(2) A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序；任務(wù):設(shè)An為2n個圓盤完成上述任務(wù)所需的最少移動次數(shù)，對于輸入的n，輸出An。 【輸入】 ，表示在A柱上放有2n個圓盤。 【輸出】 ，包含一個正整數(shù)，為完成上述任務(wù)所需的最少移動次數(shù)An。 【輸入輸出樣例1】 1 2 【輸入輸出樣例2】 2 6 【限制】 對于50%的數(shù)據(jù)， 1=n=25 對于100% 數(shù)據(jù)， 1=n=200 【提示】 設(shè)法建立An與An1的遞推關(guān)系式。
試題試卷相關(guān)推薦
鄂ICP備17016276號-1