Analiza programów

17.06.2009

Bagaż podręczny

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
 
#define min(x, y) ((x) < (y)) ? (x) : (y) //REV: czy nikt inny na œwiecie nie potrzebował tej funkcjonalnoœci?
#define max(x, y) ((x) > (y)) ? (x) : (y) //REV: nie ma czegoœ takiego w bibliotekach?
//REV: podejrzanie długi plik
typedef struct _prostokat_t 
{ 
	int w; 
	int s; 
	int w_b;
	int s_b;
 
	int liczba_paczek;
	int* paczki;
 
	struct _prostokat_t* d[4]; 
} prostokat_t;
 
const int poziom_max = 20;
int buduj_drzewo(prostokat_t* drzewo)
{
	static int poziom = 0;
	static int i, j;//REV: unused variable j
	static int w_max, w_min, s_max, s_min, w, s, w_b, s_b;
	static int p, q, x, y;
 
	w_b = drzewo->w_b / 2;
	s_b = drzewo->s_b / 2;
	if ((drzewo->liczba_paczek > 1) && (poziom < poziom_max) && ((w_b > 0) || (s_b > 0)))
	{
		poziom++;
 
		for (i = 0; i < 4; i++)
		{
			drzewo->d[i] = (prostokat_t*) calloc(1, sizeof(prostokat_t));
			drzewo->d[i]->paczki = (int*) malloc(sizeof(int) * 2 * drzewo->liczba_paczek);//REV: hola! nie za dużo tej pamięci?
		}
 
		drzewo->d[3]->w = drzewo->w;
		drzewo->d[3]->s = drzewo->s;
		drzewo->d[3]->w_b = w_b;
		drzewo->d[3]->s_b = s_b;
 
		drzewo->d[0]->w = drzewo->w;
		drzewo->d[0]->s = drzewo->s + drzewo->d[3]->s_b;
		drzewo->d[0]->w_b = drzewo->d[3]->w_b;
		drzewo->d[0]->s_b = drzewo->s_b - drzewo->d[3]->s_b;
 
		drzewo->d[2]->w = drzewo->w + drzewo->d[3]->w_b;
		drzewo->d[2]->s = drzewo->s;
		drzewo->d[2]->w_b = drzewo->w_b - drzewo->d[3]->w_b;
		drzewo->d[2]->s_b = drzewo->d[3]->s_b;
 
		drzewo->d[1]->w = drzewo->d[2]->w;
		drzewo->d[1]->s = drzewo->d[0]->s;
		drzewo->d[1]->w_b = drzewo->d[2]->w_b;
		drzewo->d[1]->s_b = drzewo->d[0]->s_b;//REV for(int x=0;x<2;x++)for(int y=0;y<2;y++){drzewo->d[x*2+y].w=drzewo->w+x*w_b;...}
		w = drzewo->d[1]->w;
		s = drzewo->d[1]->s;
 
		w_max = s_max = 0;
		w_min = s_min = INT_MAX;
 
		for (i = 0; i < drzewo->liczba_paczek; i++)
		{
			x = drzewo->paczki[2 * i];
			y = drzewo->paczki[2 * i + 1];
 
			w_max = max(y, w_max);
			w_min = min(y, w_min);
			s_max = max(x, s_max);
			s_min = min(x, s_min);
 
			if (x < s)
			{
				if (y < w)
				{
					q = 3;
				}
				else
				{
					q = 2;
				}
			}
			else
			{
				if (y < w)
				{
					q = 0;
				}
				else
				{
					q = 1;
				}
			}
 
			p = 2 * drzewo->d[q]->liczba_paczek;
			drzewo->d[q]->paczki[p] = x;
			drzewo->d[q]->paczki[p + 1] = y;
			drzewo->d[q]->liczba_paczek++;			
		}
 
		drzewo->w = w_min;//REV: hm...a więc te pola były niezainicjowane...szkoda, że już ich używaliœmy
		drzewo->s = s_min;
		drzewo->w_b = w_max - w_min;
		drzewo->s_b = s_max - s_min;
 
		if ((w_max == w_min) && (s_max == s_min))
		{
			for (i = 0; i < 4; i++)
			{
				free(drzewo->d[i]->paczki);
				free(drzewo->d[i]);
				drzewo->d[i] = NULL;
			}
		}
		else
		{
			for (i = 0; i < 4; i++)
			{
				if (drzewo->d[i]->liczba_paczek)
				{
					drzewo->d[i]->paczki = (int*) realloc(drzewo->d[i]->paczki, sizeof(int) * 2 * drzewo->d[i]->liczba_paczek);
				}
				else
				{
					free(drzewo->d[i]->paczki);
					free(drzewo->d[i]);
					drzewo->d[i] = NULL;
				}
			}
 
			free(drzewo->paczki);
			drzewo->paczki = NULL;
 
			if (drzewo->d[0])
			{
				buduj_drzewo(drzewo->d[0]);
			}
 
			if (drzewo->d[1])
			{
				buduj_drzewo(drzewo->d[1]);
			}
 
			if (drzewo->d[2])
			{
				buduj_drzewo(drzewo->d[2]);
			}
 
			if (drzewo->d[3])//REV: for :)
			{
				buduj_drzewo(drzewo->d[3]);
			}
		}
 
		poziom--;
	}
	else//REV: ok poddałem się tutaj, za długie i nie podzielone na bloki funkcje, utrudniajš odbiór:)
	{
		w_max = s_max = 0;
		w_min = s_min = INT_MAX;
 
		for (i = 0; i < drzewo->liczba_paczek; i++)
		{
			x = drzewo->paczki[2 * i];
			y = drzewo->paczki[2 * i + 1];
 
			w_max = max(y, w_max);
			w_min = min(y, w_min);
			s_max = max(x, s_max);
			s_min = min(x, s_min);
		}
 
		drzewo->w = w_min;
		drzewo->s = s_min;
		drzewo->w_b = w_max - w_min;
		drzewo->s_b = s_max - s_min;
	}
 
	return 0;
}
 
