1 小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合。
2 #include "pch.h" 3 #include <iostream> 4 using namespace std; 5 6 unsigned long long test(int K, int N, int M) 7 { 8 if (K <= 0 || N <= 0 || M <= 0)return 0; 9 //一样可计算出结果，但没必要算 10 if (K > N * M)return 0; 11 if (K == N * M)return 1; 12 int L = K < M ? K : M; 13 unsigned int ***p = new unsigned int**[N]; 14 15 for (int i = 0; i < N; i++) 16 { 17 p[i] = new unsigned int *[L + 1]; 18 for (int j = 0; j <= L; j++) 19 { 20 //全初始化为0 21 p[i][j] = new unsigned int[K + 1](); 22 } 23 }
//此处从0开始是因为列数0用于累计所有的未选择项，简单来说，就是统计跨层迭代，从而可以只观察上一层就可以计算出跨层的累计迭代数 24 for (int i = 0; i <= L; i++) 25 { 26 p[0][i][i] = 1; 27 } 28 for (int i = 1; i < N; i++) 29 { 30 //吃j串状态 31 for (int j = 0; j <= L; j++) 32 { 33 //吃完总计串数为k 34 for (int k = 0; k <= K; k++) 35 { 36 37 for (int l = 0; l <= L; l++) 38 { 39 //此轮吃完j串总计k串的方法共有上一轮所有选择剩下k-j的方法数 40 if (k - j >= 0) 41 p[i][j][k] += p[i - 1][l][k - j]; 42 } 43 } 44 } 45 } 46 unsigned long long sum = 0; 47 for (unsigned int i = 0; i <= L; i++) 48 { 49 sum += p[N - 1][i][K]; 50 } 51 //防止内存泄漏 52 for (int i = 0; i < N; i++) 53 { 54 55 for (int j = 0; j <= L; j++) 56 { 57 //全初始化为0 58 delete[]p[i][j]; 59 } 60 delete[]p[i]; 61 } 62 delete[]p; 63 return sum; 64 } 65 66 int main() 67 { 68 69 int N, M, K; 70 cout << "请输入要吃的窜数" << endl; 71 cin >> K; 72 cout << "请输入种类数" << endl; 73 cin >> N; 74 cout << "请输入每种的数量" << endl; 75 cin >> M; 76 cout << "一共可以有 " << test(K, N, M) << " 种吃法" << endl;; 77 }
若此题使用函数调用遍历，非常简单，但即使是使用优化剪枝一样可能导致栈溢出
直接遍历法，每次决策吃第i种j串，都得继续遍历余下所有的可能，直至到决策n为止（做 了算法剪枝也差不多）
下面即为直接函数调用方法进行遍历
1 //待优化，数值过大时，栈过深 2 #include "pch.h" 3 #include <iostream> 4 #include<string> 5 6 using namespace std; 7 /* 8 9 四、小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合 10 //设相同种类同数量为1个点餐组合，即 A1 B19 无论A出现在哪均为一种,那么为了模拟不重复，选择了一种的数量后，后面就不能选择选择过的 11 */ 12 unsigned long long f( int n,int left,int N ,int M) 13 { 14 15 //吃完 16 if (left == 0)return 1; 17 //没有下一种了 18 if (n > N)return 0; 19 unsigned long long sum = 0; 20 21 for (int i = 0; i <=left&&i<=M; i++) 22 { 23 sum =sum+ f(n + 1, left - i,N, M); 24 } 25 26 return sum; 27 } 28 unsigned long long test(int K, int N, int M) 29 { 30 unsigned long long result = 0; 31 //非法数据 32 if (K == 0||N==0||M==0)return 0; 33 //没有吃够的吃法 34 if (K > N*M)return 0; 35 //选择第N种烧烤 36 for (int i = 0; i <=M&&i <=K; i++) 37 { 38 result = result + f(2,K-i,N,M); 39 } 40 return result; 41 } 42 43 int main() 44 { 45 46 int N, M, K; 47 cout << "请输入要吃的窜数" << endl; 48 cin >> K; 49 cout << "请输入种类数" << endl; 50 cin >> N; 51 cout << "请输入每种的数量" << endl; 52 cin >> M; 53 cout << "一共可以有 " << test(K, N, M) << " 种吃法" << endl;; 54 }
一、 小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合。
#include"pch.h"
#include<iostream>
usingnamespace std;
unsignedlonglong test(intK, intN, intM)
{
if (K <= 0 || N <= 0 || M <= 0)return 0;
//一样可计算出结果，但没必要算
if (K > N * M)return 0;
if (K == N * M)return 1;
int L = K < M ? K : M;
unsignedint ***p = new unsignedint**[N];
for (int i = 0; i < N; i++)
{
p[i] = newunsignedint *[L + 1];
for (int j = 0; j <= L; j++)
{
//全初始化为0
p[i][j] = newunsignedint[K + 1]();
}
}
for (int i = 0; i <= L; i++)
{
p[0][i][i] = 1;
}
for (int i = 1; i < N; i++)
{
//吃j串状态
for (int j = 0; j <= L; j++)
{
//吃完总计串数为k
for (int k = 0; k <= K; k++)
{
for (int l = 0; l <= L; l++)
{
//此轮吃完j串总计k串的方法共有上一轮所有选择剩下k-j的方法数
if (k - j >= 0)
p[i][j][k] += p[i - 1][l][k - j];
}
}
}
}
unsignedlonglong sum = 0;
for (unsignedint i = 0; i <= L; i++)
{
sum += p[N - 1][i][K];
}
//防止内存泄漏
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= L; j++)
{
//全初始化为0
delete[]p[i][j];
}
delete[]p[i];
}
delete[]p;
return sum;
}
int main()
{
int N, M, K;
cout <<"请输入要吃的窜数"<< endl;
cin >> K;
cout <<"请输入种类数"<< endl;
cin >> N;
cout <<"请输入每种的数量"<< endl;
cin >> M;
cout <<"一共可以有 "<< test(K, N, M) <<" 种吃法"<< endl;;
}