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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.59
BOR1K
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
#1

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

29.04.2010, 14:06. Просмотров 3676. Ответов 11
Метки нет (Все метки)

Сегодня был на олимпиаде. Проверка была через 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++ Как возвести число в степень
Возвести число в степень C++
C++ Возвести число в a степень 7 за 4 операций
Возвести число в (7) семизначную степень C++
C++ Длинная арифметика - возвести число в большую степень
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
666 / 528 / 45
Регистрация: 05.03.2010
Сообщений: 1,271
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
Эксперт С++
8282 / 3501 / 143
Регистрация: 03.07.2009
Сообщений: 10,707
29.04.2010, 14:52     Возвести число в 7000 степень #5
BOR1K, можете переделать под свои надобности Найти, на сколько нулей оканчивается число N
Evg
Эксперт CАвтор FAQ
17409 / 5647 / 354
Регистрация: 30.03.2009
Сообщений: 15,451
Записей в блоге: 26
29.04.2010, 16:10     Возвести число в 7000 степень #6
Самый простой вариант в техническом исполнении - все числа представлять в виде строк, все операции выполнять в виде строк (столбиком). С делением при таком подходе нужно будет повозиться, но сложение, вычитание и умножение делаются несложно. Понятно, что такой способ более медленный, чем общепринятые способы представления длинных чисел. Но тут по крайней мере понятно и не надо заморачиваться дополнительными проблемами перевода числа в десятичную систему счисления (надо же хоть в каком-то виже напечатать результат)
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
Эксперт CАвтор FAQ
17409 / 5647 / 354
Регистрация: 30.03.2009
Сообщений: 15,451
Записей в блоге: 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
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
29.04.2010, 17:43  [ТС]     Возвести число в 7000 степень #10
Имхо ничего выдумывать не надо, другие ее решили за 5 минут, причем я тоже, но других она прошла тесты, вроде как они не си писали, но блин, не может такого быть((
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,345
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++ Вещественное число возвести в целую положительную степень n
Если введенное число отрицательное и четное, то возвести его в 3 степень, иначе возвести в квадрат C++
Возвести натуральное число в натуральную степень C++
C++ Возвести число в степень(дробную)
Asm вставка в С++ возвести число в степень C++

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru