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

Возвести число в 7000 степень - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.59
BOR1K
 Аватар для BOR1K
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
29.04.2010, 14:06     Возвести число в 7000 степень #1
Сегодня был на олимпиаде. Проверка была через contester, в задачи есть место где нужно возвести число в степень.
Никак работать не хотела. Потом увидел тесты. Там 9 возводилась в 7000.
ЭТО ЖЕ КАКОЙ НАДО ТИПА ДАННЫХ ЧТО-БЫ ЭТО СДЕЛАТЬ ЧЕРЕЗ ОБЫЧНЫЙ POW()???
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2010, 14:06     Возвести число в 7000 степень
Посмотрите здесь:

C++ Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++.
C++ Возвести вещественное число A в целую положительную степень k
C++ Как возвести число в степень
Написать программу, которая вычисляет целую степень, в которую необходимо возвести число 2, чтобы получить число, ближайшее меньшее либо равное числу, C++
C++ Возвести число в a степень 7 за 4 операций
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FireNovel
 Аватар для FireNovel
150 / 73 / 8
Регистрация: 09.04.2010
Сообщений: 297
29.04.2010, 14:20     Возвести число в 7000 степень #2
Цитата Сообщение от BOR1K Посмотреть сообщение
ЭТО ЖЕ КАКОЙ НАДО ТИПА ДАННЫХ ЧТО-БЫ ЭТО СДЕЛАТЬ ЧЕРЕЗ ОБЫЧНЫЙ POW()???
А с чего ты взял, что вычисляют через обычный POW()

Как вариант long long long long ... double pow(double, double)
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
29.04.2010, 14:20     Возвести число в 7000 степень #3
используйте массив
KReoN
1 / 1 / 0
Регистрация: 07.06.2009
Сообщений: 11
29.04.2010, 14:37     Возвести число в 7000 степень #4
Цитата Сообщение от FireNovel Посмотреть сообщение
А с чего ты взял, что вычисляют через обычный POW()

Как вариант long long long long ... double pow(double, double)
Дык, это вдеь еще и заранее надо посчитать какого объема массив создавать
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
29.04.2010, 14:52     Возвести число в 7000 степень #5
BOR1K, можете переделать под свои надобности Найти, на сколько нулей оканчивается число N
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16828 / 5249 / 321
Регистрация: 30.03.2009
Сообщений: 14,136
Записей в блоге: 26
29.04.2010, 16:10     Возвести число в 7000 степень #6
Самый простой вариант в техническом исполнении - все числа представлять в виде строк, все операции выполнять в виде строк (столбиком). С делением при таком подходе нужно будет повозиться, но сложение, вычитание и умножение делаются несложно. Понятно, что такой способ более медленный, чем общепринятые способы представления длинных чисел. Но тут по крайней мере понятно и не надо заморачиваться дополнительными проблемами перевода числа в десятичную систему счисления (надо же хоть в каком-то виже напечатать результат)
BOR1K
 Аватар для BOR1K
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
29.04.2010, 17:14  [ТС]     Возвести число в 7000 степень #7
Лимит времени 3000 мс. Лимит памяти 65000Кб.

Добавлено через 25 секунд
Лимит времени 3000 мс. Лимит памяти 65000Кб.
Автор: Фёдор Меньшиков, ВГПУ. Сложность Альфа

Для натуральных чисел a и n вычислить an.

Ввод
В первой строке находятся разделённые пробелом a и n.
Вывод
Выводится одно число - результат без стоящих впереди нулей, стоящих впереди и позади пробелов.
Ограничения
1 ≤ a ≤ 9; 1 ≤ n ≤ 7000.

Ввод 1 Ввод 2
3 20
5 50
Вывод 1 Вывод 2
3486784401
88817841970012523233890533447265625
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16828 / 5249 / 321
Регистрация: 30.03.2009
Сообщений: 14,136
Записей в блоге: 26
29.04.2010, 17:16     Возвести число в 7000 степень #8
Цитата Сообщение от BOR1K Посмотреть сообщение
Лимит времени 3000 мс
Без знаний частоты процессора говорит мало о чём, но для строкового представления скорее всего в такие лимиты по времени не уложиться. Я так понимаю, что это всё-таки 3 секунды. Хотя фиг знает...
Ivaneo
2 / 2 / 0
Регистрация: 01.08.2009
Сообщений: 16
29.04.2010, 17:39     Возвести число в 7000 степень #9
В задаче с возведением в степень в качестве яйчейки для хранения большого числа можно использовать структуру с полем большой длины. И да, там можно задавать длину полей в байтах
BOR1K
 Аватар для BOR1K
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
29.04.2010, 17:43  [ТС]     Возвести число в 7000 степень #10
Имхо ничего выдумывать не надо, другие ее решили за 5 минут, причем я тоже, но других она прошла тесты, вроде как они не си писали, но блин, не может такого быть((
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
29.04.2010, 17:47     Возвести число в 7000 степень #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Почему же не уложиться? Конечно, способ "в лоб" с тупым накручиванием цикла типа for(int i = 0; i < 7000; ++i) ... может и не уложиться - на это и расчет. А если вспомнить школьную алгебру и посчитать как (((9 ^ 7) ^ 10) ^ 10) ^ 10 (здесь ^ - возведение в степень), то получится уже существенно быстрее.
А если взять алгоритм быстрого возведения в степень, то там потребуется всего 18 умножений - это уже вполне приемлемо за указанное время. У меня, например, по алгоритму быстрого возведения в степень, на PIV 3 ГГц эта самая 9^7000 считается всего за 31 мс - почти в сто раз быстрее, чем требуется в тесте :-)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2010, 17:48     Возвести число в 7000 степень
Еще ссылки по теме:

C++ Возвести число в 10 степень, используя только четыре операции умножения
Возвести число в (7) семизначную степень C++
C++ Длинная арифметика - возвести число в большую степень

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16828 / 5249 / 321
Регистрация: 30.03.2009
Сообщений: 14,136
Записей в блоге: 26
29.04.2010, 17:48     Возвести число в 7000 степень #12
CheshireCat, во! Вот были какие-то подозрения, что копать надо в этом направлении, но что-то не додумался
Yandex
Объявления
29.04.2010, 17:48     Возвести число в 7000 степень
Ответ Создать тему
Опции темы

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