Задачи по C/С++ - [600] :: Прикладное программирование

#include <iostream>
#include <string>
#include <vector>
#include <cstdarg>

using namespace std;

const unsigned humans_q = 3;
const unsigned name_length = 8;

const char boys[humans_q][name_length] = { "Petya", "Vasya", "Misha" };
const char girls[humans_q][name_length] = { "Katya", "Lena", "Olya" };
unsigned childs_per_pair[humans_q][humans_q] = { {8, 6, 7}, { 4, 7, 6}, {6, 2, 1} };

const int char_buffer_size = 256;

struct Pair {
Pair(unsigned b=0, unsigned g=0, unsigned ch=0) : boy(b), girl(g), children(ch) {};
void set(unsigned b, unsigned g, unsigned ch) { boy=b; girl = g; children = ch; };
unsigned boy, girl, children;
};

typedef vector<Pair> pairs_t;

class fast_string {
public:
fast_string() { istring[0] = '\0'; };

void sprintf(const char* format, ...) {
va_list args;
va_start(args, format);
vsprintf(istring, format, args);
va_end(args);
}

const char* c_str() const { return istring; };

private:
char istring[char_buffer_size];
fast_string(const fast_string&) { /* forbidden */};
};
ostream& operator<<(ostream& out, const fast_string& fs) {
out << fs.c_str(); return out;
};

fast_string allpairs;
unsigned total_children = 0;

class Quad {
public:
Quad(pairs_t& vect, int _side) : side(_side) {
quad = new Pair*[side];
register int v_ndx = 0;
for (register int i=0; i<side; ++i) {
quad[i] = new Pair[side];
for (register int j=0; j<side; ++j) {
    quad[i][j] = vect[v_ndx++];
}
}
}

Quad& sub_quad(int line) {
pairs_t pairs((side-1)*(side-1));
register int p_ndx = 0;
for (register int i=0; i<side; ++i) {
if (i==line) continue;
for (register int j=1; j<side; ++j)
    pairs[p_ndx++] = quad[i][j];
}
return *(new Quad(pairs, side-1));
}

int get_side() { return side; };

Pair& get_pair(int i, int j) {
return quad[i][j];
};

~Quad() {
for (int i=0; i<side; ++i)
delete[] quad[i];
delete[] quad;
}

private:
Quad(const Quad&) {};
int side;
Pair** quad;
};

void get_pair(Quad& q, fast_string& history, unsigned children_count) {
int side = q.get_side();
if (side == 1) {
children_count += q.get_pair(0,0).children;
if (children_count > total_children) {
total_children = children_count;
allpairs.sprintf("%s%s+%s", history.c_str(), boys[q.get_pair(0,0).boy], girls[q.get_pair(0,0).girl]);
}
}
else {
for (int i=0; i<side; ++i) {
fast_string fs;
fs.sprintf("%s%s+%s ", history.c_str(), boys[q.get_pair(i,0).boy], girls[q.get_pair(i,0).girl]);
get_pair(q.sub_quad(i), fs, q.get_pair(i,0).children + children_count);
}
}
}

int main () {

pairs_t pairs;

for (unsigned i=0; i<humans_q; ++i)
for (unsigned j=0; j<humans_q; ++j)
pairs.push_back(Pair(i,j, childs_per_pair[i][j]));

Quad q(pairs, humans_q);

fast_string fs;
get_pair(q, fs, 0);

cout << allpairs << endl;
cout << "There are "<<total_children<<" childrens"<<endl;

return EXIT_SUCCESS;
}

Модерирует : ShIvADeSt
Версия для печати • Подписаться • Добавить в закладки
На первую страницу • к этому сообщению • к последнему сообщению