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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Найти "средний" по величине делитель числа http://www.cyberforum.ru/cpp-beginners/thread363028.html
Надо найти "средний" по величине делитель числа х.Использовать прибавление 1 = + - х :-целочисленное деление и %-остаток от деления. 3.3 Запрещено создавать темы с бессмысленными названиями вроде "Помогите!", "Вопрос" и т.п
C++ странная последовательность Во входном файле записана последовательность чисел в странном формате: у каждого числа сначала записано количество цифр в этом числе, а потом через пробел - сами цифры. Последовательность заканчивается числом 0. В выходной файл нужно вывести сначала количество чисел в последовательности, а потом - сами числа. Количество чисел в последовательности не превышает 1000. В числах - не более 4-х... http://www.cyberforum.ru/cpp-beginners/thread363025.html
Линейные Односвязные Списки С++ C++
Разработать и реализовать программу создания и обработки линейного односвязного списка с одним информационным полем, которое содержит целое число. Программа должна содержать меню с перечнем возможностей работы со списком и выбора соответствующего пункта меню с обращением к функции, реализующей выбранное действие над списком: (меню сама сделаю..мне бы те программки которые ниже..а то я совсем...
написать программу вычисляющие ИМЛ с помощью узлов Чебышева C++
помоги кто чем может а...cout<<"Help me"<<endl;
C++ Задача с вычислениями по формулам http://www.cyberforum.ru/cpp-beginners/thread363004.html
Помогите пожалуйста написать программу для расчёта по двум формулам, результат первой должен совпадать со второй. формулы: {Z}_{1} = \frac{sin2\alpha+sin5\alpha-sin3\alpha}{cos\alpha+1-{2sin}^{2}2\alpha}; {Z}_{2} = 2sin\alpha то есть пользователь вводит величину угла (альфа) например: ввод: 0 вывод: 0.00 0.00
C++ Для данных областей... Для данных областей составить линейную программу , которая печатает true ,если точка с координатами (x,y) принадлежит закрашенной области , и false – в противном случае. подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.10.2011, 17:20     Извлечение корня, длинная арифметика
Было решение на 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;
}
 
Текущее время: 07:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru