🚀 go-pugleaf

On pon, 29 mar 2010 15:54:23 in article news:<hoqb68$96v$1@srv.cyf-kr.edu.pl>
"Tomasz Stypuła" wrote:
> Witam,
> 
> Liczby natruralne a i b spełniają warunek: 5/31 < a/b < 7/43.
> Znaleźć najmniejszą możliwą wartość b.

Przepiszmy to ogólniej: c/d < a/b <e/f

Na myśl przychodzą mi:
http://pl.wikipedia.org/wiki/Ciąg_Fareya
http://pl.wikipedia.org/wiki/Drzewo_Sterna-Brocota
 
> (zadanie wzięte z pewnego zbioru zadań maturalnych)

Ale chyba tego powyższego nie uczą???
Można jednak z tego wyciągnąć wniosek, że b będzie w przedziale [1,d+f].

Wypisywanie ciągów Fareya nie wydaje mi się efektywne.
Na razie nie widzę lepszej metody  niż kolejne sprawdzanie:

Dla b=1,2,... obliczamy a=floor(b*c/d)+1 i sprawdzamy warunek a/b < e/f.
(floor to polsku podłoga lub część całkowita).


A może ...

Wracając do Sterna-Brocota wydaje mi się, że rozwijając p=c/d,
k=e/f, m=a/b w ułamki łańcuchowe możemy uzyskać pożądany wynik.
Korzystając z notacji poziomej:
    http://pl.wikipedia.org/wiki/U%C5%82amek_%C5%82a%C5%84cuchowy
i własności tych ułamków:
   http://perl.plover.com/yak/cftalk/TALK/slide044.html
możnaby wypracować jakiś algorytm.

Mając 
  p=[p0,p1,p2,...]
  k=[k0,k1,k2,...]
trzeba rozważać różne przypadki, w zależności od pierwszej
pozycji "i", gdzie p(i)<>k(i). Gdy któryś z ciągów kończy się
wcześniej, to można przyjąć, że na następnej pozycji występuje
nieskończoność.

1) Najłatwiej jest, gdy abs(ki-pi)>1 - mamy dwa podprzypadki:
   1a) i - parzyste,    m=[p1,...,p(i-1),pi+1]
       czyli bierzemy pierwsze "i"-pozycji, a ostatnią
       zwiększamy o jeden.
   1b) i - nieparzyste, m=[k(1),...,k(i-1),k(i)+1]

c/d=0   [0]
a/b=1   [1]
e/f=5   [5]

c/d=(3 /2)      [1, 2]
a/b=2           [2]
e/f=(11 /2)     [5, 2]

c/d=(13 /5)     [2, 1, 1, 2]
a/b=(8 /3)      [2, 1, 2]
e/f=(37 /13)    [2, 1, 5, 2]

c/d=(11 /9)     [1, 4, 2]
a/b=(16 /13)    [1, 4, 3]
e/f=(5 /4)      [1, 4]

c/d=(6 /5)      [1, 5]
a/b=(4 /3)      [1, 3]
e/f=(3 /2)      [1, 2]

c/d=(33 /29)     [1, 7, 4]
a/b=(107 /94)    [1, 7, 4, 3]
e/f=(5725 /5029) [1, 7, 4, 2, 3, 4, 5]

2) Gdy abs(ki-pi)=1, to sprawa się nieco komplikuje ... :(

On 29 Mar, 15:54, "Tomasz Stypuła" <tsWYTNI...@wa.fema.pl> wrote:
> Witam,
>
> Liczby natruralne a i b spełniają warunek: 5/31 < a/b < 7/43.
> Znaleźć najmniejszą możliwą wartość b.
>
> (zadanie wzięte z pewnego zbioru zadań maturalnych)
>
> W tym konkretnym przypadku jest dość znośnie, ale jeśli wziąć
> jakieś inne liczby, to może być gorzej (chyba, że coś przeoczyłem).
> Jakie jest dobre podejście do takiego zadania?

Jest prosta metoda generowania wymiernych przyblizen.
Zaczynamy od a/b=0/1.
Teraz powtarzamy. Jesli nasz ulamek jest mniejszy niz
x, zwiekszamy licznik, jesli nie - mianownik.

Mozna zastosowac to do naszego problemu, zwiekszamy licznik
jesli jestesmy na lewo od przedzialu, mianownik, gdy jestesmy na
prawo od przedzialu. W koncu trafimy i bedzie to liczba o najmniejszej
sumie a+b. Chwila zastanowienia i okaze sie, ze to bedzie rowniez
liczba o najmniejszym b.

Niestetyy, jest to dobry sposob dla komputera, ale dosc czasochlonny
przy recznym liczeniu.

pozdrawiam
bartekltg

  Tomasz Stypuła napisał:

> Liczby natruralne a i b spełniają warunek: 5/31<  a/b<  7/43.
> Znaleźć najmniejszą możliwą wartość b.
>
> (zadanie wzięte z pewnego zbioru zadań maturalnych)
>
> W tym konkretnym przypadku jest dość znośnie, ale jeśli wziąć
> jakieś inne liczby, to może być gorzej (chyba, że coś przeoczyłem).
> Jakie jest dobre podejście do takiego zadania?

Co to znaczy, że jest dość znośnie?. Znasz jak to rozwiązać ?, no to wiesz jak rozwiązać 
te inne ;).
W takich zadaniach trudniej jest ułożyć tak treść zadania, żeby było jednoznaczne 
rozwiązanie niż je rozwiązać!

5/31 < a/b < 7/43   /* mnożymy przez obydwa mianowniki

  215 < 31*43 *a/b < 217
co mamy pomiędzy 215 i 217 ;) 216
Ponieważ 31 , 43 i 216 są względnie pierwsze a 'a' i 'b' powinny być całkowite, stąd

a= 216    b=31*47

PS. zadanie jest prymitywne, ale ponieważ Mirek wyciągnął armatę to odrobiłem za ciebie 
szybciutko to zdanie żebyś nie wpadł w kompleksy

-- 
  Boguś

On 30 Mar, 17:08, Boguś <telemor...@wp.pl> wrote:

> Co to znaczy, że jest dość znośnie?. Znasz jak to rozwiązać ?, no to wiesz jak rozwiązać
> te inne ;).
> W takich zadaniach trudniej jest ułożyć tak treść zadania, żeby było jednoznaczne
> rozwiązanie niż je rozwiązać!
>
> 5/31 < a/b < 7/43   /* mnożymy przez obydwa mianowniki
>
>   215 < 31*43 *a/b < 217
> co mamy pomiędzy 215 i 217 ;) 216
> Ponieważ 31 , 43 i 216 są względnie pierwsze a 'a' i 'b' powinny być całkowite, stąd
>
> a= 216    b=31*47
>
> PS. zadanie jest prymitywne, ale ponieważ Mirek wyciągnął armatę to odrobiłem za ciebie
> szybciutko to zdanie żebyś nie wpadł w kompleksy

Wszytko pieknie, tyle, ze zle!
Poprawna odpowiedzia jest najprawdopodobniej 6/37.
Chcemy miec jak najmniejszy b.
W dodatku problem wydaje sie jednoznaczny.

pozdrawiam
bartekltg

On wto, 30 mar 2010 18:29:10 in article news:<d8e8a804-6054-48c5-bbea-cdc113efc242@k19g2000yqn.googlegroups.com>
bartekltg wrote:
> Poprawna odpowiedzia jest najprawdopodobniej 6/37.
> Chcemy miec jak najmniejszy b.
> W dodatku problem wydaje sie jednoznaczny.

Potwierdzam

c/d=(5 /31)     [0, 6, 5]
a/b=(6 /37)     [0, 6, 6]
e/f=(7 /43)     [0, 6, 7]

Użytkownik "Boguś" <telemorele@wp.pl> napisał
w wiadomości news:hot4ri$f5q$1@nemesis.news.neostrada.pl...
>  Tomasz Stypuła napisał:
>
>> Liczby natruralne a i b spełniają warunek: 5/31<  a/b<  7/43.
>> Znaleźć najmniejszą możliwą wartość b.
>>
>> (zadanie wzięte z pewnego zbioru zadań maturalnych)
>>
>> W tym konkretnym przypadku jest dość znośnie, ale jeśli wziąć
>> jakieś inne liczby, to może być gorzej (chyba, że coś przeoczyłem).
>> Jakie jest dobre podejście do takiego zadania?
>
> Co to znaczy, że jest dość znośnie?.

To zapewne znaczy że da się w "znośnym" czasie porachować
"na piechotę", w przeciwieństwie np. do tego samego polecenia
przy warunku z mianownikami o rząd lub dwa wyższymi.



> W takich zadaniach trudniej jest ułożyć tak treść zadania,
> żeby było jednoznaczne rozwiązanie niż je rozwiązać!
>
> 5/31 < a/b < 7/43   /* mnożymy przez obydwa mianowniki
>
>  215 < 31*43 *a/b < 217
> co mamy pomiędzy 215 i 217 ;) 216

Oraz alef_zero innych liczb wymiernych...


> Ponieważ 31 , 43 i 216 są względnie pierwsze a 'a' i 'b'
> powinny być całkowite,

No ale to tylko gdy się uprzesz, że iloczyn  31*43*a/b  na być
całkowity. A w zadaniu takiego wymagania nie ma - może być
niecałkowity, byle znajdował się w przedziale (215, 217)...


> stąd
>
> a= 216    b=31*47

Tylko że b = 31*43, jeśli już...


Maciek 

On 30 Mar, 17:08, Boguś <telemor...@wp.pl> wrote:
>   Tomasz Stypu a napisa :
>
> > Liczby natruralne a i b spe niaj warunek: 5/31<  a/b<  7/43.
> > Znale najmniejsz mo liw warto b.
>
> > (zadanie wzi te z pewnego zbioru zada maturalnych)
>
> > W tym konkretnym przypadku jest do zno nie, ale je li wzi
> > jakie inne liczby, to mo e by gorzej (chyba, e co przeoczy em).
> > Jakie jest dobre podej cie do takiego zadania?
>
> Co to znaczy, e jest do zno nie?. Znasz jak to rozwi za ?, no to wiesz jak rozwi za
> te inne ;).

No właśnie, że nie jest tak prosto :)

> W takich zadaniach trudniej jest u o y tak tre zadania, eby by o jednoznaczne
> rozwi zanie ni je rozwi za !

Tutaj jest jednoznaczne, bo b jest _naturalne_ i szukamy
_najmniejszego_, a zbiór b spełniających warunki jest niepusty
- możesz wziąć średnią z tych ułamków i otrzymasz ułamek wymierny
pomiędzy.

> 5/31 < a/b < 7/43   /* mno ymy przez obydwa mianowniki
>
>   215 < 31*43 *a/b < 217
> co mamy pomi dzy 215 i 217 ;) 216
> Poniewa 31 , 43 i 216 s wzgl dnie pierwsze a 'a' i 'b' powinny by ca kowite, st d
>
> a= 216    b=31*47
>
> PS. zadanie jest prymitywne, ale poniewa Mirek wyci gn armat to odrobi em za ciebie
> szybciutko to zdanie eby nie wpad w kompleksy
>

Dzięki za chęci, ale rozwiązanie jest błędne, co już Ci Bartek
napisał.

To konkretne zadanie zrobiłem tak (na początku nie miałem żadnego
rozsądnego sposobu poza sprawdzaniem b po kolei,
a potem zacząłem szukać ograniczeń na b):

5/31<  a/b<  7/43

jest równoważne

a/7 < b - 6a < a/5

Stąd wynika ograniczenie, ze a >= 6 (bo b-6a jest całkowite i
dodatnie),
a stąd dalej że 36 <= 6a < b. Czyli b >= 37. Sprawdzam, że b=37 jest
ok.


Pozdrawiam,

Tomek

Dziękuję wszystkim za wypowiedzi, w szczególności Mirkowi za
przywołanie drzewa  Sterna-Brocota (nauczyłem się jak prosto otrzymać
ułamek wymierny pomiędzy dwoma danymi) i  Bartkowi za metodę dla
komputera.
Wygląda więc na to, że w tym zadaniu dużą rolę odgrywają
nieprzypadkowe dane, ale czy jest to dobre zadanie na maturę to inna
kwestia.
Moim zdaniem dobre jako jedno z tych wymagających trochę
pokombinowania - chociaż kto wie - czasem brutalna siła wygrywa.

Pozdrawiam,
Tomek

On wto, 30 mar 2010 17:08:40 in article news:<hot4ri$f5q$1@nemesis.news.neostrada.pl>
Boguś wrote:
> PS. zadanie jest prymitywne, ale ponieważ Mirek wyciągnął armatę to odrobiłem za ciebie 
> szybciutko to zdanie żebyś nie wpadł w kompleksy

No to bez armat, z wykorzystaniem materiału dostępnego w liceum :)

Ogólny zapis zadania: min(b) dla:
p=c/d, m=a/b, k=e/f
p < m < k

Nierówności możemy sprowadzić do równań:

m-p=(a*d-b*c)/(b*d) > 0 ==>  

  (1) m-p=d1/(b*d), gdzie całkowite d1>0

k-m=(b*e-a*f)/(b*f) > 0 ==>  

  (2) k-m=d2/(b*f), gdzie całkowite d2>0

Uład równań (1) i (2) po przekształceniach:

  d1 - a d + b c = 0
  a f - b e + d2 = 0

rozwiązany względem a,b daje:
                           d1 e + c d2      d1 f + d d2
(3)                  [[a = -----------, b = -----------]]
                            d e - c f        d e - c f

po podstawieniu danych z zadania: [c = 5, d = 31, e = 7, f = 43]
otrzymujemy:
                          5 d2 + 7 d1      31 d2 + 43 d1
                    [[a = -----------, b = -------------]]
                               2                 2

Dla d1=1, d2=1 otrzymujemy najmniejsze całkowite rozwiązanie:
                               [[a = 6, b = 37]]

W ogólny przypadku liczbowym znalezienie d1,d2 będzie
trudniejsze ...
Nie mam pomysłu, krążąc w kółko ląduję na kolejnym sprawdzaniu
jak np. w algorytmie podanym przez bartekltg.

END

W ostatnim mój poście myślami byłym gdzie indziej ;). No i wyszedł falstart po którym 
wywiązała się ożywiona dyskusja. Padły poprawne odpowiedzi i różne drogi do niego.

napisał m.in. Mirek :

>>> PS. zadanie jest prymitywne, ale ponieważ Mirek wyciągnął armatę to odrobiłem za ciebie
>> szybciutko to zdanie żebyś nie wpadł w kompleksy

i teraz użył pistoleciku ;) tj zestawu równań i rozwiązał je

> No to bez armat, z wykorzystaniem materiału dostępnego w liceum :)
........
> otrzymujemy:
>                               5 d2 + 7 d1      31 d2 + 43 d1
> (4)                     [[a = -----------, b = -------------]]
>                                 2                 2
>
> Dla d1=1, d2=1 otrzymujemy najmniejsze całkowite rozwiązanie:
>                                 [[a = 6, b = 37]]

Wynik jest oczywiście poprawny i co najważniejsze umożliwia obliczenie dalszych rozwiązań

Spróbujmy jednak sprawę uprościć :
    (5)      5/31 < a/b < 7/43
wyjściową nierówność (5) odrócimy tak 1/wyrażenie . Możemy to zrobić bezpiecznie bo 
wszystkie składniki są dodatnie. Musimy tyko pamiętać, żeby zmienić kierunek nierówności

   (6)    31/5 > b/a > 43/7   => (6+1/5) > b/a > (6+1/7)

Pomiędzy 1/5 a 1/7 jest 1/6 . Czyli b/a=6+1/6  =>  a=6 b=37

Nie przyjrzałem się dokładnie wprowadzeniu wzoru (4) Mirka, ale powinno być tak:
   'jeżeli d1+d2 jest nieparzyste to nie dziel przez 2'

Te same dalsze wyniki prościej możemy otrzymać tak:
   (7)    (6+1/5) > (6+n1/n2) > (6+1/7) po odjęciu 6 otrzymujemy
   (8)       1/5 > n1/n2  > 1/7
  z nierówności lewej otrzymujemy n2 > 5 n1 z nierówności prawej otrzymujemy n2 <7 n1
czyli (9)    5 n1 < n2 < 7 n1
Rozwiązaniem jest b/a = 6 + n1/n2  => (10)  a= n2   b= 6 n2 + n1

  n1    n2           ( a,b)
   1     6           (6,37)
   2   11,12,13      (11,68),(12,74),(13,80)
   3 16,17,18,19,20  (16,99),(17,105),(18,111),(19,117),(20,123)
  itd
[ dopisek - niektóre wyniki nie są względnie pierwsze, można je uprościć i otrzymujemu 
wcześniejsze wyniki np (12,74) -> (6,37)   (18,111) -> (6,37)    ]

Znając już sposób rozwiązywanie tych zadań możemy bez problemu dla przykładu rozwiązać 
takie zadanie
    7/64 < a/b < 9/82
jak również bardziej złożonego np takiego
   11/35 < a/b < 7/22
Przypominam :  szukamy najmniejszego b .
Miłej zabawy

-- 
  Boguś

Użytkownik "bartekltg" <bartekltg@gmail.com> napisał
w news:21f61cac-3ddf-4196-bde6-38190a537738@v20g2000yqv.googlegroups.com...
>
>>
>> (........)
>>
>
> Jest prosta metoda generowania wymiernych przyblizen.
> Zaczynamy od a/b=0/1.
> Teraz powtarzamy. Jesli nasz ulamek jest mniejszy niz
> x, zwiekszamy licznik, jesli nie - mianownik.

Komputer to elektroniczny debil, posłusznie i bez refleksji
wykona najdłuższe działania -- tyle że jest mega-giga-szybki,
dzięki czemu te działania mają jakąś szansę powodzenia.  ;)

Ale ta metoda jest zbyt prymitywna, zatem za długa, nawet
jak na komputer.

Wyobraźmy sobie, że szukamy liczby 99,7. Jak to pójdzie?
Ano najpierw sto iteracji po liczbach naturalnych. Gdy
100/1 okaże się za duże, zwiększymy mianownik o 1 ...i co?
I jesteśmy przy 100/2 = 50. Czyli w połowie przebytej
już raz drogi! I mamy przed sobą kolejne prawie sto iteracji
(50 1/2, 51, 51 1/2, ...) do osiągnięcia liczby 99, którą
PRZED CHWILĄ sprawdzaliśmy i okazała się jeszcze za mała!

Po czym w dwu kolejnych krokach znów dojdziemy do 100,
zwiększymy licznik do 3 i znajdziemy się przy liczbie
200/3, i znów mamy przed sobą sto iteracji...

Może więc przy zwiększaniu mianownika skorygować również
licznik? Tak, aby uzyskany ułamek był możliwie bliski
ostatniej sprawdzonej liczbie (ale nie większy od niej):

    licznik   L := floor( (L - 1) * (M + 1) / M )
    mianownik M := M + 1

W ten sposób wykrycie reprezentacji 99,7 = 997/100
zajmuje 124 iteracje zamiast 1006.
A gdybyśmy tak na początek mogli wziąć L = floor z danej,
to pozostanie tylko 25 iteracji do wykonania (alogrytmowi
prymitywnemu oszczędza to tylko pierwszej setki kroków,
pozostałe 900 musi przejść).


Maciek