Cos dla znudzonych, majacych duzo czasu

[Toster]

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;

[Force]

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

[Toster]

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.

[Force]

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ć

[Toster]

zaproponuje liczby zobaczymy czy sa bardziej rownomierne niz moje ostatnie:

1, 2, 3, 4, 5, 7, 10, 18, 19

[Force]

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