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

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

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

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

08.10.2011, 13:58. Просмотров 2383. Ответов 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];
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2011, 13:58     Извлечение корня, длинная арифметика
Посмотрите здесь:

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

Длинная арифметика N+1 - C++
Помогите плиз. Вводится n. Вывести N+1. Ограничений нет. Я понимаю что надо ввести массив и читать каждый символ. Оставшиеся елементы...

Длинная арифметика - C++
Здравствуйте! Есть задание: Составить программу для вычисления числа: (2^64) - 1. В результате сохранить все цифры. 2^64 - это 2...

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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 секунд
Если я конечно правильно понял задание
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.10.2011, 15:34  [ТС]     Извлечение корня, длинная арифметика #3
для чисел до 10^3000
kazak
3034 / 2355 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
08.10.2011, 15:37     Извлечение корня, длинная арифметика #4
C++
1
b = static_cast<int>(sqrt(static_cast<double>(a)));
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 значного целого числа?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2011, 17:20     Извлечение корня, длинная арифметика
Еще ссылки по теме:

Длинная арифметика - C++
class BigInt { static const int max_size = 100000;//количество десятичных разрядов, которые должно вмещать static...

Длинная арифметика - C++
http://www.********/index.asp?main=task&amp;id_task=103 Как решить эту задачу? С помощью чего, и в чем смысл решения длянной...

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

длинная арифметика - C++
решите задачку: пользователь вводит 2 больших числа (числа от -1*2^127 до 1*2^127-1). Написать программу для суммирования таких чисел.

Длинная арифметика - C++
Здравствуйте, есть такая задача.. Препод по алгоритмам задал сделать программу для перевода чисел в разные системы счислений. Это...

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


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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1928 / 1194 / 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;
}
Yandex
Объявления
08.10.2011, 17:20     Извлечение корня, длинная арифметика
Ответ Создать тему
Опции темы

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