числа — Как рассчитать и напечатать 3 ^ 9999 на С ++?
Может кто-нибудь объяснить, как позволить операциям типа 3 ^ 9999 работать в C ++, как я обнаружил, если число слишком длинное, это вызывает проблемы. Я слышал, что есть способ решить это. (Пожалуйста, не предлагайте никаких внешних библиотек)
Решение
Надеюсь, вы не ищете оптимизации …
int N = 9998;
int M = 5000;
int arr [M];
for ( int j = 0 ; j < M ; ++j )
arr[j]=0;
arr[M-1] = 3;for ( int i = 0 ; i < N ; ++i ) {
for ( int j = 0 ; j < M ; ++j )
arr[j] = arr[j]*3;
for ( int j = M-1 ; j > 0 ; --j ) {
arr[j-1] = arr[j-1] + arr[j]/10;
arr[j] = arr[j]% 10;
}
}for ( int j = 0 ; j < M ; ++j )
std::cout << arr[j];
Другие решения
Разделите вашу проблему на три проблемы.
1) Сначала примите решение, как умножить очень длинные целые числа.
2) поворот 9999 в двоичный 10011100001111, Есть 14 бит. 8 бит установлены. Установить биты (в порядке от конца) означает, что 9999 = 1 + 2 + 4 + 8 + 256 + 512 + 1024 + 8192, Факторы полезны, так как 3^2 = 3^1 * 3^1 и т.д. в целом n^(2^m) = n^(2^(m-1)) * n^(2^(m-1)), Вы можете рассчитать факторы в цикле, начиная с 3^1 = 3, что составляет 13 умножений.
3) Рассчитать 3^9999 = 3^1 * 3^2 * 3^4 * 3^8 * 3^256 * 3^512 * 3^1024 * 3^8192 умножая факторы в результате. Это делает еще 7 умножений.
Для вычисления 3 ^ 9999 вам нужно 20 очень длинных целочисленных умножений.
Поскольку вы запросили решение, которое не зависит от библиотеки, вам придется сделать это трудным путем.
Создайте функцию, которая умножает два массива цифр вместе. Вам понадобится около log10(3)*9999 цифры для этого, или 4771. Инициализируйте два массива со всеми нулями и символом 3, затем умножьте первый на второй 9998 раз.
Любые идеи о том, как я мог бы сделать это еще хуже, чтобы его профессор не принял это? знак равно
#include <stdio.h>
#include <string.h>
int main()
{
unsigned char ds[9999];
unsigned char c;
ds[0] = 3;
bzero(ds+1, 9998);
for(int p = 2; p <= 9999; p++)
{
c = 0;
for(int d=0; d<p/2+1; d++)
{
ds[d] = ds[d] * 3 + c;
c = ds[d] / 10;
ds[d] = ds[d] % 10;
}
}
int d = 9998;
for(; d>=0; d--)
if(ds[d] != 0)
break;
for(; d>=0; d--)
printf("%d", ds[d]);
printf("\n");
}