Toster Napisano Październik 3, 2008 Zgłoś Share Napisano Październik 3, 2008 Hejka, Ostatnio bawie sie w podzialy zbioru i zastanawiam sie czy komus jakby sie nudzilo nie chcialoby sie troche pokombinowac. Opisze problem i napisze co udalo mi sie narazie uzyskac. Otoz mamy trzy przedzialy liczbowe 660 000 000 - 660 999 999 667 000 000 - 667 999 999 668 000 000 - 668 999 999 czyli w sumie kolo 3 000 000 liczb. teraz mamy taka operacje: i mod n = 0 gdzie i to wartosc z tych przedzialow, natomiast n to jedna z 9 liczb. czyli zalozmy np ze: n = 1, 2, 3, 7, 8, 9, 10, 12, 25 w efekcie robimy petle po wartosciach n, jesli liczba i spelnia warunek i mod n[k] = 0 to zwiekszamy wynik dla k o 1 w efekcie otrzymamy takie cos: 1 - 27,4 % 2 - 17,1 % 3 - 13,0 % 7 - 9,6 % 8 - 6,7 % 9 - 7,6 % 10 - 6,7 % 12 - 8,0 % 25 - 4,0 % czyli z 3000 000 liczb 17,1% bylo podzielne bez reszty przez 2. Do czego dazymy ? Ano do tego aby uzyskac rownomierne rozdzielenie po wszystkich 9 przedzialach... czyli znalezc takie liczby n aby w kazdym przedziale bylo po ~11,1% wszystkich wartosci. Wazne jest aby wszystkie liczby byly przypisane do odpowiednich przedzialow. Ponizej wklejam kod jaki naklepalem po krotce, w miare moich postepow bede dorzucal kolejne wersje/modyfikacje TTab = array[0..8] of integer; function findBest(var dat: TTab):integer; const prefix: array[0..2] of integer = (660000000, 667000000, 668000000); var t, i, j: integer; pref, y: integer; a: array[0..8] of integer; prc, tmp: real; b: boolean; begin for t := 0 to 8 do begin a[t] := 0; repeat dat[t] := Random(30); if dat[t] <> 0 then begin b := false; for y := 0 to t-1 do if dat[t] = dat[y] then begin b := true; break; end; if b = false then break; end; until false; end; dat[0] := 1; for t := 0 to 8 do for y := 0 to t -1 do if dat[t] < dat[y] then begin i := dat[t]; dat[t] := dat[y]; dat[y] := i; end; for j := 0 to High(prefix) do begin pref := prefix[j]; for t := 0 to 1000000 do begin y := pref + t; for i := 8 downto 0 do begin if y mod dat[i] = 0 then begin Inc(a[i]); break; end; end; end; end; tmp := 1; for t := 0 to 8 do begin prc := a[t] * 100 / 3000000; prc := Abs(prc - 11.1); tmp := tmp + prc; end; Result := Round( tmp ); end; procedure ShowBest(const dat: TTab); const prefix: array[0..2] of integer = (660000000, 667000000, 668000000); var t, i, j: integer; pref, y: integer; a: array[0..8] of integer; prc: real; begin for t := 0 to 8 do a[t] := 0; for j := 0 to High(prefix) do begin pref := prefix[j]; for t := 0 to 1000000 do begin y := pref + t; for i := 8 downto 0 do begin if y mod dat[i] = 0 then begin Inc(a[i]); break; end; end; end; end; for t := 0 to 8 do begin prc := a[t] * 100 / 3000000; form2.memo1.lines.add( Format('%d - %.1f', [t, prc] )); end; end; procedure TForm2.Button4Click(Sender: TObject); var bestT: TTab; bestC: integer; tmp: TTab; t, y: integer; s: string; begin Randomize; bestC := 100000; for t := 0 to 100 do begin y := findBest(tmp); if y < bestC then begin bestC := y; bestT := tmp; end; memo1.lines.add('pass:'+IntToStr(t)+' Coeff:'+IntToStr(y)); end; memo1.lines.add('BestCoef:'+IntToStr(bestC)); s := ''; for t := 0 to 8 do s := s + IntToStr(bestT[t])+', '; memo1.lines.add(s); ShowBest(bestT); end; Always Dark<br /> Link do komentarza Udostępnij na innych stronach More sharing options...
Force Napisano Październik 3, 2008 Zgłoś Share Napisano Październik 3, 2008 1 - czyli że żyje 2 - coś przykłąd jest zrąbany, jak możliwe, aby z 3 000 000 sąsiednich liczb tylko 17% była parzysta(mod 2 =0) to musi byc 50% 3 - jeszcze nie wymyśliłem bo minęło 5 minut, ale pierwsze spostrzeżenie, wszystkie dziewięć liczb musi być względnie pierwsze z każdą z tych liczb (lub bardzo duże) 4 - te 11% to musza być rodzielne między sobą, inaczej mówią-dla każdej z tych 3000000 liczb istnieje dokładnie jedna liczba z tych 9, a dla każdej z tych 9 istnieje dokładnie 1000000/3 liczb z 3000000? A tak wogóle to wydaje mi się, że nie da się takich 9 liczb znaleźć ponieważ, dla każdych ab (nawet NWD(a,B)=1) istnieje NWW(a,B)=c i a |c oraz b | c więc c/a =d e=c/b czyli już w przedziale 1..c mamy liczb podzielnych przez a różną od tych przez b, i ta różnica będzie taka sama w przedziale c+1..c+c; c+c+1..c*3. Jeśli natamiast potrzebujemy 9 liczb które modulo z czymś dają 0 i dla każdej chcemy aby coś było (np. tylko 2 liczby) to da się, ale będzie to rzadkie pokrycie. Ok, oto mój pomysł: definiujemy jedną liczbę, która ma być największa musi być ona przypuszczalnie większa od pierwiastka z 668 999 999, nazwijmy ją "c", a ilość wystąpień w zbiorze "k", obliczamy (C*k-3000000)/(k+1) nazwijmy to d, i teraz możliwe liczby które pokryją nasz przedział też k-razy to liczby z przedziału d..c", jak d jest wieksze od c, to za małe "c" ustaliliśmy". We wzorze 3000000 bo tyle liczb jest w przedziale. Teraz pesudo dowód tezy, która nie jest pewna. Otóż - keśli mamy 9 liczb, nie ma sensu badać innych niż skrajne bo wystarczy, że najmniesza daje 11% i największa, inne też muszą jak nie to: pokrywają mniej,ale stąd wynika, że ta nasza najwieksza nie jest największa; jak wiecej to odwrotnie z najmniejszą. Najmniejsza liczba to a, największa b, nie mogą się różnić w ilościach nawet o jeden, więc badam czy różnica jest >=1, k-ilość tych co dziela się przez "b" to otrzymujemy k*b oraz k*a, ale chcemy wiedzieć, czy "a" się zmieści więcej razy (bo jest mniejsza) to badamy (k+1)*a, tworzymy nierówność a(k+1)-bk "bla bla" możemy upakować maks "k" razy, a jak "a" > "b" to wogóle wał, bo "b" za małe wzięliśmy no i b-a >= 8 bo musimy wziąść 9 liczb. Czyli binarnie szukamy najmniejszego "b"(dostajemy z automata "k") co "a" by spełniło tę nierówność (może jednak "b" mniejsze od tego pierwiastka) i masz przedzał [a..b] z którego bierzesz 9 liczb i gotowe . Wiem, że mało gramatycznie napisane Ale sprawdź czy daje takie wynik jak chcesz, bo to co napisałem to teoria Baza tysięcy lotnisk: http://airportsbase.com Link do komentarza Udostępnij na innych stronach More sharing options...
Toster Napisano Październik 3, 2008 Autor Zgłoś Share Napisano Październik 3, 2008 Ad 2 jak zerkniesz do kodu to sprawdzane sa liczby od najwiekszej do najmniejszej, wiec jesli sprawdzony jest ktorys z wczesniejszych warunkow (np podzielne przez 3) to nie dochodzi do 2. Pozatym nie zakladam ze istnieje mozliwosc wyznaczenia liczb takich aby bylo dokladnie po rowno. Chodzi o to aby dostac mozliwie rownomierny podzial. Always Dark<br /> Link do komentarza Udostępnij na innych stronach More sharing options...
Force Napisano Październik 3, 2008 Zgłoś Share Napisano Październik 3, 2008 Up, widzę, że jak edytowałem posta to odpisałeś to chce to pokazać Edit: "jak zerkniesz do kodu to sprawdzane sa liczby od najwiekszej do najmniejszej, wiec jesli sprawdzony jest ktorys z wczesniejszych warunkow (np podzielne przez 3) to nie dochodzi do 2." z takim założeniem, mój pomysł nie da najbardziej optymalnego rozwiązania. No i nie wiem dalej, że mam podzielić wszystkie 3000000 liczb do zbiorów, wg mnie to nie wykonalne, ale dowodu już na to, że niewykonalne nei chce mi się pisać Baza tysięcy lotnisk: http://airportsbase.com Link do komentarza Udostępnij na innych stronach More sharing options...
Toster Napisano Październik 3, 2008 Autor Zgłoś Share Napisano Październik 3, 2008 zaproponuje liczby zobaczymy czy sa bardziej rownomierne niz moje ostatnie: 1, 2, 3, 4, 5, 7, 10, 18, 19 Always Dark<br /> Link do komentarza Udostępnij na innych stronach More sharing options...
Force Napisano Październik 4, 2008 Zgłoś Share Napisano Październik 4, 2008 ja myślę, że nalezy najpierw wziąść k liczb tak aby w każdej było NWW(te liczby)/k liczb przydzielonych, a potem k zwiększać aż do 9, np. dla k=1 mamy "1", dla k=2 mamy "1" i "2", dla k=3 mamy "1","2","3", dla k=4 "1,2,3,4", dla k=6 "1,2,3,4,5,6" (nie da się dokładnie zrobić, ale dla 1,2,3,4,5,6 mamy tak:16,8,8,8,10,10 dla 1..60 więc nie jest aż tak źle) ogólnie uważam, że powinny to być jak najmniejsze liczby bo najwięcej każda pokryje. Dla k=5 to mamy 5,4,3,2,1 i odpowiednio w 60 liczbach: 12,12,11,10,15, to wydaje mi się, że dla liczb 1,2,3,4,5,6,7,8,9 będziesz miał najlepszy rozkład w 2520 (NWW tych liczb) więc też najlepszy dla Twojego przedziału Baza tysięcy lotnisk: http://airportsbase.com Link do komentarza Udostępnij na innych stronach More sharing options...
Polecane posty
Zarchiwizowany
Ten temat jest archiwizowany i nie można dodawać nowych odpowiedzi.