Afişează mesaje
Pagini: [1]
1  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 199 Graf : Februarie 27, 2012, 09:00:05
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.
2  infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Introducere in algoritmi : Februarie 06, 2012, 14:21:10
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.
3  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Code golf challenge: logaritm : Februarie 03, 2012, 19:06:18
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));
}
4  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1232 Subarbore : Ianuarie 25, 2012, 14:54:57
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!
5  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2012 / Răspuns: Subarbore : Ianuarie 22, 2012, 13:11:28
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?
6  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2012 / Răspuns: Subarbore : Ianuarie 22, 2012, 09:31:23
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!
7  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 033 Flux maxim de cost minim : Ianuarie 13, 2012, 22:36:34
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
8  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 028 Sortare prin comparare : Mai 03, 2011, 18:53:50
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 ?
9  infoarena - concursuri, probleme, evaluator, articole / Articole / Răspuns: Introducere in asamblare : Aprilie 08, 2010, 12:49:40
Inca un site foarte util pentru invatarea limbajului de asamblare(pentru Win32): http://win32assembly.online.fr/
Pagini: [1]
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines