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

Cвязанные списки. Длинная арифметика. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Оформление чёрного окна консоли VS C++ http://www.cyberforum.ru/cpp-beginners/thread68034.html
Здравствуйте. Как в си ++ в чёрном окне сделатать следующее: Нужно сделать заливку синим цветом и чтоб буквы голубым (Как в FAR'е). Нужно сделать размер окна на весь экран автоматом. Нужно в переменную записать текущие размеры окна (в пробелах). Нужно сделать выпадающую менюшку как в FAR'е. Пожалуйста помогите....
C++ шестнатеричное число как в с++ преобразовать десятичное число в шестнатеричное? http://www.cyberforum.ru/cpp-beginners/thread68032.html
C++ Найти произведение чисел в массиве
кто может помочь #include <iostream.h> #include <stdlib.h> #define N 10 void main() { randomize(); for (int i=0;i<N;i++) {
Циклические очереди в C++ C++
Привеет всем;) нужно написать функции занесения и извлечения данных для циклической очереди???(обратите внимание на аргументы можно использовать перегрузку функций - так в задании написано:scratch:) простую очередь я вот так накидала(правильно ли?!!): struct Queue { int d; Queue *p; };
C++ Сортировка слов по алфавиту методом выбора. http://www.cyberforum.ru/cpp-beginners/thread68020.html
Как это дело реализовать? Задать числовое значение каждой букве в алфавите или же использовать аски ? Посоветуйте)
C++ Напишите пожалуйста програмный код) Здраствуйте! Помогите пожалуйста бедной)С++ 1)Написать программу используя функциюкоторая определяет:является ли число целым(с с помощью цикла for) 2)Написать программу которая заминяет отрицательные элементы массива на среднее арифметическое а положительные элементы на произведение элементов массива. подробнее

Показать сообщение отдельно
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
01.12.2009, 10:16
odip,
ну, это смотря как посмотреть....

Myth,
рабочий код

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
//ЙА ПРОГРАММКО, ЙА предназначена для возведения числа в большую 
//(200 знаков и больше) степень. Вводимыми данными являются 
//основание и степень, результат работы: 
//число = основание^степень. Изначально работает без 
//потери точности. Для хранения длинных чисел 
//используются двусвязные списки.
//Для возведения в степень исользуется аналог алгоритма
//"быстрого возведения в степень" основан на равенствах
//x^(2*n) = (x^n)*(x^n) и x^(2n+1) = (x^n)(x^n)*x .
//Код работает только с положительными целыми числами.
 
#include <iostream>
using namespace std;
 
#define UT unsigned int
//Определяет тип полезных данных хранимых в узлах списка.
//Рекомендуемо: unsigned long int
#define RIDEX 10
//Определяет основание системы счисления используемой 
//для хранения чисел в списках. Число представляется в виде:
//p=13!= 800*ridex^0+20*ridex^1+227*ridex^2+6*ridex^3 
//р=13!= 800_20_227_6(ridex)
//head->node1(800)<->node2(20)<->node3(227)<->node4(6)<-tail
//СТРОГО: ridex^2 < 256^sizeof(UT)
//СТРОГО: ridex кратно двум.
//СТРОГО: ridex*10 < 256^sizeof(UT)
//Рекомендуемо: ridex кратно 10. Облегчит написание функций ввода-вывода.
 
class Nodes 
{
    public:
        UT digit;
        Nodes* next;
        Nodes* prior;    
};// Что тут не понятного? Описание узлов списка.
 
 
class Long_numbers 
{
    private:
        Nodes* head; 
        Nodes* tail;
        Nodes* active; 
        Nodes* marker;   
        void Create()
        {
            Nodes* tmp = new Nodes;
            head = tmp;
            tail = tmp;
            tmp->next = NULL;
            tmp->prior = NULL;
            active = head;
            tmp->digit=0;
            marker = NULL;
        }
        
        void add_node(UT value)
        {
            Nodes* tmp = new Nodes;
            tmp->digit = value;
            tail->next = tmp;
            tmp->next = NULL;
            tmp->prior = tail;
            tail = tmp;             
        }// Добавляет узел в хвост списка. Записывает в него value.
 
 
       //ниже:Заглушка для оработки ошибок внутри класса
       void error_gag(int e)
       {
            printf("Error in Long_numbers: ");
            switch (e)
            {
                case 1:
                    {
                        printf("going before Head!\n");
                        active=head;
                    }
                case 2:
                    {
                        printf("decrement error!\n");
                    }
                case 3:
                    {
                        printf("invalid value in set-function!\n");
                    }
                case 4:
                    {
                        printf("in division_two modulus is 1!\n");
                    }
                default:printf("something wrong!\n");
            }
        }//Заглушка для оработки ошибок внутри класса        
 
 
    public:
        Long_numbers(){Create();}
        ~Long_numbers()
        {
            Nodes* tmp = head;
            while (tmp!=NULL)
            {
                head = tmp->next;
                delete tmp;
                tmp = head;
            }
        }
 
//Навигация по списку:
        void go_lowest(){active = head;}//Переход в наименьший разряд.
        bool its_lowest(){return (active->prior==NULL)?true:false;}
        void go_highest(){active=tail;}//Переход в наибольший разряд.
        bool its_highest(){return (active->next==NULL)?true:false;}
        void mark(){marker = active;}//Помечает текущий узел в списке.
        void go_mark(){active = marker;}//Переходит к помеченому узлу.
//функции работы с разрядами(узлами списка)
        UT get(){return (active->digit);}//Возвращает значение хранимое в разряде.        
 
