szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 maja 2011, o 21:53 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
Obrazek

Sprawa wygląda tak: trzeba znaleźć najkrótszą drogę między danymi dwoma punktami o współrzędnych (w _{x} ; \ w _{y} ) oraz (r _{x} ; \ r _{y} ), jednak na obszarze (0; \ d) można się poruszać jedynie równolegle do osi OX. Czyli trzeba znaleźć długość najkrótszej możliwej łamanej zaznaczonej na czerwono na rysunku.

Dane to oczywiście: w _{x}, \ w _{y}, \ r _{x}, \ r _{y}, \ d.

Moje pytanie brzmi: jak zrobić to najsprytniej? Bo wiem że jakoś sprytnie się da.


Sformułowałem tak pytanie, gdyż zadanie to zrobiłem, jednak straciłem dużo włosów przy koszmarnych obliczeniach i nie bardzo mnie to satysfakcjonuje. Przedstawię jednak jak to robiłem:

Wprowadziłem stałą y=h, gdzie h jest niewiadomą którą chcemy znaleźć, dla której poprowadzona łamana będzie najkrótsza. Wobec tego optymalizuję taką funkcję:

f(h)= \sqrt{(w _{x}-d)^{2} + (w _{y}-h)^{2}} +  \sqrt{( r _{y}-h)^{2} +  r _{x}^{2}} + d

W takim razie policzenie pochodnej i szukanie minimum jest co najmniej niewygodne i jestem pewien że da się prościej (a zawsze dążę do tego żeby zrobić zadanie na kilka sposobów i szukać zawsze prostszych rozwiązań).


Jakieś pomysły?
Góra
Mężczyzna Offline
PostNapisane: 20 maja 2011, o 22:03 
Administrator

Posty: 21381
Lokalizacja: Wrocław
Zauważ, że droga na obszarze (0,d) nie wpływa na na długość całej drogi - zawsze jest taka sama. Wyobraź sobie zatem, że "zniknąłeś" ten obszar (opcja "Ukryj" w Excelu...).

JK
Góra
Mężczyzna Offline
PostNapisane: 20 maja 2011, o 22:07 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
czyli po prostu Pitagoras dla punktów: (w _{x}-d; \ w _{y}  ) i (r _{x} ; \ r _{y} ) plus oczywiście d? Faktycznie tak wygląda na rysunku, ale nie chciałem się sugerować tym..

-- 21 maja 2011, o 00:14 --

zastanawiam się nad uzasadnieniem tego.. oczywiście gdy optymalizowałem napisaną przeze mnie funkcję odległość d nie miała znaczenia bo pochodna ze stałej to zero.. zawsze myślałem że obszar (0; \ d) mimo że jest stały to wpływa na h..

-- 22 maja 2011, o 18:35 --

tak właściwie to mam taki program do napisania.. obliczanie wyżej wymienioną przeze mnie metodą daję błędny wynik.. ma ktoś jakiś pomysł jak sprytnie znaleźć tą najkrótszą drogę?
Góra
Mężczyzna Offline
PostNapisane: 30 maja 2011, o 16:30 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
podbijam temat, problem uważam wciąż za nierozwiązany.. jakieś pomysły co do sprytnego obliczenia tej drogi?
Góra
Mężczyzna Offline
PostNapisane: 30 maja 2011, o 16:37 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
adambak napisał(a):
czyli po prostu Pitagoras dla punktów: (w _{x}-d; \ w _{y}  ) i (r _{x} ; \ r _{y} ) plus oczywiście d?

A co jest złego w tym? Wygląda całkiem dobrze. Na jakimś przykładzie nie działa?
Góra
Mężczyzna Offline
PostNapisane: 30 maja 2011, o 17:08 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
Tak, nie działa. Najgorsze w tym wszystkim są dwie rzeczy:
1) nie jestem w stanie podać testu dla którego nie działa
2) jest to jedno z zadań z Polskiego SPOJa na którym to czynnie szkolę się w programowaniu, jednak w takim razie temat robi się informatyczny i serdecznie przepraszam moderatorów za taki rozwój sytuacji, ale muszę podać kod, bo być może nie ze względów matematycznych program nie przechodzi (jeśli to będzie konieczne to oczywiście niech temat zostanie przeniesiony do działu Informatyka, umieściłem go tutaj, bo tak chciałem rozwiązać to, a dział Informatyka jest rzadziej odwiedzany, przyznaję że to mnie skusiło do umieszczenia tego w takiej formie tutaj)

Program oczywiście przechodzi wszystkie testy gdy d=0, jednak ani jednego gdy d \neq 0, czyli coś tutaj nie zdaje egzaminu. Być może w takim razie ja robię jakiś błąd w kodzie.

To jeszcze podam specyfikację problemu.
Wejście: liczba n, wskazująca na ilość przedmiotów o współrzędnych w drugiej i trzeciej ćwiartce układu współrzędnych (czyli na rysunku przedstawia je punkt: (r  _{x}  ; \ r _{y} )), współrzędne (w _{x} ; \ w _{y} ) określające nasze położenie, liczba t będąca czasem jaki mamy na odbycie drogi między (w _{x} ; \ w _{y} ) a jednym z przedmiotów (w tę i z powrotem), długość d (na tej długości poruszamy się z prędkością 1 \frac{m}{s}), oraz liczba v oznaczająca prędkość z jaką się poruszamy wszędzie tylko nie w (0; \ d), wszystkie dane na wejściu są całkowite

Wyjście: maksymalna liczba przedmiotów jakie możemy przenieść do punktu (w _{x} ; \ w _{y} ) (drogę zawsze odbywamy z tego punktu do przedmiotu i z powrotem) w czasie t


Program napisany w C:
Kod:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <math.h>

void quicksort(double *tab, int x, int y)
{
  int i,j;
  double v,temp;
  i=x;
  j=y;
  v=tab[x];
 
  do
  {
    while(v>tab[i])i++;
    while(v<tab[j])j--;
    if(i<=j)
    {
      temp=tab[i];
      tab[i]=tab[j];
      tab[j]=temp;
      i++;
      j--;
    }
  }
  while(i<=j);
 
  if(x<j)quicksort(tab,x,j);
  if(i<y)quicksort(tab,i,y);
}

int main()
{
  int n,i;
  double t,d,wx,wy,rx,ry,v,s,czas;
 
  scanf("%d", &n);
  scanf("%lf%lf%lf%lf%lf", &t, &d, &wx, &wy, &v);

  double czasy[n];
  for(i=0; i<n; i++)
  {
    scanf("%lf%lf", &rx,&ry);
    wx-=d;
    s=sqrt((wx-rx)*(wx-rx)+(wy-ry)*(wy-ry));
    czasy[i]=2*(d+(s/v));
  }
 
  quicksort(czasy, 0, n-1);
 
  i=0;
  czas=0.0;
  while(czas<=t)
  {
    czas+=czasy[i];
    i++;
  }

  printf("%d\n", i-1);
  return 0;
}



czyli tworzę tablicę czasów dla każdego z przedmiotów, czasy obliczam obliczając wcześniej drogę zgodnie z tym co powyżej, sortuję ją i sprawdzam ile przedmiotów maksymalnie mogę przenieść..
Góra
Mężczyzna Offline
PostNapisane: 30 maja 2011, o 20:58 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Jedyny błąd jaki widzę jest taki, że w ostatniej pętli nie patrzysz czy i<n, więc możesz wyjść poza tablicę. Pewnie jednak nie jest to ten błąd który powoduje złe wyniki dla wszystkich d>0.
Góra
Mężczyzna Offline
PostNapisane: 30 maja 2011, o 21:15 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
Też już o tym myślałem i poprawiałem, jednak z tym samym rezultatem.. To nie to, z resztą program nie wywalał błędu SIGSEGV tylko ciągle błędną odpowiedź, ale faktem jest że dopiero dzisiaj to zauważyłem, a błąd jednak spory..

No nic, szukam dalej, długo już nie mogę zmęczyć tego zadania..
Góra
Mężczyzna Offline
PostNapisane: 31 maja 2011, o 00:04 
Użytkownik

Posty: 2911
Lokalizacja: Kraków
Chyba znalazłem ten błąd.

Instrukcja:
Kod:
1
wx-=d;


Za każdym cyklem w pętli współrzędna wx jest zmniejszana o d.
Proponuję ją wyrzucić, a odejmowanie zrobić tu:
Kod:
1
s=sqrt((wx-d-rx)*(wx-d-rx)+(wy-ry)*(wy-ry));
Góra
Mężczyzna Offline
PostNapisane: 31 maja 2011, o 00:20 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
Niesamowite... czegoś tak głupiego nie zrobiłem (i nie mogłem znaleźć) od... już nie pamiętam jak dawna, teraz oczywiście przechodzi wszystkie testy poprawnie..

Dzięki!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 znaleźć przeciwobraz - zadanie 2  gawli  10
 znalezc dziedzine funkcji - zadanie 2  pastazip  1
 Znaleźć wszystkie funkcje.  pawlo392  2
 Znaleźć wszystkie funkcjie, dla których zachodzi równość.  marek24  1
 znaleźć funkcje odwrotne - zadanie 2  yoyki  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl