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

Деление больших чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
kenny58
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 19
12.05.2012, 22:07     Деление больших чисел #1
Доброго времени суток. Спасите пожалуйста, как здесь быть

Даны два числа. Ваша задача найти частное и остаток от деления.

Input
В первой строке дано делимое, во второй - делитель. Каждое число может содержать от 1 до 5 000 000 цифр.[/B] Все цифры в обоих числах одинаковые.
Output
Запишите частное в первой строке, а остаток - во второй.

Input
111
11
Output
10
1
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_or_75
-1 / 0 / 0
Регистрация: 18.02.2012
Сообщений: 244
12.05.2012, 22:10     Деление больших чисел #2
я давно хотел написать программу каторая делить числа ввида 99999999999999999999999999999999999999999999999999999999 на 2 или 3 но у меня так и не получилось
думаю и мне надо знать ответ
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
12.05.2012, 22:19     Деление больших чисел #3
Вы не умеете делить столбиком?
kenny58
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 19
12.05.2012, 22:56  [ТС]     Деление больших чисел #4
как ее реализовать при больших числах
Avazart
 Аватар для Avazart
6893 / 5133 / 250
Регистрация: 10.12.2010
Сообщений: 22,561
Записей в блоге: 17
12.05.2012, 23:37     Деление больших чисел #5
Первое что на ум пришло поместить каждый разряд большего числа в std::vector<>
и делить(поразрядно) как уже предложили столбиком помещая результат в другой вектор.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.05.2012, 01:10     Деление больших чисел #6
Ну, в данном конкретном случае всё несколько проще. Цифра-то только одна.
Например, если поделить 7777777777777777 на 77777, то получится 1000010000100 и 77 в остатке. Второе число по длине укладывается в первом 3 раза и ещё 2 семёрки остаётся. Поэтому результат содержит 3 единицы (сколько раз уложилось), разделённые 4 нулями (на 1 меньше длины делителя), и ещё 2 нуля на конце (по длине остатка). В общем-то это, конечно, деление почти в чистом виде, только не надо ничего вычитать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2012, 16:13     Деление больших чисел
Еще ссылки по теме:

C++ Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел больших 20
C++ Деление вещественных чисел
Деление двух чисел C++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2796 / 1572 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
13.05.2012, 16:13     Деление больших чисел #7
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <sstream>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
const char  DIG_MIN         =   '1';
const char  DIG_MAX         =   '9';
const int   NUM_LEN_MIN     =   1;
const int   NUM_LEN_MAX     =   5000000;
/////////////////////////////////////////////////////////////////////////////////////////
template<class T>
T  input_val
        (
            T_str   prompt,            
            T       val_min,
            T       val_max            
        )
{    
    std::ostringstream  sout;
    sout    <<  prompt
            <<  " от "
            <<  val_min
            <<  " до "
            <<  val_max
            <<  ":"
            <<  '\t';    
    
    bool    value_has_correct_type  =   false;
    T       val_res                 =   T();
    do
    {
        std::cout   <<  sout.str();
        T_str   val_str;
        std::cin    >>  val_str;
        std::istringstream  ssin(val_str);
        char    c   =   0;
        value_has_correct_type  =       ( ssin  >>  val_res )   !=  0
                                    &&  ( ssin  >>  c       )   ==  0;
    }while
        (
                !value_has_correct_type
            ||  val_res     <   val_min
            ||  val_res     >   val_max
        );
 
    std::cout   <<  std::endl;
    return  val_res;  
}
/////////////////////////////////////////////////////////////////////////////////////////
char  input_digit()
{
    return  input_val<char>
            (
                "Введите цифру",            
                DIG_MIN,
                DIG_MAX                
            );    
}
/////////////////////////////////////////////////////////////////////////////////////////
int  input_dividend_len()
{
    return  input_val<int>
                (
                    "Введите длину делимого",            
                    NUM_LEN_MIN,
                    NUM_LEN_MAX           
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  input_divisor_len()
{
    return  input_val<int>
                (
                    "Введите длину делителя",            
                    NUM_LEN_MIN,
                    NUM_LEN_MAX            
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
T_str  get_quotient
    (        
        int     dividend_len,
        int     divisor_len
    )
{
    T_str  res_str;
    for( int  i = 0; i < dividend_len - divisor_len + 1; ++i )
    {
        res_str.push_back(i % divisor_len == 0 ? '1' : '0');
    }
    if( res_str.empty() )
    {
        res_str = "0";
    }
    return  res_str;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_str  get_remainder
    (
        int     dividend_len,
        int     divisor_len,
        char    digit    
    )
{
    T_str   res_str
                (
                    dividend_len % divisor_len,
                    digit                
                );
 
    if( res_str.empty() )
    {
        res_str = "0";
    }
    return  res_str;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_quotient(T_str  quotient)
{
    std::cout   <<  quotient
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_remainder(T_str  remainder)
{
    std::cout   <<  remainder
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale("")); 
    char    digit           =   input_digit         ();
    int     dividend_len    =   input_dividend_len  ();
    int     divisor_len     =   input_divisor_len   ();    
        
    T_str   quotient    =   get_quotient
                                (                                    
                                    dividend_len,
                                    divisor_len                                    
                                );
 
    T_str   remainder   =   get_remainder
                                (                                    
                                    dividend_len,
                                    divisor_len,
                                    digit    
                                );
 
    print_quotient  ( quotient  );
    print_remainder ( remainder );
}
Yandex
Объявления
13.05.2012, 16:13     Деление больших чисел
Ответ Создать тему
Опции темы

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