Faktoriális végén hány nulla?

Algoritmusok

Egy másik thread-ben olvastam ezt a feladatot és elindította a fantáziámat. A faktoriális végén található nullák számához biztos nem kell magát a számot kiszámolni. Hogyan kaphatjuk meg tehát a nullál számát egy "energiatakarékos" algoritmussal?A feladat/játék tehát a következő:

1. Határozzuk meg az 50! végén található nullák számát számológépet nem igénylő módszerrel (tehát használhatsz táblázatkezelőt, de csak nyilvántartásra).

2. Adjunk meg algoritmust, ami tetszőleges n-re (1 <= n <= 65535, egyelőre) megadja az n! (1*2*...*n) végén található nullák számát. Valszeg O(n^2)-be bele kell férjen a tárigény és a futási idő is.

  • 6110 megtekintés

( Nyizsa v | 2007. 11. 17., szo – 14:47 )

for (i=1;5^i<n;i++)
nullak==nullak+n/5^i;

--
Debian - The "What?!" starts not!

( csko | 2007. 11. 17., szo – 14:48 )

Ami most így hirtelen eszembe jut, hogy számoljuk meg a kettes és az ötös tényezők számát, és vegyük a kettőnek a minimumát. 10 = 2 * 5

tenyezok(i, n) := i-ben "hanyszor van meg" n

otos = 0, kettes = 0
ciklus i = 1 -től n -ig
otos := otos + tenyezok(i, 5)
kettes := kettes + tenyezok(i, 2)

vegeredmeny := min(otos, kettes)

( gsimon | 2007. 11. 17., szo – 14:59 )

Szépen menni kell végig 1..n-ig, minden számra nézni, hogy 2-nek ill. 5-nek hányadik hatványával osztható, ezen kitevőket összegezni sorra, majd a végén a szumma_2_kitevo és a szumma_5_kitevo közül venni a kisebbiket.
Tizes szrdsz-ben nullát a szám végére a 10-zel való szorzás generál, azaz azt kell keresnünk, hogy az adott faktoriális 10-nek mely legnagyobb hatványával osztható. 10=2*5, azaz ha a faktoriális osztható pl. 2^n-nel ill. 5^m-nel, akkor osztható 10^min(n,m)-nel.
Mivel a faktoriálisban teljesen mindegy, hogy egy 2-es vagy 5-ös osztót a szorzat mely tagja hozott be, ezért ezeket kereshetjük a faktoriális kiszámolása nélkül is.
Egy x szám 2-es ill. 5-ös osztóinak a keresése log(x) nagyságrendű, a faktoriális során n db számot kell néznünk, ezért ez egy n*log(n)-es feladat. 


int n, k, d5, d2;

d5 = d2 = 0;
for (n = 1; n < 50; n++)
{
  k = n;
  while ((k % 2) == 0)
  {
    d2++;
    k /= 2;
  } 
   while ((k % 5) == 0)
  {
    d5++;
    k /= 5;
  } 
}
k = (d2 < d5) ? d2 : d5;
printf("%d! vegen %d db nulla van\n", n, k);

( siposa v | 2007. 11. 17., szo – 15:07 )

Na, ez gyors volt :) Köszönet mindenkinek!

( NevemTeve | 2007. 11. 17., szo – 16:40 )

Tehát, hogy összefoglaljuk: csak az ötösökkel kell törödni, figyelve a magasabb hatványokra is, tehát a végső válasz:

[n/5]+[n/25]+[n/125]+...

programmal valami ilyesmi:

int n, sum, div;
for (sum=0, div=5; div<=n; div*=5) sum += n/div;

( zamboriz v | 2007. 11. 17., szo – 16:49 )

> Valszeg O(n^2)-be bele kell férjen a tárigény és a futási idő is.

És tényleg belefér: :-))) 


