将题目抽象,建模 事实上就是一个数学的小球投盒问题:
- 我们一共有n个球
- 我们一共有10个盒
- 每个盒不能为空
- 每个盒中的小球最多为3个
分析n的各种情况,显然得到:
- 当$0\leq n< 10$时,无法保证盒不空,只需输出0
- 当$30< n \leq 5000$时,无法达到所需的美味度,只需输出0
- 当$n=30$和n$=10$的时候答案只有一种
而当n使得程序有结果时(即$10\leq n \leq 30$),枚举就开始了:
算法1:
- 创建若干个10个元素的数组,代表这10种配料,都初始化为1个
- n-=10
接下来就是重点
写一个十重循环,每一重循环代表一种配料
每次进入循环的时候尝试给该配料+1并判断n是否已经用光,如果已经用光,保存该情况
返回到上一情况,并进入下一重循环。
以人的思考来说: 我们先把所有盒子各放一个球,然后尽量将靠前的盒子填满,然后从中转移给后面的盒子,每次转移就生成一种新的情况
算法2:
- 创建若干个10个元素的数组,代表这10种配料,都初始化为0个
写一个十重循环,枚举从{1111111111}到{3333333333}的所有情况,每次判断和是否为n
算法3: 用递归实现,思路类似算法1
算法2代码参考:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int save[500000][10];
int main(){
int n;
scanf("%d",&n);
if(n>=10&&n<=30){
int cnt=0;
int a,b,c,d,e,f,g,h,i,j;
for(a=1;a<=3;++a){
for(b=1;b<=3;++b){
for(c=1;c<=3;++c){
for(d=1;d<=3;++d){
for(e=1;e<=3;++e){
for(f=1;f<=3;++f){
for(g=1;g<=3;++g){
for(h=1;h<=3;++h){
for(i=1;i<=3;++i){
for(j=1;j<=3;++j){
if(a+b+c+d+e+f+g+h+i+j==n){
++cnt;
save[cnt][0]=a;
save[cnt][1]=b;
save[cnt][2]=c;
save[cnt][3]=d;
save[cnt][4]=e;
save[cnt][5]=f;
save[cnt][6]=g;
save[cnt][7]=h;
save[cnt][8]=i;
save[cnt][9]=j;
}
}
}
}
}
}
}
}
}
}
}
printf("%d\n",cnt);
for(i=1;i<=cnt;++i){
for(j=0;j<9;++j){
printf("%d ",save[i][j]);
}
printf("%d\n",save[i][9]);
}
}
else{
printf("%d\n",0);
}
return 0;
}