        void go_high()
        {
            if (active->next==NULL)
                add_node(0);       
            active = active->next; 
        }//Переход в следующий разряд. Если узел не существует, то будет создан.
 
        void go_low()
        {
            if (active->prior!=NULL)
                active = active->prior;  
            else 
                error_gag(1);
        }//Переход в предыдущий разряд.
 
        void set(UT tmp)
        {            
            if ((tmp>=0)&&(tmp<RIDEX))
                active->digit = tmp;
            else error_gag(3);
        }//Устанавливает значение в разряд.
 
 
//Функции работы с числом.
        //ниже: Проверяет кратность х двум, если кратно, возвращает true 
        bool multiplicaty_two(){return (head->digit%2==0)?true:false;}
        //ниже: возарщает true, если большое число равно нулю.
        bool zerro(){ return (tail->digit==0)?true:false;}
 
        //ниже: Уменьшает х на единицу. Строго: младший разряд больше либо равен 1.
        void decrement()
        {
            if ( head->digit >= 1 )
                head->digit--;
            else
                error_gag(2);
        }
        
       
        //ниже: добавляет к текущему разряду число.( Исп: перенос в старший разряд)
        void add(UT carry)
        {
            Nodes* ip = active;
            while(true)
            {
                carry += ip->digit ;
                ip->digit = carry%RIDEX;
                carry -= ip->digit;
                carry /=RIDEX;
                if (carry==0) break;
                if (ip->next == NULL) add_node(0); //{ add_node(carry); break; }
                ip = ip->next;                            
            }
        }//Добавляет к текущему разряду число carry (строго меньшее ridex^2). 
        //В случае необходимости выполняет правку старших разрядов.
        
        //ниже: Производит деление на 2.Строго: число кратно 2.
        //пробегает список от хвоста к голове, деля значение разряда на два,
        //переносит остаток от деления в следующий разряд:
        void division_two()
        {
            UT carry = 0;//для переноса частного от деления.
            Nodes* ip = tail;//итерационный указатель.
            while(true)
            {
                if (ip->digit%2==0)
                {
                    ip->digit = (ip->digit+carry*RIDEX)/2;
                    carry=0;
                }
                else
                {
                    ip->digit = (ip->digit+carry*RIDEX-1)/2;
                    carry=1;
                }
                
                if(ip==head)
                {
                    if(carry) error_gag(4);//Error: modulus in lowest is one                    
                    break;
                }
                    
                ip = ip->prior;
                
  //             
            }
        //Старший разряд мог обратиться в ноль, если так, его нужно убрать:
        if(tail->digit == 0)
        {
            if (tail!=head)//чтоб не "убить" число 0 записаное в один узел.
            {
                tail = tail->prior;
                delete (tail->next);
                tail->next=NULL;           
            }
        }
                
        }//Производит деление на 2.Строго: число кратно 2.
 
        
};
 
 
 
//ниже: Умножает b на a и помещает результат в b.СТРОГО: &a!=&b
void multiplication(Long_numbers* b, Long_numbers* a);
void output(Long_numbers* x);//Выводит длинное число куда-нибудь(На экран?)
void input(Long_numbers* x);//Обеспечивает ввод длинного числа
void dig_copy(Long_numbers* x, Long_numbers* y);//Kопирует нижние разряды Х в У.
 
