リュックサックタイプの問題
タイトル:
2つの整数nとmを入力し、数列1,2,3から.....nの中で勝手にいくつかの数を取って、
これとmを等しくするには、その中のすべての可能な組合せを列挙することが要求される.
考え方:再帰のたびに、現在の要素を数列に追加するかどうかを考慮し、ある値に達するまで知る.
コード実装:
同類テーマ:
タイトル:昇順で並べ替えられた配列と数値を入力します.
配列の中で2つの数を探して、それらの和がちょうど入力された数字になるようにします.
要求時間複雑度はO(n)である.複数対の数字の和が入力に等しい数字があれば、いずれかのペアを出力すればよい.
たとえば、配列1、2、4、7、11、15、および数字15を入力します.4+11=15のため、4と11が出力される.
考え方:この問題に対して1つの配列の記録を増やせばいいです.他は同じです.
同期ブログ:http://blog.csdn.net/moxiaomomo/archive/2011/05/24/6441831.aspx
2つの整数nとmを入力し、数列1,2,3から.....nの中で勝手にいくつかの数を取って、
これとmを等しくするには、その中のすべての可能な組合せを列挙することが要求される.
考え方:再帰のたびに、現在の要素を数列に追加するかどうかを考慮し、ある値に達するまで知る.
コード実装:
view plaincopy to clipboardprint?
#include<iostream>
#include<deque>
using namespace std;
void findNums(int n,int leftSum,deque<int>& deq)
{
if(n<0||leftSum<0)return; // ,
if(leftSum>0)
{
deq.push_front(n); // n
findNums(n-1,leftSum-n,deq);
deq.pop_front();
findNums(n-1,leftSum,deq);
}
else { // ,
deque<int>::iterator i=deq.begin();
for(;i!=deq.end();++i)
{
cout<<*i<<" ";
}
cout<<endl;
}
}
int main()
{
deque<int> myDeq;
findNums(10,35,myDeq);
return 0;
}
同類テーマ:
タイトル:昇順で並べ替えられた配列と数値を入力します.
配列の中で2つの数を探して、それらの和がちょうど入力された数字になるようにします.
要求時間複雑度はO(n)である.複数対の数字の和が入力に等しい数字があれば、いずれかのペアを出力すればよい.
たとえば、配列1、2、4、7、11、15、および数字15を入力します.4+11=15のため、4と11が出力される.
考え方:この問題に対して1つの配列の記録を増やせばいいです.他は同じです.
同期ブログ:http://blog.csdn.net/moxiaomomo/archive/2011/05/24/6441831.aspx