#!/usr/bin/perl

  $f = 50;

  $nullak = 0;
  if( $f > 15625 ){ $nullak += 3906 * int($f/15625); $f %= 15625; }
  if( $f >  3125 ){ $nullak +=  781 * int($f/ 3125); $f %=  3125; }
  if( $f >   625 ){ $nullak +=  156 * int($f/  625); $f %=   625; }
  if( $f >   125 ){ $nullak +=   31 * int($f/  125); $f %=   125; }
  if( $f >    25 ){ $nullak +=    6 * int($f/   25); $f %=    25; }
  if( $f >     5 ){ $nullak +=        int($f/    5);              }

  print $nullak, "\n";

#

Jogos, kijavítottam: 


#!/usr/bin/perl

  $f = 50;

  $nullak = 0;
  if( $f >= 15625 ){ $nullak += 3906 * int($f/15625); $f %= 15625; }
  if( $f >=  3125 ){ $nullak +=  781 * int($f/ 3125); $f %=  3125; }
  if( $f >=   625 ){ $nullak +=  156 * int($f/  625); $f %=   625; }
  if( $f >=   125 ){ $nullak +=   31 * int($f/  125); $f %=   125; }
  if( $f >=    25 ){ $nullak +=    6 * int($f/   25); $f %=    25; }
  if( $f >=     5 ){ $nullak +=        int($f/    5);              }

  print $nullak, "\n";

#

Általánosítsuk (; 


#!/usr/bin/perl

$f = 50;

$hatvanyok[0] = 1;
$n[0] = 0;
for ($kitevo = 0; ($hatvanyok[$kitevo+1] = 5*$hatvanyok[$kitevo]) <= $f; $kitevo++) {
        $n[$kitevo+1] = $n[$kitevo]+$hatvanyok[$kitevo];
}

$nullak = 0;
while ($kitevo) {
        $nullak += $n[$kitevo]*int($f/$hatvanyok[$kitevo]);
        $f %= $hatvanyok[$kitevo--];
}
print $nullak, "\n";

( strangelove | 2007. 11. 17., szo – 18:56 )

más számrendszerben mitől függ a nulláxáma?

binárisan pl. n-(n egyeseinek száma)
egyébként első lövésre, meggondolás nélkül a legnagyobb prÍmhatvány osztója n-nek legyen q, és ekkor:
eredmény=[n/q]+[n/q^2]+[n/q^3]+...

szerk.:
négyzetmentes x-re tökös, x=12, x=20, x=72, x=360, hát nem feltétlen, még nem csekkoltam... x a számrendszer alapja.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

ha senki nem írja ide a megoldást, akkor majd én.

szóval elegendő prímhatványokra tudni, majd venni a minimumukat.
ha prímekre tudjuk, akkor tudjuk prímhatványokra is.
prím alapú számrendszerekre meg tudjuk.
Q.E.D.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

( lazly | 2007. 11. 26., h – 13:03 )

Es ehez mit szoltok?
Persze van benne egy olyasmi felteves hogy egyszerre soha nem fog tobb tizedes jogy ugrani az elso ket tizedjegy osszeszorzasatol mint 10. Ez matematikailag szerintem belathato mindenesetre szerintem. :)
Es az en megoldasom tetszoleges szamrendszerben mukodik, csak a szorzast kell kicsit atpofozni benne es kesz is. :D
Parameternek add neki hogy meddig akarod szamoltatni. 


#/bin/bash
szam=1 ; nullak=0
for i in `seq $1`; do
  szam=$[$szam*$i]
  enged=0
  while `exit $enged`; do
    maradek=$[$szam%10]
    if [ $maradek -eq 0 ]; then
      nullak=$[$nullak+1]
      szam=$[$szam/10]
    else
      enged=1 ; fi
  done
  szam=$[$szam%100000000000]
done
echo $nullak

-------------------------------
"A gorog katolikus noknek 8 dioptria alatt nem kotelezo a bajusz!" avagy "Nozni csak muholdal lehet..."