Matematické Fórum

Já jsem nemyslel algoritmus pro program ale pro člověka :-)

↑ BrozekP:

100k faktorial by to asi nezvladl, i kdyz pro zajimavost si to zkusim, ramky mam dost :D Jediny problem by mel byt omezeni typu long double, ktery muze nabyvat hodnot 10^4932 (EDIT: to jsem si přečetl), unsigned long double (? je vubec takovy datovy typ) tedy 10^9864. To opravdu nevim, jestli by pro 100k! stačilo :D Máš pravdu, s velkýma faktoriálama bys mi to rozbil na bity :)

Jinak přes ten prvočíselnej rozklad se nechytám

↑ BrozekP:
Dělat rozklad čísla n! by bylo asi zbytečné (a asi pro velká n neproveditelné), protože když budu mít vyčíslený n! tak stačí sečíst nuly.
Já myslím udělat to takto:
1.Brát postupně jednotlivá čísla od n dolů po jedné až k číslu 2. (jeden cyklus)
  (tedy čísla n,n-1,n-2,...5,4,3,2)
2.U každého čísla zkoušet dělitelnost 5-ti (kolikrát je to číslo dělitelné 5-ti) a také 2-mi.
  Zapisovat si (přičítat) do nějakých součtů počet dělitelů 2-mi a počet dělitelů 5-ti.
3.Potom vzít menší číslo z těchto výsledků - to je počet 0 na konci.
4.Jak už tady někdo psal počet dělitelů 2-mi bude určitě větší než počet dělitelů 5-ti, takže   stačí dělit pouze 5-ti. a to do čísla 5.
5. Z toho je vidět, že stačí brát čísla končící 5-ti nebo nulou. a dělit pouze tato.

Pseudokód:
deklaruj i,n,k,pocitadlo: Integer
zadej číslo (n)
i = n mod 5
i = n-i
pocitadlo = 0
dokud i>=5 dělej
začátek cyklu
  k = i
  dokud k mod 5 = 0 dělej
  začátek cyklu
    pocitadlo = pocitadlo + 1
    k = k div 5
  konec cyklu
  i = i-5
konec cyklu
Výstup:
Číslo n! obsahuje na konci pocitadlo nul.

Ještě to jde o mnoho zjednodušit:
1. n podělíme číslem 5 to je číslem 5^1 (n div 5) - dostaneme počet nul od té pětky
2. n podělíme číslem 25 to je číslem 5^2 (n div 25)-dostaneme počet nul od té 25
3. Takto postupně dělíme číslo n mocninami 5-ti až do té doby, že n div 5^x = 0.
4. Sečteme jednotlivé výsledky dělení a máme počet nul na konci.

↑ Honzc:

Máš pravdu, špatně jsem to přečetl.

↑ byk7:
Ten bod 3. je špatně - má být 5^x<k.
Proč to dělat tak složitě.
Takto je to jednoduché
1.Nadefinuj n,k,p jako Integer (nebo Int64)
2.Zadej n (to je číslo, ze kterého se udělá faktoriál, a my máme zjistit počet nul na konci)
3. Výpočet
k = 5;
p = 0;
dokud (n div k)>0 dělej
začátek cyklu
  p = p+(n div k);
  k = 5*k;
konec cyklu
4. Vypiš p (to je počet nul na konci

Program v Pascalu:

program Nuly;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,k,p,pokr,konec: Integer;
    anone:string;
begin
  pokr := 0;                         //Promenna pro moznost pokracovani
  WriteLn('--------------------- Nuly ve faktorialu --------------------------');  //Uvodni vypis
  WriteLn;
  WriteLn(' Na vstupu se zada cislo n, ze ktereho chceme zjistit faktorial.');
  WriteLn(' Na vystupu je pak pocet nul na konci faktorialu z tohoto cisla n.');
  while pokr=0 do
  begin
    n := -1;
    WriteLn;
    WriteLn(' Vstup');
    //zadani cisla n
    repeat                         //Dokud se nezada cislo porad opakujeme zadani
      try
        Write(' Zadej cislo n: ');
        ReadLn(n);
      except
        on EInOutError do         //Osetrení spatnych vstupu-napr.pismena,
        begin                     //nebo cisla vetsi nez 2147483647 (rozsah Integer)
          WriteLn(' n musi byt cele cislo z intervalu <0,2147483647>');
          n := -1;
        end;
      end;
    until n<>-1;
    if (n<0)or(n>2147483646) then    //Pokud zadame cislo mimo interval
    repeat                      //tak to nedovolime
      WriteLn(' m musi byt cele cislo z intervalu <0,2147483647>');
      Write(' Zadej cislo n: ');
      ReadLn(n);
    until (n>=0)and(n<=2147483646);
    WriteLn;
    k := 5;                       //tohle je cely vypocet
    p := 0;
    while (n div k)>0 do
    begin
      p := p+(n div k);
      k := 5*k;
    end;                          //ostatni jsou opicky

    WriteLn(' Vystup');
    WriteLn(' Pocet nul na konci '+IntToStr(n)+'! je: '+IntToStr(p));
    konec := 0;
    repeat
      WriteLn;                               //Opakujeme vyzvu, dokud nenapisme a nebo n
      Write(' Nove cislo n? [a/n] ');     //Chceme-li novou matici napiseme a
      ReadLn(anone);
      if (anone='n')or(anone='N')or(anone='a')or(anone='A') then
        konec := 1
      else
      begin
        WriteLn;
        WriteLn(' Musis zadat a nebo n');
      end;
    until konec<>0;
    if (anone='n')or(anone='N') then     //V pripade ze napiseme n + ENTER - program skonci
      pokr := 1;
  end;

end.

↑ byk7:

Kdyby byl v nerovnosti faktoriál, tak bys tímto získal přesně počet nul v dekadickém zápise čísla . Jenže takovýto dekadický zápis máš jen málokdy k dispozici. V nerovnosti má být opravdu jenom . Pomocí součtu viz ↑ Pavel: pak získáš počet nul, aniž bys musel pracně počítat hodnotu čísla .