Cümə, 09.12.2016, 20:27
İnformatikanın məktəbdə tədrisi
Baş səhifə Qeydiyyat Giriş
e-mail: informatik-az@mail.ru · RSS
Menyu
Fotoşəkillər
Giriş forması
Sorğu
Müəllim kimi informatika dərslərində tez-tez istifadə edirəm:
Cavabların sayı: 6163
Faydalı keçidlər

  • ict.edu.az
  • ict.az
  • telekommunikasiya.edu.az
  • İnf-math.narod.ru
  • Millibyte.az
  • kayzen.az/blog/informatika
  • alqoritm.ucoz.org
  • mincom.gov.az
  • Facebook-da
    Təqvim
    «  Dekabr 2016  »
    B.e.Ç.a.ÇC.a.CŞB
       1234
    567891011
    12131415161718
    19202122232425
    262728293031
    Təqdimatlar
    Saat
    Statistika

    Onlayn: 12
    Ziyarətçilərin sayı: 12
    Qeydiyyatdan keçənlərin sayı: 0


     2-23r
    Дано натуральное число n (1< n <109). Определить, на сколько нулей оканчивается  n!

    Если мы будем вычислять n!, то эту задачу сумеем решить только максимально до n=20 (смотри предыдущую задачу). Значит надо придумать какой-то другой алгоритм – без вычисления самого n!
    Мы знаем (!?), что любое число можно представить  произведением простых делителей (смотри задачу 2.17). Например; 96=2^5*3, 19819800 = 2^3*3^2*5^2*7*11^2*13.
    Представим n! как произведение простых множителей. n! = 2^n2*3^n3*5^n5*7^n7…. Как по вашему, здесь больше 2-ек и 5-ок? То есть, что больше  n2 или  n5? Конечно 2-ек. Ведь в представлении n! = 1*2*3*4*5*6*7*8*9*10*11*12*…каждое второе число, начиная с 2, делится на 2 и только каждое 5-ое делится на 5. Значит 5-ок меньше , чем 2-ек. 0 в конце числа появляется, когда 2 умножается на 5, и количество 0-ей будет столько, сколько существует пар множителей 2 и 5. Но 5-ок меньше, чем 2-ек, и получается, что количество 0-ей в  числе n! равно количеству 5-ок в разложении n! на простые множители, то есть числу n5. А теперь подсчитаем это число.
    В произведении n! = 1*2*3*4*5*6*7*8*9*10*11*12*… *n   5 появляется через 5 чисел и количество вхождений равно n div 5. В 25, 50 … 5 входит уже 2 раза и таких вхождений  будет n div 25. В 125 … 5 входит 3 раза и таких вхождений будет n div 125 и так далее (делим на степени числа 5). Вот и весь алгоритм. Давайте вручную подсчитаем сколько в конце нулей в числе 1000!   s = (1000 div 5) + (1000 div 25) +(1000 div 125) + (1000 div 625) =249. 
    Число 1000! оканчивается на 249 нулей. 
    В нашей программе мы так и поступаем: s:=s + (n div p); (строка 10) выполняется до тех пор степень 4 (p:=p*5;
    строка 11) будет меньше самого числа n.

    1

    2

    3

    4

    5

    6

    7

    8

    10

    11

    12

    13

    14

    15

    16

    17

    18

    Program A2_23;

    Var

     p, s,n:integer;

    BEGIN

     readln(n);

     p:=5; s:=0;

     while (p<=n) do

      begin

       s:=s + (n div p);

       p:=p*5;

      end;

     writeln(s);

     readln;

    END.

    //Program A2.23;

    #include <iostream>

     

    using namespace std;

     

    int main()

    {

        int p=5,s=0,n;

        cin>>n;

        while(p<=n)

        {

            s=s+n/p;

            p=p*5;

        }

        cout<<s<<endl;

        return 0;

    }


















































































    Copyright İsaNaida © 2016
    PYTHON 3.4
    ALPLogo
    Elan
    Fəxr edirik


    Bölmələr
    MÜSABİQƏ
    Azərbaycanda İKT
    Axtarış
    Video
    Info-Ko