Форум программистов, компьютерный форум CyberForum.ru

факториал - C++

Восстановить пароль Регистрация
 
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
11.11.2011, 09:52     факториал #1
найти число нулей в конце факториала числа N по основанию каждого множителя K (1<=N<=1000000000, 2<=K<=1000)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
typedef unsigned long long ulong;
#include <vector>
#include <sstream>
#include <iomanip>
using namespace std;
const int base = 1000000000;
class BigNumb
{
    vector<int> numb;
public:
    BigNumb();
    BigNumb(ulong num);
    BigNumb& operator  =(const BigNumb& num);
    bool operator ==(const BigNumb& num)
    {
        return numb==num.numb;
    }
    int operator %(int num)
    {
        return *numb.begin()%num;
    }
    BigNumb  operator  *(const BigNumb &num);
    BigNumb  operator *=(const BigNumb& num);
    BigNumb  operator  /(long num);
    BigNumb  operator /=(long num);
    friend ostream& operator <<(ostream& ost,BigNumb& num)
    {
        if(num.numb.empty())
            ost << 0;
        else
            ost << num.numb.back();
        for(int i=(int) num.numb.size()-2;i>=0;--i)
            ost << setfill('0') << setw(9) << num.numb[i];
        return ost;
    }
};
BigNumb::BigNumb()
{
    numb.push_back(0);
}
BigNumb::BigNumb(ulong num)
{
    ostringstream ost;
    ost << num;
    string str = ost.str();
    for(int i=str.length();i>0;i-=9)
    {
        if(i<9)
        {
            numb.push_back(atoi(str.substr(0,i).c_str()));
        }
        else
        {
            numb.push_back(atoi(str.substr(i-9,9).c_str()));
        }
    }
}
BigNumb& BigNumb::operator =(const BigNumb &num)
{
    this->numb = num.numb;
    return *this;
}
BigNumb BigNumb::operator *(const BigNumb &num)
{
    BigNumb n;
    n.numb.resize(numb.size()+num.numb.size());
    for(size_t i=0;i<numb.size();++i)
        for(int j=0,carry=0;j<num.numb.size() || carry; ++j)
        {
            long long cur = n.numb[i+j] + numb[i] * 1ll * (j < (int)num.numb.size() ? num.numb[j] : 0) + carry;
            n.numb[i+j] = int (cur % base);
            carry = int (cur / base);
        }
        while(n.numb.size() > 1 && n.numb.back() == 0)
            n.numb.pop_back();
    return n;
}
BigNumb BigNumb::operator *=(const BigNumb &num)
{
    return *this = *this * num;
}
BigNumb BigNumb::operator /(long num)
{
    int carry = 0;
    for (int i=(int)numb.size()-1; i>=0; --i)
    {
        long long cur = numb[i] + carry * 1ll * base;
        numb[i] = int (cur / num);
        carry = int (cur % num);
    }
    while (numb.size() > 1 && numb.back() == 0)
    numb.pop_back();
    return *this;
}
BigNumb BigNumb::operator /=(long num)
{
    return *this=*this/num;
}
void main()
{
    /*freopen("INPUT.TXT",   "r", stdin);
    freopen("OUTPUT.TXT",  "w", stdout);*/
    ulong N,c=0;
    int K;
    BigNumb r=1, n;
    cin>>N>>K;
    char buf[100000];
    for(int i=2;i<=N;i++)
    {
        itoa(i,buf,K);
        n=atol(buf);
        r*=n;
    }
    cout<<r<<endl;
    while(true)
    {
        n=r%10;
        if(n==0)
            c++;
        else
            break;
        r/=10;
    }
    cout << c << endl;
}
считает что то не правильно...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2011, 09:52     факториал
Посмотрите здесь:

C++ факториал
C++ Факториал (n-1)!
факториал в с++ C++
C++ Факториал
C++ Факториал Си
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
11.11.2011, 10:02     факториал #2
1. Название темы - неправильное. Все думают, что новичок не знает, как написать факториал...
2. Сугубое имхо навскидку. Нулей должно быть столько, сколько множителей (2*5). Надо посчитать, сколько там двоек и сколько пятерок. Наименьшее из них и будет количество нулей. Не?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.11.2011, 10:07     факториал #3
Вы длинной арифметикой это что ли делаете? Не вариант, тут комбинаторика.
Есть код, находит количество нулей в конце факториала N в системе счисления с основанием K.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cmath>
#include <climits>
 
#ifndef __int64
   typedef long long __int64;
#endif
 
__int64 n, k, i, j, simples[10000], d[10000];
 
