Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 27. 10. 2019 02:08 — Editoval Uživatel919 (27. 10. 2019 02:11)

Uživatel919
Zelenáč
Příspěvky: 6
Reputace:   
 

Efektivní algoritmus kombinačního čísla

Předem díky.

Čtu Průvodce labyrintem algoritmů a v kapitole 1., cvičení 5. jsem narazil na problém.

Můj algoritmus není schopen splnit podmínku „… který si vystačí s čísly omezenými n-násobkem výsledku.“

Problém je, že mé řešení je vždy omezeno velikostí samotného výsledku a nejsem schopen odhalit ten (méně efektivní) algoritmus splňující zadání.

Uvažoval jsem i o kompozici polynomu, různých roznásobeních apod., ale vše se ukazalo liché.

Algoritmus

Slovní popis

1. Stanovuje se výpočet čitatele kratší o max((n-k), k).
2. Z min((n-k), k) se získávají součinitelé.
3. Pro i = max((n-k), k) + 1 až n
    a1. Stanovuje se max. součinitel z kroku 2 soudělný k aktuálnímu mezivýsledku. (Pokud takový existuje.)
    a2. Mezivýsledek se krátí nalezeným součinitelem. (Pokud byl nalezen.)
    a3. Takový součinitel je vyřazen ze seznamu součinitelů, protože byl již vykrácen.
    b1. Jako a1, ale pro aktuální i.
    b2. Jako a2, ale pro aktuální i.
    b3. Jako a3, ale pro aktuální i.
    c. Nový mezivýsledek je roven součinu jeho (pokracené) velikosti s (pokraceným) i.
4. Vrací se mezivýsledek

Řešení v C#

Code:

public void KombinačníČíslo(int n, int k)
{
  // TODO: Známé výsledky nepočítat, tj. n nad n, k = 1, k = 0 apod.

  (int referent, int dělitel) jmenovatel = default; // Velikosti bez faktoriálu.

  int jmenovatelVariacíBezFaktoriálu = n - k;

  if (jmenovatelVariacíBezFaktoriálu > k) // Faktoriál čitatele se počítá od max((n-k), k) + 1.
  {
    jmenovatel.referent = jmenovatelVariacíBezFaktoriálu;
    jmenovatel.dělitel = k;
  }
  else
  {
    jmenovatel.referent = k;
    jmenovatel.dělitel = jmenovatelVariacíBezFaktoriálu;
  }

  var součiniteléVeJmenovateli = SoučiniteléVeJmenovateli();

  // Mezivýsledek je rovnou max((n-k), k) + 1. (Ušetří se obrátka 1 × max((n-k), k) + 1.)
  Console.WriteLine($"    n {n}, k {k}; { Výsledek(jmenovatel.referent + 1, jmenovatel.referent + 2, n) }");

  // Rozpad na součinitele.
  List<int> SoučiniteléVeJmenovateli()
  {
    var součinitelé = new List(jmenovatel.dělitel);
    for (var i = jmenovatel.dělitel; i > 1; --i) // Jedna se vynechává.
    {
      součinitelé.Add(i);
    }

    return součinitelé;
  }
  
  int koef;
  long Výsledek(long result, int current, in int limit)
  {
    Console.Write(result);

    int dělitelResultu = součiniteléVeJmenovateli.Where(svj => result % svj == 0).MaxOrDefault(); 
    if (dělitelResultu != default)
    {
      result /= dělitelResultu; // Krátí se mezivýsledek (v čitateli).
      součiniteléVeJmenovateli.Remove(dělitelResultu);
    }

    Console.WriteLine(" " + result);
    Console.Write(current);

    int dělitelCurrentu = součiniteléVeJmenovateli.Where(svj => current % svj == 0).MaxOrDefault();
    if (dělitelCurrentu == default)
    {
      koef = current;
    }
    else
    {
      koef = current / dělitelCurrentu; // Krátí se aktuální číslo z čitatele.
      součiniteléVeJmenovateli.Remove(dělitelCurrentu);
    }

    Console.WriteLine(" " + koef);

    if (current > limit)
    {
      return result;
    }

    return Výsledek(checked(result * koef), ++current, in limit);
  }
}

Moje logika

Vyjděme z příkladu 11 nad 7, kdy výsledek je 330. Omezení mezivýsledku je tedy 11 × 330 = 3630.

1. 11! je 39 916 800‬. Čitatel tedy musí být krácen.
2. 7! je 5040. Musí tedy být použit menší z součinitelů jmenovatele pro výpočet jeho výpočet (a druhý pro krácení čitatele).
3. Zbývá tedy 8 × 9 × 10 × 11 / 4 × 3 × 2 (4!).
4. 8 × 9 × 10 × 11 = 7920. Tedy i zbytek čitatele musí být krácen.
5. Po vykrácení je součin 2 × 3 × 5 × 11 = 330. Což je ovšem už výsledek.

Můj problém

1. Pakliže je mezivýsledek omezen n-násobkem výsledku, lze říci, že pro poslední mezivýsledek, platí, že ve jmenovateli zbylo právě n. Kde by se tam vzalo?
2. Jak zaručím, že čitatel bude dostatečně pokrácen, aby splnit omezení n-násobku výsledku a zároveň byl pokrácen dostačně málo, abych spolehlivě stanovil jeho max. velikost n × výsledek?

Offline

 

#2 27. 10. 2019 02:37

laszky
Příspěvky: 1544
Škola: MFF UK, FJFI CVUT
Reputace:   122 
 

Re: Efektivní algoritmus kombinačního čísla

↑ Uživatel919:

Ahoj. Ja bych na to sel napr. tak, ze
$\binom{11}{4} = \binom{10}{3}\cdot \frac{11}{4} = \binom{9}{2}\cdot \frac{11}{4}\cdot \frac{10}{3} = \cdots$

Pri vypoctu $\binom{11}{4}$ bych tedy zacal "z druhe strany" : $8=11-4+1$

$\binom{8}{1} = 8$
$\binom{9}{2} = 8 \cdot \frac{9}{2} = 4\cdot 9 = 36$
$\binom{10}{3} = 36 \cdot \frac{10}{3} = 12\cdot 10 = 120$
$\binom{11}{4} = 120 \cdot \frac{11}{4} = 30 \cdot 11 = 330$

Offline

 

#3 27. 10. 2019 05:07 — Editoval Uživatel919 (27. 10. 2019 05:08)

Uživatel919
Zelenáč
Příspěvky: 6
Reputace:   
 

Re: Efektivní algoritmus kombinačního čísla

↑ laszky:

Dobře, ale když se začne na lichém čísle, řekněme pro 15 nad 3.

$\frac{15 × 14 × 13 }{3 × 2 × 1} = 455$

1. 13
2. 13 ÷ 2 = 6,5
3. 91 ÷ 3 = 30,3333…
4. 455.

Mělo by se to počítat v celočíselné proměnné. Je to spolehlivé a tuším, že i rychlé. Navíc i kdybych zkontroval, jestli je číslo soudělné a případně krátil až po součinu, tak pořád nikde nevidím omezení n × výsledek. V tomto případě 455 × 15 = 6825. Číslo, které není přítomno ani vzdáleně.

Trochu tabulek

http://software919.sweb.cz/Lich%C3%A9.png

352716 ÷ 7 = 50388
19 × 50388 = 957372 (n × výsledek)
957372 ÷ 352716  = 2,7142…
               
http://software919.sweb.cz/Sud%C3%A9.png

19 × 27132 = 515508 (n × výsledek)

Nicméně díky za vzorečky. Nevěděl jsem, že platí, že ((n nad k) $\vee $ (n nad k) × (n + 1)) % (k + 1) = 0. Předpokládám, že je zužitkuji.

Offline

 

#4 27. 10. 2019 11:36

laszky
Příspěvky: 1544
Škola: MFF UK, FJFI CVUT
Reputace:   122 
 

Re: Efektivní algoritmus kombinačního čísla

↑ Uživatel919:

Ahoj, zkratis jeste pred soucinem:

$\binom{13}{1} = 13$
$\binom{14}{2} = 13 \cdot \frac{14}{2} = 13\cdot 7 = 91$
$\binom{15}{3} = 91 \cdot \frac{15}{3} = 91\cdot 5 = 455$

Omezeni je 1 x vysledek. :-)

Neni zac (ty vzorecky).

Offline

 

#5 27. 10. 2019 15:21 Příspěvek uživatele Uživatel919 byl skryt uživatelem Uživatel919. Důvod: Příspěvek zdá se zbytečný.

#6 27. 10. 2019 18:30 — Editoval Uživatel919 (27. 10. 2019 20:32)

Uživatel919
Zelenáč
Příspěvky: 6
Reputace:   
 

Re: Efektivní algoritmus kombinačního čísla

Naimplementoval jsem algoritmus dle nových postupů, ale bohužel algoritmus je méně efektivní, resp. dříve přeteče proměná. Např. pro (65 nad 33) už nefunguje. Jednoduše má větší mezivýsledky.

Code:

public void Spočti(int n, int k)
{
  // TODO: Známé výsledky nepočítat, tj. n nad n, k = 1, k = 0 apod.

  (int početOpakování, int velikostKrácení) počtyJmenovatele = default;

  int jmenovatelVariacíBezFaktoriálu = n - k;

  if (jmenovatelVariacíBezFaktoriálu > k)
  {
    počtyJmenovatele.velikostKrácení = jmenovatelVariacíBezFaktoriálu;
    počtyJmenovatele.početOpakování = k;
  }
  else
  {
    počtyJmenovatele.velikostKrácení = k;
    počtyJmenovatele.početOpakování = jmenovatelVariacíBezFaktoriálu;
  }

  bool kráceno = false;
  // První obrátku není třeba počítat.
  Console.WriteLine($"    n {n}, k {k}; { Výsledek(počtyJmenovatele.velikostKrácení + 1, 2, počtyJmenovatele.velikostKrácení + 2, počtyJmenovatele.početOpakování) }");

  int auxCurrent;
  long Výsledek(long result, int count, int current, in int limit)
  {
    if (count > limit)
    {         
      return result;
    }

    Console.Write(current);
    if (current % count == 0)
    {
      auxCurrent = current / count;
      kráceno = true;
    }
    else
    {
      auxCurrent = current;
    }

    Console.WriteLine(" " + auxCurrent);

    Console.Write(result);

    if (!kráceno && result % count == 0)
    {
      result /= count;
      kráceno = true;
    }

    Console.Write(" " + result);

    result = checked(result * auxCurrent);

    if (!kráceno && result % count == 0)
    {
      result /= count;
    }

    Console.WriteLine(" " + result);
    kráceno = false;

    return Výsledek(result, ++count, ++current, in limit);
  }
}

Porovnání pro (47 nad 27)

http://software919.sweb.cz/Porovn%C3%A1n%C3%AD.png

Vpravo nový algoritmus. Na posledním řádku s vypočty vpravo je v prostřed mezivýsledek, který je ovšem u původního algoritmu maximální, což zde neplatí.

Pořád mi uniká, proč by měly být mezivýsledky omezeny n-násobkem výsledku. Otázku nechám otevřenou.

Offline

 

#7 27. 10. 2019 18:38

laszky
Příspěvky: 1544
Škola: MFF UK, FJFI CVUT
Reputace:   122 
 

Re: Efektivní algoritmus kombinačního čísla

↑ Uživatel919:

A ty pocitas $\binom{47}{27}$ namisto lehcich $\binom{47}{20} = \binom{47}{27}$ ?

Offline

 

#8 27. 10. 2019 19:11 — Editoval Uživatel919 (27. 10. 2019 20:31)

Uživatel919
Zelenáč
Příspěvky: 6
Reputace:   
 

Re: Efektivní algoritmus kombinačního čísla

↑ laszky:

Úplně nerozumím, ale počítá se vždy v obou algoritmech s tím menším (n-k), k, tedy min((n-k), k). Proto pro n = 47 a k = 27, se to počítá jako

$\frac{47 \cdot 46 \cdot 45 \ldots 30 \cdot 29 \cdot 28 }{20 \cdot 19 \cdot 18 \ldots 3 \cdot 2 \cdot 1}$.

Je to vidět i tabulkách, kde jsou ze začátku čísla 28, 29.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson