Сколько раз мне нужно добавить 2, чтобы получить значение, эквивалентное 2, поднятое до 1000

Question

Я пытаюсь решить Project Euler Prob 16. Я планирую взять двумерный массив для хранения вычислений и сохранения результатов. Чтобы вычислить 2, поднял до 3, мне нужно добавить 2, 4 раза Чтобы вычислить 2, поднял до 4, мне нужно добавить 2, 8 раз Точно так же, сколько раз мне нужно будет добавить 2 к результату, чтобы поднять 2 до 1000? Какая структура данных будет лучше всего подходить для этого (предпочтительно в C ++)? И какой будет хороший алгоритм для решения этой проблемы в C ++?

Answer 1

Если я вас правильно понимаю, вы спрашиваете, какую структуру данных вы должны использовать для хранения цифр целочисленного значения результата 2 ¹⁰⁰⁰ . Вместо того, чтобы изобретать велосипед, я бы рекомендовал использовать что-то вроде класса Java BigInteger , который будет содержать произвольно большие числа.

Answer 2

Решение точно такой же проблемы было показано ранее здесь . Количество десятичных цифр в 2 ¹⁰⁰⁰ равно ceil((1000 + 1) * log10(2)) = 302. Для завершения строки потребуется еще один символ, '\0'. * log10(2) = * 0.3 может быть аппроксимировано с / 3 = * 0.3(3).