用程序找到这个智力题的所有答案

显示全部楼层 · 2021-1-27 06:56:29

有一个蛋糕，被切成了100份，现将这个100份装到12个盘子中，要求每个盘子中的份数不能为0，并且份数中必须还有数字3，不论个位或者十位，例如13份，37份等。
请给出每个盘子中各装多少份的所有答案。
我先给出一个解（3，3，3，3，3，3，3，3，3，3，33，37）。
分 -->

千问 · 2021-1-27 06:56:29

先找出100以内所有有3的数,列成数组.
然后用动态规划应该能解!

千问 · 2021-1-27 06:56:29

因为都是100内的并且都是带有3字的自然数组合
所以共有313233343536373839330313233343536373839
一共有20个数字．
又因为每个盘子最不能为空即最小也要是311*3=33100-33=67　
所以可以排除掉738393这3个数字只剩17个数字
共有17^12种取数方法这个数值太大了.
要想全部枚举估计不可能了.....

千问 · 2021-1-27 06:56:29

用dp(m,n)来表示m个盘子中摆放n块蛋糕（且每个盘子中的蛋糕数量含有3）的方案总数。
边界条件：
dp(m,n)=0，m
Subgetit()
Dims(2To12,3To100)AsString,i&,j&,k&
t=Array(3,13,23,30,31,32,33,34,35,36,37,38,39,43,53,63)
Fori=0ToUBound(t)
Forj=0ToUBound(t)
Ift(i)+t(j)""Then
Fori=0ToUBound(t)
Ifk+t(i)

千问 · 2021-1-27 06:56:29

MyCPPCode
#include
#defineALL100
#defineTOTAL12
#defineOPTIONS16
voidDumpResult(int*buffer)
{
if(NULL==buffer)return;
std::coutTOTAL)return;
if(sum>ALL)return;
//Ifreachthe12boxes
if(offset==TOTAL)
{
//Whetherresultshouldbedump
if(sum==ALL)
//Iftotalpiecesareexactmatch
DumpResult(buffer);
return;
}
//Recursivesearchresult
for(intindex=0;indexALL,itmeansleftoptionsareuseless.
//So,justreturnundersuchcondition.
return;
}
}
}
intmain(void)
{
intvalues[]={3,13,23,30,31,32,33,34,35,36,37,38,39,43,53,63};
intresult[12];
FindSolutions(values,result,0,0);
returnEXIT_SUCCESS;
}

千问 · 2021-1-27 06:56:29

3楼正解，5楼代码没一点优化，速度上可能会有一点慢，优化一下还是可以的，有些情况是可以提前结束掉的

千问 · 2021-1-27 06:56:29

好好想了一下这题，发现如果仔细分析一下,用铅笔都能写出答案来。
100以内的可使用得数包括3132330313233343536373839435363738393
其中分为两类：
1、3132333435363738393
2、30313233343536373839
（33同时属于这2类）
由于12个数的加和为100，因此可以判断出，不可能全由第一类数组成（否则加和的尾数应当是6）
因此第一种形式应当为11个第1类数和一个37组成，11个第一类的个位加和为33，加上37=70，实际上也就剩下30，可以分配到11个第1类数上。
组合共3种，111，12，03
因此第一种形式共3种：
3333333313131337
333333333132337
33333333333337
由于不可能同时存在3个第2类数（否则加和>100），所以第2种形式为
10个第1类数，2个第2类数，由于10个第1类数的各位加和为30，2个第2类数加和最小为60，因此又分为2种情况，9个3，1个13和2个30，或10个3，2个第2类数
因此第2种形式共6种
333333333133030
33333333333139
33333333333238
33333333333337
33333333333436
33333333333535
由于33333333333337已经在第一种形式中出现了，因此全部组合共8种
3333333313131337
333333333132337
33333333333337
333333333133030
33333333333139
33333333333238
33333333333436
33333333333535

千问 · 2021-1-27 06:56:29

原来给的方法是排列式的结果，如果只是找组合方式的结果的话，那么可以这样优化这个函数：
voidFindSolutions(int*options,int*buffer,intprevious,intsum,intoffset)
{
//BasicErrorandunnecessarycalculationfilter
if(buffer==NULL||options==NULL)return;
if(offsetTOTAL)return;
if(sum>ALL)return;
//Ifreachthe12boxes
if(offset==TOTAL)
{
//Whetherresultshouldbedump
if(sum==ALL)
//Iftotalpiecesareexactmatch
DumpResult(buffer);
return;
}
//Recursivesearchresult
for(intindex=previous;indexALL,itmeansleftoptionsareuseless.
//So,justreturnundersuchcondition.
return;
}
}
}

千问 · 2021-1-27 06:56:29

好像是穷举法楼上太厉害了学习学习

千问 · 2021-1-27 06:56:29

mark学习