Antonio Mario Caruso

[8/6/2011]

• Liste di Segmenti: soluzione
• Simulazione n-corpi: soluzione di complessità $$O(n^2)$$

Liste di Segmenti Disgiunti

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
typedef struct seg {
    int start, end;
    struct seg *next;
} segment;
void printlist(segment *list)
{
    for (; list; list=list->next)
        printf("(%d,%d) ", list->start, list->end);
    printf("n");
}
void advance_and_cancel(segment *p, int b)
{
    segment *q = p->next, *t = p->next;
    while (q && b >= q->start)  {
        t = q->next;
        if (b >= q->end) free(q);
        else { p->end = q->end; p->next = q->next; free(q); return; }
        q = t;
    }
    p->next = q; p->end = b;
}
segment *insert(segment *h, int a, int b)
{
    segment *n = (segment*)malloc(sizeof(segment));
    n->start = a;
    n->end = b;
    n->next = NULL;
    if (h == NULL) return n;
    segment *p = h, *prev=NULL;
    for (; p!=NULL; prev=p, p=p->next)
    {
        if (p->end < a && p->next==NULL) {  // p < [a,b] inserisco in coda
            p->next = n;
            return h;
        }
        if (b < p->start) {                 // [a,b] < p
            n->next = p;
            if (prev) { prev->next = n; return h; } else return n;
        }
        if (p->start <= b && b <= p->end)   // b dentro
        {
            if (p->start <= a && a <= p->end)  // [a,b] dentro p;
            {  free(n);    return h; }
            p->start = a; free(n);  return h;
        }
        // intersezione
        if (p->start <= a && a <= p->end)   // a dentro p.
        {
            //   p->start...a...p->end...b...
            free(n);
            advance_and_cancel(p,b);
            return h;
        }
        if (a <= p->start && p->end <= b) // p dentro [a,b]
        {
            p->start = a;
            free(n);
            advance_and_cancel(p,b);
            return h;
        }
    }
    return h;
}
int main(int argc, char *argv[])
{
    segment *testa = NULL;
    int a,b;
    int seme = (argc < 2) ? time(NULL) : atoi(argv[1]);
    srand(seme);
    printf("seme = %dn",seme);
    if (seme == 0)
    {
        while(scanf("%d %d",&a,&b)>0)
        testa = insert(testa,a,b);
    } else
        for (int i=0; i<20; i++) {
            a = rand() % 250 + 1;
            b = a + rand() % 40;
            printf("(%d %d) ",a,b);
            testa = insert(testa,a,b);
            printf("- list: "); printlist(testa);
        }
    printf("nn");
    segment *p; int count=1;
    for (p=testa; p; p=p->next)
        printf("%d: (%d,%d)n", count++, p->start, p->end);
    printf("n");
}

N-Corpi:

#include <gtk/gtk.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "graphics.h"
#define M_PI  3.14159265358979323846
#include "body.h"
int N;
double radius;
body *pianeti = NULL;
void parseInput(void)
{
	scanf("%dn",&N);
	double raggio;
	scanf("%lfn",&raggio);
	radius = raggio;
	printf("numero particelle: %dn",N);
	printf("raggio: %en",raggio);
	pianeti = (body *)malloc(sizeof(body)*N);
	for (int i = 0; i < N; i++) {
        double px, py, vx, vy, mass;
		int red, green, blue;
		scanf("%lf %lf %lf %lf %lf", &px, &py, &vx, &vy, &mass);
		scanf("%d %d %dn", &red, &green, &blue);
		body b = { px, py, vx, vy, 0, 0, mass,
                   red/255.0, green/255.0, blue/255.0 };
		pianeti[i] = b;
	}
#ifdef DEBUG
	for (int i = 0; i < N; i++) {
		body b = pianeti[i];
		printf("%e %e %e %e %e ", b.px, b.py, b.vx, b.vy, b.mass);
		printf("%d %d %dn", b.r, b.g, b.b);
	}
#endif
}
static const double dt = (2*M_PI)/20.0;
static double tempo = 0;
void draw(cairo_t *cr)
{
	for (int i=0; i<N; i++)
	{
		double x = pianeti[i].px;
		double y = pianeti[i].py;
		double px = x*scale + dr;
		double py = dr - y*scale;
		cairo_set_source_rgb(cr, pianeti[i].r, pianeti[i].g, pianeti[i].b);
		cairo_arc(cr,px,py,1,0,2*M_PI);
		cairo_stroke(cr);
	}
}
void compute(void)
{
    // calcola le forze
    for (int i = 0; i < N; i++) {
        body_resetForce(&pianeti[i]);
        for (int j = 0; j < N; j++) {
            if (i != j) body_addForce(&pianeti[i],&pianeti[j]);
        }
    }
	// aggiorna le posizioni
    for (int i = 0; i < N; i++)
		body_update(&pianeti[i],dt);
	tempo += dt;
//	printf("%f ",tempo); body_print(&pianeti[0]); printf("n");
}
int main(int argc, char *argv[])
{
	parseInput();
	graphics_configure(argc, argv, "Pianeti", 400, 400);
    graphics_xrange(-radius/2.0,radius/2.0);
    graphics_yrange(-radius/2.0,radius/2.0);
    graphics_run();
}

#include <stdio.h>
#include <math.h>
#include "body.h"
void body_resetForce(body* const b)
{
	b->fx = b->fy = 0.0;
}
void body_update(body* const b, double dt)
{
    b->vx += dt * b->fx / b->mass;
    b->vy += dt * b->fy / b->mass;
    b->px += dt * b->vx;
    b->py += dt * b->vy;
}
void body_addForce(body *const a, body *const b)
{
    double dx = b->px - a->px;
    double dy = b->py - a->py;
    double dist = sqrt(dx*dx + dy*dy);
    double F = (G * a->mass * b->mass) / (dist*dist + EPS*EPS);
    a->fx += F * dx / dist;
    a->fy += F * dy / dist;
}
void body_print(body* const p)
{
	printf("%e %e %e %e",p->px, p->py, p->vx, p->vy);
}

Include body.h:

#define G     6.67e-11
#define EPS   3E4      // softening parameter
struct body {
	double  px, py, vx, vy, fx, fy, mass;
	double r,g,b;
};
typedef struct body body;
void body_print(body* const p);
void body_addForce(body *const a, body *const b);
void body_update(body* const b, double dt);
void body_resetForce(body* const b);

Altri file: graphics.c, graphics.h, dati.zip