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

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

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

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

29.04.2010, 14:06. Просмотров 3754. Ответов 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++
Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++.

Если введенное число отрицательное и четное, то возвести его в 3 степень, иначе возвести в квадрат - C++
Ввести целое число В. Если В отрицательное и четное, то возвести его в 3 степень, иначе возвести в квадрат

Возвести число в степень - C++
Дано натуральное n. Написать программу вычисления a^n("а" в степени n)

Как возвести число в степень - C++
Как возвести число в степень ???

Возвести число в a степень 7 за 4 операций - C++
Нужно использовать только операцию умножения #include <iostream> using namespace std; int main() { double a,b; cin >>...

Возвести число в (7) семизначную степень - C++
Подскажите пожалуйста, как можно реализовать данную функцию? К примеру необходимо число 2 возвести в 1234567 степень. Проблема заключается...

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

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

Как вариант long long long long ... double pow(double, double)
Дык, это вдеь еще и заранее надо посчитать какого объема массив создавать
M128K145
Эксперт С++
8286 / 3505 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
29.04.2010, 14:52 #5
BOR1K, можете переделать под свои надобности Найти, на сколько нулей оканчивается число N
Evg
Эксперт CАвтор FAQ
17625 / 5849 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
29.04.2010, 16:10 #6
Самый простой вариант в техническом исполнении - все числа представлять в виде строк, все операции выполнять в виде строк (столбиком). С делением при таком подходе нужно будет повозиться, но сложение, вычитание и умножение делаются несложно. Понятно, что такой способ более медленный, чем общепринятые способы представления длинных чисел. Но тут по крайней мере понятно и не надо заморачиваться дополнительными проблемами перевода числа в десятичную систему счисления (надо же хоть в каком-то виже напечатать результат)
BOR1K
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
29.04.2010, 17:14  [ТС] #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
17625 / 5849 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
29.04.2010, 17:16 #8
Цитата Сообщение от BOR1K Посмотреть сообщение
Лимит времени 3000 мс
Без знаний частоты процессора говорит мало о чём, но для строкового представления скорее всего в такие лимиты по времени не уложиться. Я так понимаю, что это всё-таки 3 секунды. Хотя фиг знает...
Ivaneo
2 / 2 / 0
Регистрация: 01.08.2009
Сообщений: 16
29.04.2010, 17:39 #9
В задаче с возведением в степень в качестве яйчейки для хранения большого числа можно использовать структуру с полем большой длины. И да, там можно задавать длину полей в байтах
BOR1K
14 / 14 / 4
Регистрация: 19.09.2009
Сообщений: 289
29.04.2010, 17:43  [ТС] #10
Имхо ничего выдумывать не надо, другие ее решили за 5 минут, причем я тоже, но других она прошла тесты, вроде как они не си писали, но блин, не может такого быть((
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,368
29.04.2010, 17:47 #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Почему же не уложиться? Конечно, способ "в лоб" с тупым накручиванием цикла типа for(int i = 0; i < 7000; ++i) ... может и не уложиться - на это и расчет. А если вспомнить школьную алгебру и посчитать как (((9 ^ 7) ^ 10) ^ 10) ^ 10 (здесь ^ - возведение в степень), то получится уже существенно быстрее.
А если взять алгоритм быстрого возведения в степень, то там потребуется всего 18 умножений - это уже вполне приемлемо за указанное время. У меня, например, по алгоритму быстрого возведения в степень, на PIV 3 ГГц эта самая 9^7000 считается всего за 31 мс - почти в сто раз быстрее, чем требуется в тесте :-)
Evg
Эксперт CАвтор FAQ
17625 / 5849 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
29.04.2010, 17:48 #12
CheshireCat, во! Вот были какие-то подозрения, что копать надо в этом направлении, но что-то не додумался
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.04.2010, 17:48
Привет! Вот еще темы с ответами:

Возвести число в степень(дробную) - C++
В соседней теме помог сделать возведение в целочисленную степень и вот стало интересно, но что-то не могу придумать как сделать возведение...

Asm вставка в С++ возвести число в степень - C++
Возвести число А в степень n (на Assemblerе в С++)

Возвести натуральное число в натуральную степень - C++
Напишите программу, которая вводит натуральные числа A и N и вычисляет A N . По теме циклы ! Входные данные Входная строка содержит...

Вещественное число возвести в целую положительную степень n - C++
вычислить an(n&gt;0). входные данные: а-вещественное число которую надо возвести в целую положительную степень n выходные...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.04.2010, 17:48
Ответ Создать тему
Опции темы

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