#include #include #include #include #include #include #include #include #include const double DEFAULT_V = 0.8; const double V_T = 25.85e-3; const double EPS = 1e-3; enum elem_type { ELEM_V , ELEM_I , ELEM_R , ELEM_D /* , ELEM_C , ELEM_L */ }; struct record { elem_type type; unsigned int source; unsigned int drain; double value; }; double diode_i (double v) { return 1e-12 * (exp(v / V_T) - 1); } void read_records (std::vector &res, FILE *stream) { size_t n = 0; char *lineptr = NULL; int i = 0; while (getline(&lineptr, &n, stream) != -1) { ++i; struct record rec; char *type = strtok(lineptr, " \t"); if (*type == '*') continue; char *src = strtok(NULL, " \t"); char *dst = strtok(NULL, " \t"); if (!dst) { errx(1, "%d: Not enough arguments", i); } char *val = NULL; switch (*type) { case 'V' : val = strtok(NULL, " \t"); rec.type = ELEM_V; break; case 'I' : val = strtok(NULL, " \t"); rec.type = ELEM_I; break; case 'R' : val = strtok(NULL, " \t"); rec.type = ELEM_R; break; case 'D' : rec.value = DEFAULT_V; rec.type = ELEM_D; break; default : errx(1, "%d: Unknown elem type %c", i, *type); } char *endptr; rec.source = strtol(src, &endptr, 10); if (*endptr) errx(1, "%d: Invalid format in source description %s", i, src); rec.drain = strtol(dst, &endptr, 10); if (*endptr && rec.type != ELEM_D) errx(1, "%d: Invalid format in destination description %s", i, dst); if (val) { rec.value = strtod(val, &endptr); } res.push_back(rec); } } #define SQR(x) (x)*(x) typedef double elem; struct matrix { size_t n; size_t m; elem **e; }; struct matrix *build_matrix (size_t n, size_t m, elem elems[]) { struct matrix* matr = (struct matrix*)malloc(sizeof(struct matrix)); matr->n = n; matr->m = m; matr->e = (elem**)malloc(m * sizeof(elem*)); for (unsigned short i = 0; i < m; ++i) { matr->e[i] = (elem*)malloc(n * sizeof(elem)); for (unsigned short j = 0; j < n; ++j) matr->e[i][j] = elems ? elems[i*n + j] : 0; } return matr; }; void destroy_matrix (struct matrix *m) { for (size_t i = 0; i < m->n; ++i) free(m->e[i]); free(m->e); } void print_matrix (struct matrix *m) { printf("("); for (unsigned short i = 0; i < m->m; ++i) { if (i != 0) printf(" "); printf("( "); for (unsigned short j = 0; j < m->n; ++j) printf("% .05lf\t", m->e[i][j]); printf(")"); if (i == m->m - 1) printf(")"); printf("\n"); } } struct matrix *solve_circ_matrix (struct matrix *a, struct matrix *z) { for (size_t i = 1; i < a->m; ++i) { for (size_t j = 1; j < i; ++j) { double mult = a->e[i][j]; for (size_t k = j; k < a->n; ++k) { a->e[i][k] -= a->e[j][k] * mult; } z->e[i][0] -= z->e[j][0] * mult; } double div = a->e[i][i]; for (size_t k = i; k < a->n; ++k) { a->e[i][k] /= div; } z->e[i][0] /= div; } struct matrix *r = build_matrix(1, a->n - 1, NULL); for (size_t i = a->m - 1; i > 0; --i) { int ni = i - 1; r->e[ni][0] = z->e[i][0]; for (size_t k = a->n - 1; k > i; --k) { r->e[ni][0] -= a->e[i][k] * r->e[k-1][0]; } } return r; } double matrix_epsilon (struct matrix *a, struct matrix *b) { size_t n = a->n > b->n ? b->n : a->n; size_t m = a->m > b->m ? b->m : a->m; double res = 0; for (size_t i = 0; i < m; ++i) for (size_t j = 0; j < n; ++j) res += SQR(b->e[i][j] - a->e[i][j]); return sqrt(res); } void create_circuit_matrix (struct matrix **ar, struct matrix **zr, const std::vector& recs) { size_t vn = 0; std::set nodes_set; nodes_set.insert(0); for (size_t i = 0; i < recs.size(); ++i) { vn += recs[i].type == ELEM_V; nodes_set.insert(recs[i].source); nodes_set.insert(recs[i].drain); } std::vector nodes (nodes_set.size()); std::copy(nodes_set.begin(), nodes_set.end(), nodes.begin()); std::map indeces; for (size_t i = 0; i < recs.size(); ++i) { if (!indeces.count(nodes[i])) indeces[nodes[i]] = i; } size_t n = vn + nodes.size(); struct matrix *a = build_matrix(n, n, NULL); struct matrix *z = build_matrix(1, n, NULL); size_t vc = 0; for (size_t i = 0; i < recs.size(); ++i) { switch (recs[i].type) { case ELEM_V: ++(a->e[nodes.size() + vc][indeces[recs[i].source]]); --(a->e[nodes.size() + vc][indeces[recs[i].drain]]); ++(a->e[indeces[recs[i].source]][nodes.size() + vc]); --(a->e[indeces[recs[i].drain]][nodes.size() + vc]); z->e[nodes.size() + vc][0] += recs[i].value; ++vc; break; case ELEM_I: z->e[indeces[recs[i].source]][0] -= recs[i].value; z->e[indeces[recs[i].drain]] [0] += recs[i].value; break; case ELEM_R: a->e[indeces[recs[i].source]][indeces[recs[i].source]] += 1/recs[i].value; a->e[indeces[recs[i].drain]][indeces[recs[i].drain]] += 1/recs[i].value; a->e[indeces[recs[i].source]][indeces[recs[i].drain]] -= 1/recs[i].value; a->e[indeces[recs[i].drain]][indeces[recs[i].source]] -= 1/recs[i].value; break; case ELEM_D:; double I = diode_i(recs[i].value); double g = I / V_T; double ieq = I - g * recs[i].value; a->e[indeces[recs[i].source]][indeces[recs[i].source]] += g; a->e[indeces[recs[i].drain]][indeces[recs[i].drain]] += g; a->e[indeces[recs[i].source]][indeces[recs[i].drain]] -= g; a->e[indeces[recs[i].drain]][indeces[recs[i].source]] -= g; z->e[indeces[recs[i].source]][0] -= ieq; z->e[indeces[recs[i].drain]] [0] += ieq; break; } } *ar = a; *zr = z; } void correct_diodes (std::vector& recs, const struct matrix* res) { for (size_t i = 0; i < recs.size(); ++i) { if (recs[i].type != ELEM_D) continue; double src = recs[i].source ? res->e[recs[i].source-1][0] : 0; double dst = recs[i].drain ? res->e[recs[i].drain -1][0] : 0; recs[i].value = src - dst; } } int main() { std::vector rec; read_records(rec, stdin); struct matrix *a, *z; double def[] = {3000}; struct matrix *old = build_matrix(1, 1, def); struct matrix *curr = NULL; do { if (curr) { destroy_matrix(old); old = curr; } create_circuit_matrix(&a, &z, rec); curr = solve_circ_matrix(a, z); correct_diodes(rec, curr); } while (matrix_epsilon(old, curr) > EPS); print_matrix(curr); }