int main()
{
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    std::cin >> n >> k;
    
    j = k;
    
    for ( i = 2; i <= j  ; )
    {
        if ( k % i == 0 )
        {
            ++simples[i];
            k /= i;
        }
        else
        {
            ++i;
        }
    }
    if (k > 1)
        ++simples[k];
    
    __int64 answer = LONG_MAX;
    
    for (__int64 i = 0 ; i <= j ; ++i)
    {
        if ( simples[i] )
        {
            __int64 tmp = i, res = 0;
            while ( n / tmp )
            {
                res += n / tmp;
                tmp *= i;
            }
            
            answer = std::min( answer, res / simples[i] );
        }
    }
    
    std::cout << answer;        
}
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
11.11.2011, 10:40  [ТС]     факториал #4
Цитата Сообщение от diagon Посмотреть сообщение
Вы длинной арифметикой это что ли делаете? Не вариант, тут комбинаторика.
Есть код, находит количество нулей в конце факториала N в системе счисления с основанием K.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cmath>
#include <climits>
 
#ifndef __int64
   typedef long long __int64;
#endif
 
__int64 n, k, i, j, simples[10000], d[10000];
 
int main()
{
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    std::cin >> n >> k;
    
    j = k;
    
    for ( i = 2; i <= j  ; )
    {
        if ( k % i == 0 )
        {
            ++simples[i];
            k /= i;
        }
        else
        {
            ++i;
        }
    }
    if (k > 1)
        ++simples[k];
    
    __int64 answer = LONG_MAX;
    
    for (__int64 i = 0 ; i <= j ; ++i)
    {
        if ( simples[i] )
        {
            __int64 tmp = i, res = 0;
            while ( n / tmp )
            {
                res += n / tmp;
                tmp *= i;
            }
            
            answer = std::min( answer, res / simples[i] );
        }
    }
    
    std::cout << answer;        
}
а не подскажите что в моем коде не так, он считает что то не так...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.11.2011, 10:44     факториал #5
Цитата Сообщение от Zheka91 Посмотреть сообщение
а не подскажите что в моем коде не так, он считает что то не так...
Идея решения неверная.
Факториал 10^9 будет считаться ну очень долго.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
11.11.2011, 12:04     факториал #6
Нулей должно быть столько, сколько множителей (2*5). Надо посчитать, сколько там двоек и сколько пятерок. Наименьшее из них и будет количество нулей. Не?
Как бы очевидно что 5-ок будет меньше чем 2-ек
Поэтому достаточно посчитать только 5-ки
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
11.11.2011, 12:46  [ТС]     факториал #7
Цитата Сообщение от diagon Посмотреть сообщение
Идея решения неверная.
Факториал 10^9 будет считаться ну очень долго.
да не я не про то, просто вроде моя прога вполне правильная а выдает при N=100 К=6 40 а должен 48, и я не могу найти где не правильно
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
11.11.2011, 13:48     факториал #8
Очень все странно.
Здесь
C++
1
2
3
4
5
6
for(int i=2;i<=N;i++)
* * * * {
* * * * * * * * itoa(i,buf,K);
* * * * * * * * n=atol(buf);
* * * * * * * * r*=n;
* * * * }
Ты считаешь вовсе не факториал, а произведение чисел 2*3*4*5*10*...15*20...244
А здесь
C++
1
2
3
4
5
6
7
8
9
* * * * while(true)
* * * * {
* * * * * * * * n=r%10;
* * * * * * * * if(n==0)
* * * * * * * * * * * * c++;
* * * * * * * * else
* * * * * * * * * * * * break;
* * * * * * * * r/=10;
* * * * }
Кол-во нулей получившегося произведения в 10-тичной записи

Добавлено через 1 минуту
Звездочки вылезли случайно. Я их не хотел
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2011, 12:58     факториал
Еще ссылки по теме:

C++ Факториал
факториал С++ C++
Факториал C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Zheka91
4 / 4 / 1
Регистрация: 22.11.2010
Сообщений: 101
13.11.2011, 12:58  [ТС]     факториал #9
Цитата Сообщение от diagon Посмотреть сообщение
Вы длинной арифметикой это что ли делаете? Не вариант, тут комбинаторика.
Есть код, находит количество нулей в конце факториала N в системе счисления с основанием K.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cmath>
#include <climits>
 
#ifndef __int64
   typedef long long __int64;
#endif
 
__int64 n, k, i, j, simples[10000], d[10000];
 
int main()
{
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    std::cin >> n >> k;
    
    j = k;
    
    for ( i = 2; i <= j  ; )
    {
        if ( k % i == 0 )
        {
            ++simples[i];
            k /= i;
        }
        else
        {
            ++i;
        }
    }
    if (k > 1)
        ++simples[k];
    
    __int64 answer = LONG_MAX;
    
    for (__int64 i = 0 ; i <= j ; ++i)
    {
        if ( simples[i] )
        {
            __int64 tmp = i, res = 0;
            while ( n / tmp )
            {
                res += n / tmp;
                tmp *= i;
            }
            
            answer = std::min( answer, res / simples[i] );
        }
    }
    
    std::cout << answer;        
}
а можете объяснить этот код, а то я что то ни как не пойму...
Yandex
Объявления
13.11.2011, 12:58     факториал
Ответ Создать тему
Опции темы

Текущее время: 13:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru