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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
#1

Извлечение корня, длинная арифметика - C++

08.10.2011, 13:58. Просмотров 2424. Ответов 5
Метки нет (Все метки)

По заданному натуральному числу А требуется найти наибольшее число В такое, что B^2 <= A.

вот набросал, но прога работает медленно. как ее можно оптимизировать или подскажите более быстрый способ.
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
#include <fstream>
#include <string>
#include <deque>
using namespace std;
 
int sravnenie(deque<int>& a,deque<int>& b)
{   
    int lena=a.size(),lenb=b.size();
    if (lena>lenb) return 1;
    if (lena<lenb) return 2;
    if (lena==lenb)
    {
        for (int i=0;i<lena;i++)
        {
            if (a[i]!=b[i])
                if (a[i]>b[i]) 
                    return 1;
                else
                    return 2;
        }
    }
    return 0;
}
 
 
deque<int> slozhenie(deque<int>& a,deque<int>& b)
{  
    if (a.empty()) 
        return b;
    else
    {
        int lena=a.size()-1,lenb=b.size()-1;
        int perenos = 0, achislo, bchislo, summa, i=0;
        deque<int> res;
        do 
        {
            if (lena>=i)
                achislo = a[lena-i];
            else
                achislo = 0;
 
            if (lenb >= i) 
                bchislo = b[lenb-i];
            else
                bchislo = 0;
 
            summa = achislo + bchislo + perenos;
            if (summa >= 10 )
            {
                perenos = summa / 10;
                summa = summa % 10;
            }
            else
            {perenos = 0;}
 
            res.push_front(summa);
            i++;
        }while((lena>=i)||(lenb>=i));
 
        if (perenos > 0)
        {
            res.push_front( perenos);
        }
        return res;
    }
}
 
deque <int> sq2(deque<int>& y)
{
    deque <int> a=y;
    int h=0;
    while( (!a.empty()) && (!a.back()))  {a.pop_back(); h++;}   
 
    int perenos,proizvedenie;
    int lena=a.size()-1;
    deque<int> proizv,res;
    for(int i = lena; i>=0; i--)
    {
        proizv.clear(); 
        perenos = 0;       
 
        for (int j = lena; j>=0; j--)
        {       
            proizvedenie = a[i] * a[j] + perenos;
 
            if (proizvedenie >= 10) 
            {
                perenos = proizvedenie / 10;
                proizvedenie %= 10;
            }
            else
            {perenos = 0;}          
 
            proizv.push_front(proizvedenie);
        }
        if (perenos > 0) {proizv.push_front(perenos);}
        while( (!proizv.empty()) && (!proizv.front()))  {proizv.pop_front();}
        proizv.resize(proizv.size()+lena-i);
        res=slozhenie(res,proizv);
    }    
 
    res.resize(res.size()+2*h);
    return res;
}
 
deque<int> sqrt(deque<int>& a)
{
    int n=(a.size()+1)/2;
    deque<int> r(n);
 
    for(int i=0;i<n;i++)
    {
        for (int j=9;j>=0;j--)
        {
            r[i]=j;
            if (sravnenie(sq2(r),a)!=1) break;
        }
    }
    return r;       
}
 
int main(void)
{   
    string in;
    ifstream fin ("INPUT.TXT"); 
    ofstream fout ("OUTPUT.TXT");
    fin >> in;
    deque<int> a;
    for (unsigned int i=0;i<in.size();i++)  a.push_back(in[i]-48);
    deque<int> rezult=sqrt(a);
    for (unsigned int i=0;i<rezult.size();i++)  fout <<rezult[i];
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2011, 13:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Извлечение корня, длинная арифметика (C++):

Длинная арифметика - C++
Доброго времени суток. Подскажите, как реализовать деление с остатком двух чисел, находящихся в двусвязном списке, узлы которого - цифры....

Длинная арифметика)) - C++
Программка уже почти готова, единственное неправильно находит остаток при делении По заданию: Надо ввести 2-ва целых числа неогран....

Длинная арифметика - C++
Всем привет! Хотелось бы узнать -- есть ли в С++ библиотека, где реализованы операции над длинными числами?

Длинная арифметика - C++
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших...

Длинная арифметика С++ - C++
требуется написать задачу для подсчета суммы s=1^2+2^2+3^2+...+n^2 n&gt;=20000

Длинная арифметика - C++
Алгоритмы всех операций в принципе уже готовы (длина числа ограничивается только ресурсами ПК). Осталось только подобрать качественный...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
hepr
61 / 33 / 5
Регистрация: 21.10.2010
Сообщений: 539
08.10.2011, 15:25 #2
Попробуйте это
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "stdafx.h"
#include "iostream"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int a;
    cin >> a;
    unsigned int first,second;
    first = second = 0;
    for (register unsigned int b=1;;b++)
    {
        second = b*b;
        if(second<=a)
            first = b;
        else
        {
            cout << first;
            break;
        }
    }
    system("pause");
    return 0;
}
Добавлено через 38 секунд
Если я конечно правильно понял задание
1
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.10.2011, 15:34  [ТС] #3
для чисел до 10^3000
0
kazak
3035 / 2356 / 155
Регистрация: 11.03.2009
Сообщений: 5,402
Завершенные тесты: 1
08.10.2011, 15:37 #4
C++
1
b = static_cast<int>(sqrt(static_cast<double>(a)));
0
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.10.2011, 17:11  [ТС] #5
Цитата Сообщение от kazak Посмотреть сообщение
C++
1
b = static_cast<int>(sqrt(static_cast<double>(a)));
и как с помощью этого извлечете целую часть корня например из 100 значного целого числа?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.10.2011, 17:20 #6
Было решение на e-maxx.ru, но почему-то не могу найти там эту тему, поэтому просто выложу исходник.
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
155
156
#include <cstdlib>
#include <stdio.h>
#include <string.h>
 
using namespace std;
typedef unsigned char uchar;
typedef unsigned short ushort;
 
#define MAX_LEN 3100
#define bigint ushort *
#define base 10
 
bigint tmp = new ushort[MAX_LEN];
bigint prr = new ushort[MAX_LEN];
bigint tmp1 = new ushort[MAX_LEN];
bigint tmp2 = new ushort[MAX_LEN];
 
int cmp(bigint a, bigint b){
    if(a[0]!=b[0]) return (int)a[0]-b[0];
    for(register int i=a[0];i>0;i--)
        if(a[i]!=b[i]) return (int)a[i]-b[i];
    return 0;
}
 
bigint read(){
    bigint r = new ushort[MAX_LEN];
    char s[MAX_LEN];
    scanf("%s",s);
    int c = 0, l = strlen(s);
    if(l>1)
        for(int i=0;i<l;i++, c++)
            if(s[i]!='0') break;
    r[0]=l-c;
    for(register int i=l-1; i>=c; i--)
        r[l-i]=s[i]-'0';
    return r;
}
 
void write(bigint n){
    for(int i=n[0];i>0;i--)
        printf("%d",n[i]);
}
 
void smul(bigint a, ushort b, bigint c) {
    long i, temp;
    ushort carry=0; 
    for (i=1; i<=a[0];i++) {
        temp = a[i]*b + carry;
        carry = temp / base;
        c[i] = temp - carry*base;
    }
    if (carry) {
        c[i] = carry;
        c[0] = a[0]+1;
    } 
    else c[0] = a[0];
    while(c[0]>0 && c[c[0]]==0) c[0]--;
}
 
void shift(bigint a, int s){
    for(int i=a[0];i>0;i--)
        a[i+s] = a[i];
    for(int i=1;i<=s;i++) a[i]=0;
    a[0]+=s;
}
 
void summ(bigint a, bigint b, bigint c){
    long i, temp;
    ushort carry = 0;
    if ( a[0] < b[0] ) {
        summ(b,a,c);
        return;
    }
    for (i=1; i<=b[0]; i++) {
        temp = a[i] + b[i] + carry;
        if (temp >= base) {
            c[i] = temp - base;
            carry = 1;
        } else {
            c[i] = temp;
            carry = 0;
        }
    }
    for (; i <= a[0]; i++) {
        temp = a[i] + carry;
        if (temp >= base) {
            c[i] = temp - base;
            carry = 1;
        } else {
            c[i] = temp;
            carry = 0;
        }
    }
    if (carry) {
        c[i] = carry;
        c[0] = a[0]+1;
    } 
    else c[0] = a[0];
    while(c[0]>0 && c[c[0]]==0) c[0]--;
}
 
ushort findBin(bigint a, bigint r, int cur){
    // though... it's not a binary search.
    short res = base-1;
    ushort up = base-1, down = 0;
    while(res>0){
        smul(r, 2, tmp1);
        smul(tmp1, res, tmp2);
        shift(tmp2, cur-1);
        summ(prr, tmp2, tmp);
        tmp1[0]=1; tmp1[1]=res;
        smul(tmp1, res, tmp2);
        shift(tmp2, cur*2-2);
        summ(tmp, tmp2, tmp1);
        if(cmp(tmp1,a)<=0){ 
            break;
        }
        res--;
    }
    while(res>=base) res--;
    smul(r, 2, tmp1);
    smul(tmp1, res, tmp2);
    shift(tmp2, cur-1);
    summ(prr, tmp2, tmp);
    tmp1[0]=1; tmp1[1]=res;
    smul(tmp1, res, tmp2);
    shift(tmp2, cur*2-2);
    summ(tmp, tmp2, prr); 
    return r[cur]=res;
}
 
bigint sqrt(bigint a){
    bigint r = new ushort[MAX_LEN];
    r[0] = (a[0]+1)>>1;
    for(register int i=1;i<=r[0];i++)
        r[i]=0;
    register int cur = r[0];
    while(cur){
        r[0] = (a[0]+1)>>1;
        r[cur]=findBin(a, r, cur);
        cur--;
    }
    return r;
}
 
// Program entry
int main(int argc, char** argv) {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    bigint n; bigint s;
    prr[0]=0;
    n = read();
    s = sqrt(n);
    write(s);
    return 0;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2011, 17:20
Привет! Вот еще темы с ответами:

Длинная арифметика - C++
Ребята,объясните как решить задачу , напишите хоть часть кода. Пусть даны числа a , b . Найти a+b, если a и b не больше чем 10 в...

Длинная арифметика - C++
Доброго времени, в задачке по криптоанализу столкнулся с недостатком размерности типов в с++. В процессе поиска нашел ряд решений: 1)...

Длинная арифметика - C++
:senor: Здраствуйте, пишу модуль длинной математики. В принципе, работоспособность у него положительная. Но в силу моей неопытности меня...

Длинная арифметика - C++
Всем доброго вечера. Нужна помощь в решении задачи. Составить программу для вычисления числа: 2^64-1. В результате сохранить все...


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

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

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