Ar putea sa imi spuna cineva ce e gresit in abordarea urmatoare?

1. Parcurg in latime graful incepand cu nodul X
2. Daca intalnesc un nod care imbunatateste distanta pana la unul din vecinii sai V, atunci golesc lista de tati a lui V.
3. Daca acelasi nod da un cost egal cu costul pt a ajunge in vecinul V atunci il adaug in lista de tati a lui V.
4. Dupa parcurgere pentru fiecare tata T a lui Y parcurg recursiv pana la X astfel ca maresc numarul de aparitii al fiecarui nod intalnit si apoi merg la tatal cu numarul (aparitii - 1).
5. Pentru fiecare nod care are numarul de aparitii egal cu numarul de aparitii al lui X il adaug intr-un heap.
6. Tiparesc heap-ul.

Ca sa nu mai deschid un nou topic, sunt si eu interesat de unde se mai poate gasi cartea tinand cont ca nu prea am cum sa ajung prin Bucuresti. Daca o are cineva va rog sa ma contactati. Imi cer scuze Alexandru ca intervin peste postul tau dar nu cred ca este necesar sa deschid inca un topic.

Solutia mea, desi contine ceva mai multe caractere decat cele postate anterior, adica 115 cu whitespace, se bazeaza pe ideea ca integrala din 1/x dx este ln(x). Astfel putem foarte usor face asta destul de precis, metode mai bune fiind regulile lui Simpson, dintre care este recomandata Simpson 3/8. Stiu ca este foarte lenta pt. numere mai mari, dar imi place deoarece este foarte simpla.

Cod:

#define d double
d l(d x){d a=min(1.0,x);x=max(1.0,x);d r=0;while(a<x){r+=1/a*1e-6;a+=1e-6;}if(x-1<1e-6)r*=-1;return r;}

Codul curat si un exemplu de folosire:

Cod:

#include <cstdio>
#include <algorithm>
using namespace std;

double ln(double x)
{
	double dx = min(1.0, x);
	x = max(1.0, x);
	double result = 0.0;
	while (dx < x)
	{
		result += 1 / dx * 1e-6;
		dx += 1e-6;
	}
	if (x < 1)
		result *= -1;
	return result;
}

int main()
{
	float x;
	printf("x = ");
	scanf("%f", &x);
	printf("ln(%f) = %f\n", x, ln(x));
	return 0;
}

O alta solutie ce mi-a venit in minte este bazata pe derivata lui a^x, dupa cum este cunoscut (a^x)' = a^x * ln(a). Codul bazat pe aceasta idee se afla mai jos si are 76 de caractere.

Cod:

double f(double x){return (pow(x,2.0+1e-6)-pow(x,2.0))/1e-6/pow(x,2.0+1e-7);}

Codul curat si un exemplu de utilizare:

Cod:

#include <cstdio>
#include <cmath>

double ln(double x)
{
	double df = pow(x, 2.0 + 1e-6) - pow(x, 2.0);
	double dx = 1e-6;
	double f = pow(x, 2.0 + dx / 2);
	return (df / dx) / f;
}

int main()
{
	float x;
	printf("x = ");
	scanf("%f", &x);
	printf("ln(%f) = %f\n", x, ln(x));
	return 0;
}

Edit: Acum am vazut ca nu am voie sa folosesc functia putere asa ca am adaptat ultima solutie sa foloseasca radical de ordinul doi pentru a obtine o putere rationala de ordinul 1e-6. Codul sub aceasta forma este mai jos.

Cod:

double ln(double x)
{
	double rx = x;
	for (int i = 1; i <= 20; i++)
		rx = sqrt(rx);
	double df = x * x * rx - x * x;
	double dx = 1 / (double)(1 << 20);
	return (df / dx) / (x * x * sqrt(rx));
}

Ati putea sa-mi spuneti de ce abordarea urmatoare e gresita: calculez distantele intre toate nodurile speciale, memorand drumurile intre oricare doua si apoi fac APM pe aceste drumuri, iar la sfarsit insumez costurile muchiilor din care sunt compuse drumurile avand grija sa nu le adun de mai multe ori?

Merci!

Ar putea sa-mi spuna cineva ce era gresit in a afla toate perechile de drumuri minime intre nodurile speciale si a face APM-ul pe aceste drumuri, avand in vedere ca nu ne intereseaza care este efectiv drumul cred ca se putea face chiar si cu Roy-Floyd?

1. APM-ul trebuie sa fie doar pentru cele T noduri speciale sau pentru tot graful?
2. Daca raspunsul la intrebarea precedenta este doar pentru cele T noduri speciale, atunci poate acesta sa contina si alte noduri?

Multumesc!

Cred ca este o problema cu limita de timp, nici sursa oficiala nu scoate mai mult de 70p.

Modificare:
Sursa oficiala(70p): http://infoarena.ro/job_detail/661219
Am reusit acum sa obtin 100p, sursa este http://infoarena.ro/job_detail/661390

Ati putea sa-mi spuneti si mie ce s-ar putea optimiza la http://infoarena.ro/job_detail/587011 deoarece nu ia 100p, iar acelasi algoritm scris in Pascal ia punctajul maxim http://infoarena.ro/job_detail/587028 ?

Inca un site foarte util pentru invatarea limbajului de asamblare(pentru Win32): http://win32assembly.online.fr/