int globalny_w, globalny_s;
int policz_paczki_rekurencja(prostokat_t* drzewo)
{
	if ((drzewo->w >= globalny_w) && (drzewo->s >= globalny_s))
	{
		return drzewo->liczba_paczek;
	}
	else if ((drzewo->w + drzewo->w_b >= globalny_w) && (drzewo->s + drzewo->s_b >= globalny_s))
	{
		int wynik = 0;
		if (drzewo->d[0])
		{
			wynik += policz_paczki_rekurencja(drzewo->d[0]);
		}
 
		if (drzewo->d[1])//REV: w tym miejscu pojawia się myœl o forze
		{
			wynik += policz_paczki_rekurencja(drzewo->d[1]);
		}
 
		if (drzewo->d[2])//REV: w tym miejscu myœl o forze staje się kuszšca
		{
			wynik += policz_paczki_rekurencja(drzewo->d[2]);
		}
 
		if (drzewo->d[3])//REV: w tym miejscu myœl o forze jest już nieodparta
		{
			wynik += policz_paczki_rekurencja(drzewo->d[3]);
		}
 
		return wynik;
	}
 
	return 0;
}
 
int policz_paczki(prostokat_t* drzewo, int w, int s)
{
	globalny_w = w;
	globalny_s = s;
 
	return policz_paczki_rekurencja(drzewo);
}
 
int wczytaj_dane(int* liczba_firm, int** wymiary, int* liczba_paczek, int** paczki, int* w, int* s, int* w_b, int* s_b, FILE* f) 
{//REV: rozumiem, że argument f, służy do debugu, ale przecież na standardowe wejœcie można sobie przekierować plik proœciej niż przekompilowujšc...
	int i, j; //REV: unused variable j
	int w_max = 0, w_min = INT_MAX, s_max = 0, s_min = INT_MAX; 
	int a, b; 
	fscanf(f, "%d %d", liczba_paczek, liczba_firm); 
	*paczki = (int*) malloc(sizeof(int) * 2 * (*liczba_paczek)); 
	*wymiary = (int*) malloc(sizeof(int) * 2 * (*liczba_firm));
 
	for (i = 0; i < *liczba_paczek; i++) 
	{ 
		fscanf(f, "%d %d", &b, &a); 
 
		(*paczki)[2 * i] = a; 
		(*paczki)[2 * i + 1] = b; 
 
		w_max = max(w_max, b); 
		s_max = max(s_max, a); 
		w_min = min(w_min, b); 
		s_min = min(s_min, a); 
	} 
 
	for (i = 0; i < *liczba_firm; i++) 
	{ 
		fscanf(f, "%d %d", &b, &a);//REV: być może logiczniej byłoby na odwrót?
 
		(*wymiary)[2 * i] = a; 
		(*wymiary)[2 * i + 1] = b; 
	}
 
	*w = w_min; 
	*s = s_min; 
	*w_b = w_max - w_min; 
	*s_b = s_max - s_min;
 
	return 0;
}
 
int main(int argc, char** argv)//REV: nieużywane argumenty
{
	int i;
	prostokat_t* drzewo = (prostokat_t*) calloc(1, sizeof(prostokat_t));
 
	int liczba_firm;
	int* wymiary;
 
	wczytaj_dane(&liczba_firm, &wymiary, &drzewo->liczba_paczek, &drzewo->paczki, &drzewo->w, &drzewo->s, &drzewo->w_b, &drzewo->s_b, stdin);//REV: czy wskaŸnik na drzewo, nie załatwiłby sprawy?
 
	buduj_drzewo(drzewo);
 
	for (i = 0; i < liczba_firm; i++)
	{
		printf("%d\n", policz_paczki(drzewo, wymiary[2 * i + 1], wymiary[2 * i]));//REV: jedna tablica do dwóch rzeczy? i to jeszcze w odwrotnej kolejnoœci?
	}
 
	return 0;
}
 

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com