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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
SuperSven
0 / 0 / 0
Регистрация: 17.05.2013
Сообщений: 3
#1

Разбор алгоритма программы - C++

11.02.2014, 17:44. Просмотров 253. Ответов 1
Метки нет (Все метки)

Здравствуйте, у меня есть программа, вычисляющая факториал заданного числа.

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
#include "stdafx.h"
#include <iostream>
 
 
 
using namespace std;
int a[1000],i,n,j,ost=0,num=1,c;
 
int main(){
    cin>>n;
    memset(a,0,sizeof(a));
    if(n==0 || n==1) {cout<<1; return 0;}
    a[0]=1;
    for(i=2;i<=n;i++){
        for(j=0;j<num;j++){
            c=(a[j]*i+ost);
            a[j]=c%1000;
            ost=c/1000;
 
        }
        a[num]=ost%1000;
        ost/=1000;
        a[num+1]=ost%1000;
        ost/=1000;
        a[num+2]=ost;
        ost=0;
        if(a[num+1]!=0)num+=2;
        else if(a[num]!=0)num++;
    
    }
    cout<<a[num-1];
    for(i=num-2;i>=0;i--) {
        if(a[i]>99) cout<<a[i];
        else {
            if (a[i]>9) {cout<<0<<a[i];}
            else cout<<'0'<<'0'<<a[i];
        }
    }
return 0;
}
Помогите разобраться с алгоритмом. Сначала все понятно, идет обычное вычисление факториала. Но если результат получается больше 1000, то он получается некорректный. Для исправления этого и написана эта часть:
Кликните здесь для просмотра всего текста
a[num]=ost%1000;
ost/=1000;
a[num+1]=ost%1000;
ost/=1000;
a[num+2]=ost;
ost=0;
if(a[num+1]!=0)num+=2;
else if(a[num]!=0)num++;

Но я не совсем понимаю, как она работает. И почему результат свыше 1000 получается некорректный? И вывод какой-то мудреный. Заранее благодарю за ответы.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2014, 17:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разбор алгоритма программы (C++):

Разбор алгоритма программы - C++
Здравствуйте, у меня есть программа, вычисляющая факториал заданного числа. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Разбор алгоритма - C++
Пожалуйста поясните метод сжатия LZMA. Только пожалуйста не надо кидать ссылки на википедию.

Разбор программы - C++
#include&lt;iostream&gt; using namespace std; void func1(); void func2(); int f; int main() {

разбор программы - C++
друзья хотел бы попросить помощи с одной программой, в программировании не разбираюсь по єтому пришел к вам на форум. Есть программа одно...

разбор программы - C++
Друг написал прогу, но комментарии к ней не сделал, поэтому не понятно. Помогите разобраться с программой. Вот условие: Создать класс...

Разбор программы - C++
После недели освоения cuda и разбора программ,наткнулся на урок по куда,прилагается программа перемножения матриц,собственно код: //...

1
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
11.02.2014, 20:07 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Факториал растет очень быстро. Уже 13! не влезет в int.
Чтобы обойти эту проблему, используется массив int a[1000], в каждый элемент которого записывается по три цифры получившегося числа.
т.е. 6!=720 -> a = {720 , 0, 0,0 .... }
7!=5040 -> a = {40, 5, 0, 0, 0 ... }
10!=3628800 -> a = {800, 628, 3, 0, 0, ...}
и т.д.

Число, лежащее в массиве а, последовательно умножается на все числа от 2 до n.
Умножение происходит вот здесь:
C++
1
2
3
4
5
6
7
8
9
10
11
12
for(j=0;j<num;j++) // num - сколько элементов массива занимает текущий результат вычислений
{
            c=(a[j]*i+ost); // содержимое элемента массива умножается на число, к результату добавляется остаток
            a[j]=c%1000; // новое значение в элементе массива - остаток от деления c на 1000
            ost=c/1000; // то, что в текущий элемент массива не влезает, нужно перенести в следующий
}
a[num]=ost%1000;  // это делается на случай удлинения числа
ost/=1000;
a[num+1]=ost%1000;
ost/=1000;
a[num+2]=ost;
ost=0;
Про вывод:
Старший элемент массива выводится как есть.
Для каждого из оставшихся должно быть выведено 3 цифры. Если число в элементе массива слишком маленькое, перед ним выводятся 1 или 2 нуля, чтобы в итоге было три цифры.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.02.2014, 20:07
Привет! Вот еще темы с ответами:

Разбор кода программы - C++
сделали контрольную и защитить не не могу. помогите разобрать что значит код, пожалуйста. реализация LZ метода сжатия кто может...

Разбор кода программы - C++
Здравствуйте! Помогите пожалуйста написать программу (на Bison+Flex), которая будет сканировать текстовый документ и выводить информацию об...

Разбор программы(сортировка) - C++
Как объяснить принцип работы (выделенного) кода. Не могу до конца разобрать какие действия проводит данная программа поэтапно. ...

Разбор кода простой программы новичка - C++
Народ, я вот тут только начал учиться, помогите понять ошибки. Вот код: #include &lt;iostream.h&gt; class Rabota { public: int...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru