Рассчитать пол (pow (2, n) / 10) mod 10 — сумма цифр pow (2, n)
Это тоже вопрос, связанный с математикой, но я бы хотел реализовать его в C ++ … так что у меня есть число в виде 2^n, и я должен рассчитать сумму его цифр (в базе 10; P). Моя идея состоит в том, чтобы рассчитать его по следующей формуле:
sum = (2^n mod 10) + (floor(2^n/10) mod 10) + (floor(2^n/100) mod 10) + ...
для всех его цифр: floor(n/floor(log2(10))),
Первый член легко вычислить с помощью модульного возведения в степень, но у меня проблемы с другими.
поскольку n большой, и я не хочу использовать мою большую целочисленную библиотеку, я не могу рассчитать pow(2,n) без модуля. Фрагмент кода для первого семестра:
while (n--){
temp = (temp << 1) % 10;
};
но для второго я понятия не имею. Я тоже не могу floor их индивидуально, так как это даст «0» (2/10). Можно ли этого добиться?
(http://www.mathblog.dk/project-euler-16/ для более простого решения.) Конечно, я буду искать другой путь, если это невозможно сделать с помощью этого метода. (например, сохранение цифр в байтовом массиве, как в комментарии в ссылке).
Редактировать: Спасибо за существующие ответы, но я ищу какой-то способ решить это математически. Я только что придумал одну идею, которая может быть реализована без больших чисел или цифр-векторов, я проверю, работает ли она.
Итак, у меня есть уравнение выше для суммы. Но 2^n/10^k можно записать как 2^n/2^(log2 10^k) который 2^(n-k*log2 10), Затем я беру его дробную часть и целочисленную часть и выполняю модульное возведение в степень в целочисленной части: 2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10)), После последней итерации я также умножаю его на дробное по модулю 10. Если это не сработает или я ошибаюсь где-то в представленной выше идее, я придерживаюсь векторного решения и принимаю ответ.
Редактировать: Хорошо кажется выполнение модульного возведения в степень с нецелым по модулю невозможно (?) (или я ничего не нашел об этом). Итак, я делаю решение на основе цифр / векторов.
Код НЕ работает полностью!
Это не дает хорошего значения: (1390 вместо 1366):
typedef long double ldb;
ldb mod(ldb x, ldb y){ //accepts doubles
ldb c(0);
ldb tempx(x);
while (tempx > y){
tempx -= y;
c++;
};
return (x - c*y);
};
int sumofdigs(unsigned short exp2){
int s = 0;
int nd = floor((exp2) * (log10(2.0))) + 1;
int c = 0;
while (true){
ldb temp = 1.0;
int expInt = floor(exp2 - c * log2((ldb)10.0));
ldb expFrac = exp2 - c * log2((ldb)10.0) - expInt;
while (expInt>0){
temp = mod(temp * 2.0, 10.0 / pow(2.0, expFrac)); //modulo with non integer b:
//floor(a*b) mod m = (floor(a mod (m/b)) * b) mod m, but can't code it
expInt--;
};
ldb r = pow(2.0, expFrac);
temp = (temp * r);
temp = mod(temp,10.0);
s += floor(temp);
c++;
if (c == nd) break;
};
return s;
};
Решение
В ссылке, которую вы упоминаете, у вас есть ответ, который будет работать как есть для любого числа с n <= 63. Так … почему ты спрашиваешь?
Если вам нужно запрограммировать все самостоятельно, вам нужно знать, как рассчитать двоичное деление и обрабатывать очень большие числа. Если вам не нужно все программировать, найдите библиотеку для больших целых чисел и примените алгоритм, показанный в ссылке:
BigNumber big_number;
big_number = 1;
big_number <<= n;
int result = 0;
while(big_number != 0) {
result += big_number % 10;
big_number /= 10;
}
return result;
Теперь внедрить BigNumber было бы весело. Из алгоритма мы видим, что вам нужно присваивание, сдвиг влево, не равно, по модулю и делению. Класс BigNumber может быть полностью динамическим и выделять буфер целых чисел для подгонки указанного большого числа. Он также может быть записан с фиксированным размером (как шаблон, например). Но если у вас нет времени, возможно, это подойдет:
Другие решения
Вы можете создать вектор цифр, используя некоторые методы, упомянутые в этом другом вопросе (C ++ получить каждую цифру в int), а затем просто перебрать этот вектор и сложить все.
Я реализовал это в JavaScript, как показано ниже, для нахождения суммы цифр 2 ^ 1000: (Проверьте работу CodePen)
function calculate(){
var num = 0, totalDigits = 1,exponent =0,sum=0,i=0,temp=0, carry;
var arr = ['1'];
//Logic to implement how we multiply in daily life using carry forward method
while(exponent<1000){ //Mention the power
carry=0;
for(var j=arr.length-1;j>=0;j--){
temp = arr[j]*2 + carry;
arr[j]= temp%10;
carry = parseInt(temp/10);
if(carry && !j){
arr = [carry].concat(arr); //if the last nth digit multiplication with 2 yields a carry, increase the space!
}
}
exponent++;
}
for(var i=0;i<arr.length;i++){
sum = sum+parseInt(arr[i]);
}
document.getElementById('result').value = sum; //In my HTML code, I am using result textbox with id as 'result'
//console.log(arr);
//console.log(sum);
}