PAT A1103 Integer Factorization (30分)

由于考試將近砚殿，時(shí)間愈發(fā)珍貴，復(fù)習(xí)和學(xué)習(xí)的步調(diào)同比加快芝囤。但是似炎，還行，還能喘過氣來~~主要還是因?yàn)樽鲱}少才顯得不是那么忙~~
今天認(rèn)真學(xué)習(xí)了深搜DFS和廣搜BFS悯姊∠勖辏看了大量的代碼，進(jìn)行拙劣思考并結(jié)合一個(gè)深搜的題目淺談自己的收貨體會悯许。
深搜和廣搜的思想我不說了传睹，我講只能是班門弄斧。不如說點(diǎn)實(shí)在的
不哆嗦岸晦，把題目押上來~

The K?P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K?P factorization of N for any positive integers N, K and P.

Input Specification:
Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

Output Specification:
For each case, if the solution exists, output in the format:
N = n[1]^P + ... n[K]^P

題目沒有粘全~~省的題目占了一大片文章顯得我在水字~~原題直達(dá)車
老規(guī)矩，我來解釋

意思不難睛藻，
先給你一個(gè)目標(biāo)數(shù)字N启上，
然后再給你“個(gè)數(shù)”K，
讓你求出K個(gè)某某數(shù)字的P次方店印，
讓這K個(gè)數(shù)的和等于N
木了~

這里有一個(gè)關(guān)鍵我們必須要想到
你想冈在，給了你目標(biāo)數(shù)字N，你的組合成員A按摘，起碼A^p 要小于N 叭包券。
當(dāng)(A+1)^p>N時(shí)候纫谅，誒~~這不就來了嗎？大喊一聲哪里跑
立即推--->你的遍歷范圍在0~A里面溅固，至于如何遍歷付秕，這里選取深度優(yōu)先搜索

我們預(yù)先準(zhǔn)備好
1.算次方的函數(shù)power。這沒啥好說的
2.init初始化函數(shù)侍郭，不用啥參數(shù)询吴，功能，是把你算出來的某某數(shù)的次方亮元，推到vector里面猛计，并且是把所有能推進(jìn)去的全推進(jìn)去。（當(dāng)然要和power搭配使用）
3.注意偶爆捞，我們搜索的時(shí)候奉瘤，是從最大個(gè)那個(gè)數(shù)A（就是A^p恰好不超過N）向前搜索。向前煮甥，向前盗温，前.....
4.當(dāng)有多個(gè)序列時(shí)候，輸出字典序最大的苛秕，這個(gè)簡單肌访，但我還是說一下

這道題目的思維量，相比之前我更過得艇劫，要復(fù)雜許多吼驶，但不是不可理解，只是暫時(shí)難以掌握店煞。需要時(shí)間的打磨蟹演。

代碼如下

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int targetSum;//給出的目標(biāo)數(shù)字N
int totalNum;//這是那個(gè)所謂的K
int exponent;//這是指數(shù)P
int maxFacSum = -1;

vector<int> fac;//這個(gè)放進(jìn)那些某某數(shù)的P次方
vector<int> ans;//存放字典序最大的序列，也就是答案
vector<int> temp;//臨時(shí)存放顷蟀，遞歸時(shí)候用得著

int power(int x)//這個(gè)函數(shù)沒什么說的，一看就懂
{

    int ans = 1;
    for(int i = 0 ; i< exponent ; i++)
    {
        ans *= x;
    }
    return ans;
}

void init()//這個(gè)是初始化函數(shù)鸣个。我認(rèn)為這是為了main函數(shù)簡潔起見，封裝成了函數(shù)
{
    int i = 0 ; 
    int temp = 0;
    while (temp <=targetSum)
    {
        fac.push_back(temp);
        temp = power(++i);
    }
}

void DFS(int index , int nowK , int sum ,int facsum)//core thought
{


    if(sum == targetSum && nowK == totalNum)
    {
        if(facsum > maxFacSum)
        {
            ans = temp;
            maxFacSum = facsum;
        }
        return;
    }
/*
是否可以結(jié)束的判斷囤萤，一定放在DFS內(nèi)部的前面，
這里的條件滿足是“當(dāng)你算到的和涛舍，等于了目標(biāo)澄惊，并且夠了個(gè)數(shù)K”，就能更新最佳答案并且返回了
*/



/*
要是算的比目標(biāo)的大肛搬，并且超出了要求個(gè)數(shù)K，就沒有繼續(xù)下去的必要了毕贼，直接返回
*/
    if(sum > targetSum || nowK > totalNum)
    {
        return;
    }


//這里應(yīng)該算是核心的核心
    if(index -1 >= 0)
/*index是我們之前說的那個(gè)  “某某數(shù)”  ，因?yàn)槭窍蚯氨闅v帅刀，所以index后面是大于等于0
至于為什么是index要非得減掉1，這是因?yàn)槲覀兊膄ac第一個(gè)數(shù)字是0,0的多少次方還是0（0^0除外）扣溺，所以沒有選擇第一個(gè)數(shù)字的必要
  */
  {
        temp.push_back(index);//如果我們選擇這個(gè)index的話
        DFS(index, nowK +1 , sum + fac[index] , facsum + index);//就這么操作骇窍，
//解釋一下四個(gè)參數(shù)锥余，index表示我從index這里繼續(xù)往下遍歷腹纳；nowK+1說明我現(xiàn)在又離湊齊K個(gè)近了一步；
sum+fac[index]說明我離湊齊N又近了一步驱犹；facsum+index記錄著我這K個(gè)數(shù)字的組成成員的和嘲恍，方便以后比較字典序
        temp.pop_back();//記得需要pop掉才能繼續(xù)尋找
        DFS(index-1, nowK  , sum  , facsum );//我們不選這個(gè)index，就是這個(gè)操作雄驹，參數(shù)和上面相同的道理
    }



}

int main()
{
    scanf("%d%d%d",&targetSum,&totalNum,&exponent);
    init();
    DFS(fac.size() -1 , 0 , 0 ,0);//從后面往前遍歷佃牛，開始的時(shí)候個(gè)數(shù)啊，總和啊医舆，底數(shù)總和啊俘侠，都暫且為0
    if(maxFacSum == -1 ) printf("Impossible\n");//這就是沒找到，說不可楞就行
    else
    {
        printf("%d = %d^%d",targetSum,ans[0],exponent);//輸出分成兩部分蔬将，先輸出等于...
        for(int i = 1 ; i < ans.size() ; i++)
        {
            printf(" + %d^%d",ans[i],exponent);//后面就是加幾加幾了爷速，后面的規(guī)律一樣了，循環(huán)就行
        }
    }
    return 0;
}

我覺得我把代碼解釋的夠詳細(xì)了霞怀，簡直是保姆級別手把手/手動滑稽

ok惫东，課代表自動滾上來~

深搜的模型

void DFS(參數(shù))
{    
1.  判斷邊界，這可能會有若干段代碼毙石，因題而異了
  
2.  核心的核心廉沮，對每一種進(jìn)行遍歷
for（int i= 0 ; i < n ;i ++）
{
巴拉巴拉
DFS(遞歸，這是靈魂)
回退徐矩，這個(gè)不要忘废封，很重要
}
return ；
}

我最近在思考為了把文章寫得更加生動丧蘸，總想插入一些圖片把文章生動化，但是苦于沒有素材，只能一點(diǎn)一點(diǎn)積累力喷。從下一篇文章開始吧刽漂，多放幾張有趣的圖片。

開始吟唱~~
晚安

886~~~