C# · 12月 20, 2021

C++实现 递归算法 – 赏金问题 – 整数因式分解

 使用递归方法实现以下问题

 1.赏金问题

    假设有四种面额的钱币,1 元、2 元、5 元和 10 元,而您一共给我10元,

    那您可以奖赏我1张10元,或10张1元,或5张1元外加1张5元等等。

    如果考虑每次奖赏的金额和先后顺序,那么最终一共有多少种不同的奖赏方式?

 2.整数因式分解问题

   使用递归方法,为给定整数n,找到所有可能的分解(1在解中最多出现1次)

   如:输入8,输出是1×8,8×1,2×4,4×2,1x2x2x2,…..

#include

#include

#include

using namespace std;

// 输出函数

void PrintResult(vector &Result)

{

for (size_t i = 0; i < Result.size(); ++i)

{

cout << Result[i] << " ";

}

cout << endl;

}

/*

说明:

假设有四种面额的钱币,1 元、2 元、5 元和 10 元,而您一共给我10元,

那您可以奖赏我1张10元,或10张1元,或5张1元外加1张5元等等。

如果考虑每次奖赏的金额和先后顺序,那么最终一共有多少种不同的奖赏方式?

// totalmoney : 总金额

// select : 钱币面额的选择列表

// Result : 结果列表

*/

void RecursionAlgo(int Totalmoney,vector &Select,vector &Result)

{

//每次递归需要用总金额减去使用的面额,直到Totalmoney=0,表示找到解

if (Totalmoney == 0)

{

PrintResult(Result);

return;

}

//Totalmoney < 0,不符合标准 返回

else if (Totalmoney < 0)

{

return;

}

else

{

for (size_t i = 0; i < Select.size(); ++i)

{

//重要!!!!!!!!!!!!!!!!!!!

// 这里新建vector 用于获取之前的选择,并记录当前的选择

// 新建vector临时变量便于清空错误的选择集

vector newResult = Result;

newResult.push_back(Select[i]);

RecursionAlgo(Totalmoney-Select[i],Select,newResult);

}

}

}

//数组中是否存在某值

bool IsExit(vector &Result,int value)

{

vector::iterator result = std::find(Result.begin(),Result.end(),value);

if (result == Result.end())

{

return false;

}

else

{

return true;

}

}

/*

整数分解

使用递归方法,为给定整数n,找到所有可能的分解(1在解中最多出现1次)

如:输入8,输出是1×8,…..

*/

void RecursionAlgo(int Num,vector &Result)

{

if (Num == 1)

{

PrintResult(Result);

return;

}

for (int i = 1; i <= Num; ++i)

{

//判断1是否在解中

if (IsExit(Result,1))

{

if (i == 1)

{

continue;

}

}

if (Num%i == 0)

{

vector newResult = Result;

newResult.push_back(i);

RecursionAlgo(Num/i,newResult);

}

}

}

int _tmain(int argc,_TCHAR* argv[])

{

int Totalmoney = 10;

int ia[] = {1,2,5,10};

vector Select(ia,ia+4);

vector Result;

//

RecursionAlgo(Totalmoney,Result);

RecursionAlgo(Totalmoney,Result);

return 0;

}