Форум программистов, компьютерный форум 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
29.11.2009, 14:45     Cвязанные списки. Длинная арифметика.
поправка:
в прошлом посте строку
... пусть наша степень р=13!=6227020800(dec) тогда...
читать: пусть наше число р=13!=6227020800(dec) тогда...

Продолжаем.
В прошлом посте было сформулировано что такое длинные числа и каким образом можно умножать длинные числа, давайте разберёмся, что нам нужно, для возведения числа в степень N. Покурил, подумал - увы - в мой мозг ничего кроме последовательного понижения степени не пришло. То есть x^(2*n) = (x^n)*(x^n) и x^(2n+1) = (x^n)(x^n)*x. Недостаток метода в том, что для понижения степени на три знака потребуется выполнить примерно 10 операций умножения, если наша степень длинной в 200 знаков, то для того чтоб вычислить значение, нам потребуется выполнить около 700 подобных операций (вообще-то, O(log(N)) операций.)..
Ближе к коду: есть два пути реализации: первый потребует представления степени (или куска степени) в двоичной системе; второй потребует определить операции деления на два, декримента и проверки кратности для наших длинных чисел. Склоняюсь ко второму варианту.
Тогда в реализации будет что-то подобное:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class my_long{};
my_long power;
my_long a;
my_long b;
 
while(!(power.is_empty))
{
  if(power.multiplicity()) {power.division(); multiplication(my_long &a,my_long &a);}
  else {power.decrement(); multiplication(my_long &b,my_long &a);}
}
//power.decrement() it's  power = power-1;
//power.division() it's power = power/2;
//power.multiplicity() it's  (power%2==0)?true:false;
//multiplication(b, a) its b = b*a;
Теперь определим как это делается:
Самое простое - проверка кратности двум: если младший разряд кратен двум, то и всё число кратно двум.
оперция дикримента тоже проста: Нужно вычесть из младшего разряда 1. По условию, он не кратен двум, следовательно его значение не ноль, то есть либо 1 либо больше. В любом случае - никаких заимствований делать не нужно.
Деление на два:
Код
разряд = старший разряд;
остаток = 0;
пока (разряд!=NULL)
{
  перейти в разряд;
  если ((разряд.значение)%2 == 0) 
     {разряд.значение = (разряд.значение+остаток*ridex)/2; остаток = 0;}
  иначе 
     {разряд.значение = (разряд.значение+остаток*ridex-1)/2; остаток =1;}
   разряд = предыдущий разряд // а для младшего разряда предыдущим будет NULL
}
Для того чтоб последнее нормально работало ridex следует выбирать кратным двум. А чтоб облегчить себе процесс ввода-вывода лучше кратным 10.. Вообщем, используем:
#define RIDEX
Теперь мы обладаем достаточными "знаниями" для решения задачи.

Пара замечаний: при умножении мы будем двигаться от младшего разряда к старшему, следовательно головой списка должен являться младший разряд (именно поэтому рекомендовалась
запись от младшего к старшему - для естественного движения по списку.) При делении - от старшего к младшему. Если планируется использовать один класс для представления возводимого числа и степени, то для удобства логично использовать двусвязный список (хотя, при некотором изврещании, можно и односвязным обойтись, но зачем? Хотя 4 байта на узел сэкономим=))
И еще, помимо умножения в столбик существуют алгоритмы быстрого умножения, их использование начинает давать выигрыш при числах длиннее 250 знаков..

По алгоритму вроде всё. Или нет??
 
Текущее время: 10:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru