Бред (с)
dr_mousefly сказав(ла):
for (unsigned int lastSummand = maxSummand; lastSummand * (lastSummand + 1) / 2 >= number; --lastSummand)const unsigned int firstSummand = number - lastSummand;
Пусть летит твоя Зульфия на канатах ко мне на матрас.а что, "клоун Тыемураз" звучит многообещающе...
дорогие дети! сейчас ваш любимый клоун Тыемураз исполнит свой номер "Исступление эмоций".
просим на арену нашего техноцирка...
vlad7; сказав(ла):
#include <iostream>
#include <vector>
#include <sys/time.h>
#include <time.h>
typedef std::vector<int> Int_Vector;
class splitter
{
public:
splitter(int N, int M);
~splitter();
void get_result(std::vector<Int_Vector>& v) { v = _v; }
private:
struct node
{
int index;
std::vector<node*> data;
};
int _N;
int _M;
node* _tree;
std::vector<Int_Vector> _v;
private:
void fill_tree(node* n);
void tree_iterator(node* n, int l);
void accumulator(node* n, int sum, std::vector<int>& vec);
void destruct(node* n);
};
splitter::splitter(int N, int M)
:_N(N),_M(M)
{
_tree = new node;
_tree->index = 1;
fill_tree(_tree);
tree_iterator(_tree,_M);
}
splitter::~splitter()
{
destruct(_tree);
}
void splitter::destruct(node* n)
{
std::vector<node*>::const_iterator it = n->data.begin();
for(; it<n->data.end(); it++)
{
destruct(*it);
}
delete n;
}
void splitter::fill_tree(node* n)
{
for(int i=n->index+1; i<_M; i++)
{
node* next = new node;
next->index = i;
if(((n->index+next->index)<=_M) && (next->index<=_N))
{
fill_tree(next);
n->data.push_back(next);
}
}
}
void splitter::accumulator(node* n, int sum, std::vector<int>& vec)
{
sum += n->index;
if(sum==_M)
{
vec.push_back(n->index);
_v.push_back(vec);
vec.pop_back();
}
std::vector<node*>::const_iterator it = n->data.begin();
for(;it<n->data.end();it++)
{
vec.push_back(n->index);
accumulator(*it,sum,vec);
vec.pop_back();
}
}
void splitter::tree_iterator(node* n, int l)
{
Int_Vector vec;
accumulator(n,0,vec);
std::vector<node*>::const_iterator it = n->data.begin();
for(;it<n->data.end(); it++)
{
if((*it)->index < l)
tree_iterator(*it, (*it)->index+1);
}
}
int main()
{
struct timezone tz;
struct timeval t1;
struct timeval t2;
gettimeofday(&t1,&tz);
splitter s(9,30);
gettimeofday(&t2,&tz);
printf("Processing time %d us\n", t2.tv_usec - t1.tv_usec);
std::vector<Int_Vector> v;
s.get_result(v);
std::vector<Int_Vector>::iterator itv = v.begin();
for(;itv<v.end(); itv++)
{
Int_Vector::iterator it = itv->begin();
for(;it<itv->end(); it++)
std::cout<<*it<<" ";
std::cout<<std::endl;
}
return 0;
}Processing time 444 us
1 2 3 4 5 6 9
1 2 3 4 5 7 8
1 2 3 7 8 9
1 2 4 6 8 9
1 2 5 6 7 9
1 3 4 5 8 9
1 3 4 6 7 9
1 3 5 6 7 8
1 5 7 8 9
2 3 4 5 7 9
2 3 4 6 7 8
2 4 7 8 9
2 5 6 8 9
3 4 6 8 9
3 5 6 7 9
4 5 6 7 8
6 7 8 9Спасибо, пооптимизировал.Можно и такое. Это на скорую руку на всех вариантах не прогонял, но задел для оптимизации широкий
Сам автор задачи присоединяется к выводам комиссии и приветствует решение Оршанского
Витя, ну как вы могли такой Бред пропустить, ну ладно меня не было, а еще в экспертную комиссию заделались! Это не может бесследно пройти для совета. В совете - маразм.