//========================
//====================
//===============
int main()
{   
    UT x = 0;
    Long_numbers power;
    Long_numbers number;
    Long_numbers tmp;//вспомогательный, для умножения а*а( tmp = a; a = a*tmp)
    Long_numbers t;//вспомогательный вектор.(для возведения в степень.)
    t.go_lowest();t.set(1); //t = 1
 
    system("cls");
    printf("IT's power");
    input(&power);
    printf("It's number");
    input(&number);
 
 
//Что вообще будет происходить. Если бы числа были "обычные", то код выглядел
//бы так:
//  long t=1;
//  while (power) 
//  {
//    if (power%2==0){ power/=2; number *= number; }
//    else { power-- ; t *= number; }
//  }
//  return t;
//Реализация для длинных чисел:(number*=number====>{tmp=number;number=number*tmp})
    while(!power.zerro())
    {
        if(power.multiplicaty_two())
        {
            power.division_two();
            dig_copy(&tmp, &number);//Всегда получаeтся, что number не короче tmp
            multiplication(&number,&tmp);
        }
        else
        {
            power.decrement();
            multiplication(&t,&number);
        }
    }
 
    system("cls");
 
    printf("\nSolution is done!!\n");   
    system("pause"); 
 
    output(&power);
    printf("\nit's power (must be one zerro)\n");
    system("pause");
 
    output(&t);
    printf("\nits number....\n");
    system("pause");
 
    return EXIT_SUCCESS;
}
 
 
//ниже: Умножение a на b с занесением результата в b.( b = b*a )СТРОГО: &a!=&b
void multiplication(Long_numbers* b, Long_numbers* a)
{
    if (a==b){printf("\n\t Fatal error. Press Ctrl+C.");system("PAUSE");}
    
    b->go_highest();
    UT tmp = 0;
    UT carry = 0;       //перенос в старший разряд
    while(true)
    {
        b->mark();
        tmp = b->get(); //Ибо текущее значение разряда Б измениться в первую очередь.
        b->set(0);      //И его нужно освободить.
        a->go_lowest();
        while(true)
        {
           // UT s = tmp*a->get(); //вспомогательная пременная
            b->add(tmp*(a->get()));
            if ((a->its_highest())) break;  
            a->go_high();
            b->go_high();       //Поправка на переход А в старший разряд.
        }
        b->go_mark();
        if (b->its_lowest()) break;
        b->go_low();
    }
 
} //Умножает a на b и заносит результат в b. Используется подредактированый алгоритм
// школьного умножения в столбик. Реализация: А поразрядно от меньшего к
//большему умножается на значение i-того разряда Б, результат прибавляется
//к разрядам Б старше i-того. Значения i перебираются от старшего Б до младшего.
// в результате, при полном прохождении, результат умножения А на Б оказывается 
//записаным в Б.Очевидно, А не должно совпадать с Б.PS:Количество вызовов и кода
//можно сократить раза в четыре, так что, если понятно что происходит, 
//рекомендуется оптимизировать.
 
 
//ниже: Kопирует нижние разряды y в x.
// то есть если Х=1 2 3, У = 4 5 6 7 и ridex=10, то dig_copy(&y,&x) даст У = 4 1 2 3,
// с другой стороны даст dig_copy(&x,&y) даст Х =4 5 6 7. Функция вспомогательная, 
//для возможности передачи multiplication двух одинаковых аргументов.
void dig_copy(Long_numbers* x, Long_numbers* y)
{
    x->go_lowest();
    y->go_lowest();
    while(true)
    {
        x->set(y->get());
        if(y->its_highest()) break;
        y->go_high();
        x->go_high();
    }
    if(!x->its_highest()) printf("\nwarning in dig_copy().");//совпадают не полностью
}//поразрядное копирование y в x.
 
void input(Long_numbers* x)//Написан для тестирования. ПЕРЕПИСАТЬ!!!!!
{   
    using namespace std; 
 //   system("cls");
    cout<<"\nInputing coef (num is sum coef(i)*ridex^i) from lowest to hhigest i\n";
    cout<<"end of inputing if coef = ridex\n";
    UT coef =0;
    x->go_lowest();
    cout<<"\nridex = "<<RIDEX<<"\tfirst coef is ";
    cin>>coef;
    x->set(coef);
    cout<<"\t\t\t\tfine!";
 
    do{
        cout<<"\nridex = "<<RIDEX<<"\tnext coef is ";
        cin>>coef;
        if ((coef>=0)&&(coef<RIDEX))
        {
            x->go_high();
            x->set(coef);
            cout<<"\t\t\t\tfine!";
        }
    }while(coef<RIDEX);
    cout<<"\n\t\t\t\tend of input!!\n\n\n";
    
}//Поразрядный ввод от младшего разряда к старшему. Прекращение ввода по заведомо
//неверному значению(нестрого-большее райдекс)
 
 
void output(Long_numbers* x)//написан для тестирования опереций.. Переписать!!!
{
    using namespace std; 
//    system("cls");
    cout<<"\nOutputing coef (num is sum coef(i)*ridex^i) from highest to lowest i\n";
    cout<<"ridex = "<<RIDEX<<endl;
    x->go_highest();
    while(!(x->its_lowest()))
    {
        cout<<x->get()<<endl;
        x->go_low();
    }
    cout<<x->get()<<endl<<"\t\t done!";
}// Вывод построчный от старшего разряда к младшему, 
// неявные нули в разрядах игнорируються.(002 выведет как 2)



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