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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
movielucky
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 13
#1

Найти делители "длинного" числа - C++

15.07.2014, 11:03. Просмотров 1739. Ответов 24
Метки нет (Все метки)

Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2014, 11:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти делители "длинного" числа (C++):

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений - C++
Здравствуйте, помогите написать две программы. 1) Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива. - C++
Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива. ...

Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол" - C++
кто то напишите пожалуйста, вот программа: наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные...

Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей"; - C++
Помогите пожалуйста с задачей. Могу сделать ее просто, но надо через ООП и у меня не получается. Дано натуральное число N (N<20),...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
SatanaXIII
Супер-модератор
Эксперт С++
5616 / 2651 / 246
Регистрация: 01.11.2011
Сообщений: 6,529
Завершенные тесты: 1
15.07.2014, 11:38 #2
В столбик.
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
15.07.2014, 11:40 #3
откуда возникла такая задача? как решать то я не знаю, но у числа длиной 12000 может быть дофига делителей!!!
если грубо оценить, то 2 * sqrt(n), но вообще слышал оценку что у числа n примерно n^(1 / 3) делителей, если не ошибаюсь. 10^4000 делителей? как их сохранить?
0
SatanaXIII
Супер-модератор
Эксперт С++
5616 / 2651 / 246
Регистрация: 01.11.2011
Сообщений: 6,529
Завершенные тесты: 1
15.07.2014, 11:44 #4
Цитата Сообщение от SlavaSSU Посмотреть сообщение
как их сохранить?
Можно попробовать запомнить - ассоциативные методики запоминания позволяют запомнить очень дофига бессмысленных цифр подряд.
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
15.07.2014, 12:21 #5
а нет, сейчас так проверил на нескольких числах. кубический корень - слишком много, там меньше получается.
т.е. в основном это сильно меньше чем куб корень, но все равно может быть дофига.
2 * 3 * 5 * ... * p[k];
вот так вот умножаешь последовательно простые, пока результат не станет больше исходного числа, пусть длина такого произведения равна k, тогда у числа есть примерно 2 ^ k делителей.
0
dogg12
63 / 29 / 6
Регистрация: 21.02.2011
Сообщений: 831
15.07.2014, 16:53 #6
попробуйте применить алгоритм перебора делителей
0
avg93
61 / 61 / 10
Регистрация: 11.12.2009
Сообщений: 248
Завершенные тесты: 3
15.07.2014, 17:58 #7
Цитата Сообщение от movielucky Посмотреть сообщение
Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?
А как без длинной арифметики тут? Нужны алгоритмы деления длинных чисел.
0
dogg12
63 / 29 / 6
Регистрация: 21.02.2011
Сообщений: 831
15.07.2014, 18:01 #8
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
//////////////////////////////////////////////////////////////////////////////////////
//Необходимо разделить большое чило на большое число.
//Эти числа хранятся в массиве (каждый элемент - одна цифра числа).
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_num_s;
//////////////////////////////////////////////////////////////////////////////////////
void  del_leading_zero(T_num_s&  a)
{
    while(a.size() > 1
          && a[0] == '0')
    {
        a.erase(0, 1);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
bool less_for_big_int(T_num_s  a, T_num_s  b)
{
    del_leading_zero(a);
    del_leading_zero(b);
 
    return  a.size() == b.size() ? a < b : a.size() < b.size();
}
//////////////////////////////////////////////////////////////////////////////////////
void  reduce_big_int(T_num_s&  minuend, const T_num_s&  subtrahend)
{    
    for(T_num_s::size_type  cur_pos = 0; cur_pos < subtrahend.size(); ++cur_pos)
    {
        T_num_s::size_type  minuend_cur_pos     = minuend.size()     - 1 - cur_pos;
        T_num_s::size_type  subtrahend_cur_pos  = subtrahend.size()  - 1 - cur_pos;
 
        char&        cur_minuend_dig_ref     = minuend     [minuend_cur_pos];
        const char&  cur_subtrahend_dig_ref  = subtrahend  [subtrahend_cur_pos];
 
        if(cur_minuend_dig_ref >= cur_subtrahend_dig_ref)
        {
            cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0';
        }
        else
        {
            (cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0') += 10;
            for(int i = 1; ; ++i)
            {
                if(minuend[minuend_cur_pos - i] == '0')
                {
                    minuend[minuend_cur_pos - i] = '9';
                }
                else
                {
                    --minuend[minuend_cur_pos - i];
                    break;
                }
            }
        }
        del_leading_zero(minuend);
    }
    del_leading_zero(minuend);
}
//////////////////////////////////////////////////////////////////////////////////////
void  inc_big_int(T_num_s&  a)
{    
    for(T_num_s::size_type  cur_pos = a.size() - 1;; --cur_pos)
    {
        if(a[cur_pos] < '9')
        {
            ++a[cur_pos];
            return;
        }
        else
        {
            a[cur_pos] = '0';
            if(cur_pos == 0)
            {              
                a.insert(0, "1");
                return;
            }
        }    
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_num_s  div_big_int(const T_num_s&  a, const T_num_s&  b)
{
    if(b == "0")
    {
        return  "division into zero";
    }    
 
    T_num_s  res = "0";
    T_num_s  minuend     = a;
    T_num_s  subtrahend  = b;
    
    while(subtrahend.size() < minuend.size())
    {
        subtrahend += '0';    
    }
 
    for(;;)
    {
        while(!less_for_big_int(minuend, subtrahend))
        {
            reduce_big_int(minuend, subtrahend);
            inc_big_int(res);
        }
        if(subtrahend.size() <= b.size())
        {
            break;
        }
        
        subtrahend.erase(subtrahend.size() - 1);   
        res += '0';              
        del_leading_zero(res);
    }          
    
    return  res;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    for(;;)
    {
        std::cout << "a = ";
        T_num_s  a;
        std::cin >> a;
        del_leading_zero(a);
 
        std::cout << "b = ";
        T_num_s  b;
        std::cin >> b;
        del_leading_zero(b);
 
        std::cout << "a / b = "
                  << div_big_int(a, b)
                  << std::endl
                  << std::endl
                  << std::endl;    
    }
}
0
NEbO
15.07.2014, 18:31
  #9

Не по теме:

40к бит? ха. а может уж сразу ключик выпишите, а мы тут все вместе вам его факторизуем?

0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
15.07.2014, 19:35 #10
dogg12, я вам признателен, что вы процитировали мою программу, но это решение задачи разделить одно длинное число на другое. В данной задаче делений гораздо больше, поэтому она по скорости не подойдет.
0
dogg12
63 / 29 / 6
Регистрация: 21.02.2011
Сообщений: 831
15.07.2014, 19:50 #11
Можно попробовать перейти к двоичной арифметике, как писали выше для деления "в столбик", т.к. алгоритм при таком подходе упрощается.
0
Sergio Leone
2455 / 1100 / 402
Регистрация: 07.06.2014
Сообщений: 3,259
15.07.2014, 22:54 #12
dogg12, Вы ещё не поняли, в чём затык?
Делители нужно искать в цикле, да?
Попробуйте, для начала,организовать цикл, ну, скажем, до сектилиона.
Напоминаю, что секстиллион это http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{21} (см.вики)
т.е. это число 1000000000000000000000

а теперь допишите ноликов ещё примерно 5 тысяч штук. И подумайте, сколько будем выполняться такой цикл.
0
dogg12
63 / 29 / 6
Регистрация: 21.02.2011
Сообщений: 831
15.07.2014, 23:15 #13
Я понял, но смотрите, у меня такая мысль: будем выполнять деление в столбик.
Переведем числа в двоичную систему.
Сдвигаем делитель влево до тех пор, пока старший бит не станет 1, запоминаем количество сдвигов.
Повторяем столько раз, сколько было сдвигов.
Если делитель (модифицированный) меньше делимого, то вычитаем его из делимого, очередной бит ответа — 1
иначе очередной бит ответа — 0.
Сдвигаем делитель вправо.
Если нет возможности перейти к двоичной арифметике, алгоритм усложнится, потому что на каждом шаге основного цикла надо будет не просто сравнивать делимое с делителем, а вычислять очередную цифру ответа. Для десятичных чисел сдвиг влево — это дополнение делителя справа нулем.
Я не спорю, есть и более скоростные алгоритмы, которые основаны на обработке не одного бита за раз, а сразу группы бит (2, 4, 8), но они сложнее.
0
Sergio Leone
2455 / 1100 / 402
Регистрация: 07.06.2014
Сообщений: 3,259
15.07.2014, 23:24 #14
Цитата Сообщение от dogg12 Посмотреть сообщение
Я не спорю, есть и более скоростные алгоритмы, которые основаны на обработке не одного бита за раз, а сразу группы бит (2, 4, 8), но они сложнее.
так. ещё раз.
Допустим, ваш компьютер за один такт процессора проверяет делится ли одно длинное число на другое.
Тогда Вы за одну секунду можете проверить 4 миллиарда длинных чисел (4 ГГц). Это http://www.cyberforum.ru/cgi-bin/latex.cgi?4 * {10}^{9}
Подсчитайте, пожалуйста, сколько потребуется секунд, чтобы проверить на делимость http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6000} чисел.
Полученное число секунд переведите в число лет.
И поймёте, о чём здесь говорят, когда утверждают, что не хватит времени на выполнение цикла.
0
dogg12
63 / 29 / 6
Регистрация: 21.02.2011
Сообщений: 831
15.07.2014, 23:26 #15
Тогда подобный вопрос должен стоять явно не в разделе для начинающих)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.07.2014, 23:26
Привет! Вот еще темы с ответами:

Многократное "длинное" деление (длинного на короткое) - C++
В общем есть задача на перевод с одной системы счисления в другие, где нужно использовать длинную арифметику (деление длинного на...

Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку - C++
Здравствуйте. Задача следующая: Найти все целые числа из промежутка от a до b, у которых количество делителей равно k. К примеру я взял...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.07.2014, 23:26
Ответ Создать тему
Опции темы

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