Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<math.h>
- #include<stdlib.h>
- #define DEBUG(str) //printf(str)
- typedef struct
- {
- int order;
- float *coeff;
- }poly;
- void print(poly a)
- {
- int i;
- int no_output = 1;
- for(i = a.order; i >= 0; i--)
- {
- if(a.coeff[i] == 0)
- continue;
- printf("%+.2fx^%d", a.coeff[i], i);
- no_output = 0;
- }
- if(no_output)
- {
- printf("0");
- }
- printf("\n");
- }
- poly clone(poly a)
- {
- poly c;
- int i, n;
- c.order = a.order;
- for(i = 0; i <= c.order; i++ )
- {
- c.coeff[i] = a.coeff[i];
- }
- DEBUG("Clone");
- return c;
- }
- poly multiply(poly a, poly b)
- {
- poly res;
- int i, j, n, o1 = a.order, o2 = b.order;
- res.order = o1 + o2;
- res.coeff = (float *)malloc(sizeof(float) * (res.order + 1));
- for(i = 0; i <= res.order; i++)
- res.coeff[i] = 0;
- for(i = 0; i <= o1; i++)
- for(j = 0; j <= o2; j++)
- res.coeff[i+j] += a.coeff[i] * b.coeff[j];
- DEBUG("Multiply");
- return res;
- }
- poly add(poly a, poly b)
- {
- int i, o1 = a.order, o2 = b.order;
- poly res;
- res.order = (o1>o2)?o1:o2;
- res.coeff = (float *)malloc(sizeof(float) * (res.order + 1));
- for(i = 0; i <= o1 && i <= o2; i++)
- {
- res.coeff[i] = a.coeff[i] + b.coeff[i];
- }
- while(i <= o1)
- {
- res.coeff[i] = a.coeff[i];
- i++;
- }
- while(i <= o2)
- {
- res.coeff[i] = b.coeff[i];
- i++;
- }
- res.order = i-1;
- DEBUG("Add");
- return res;
- }
- poly subtract(poly a, poly b)
- {
- int i, o1 = a.order, o2 = b.order;
- poly res;
- res.order = (o1>o2)?o1:o2;
- res.coeff = (float *)malloc(sizeof(float) * (res.order + 1));
- for(i = 0; i <= o1 && i <= o2; i++)
- {
- res.coeff[i] = a.coeff[i] - b.coeff[i];
- }
- while(i <= o1)
- {
- res.coeff[i] = a.coeff[i];
- i++;
- }
- while(i <= o2)
- {
- res.coeff[i] = - b.coeff[i];
- i++;
- }
- res.order = i-1;
- DEBUG("Subtract");
- return res;
- }
- poly generate_node_x()
- {
- poly new_node;
- new_node.order = 1;
- new_node.coeff = (float *)malloc(sizeof(float)*2);
- new_node.coeff[0] = 0;
- new_node.coeff[1] = 1;
- DEBUG("NewNode");
- return new_node;
- }
- #define AND(a,b) multiply(a,b)
- #define OR(a,b) add(a,subtract(b,multiply(a,b)))
- double f(poly p, double x)
- {
- int i;
- double res = 0;
- if(x == 0)
- return p.coeff[0];
- for(i = p.order; i > 0; i--)
- {
- res += p.coeff[i];
- res *= x;
- }
- res += p.coeff[0];
- return res;
- }
- double FalsiMethod(poly p, double s, double t, double e, int m)
- {
- int n, side = 0;
- double r, fr, fs = f(p, s), ft = f(p, t);
- for(n = 1; n <= m; n++)
- {
- r = (fs*t - ft*s) / (fs - ft);
- if (fabs(t-s) < e*fabs(t+s)) break;
- fr = f(p, r);
- if (fr * ft > 0)
- {
- t = r; ft = fr;
- if (side==-1) fs /= 2;
- side = -1;
- }
- else if (fs * fr > 0)
- {
- s = r; fs = fr;
- if (side==+1) ft /= 2;
- side = +1;
- }
- else break;
- }
- return r;
- }
- double SecantMethod(poly p, double xn_1, double xn, double e, int m)
- {
- int n;
- double d;
- for (n = 1; n <= m; n++)
- {
- d = (xn - xn_1) / (f(p, xn) - f(p, xn_1)) * f(p, xn);
- if (fabs(d) < e)
- return xn;
- xn_1 = xn;
- xn = xn - d;
- }
- return xn;
- }
- int main()
- {
- int t, n, i, x, y, z;
- //int done=0, fixedpos;
- poly node[100], ex;
- scanf("%d", &t);
- while(t--)
- {
- scanf("%d", &n);
- for(i = 1; i <= n; i++)
- {
- scanf("%d", &x);
- switch(x)
- {
- case 0:
- node[i] = generate_node_x();
- break;
- case 1:
- scanf("%d %d", &y, &z);
- node[i] = OR(node[y], node[z]);
- break;
- case 2:
- scanf("%d %d", &y, &z);
- node[i] = AND(node[y], node[z]);
- break;
- }
- }
- ex = node[i-1];
- ex.coeff[0] -= 0.5;
- /*
- fixedpos = (f(ex,0) > 0);
- t = 1;
- while(!done)
- {
- t = t/2;
- if(fixedpos && f(t) < 0)
- }
- */
- printf("%.5f\n", SecantMethod(ex, 0, 1, 5E-6, 100));
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment