推 ericinttu:我腦袋裡只有遞迴的想法, 非遞迴還沒什麼想法 10/03 02:00
推 zerodevil:非遞迴版可以參考std::next_permutation的source code 10/03 03:00
→ yauhh:原po說這是"組合"問題嗎? 剛好,看前一篇我的文章,非遞迴解. 10/03 14:22
※ 引述《WWWZZZXXXMMM (WZXM)》之銘言：
: 想請問一下
: 現在我有38個數字 要任意選取其中6個 使其湊到某個值
: 38
: 其實這就是組合C 6 的問題
: 我將這38個數存成陣列後 要用如何的演算法？
: 才可以將所有的可能跑過一遍
1. 腦袋空空的，只想到暴力法6迴圈 (這演算法應該沒錯吧？不是很確定)
int n[38] = { 目標的３８個數字};
int target_number = ???;
for(int i0=0; i0<38; ++i0)
for(int i1=i0+1; i1<38; ++i1)
for(int i2=i1+1; i2<38; ++i2)
for(int i3=i2+1; i3<38; ++i3)
for(int i4=i3+1; i4<38; ++i4)
for(int i5=i4+1; i5<38; ++i5)
{
if(target_number == n[i0] + n[i1] + n[i2] + n[i3] + n[i4] + n[i5])
{
//就是目標
}
}
2. 把暴力法改成迴圈
int n[38] = { 目標的３８個數字};
int target_number = ???;
int sn[6] ={0}; //select number
aaa(0, 0);//使用時
void aaa(int alread_select_number, int index)
{
if(alread_select_number == 5)
{
if(target_number = sn[0]+sn[1]+sn[2]+sn[3]+sn[4]+sn[5])
{
//就是目標
}
}
else
{
for(int i=index; i<38; ++i)
{
sn[alread_select_number] = n[index];
aaa(alread_select_number+1, i+1);
}
}
}
3... 還想不到怎麼用動態…
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.132.244