Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

Точная P-ая степень - C++

10.08.2011, 19:05. Просмотров 2084. Ответов 41
Метки нет (Все метки)

Точная P-ая степень
Число x является точным квадратом, если для некотого целого b, x = b2. Аналогично x является точным кубом, если для некоторого целого b, x = b3. Далее будем утверждать, что x является точной p-ой степенью, если существует такое целое b, что x = bp. По заданному целому x необходимо найти наибольшее p, для которого x является точной p-ой степенью.

Технические условия
Входные данные

Содержит одно число - 32 битовое целое знаковое x, |x| > 1.

Выходные данные

Вывести наибольшее p, для которого x является точной p-ой степенью.

Лимит времени: 1 секунда
Баллы за пройденный тест: 5
Сложность: 25%

Пример
Пример входных данных
Sample 1
17

Sample 2
1073741824 Пример выходных данных
Sample 1
1

Sample 2
30

Вот моя реализация:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cmath>
#define epsilon 1e-3
using namespace std;
 
int main()
{
int i,x,t,n;
double p,k,u;
bool minus=false;
cin >> x;
if (x<0) minus=true;
x=fabs(x);
p=log(x);
n=sqrt(x)+1;
for (i=2; i<=n; i++)
{
if (x%i==0)
{
 k=log(i);
 u=p/k; t=u+epsilon;
 if (u>=t-epsilon && u<=t+epsilon) 
  {
    if (minus) 
    {
     if (t%2==1) { cout << t << endl; return 0; }
    }
   else { cout << t << endl; return 0; }
  } 
}
}
cout << 1 << endl;
return 0;
}
Не проходит 1 тест. Кто может помочь?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2011, 19:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Точная P-ая степень (C++):

Точная степень двойки - C++
Само задание: Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае. ...

Вычислить 10-ю степень двойки сложением, умножением и просто возведением в степень. - C++
Написать код на С++ или С# или на Java Вычислить 10-ю степень двойки 1 - сложением, умножением и просто возведением в степень.

Различные варианты инициализации указателя - в чём точная разница между ними? - C++
Немного непонятен один момент. Есть некий класс Statement (конструктор используется по умолчанию). Вот четыре различных записи...

Написать программу с функцией, вычисляющей целую степень дробного числа. Учесть,что степень может быть положительной, отрицательной, нулевой - C++
Написать программу с функцией, вычисляющей целую степень дробного числа. Учесть,что степень может быть положительной, отрицательной,...

Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача - C++
У покупателя есть n монет достоинством H(1),...,H(n). У продавца есть m монета достоинством B(1),...,B(1). Может ли купить покупатель вещь...

Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++. - C++
Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++.

41
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 20:40 #2
Странный у вас алгоритм какой-то... Все проще, красивее и элегантнее на самом деле. Разложите исходное число на простые множители: x=p1^{k1}...pn^{kn}, где p1<...<pn - простые числа, k1,...,kn - их степени. Тогда ответ на вашу задачу - минимальное значение из чисел k1,...,kn. А ваши логарифмы все портят, точность теряется и многое другое.

Добавлено через 26 минут
Вот функция, вычисляющая наибольшую точную степень числа x


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <limits.h>
 
long Deg(unsigned long x)
{
   long min, i = 2, j, k;
   if (x == 0 || x == 1)
      return -1;
   min = INT_MAX;
   while (x % i != 0)
       i++;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
      while (x % i != 0)
          i++;
      if (i == j)
         k++;
      else
      {
          if (k < min)
             min = k;
          k = 1;
          j = i;
      }
      x /= i;
   }
   if (k < min)
      min = k;
   return min;
}
Добавлено через 10 минут
Но задачка красивая

Добавлено через 19 минут
Да, и чтобы отрицательные числа тоже корректно обрабатывались, надо кое-что учесть, вот вариант для любых 32-битных целых чисел со знаком и без.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<limits.h>
#include<math.h>
 
long Deg(long y)
{
   long x, min, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
   min = INT_MAX;
   while (x % i != 0)
       i++;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
      while (x % i != 0)
          i++;
      if (i == j)
         k++;
      else
      {
          if (k < min)
             min = k;
          k = 1;
          j = i;
      }
      x /= i;
   }
   if (k < min)
      min = k;
   if (!(min & 1) && y < 0)
      return 1;
   else
      return min;
}
0
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
11.08.2011, 01:54 #3
Цитата Сообщение от Olga_ Посмотреть сообщение
Тогда ответ на вашу задачу - минимальное значение из чисел k1,...,kn.
Не минимальное, а НОД всех чисел последовательности "k" .
1
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 08:21 #4
Цитата Сообщение от Overmind024 Посмотреть сообщение
Не минимальное, а НОД всех чисел последовательности "k" .
Да, точно, вы абсолютно правы, спасибо, это я частный случай значит рассматривала.

Добавлено через 12 минут
Тогда алгоритм примет такой вид:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
unsigned long Nod(unsigned long n, unsigned long m)
{
    while (n != 0 && m != 0)
        if (n >= m)
           n %= m;
        else
           m %= n;
    if (m == 0) return n;
    else return m;
}
 
long Deg(long y)
{
   long x, nod, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
   while (x % i != 0)
       i++;
   x /= i;
   j = i;
   nod = 0;
   k = 1;
   while (x != 1)
   {
      while (x % i != 0)
          i++;
      if (i == j)
         k++;
      else
      {
          nod = Nod(nod, k);
          k = 1;
          j = i;
      }
      x /= i;
   }
   nod = Nod(nod, k);
   if (!(nod & 1) && y < 0)
      return 1;
   else
      return nod;
}
 
int main()
{
   printf("%d\n", Deg(1073741824));
   return 0;
}
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 17:12  [ТС] #5
Olga_, вот результаты этой реализации:
1. Засчитано
2. Засчитано
3. Засчитано
4. Засчитано
5. Засчитано
6. Засчитано
7. Засчитано
8. Исчерпан лимит времени
9. Засчитано
10. Засчитано
11. Засчитано
12. Неверный ответ
13. Засчитано
14. Неверный ответ
15. Засчитано
16. Засчитано
17. Засчитано
18. Исчерпан лимит времени
19. Засчитано
20. Засчитано

И что можно сделать?
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 18:27 #6
Цитата Сообщение от AvengerAlive Посмотреть сообщение
И что можно сделать?
Покажите какие числа вы тестируете
0
soon
11.08.2011, 18:32
  #7

Не по теме:

полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...

0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 18:47 #8
Цитата Сообщение от soon Посмотреть сообщение

Не по теме:

полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...

В моем алгоритме все учитывается. Я рассматриваю не модули, а числа со знаком. Например, число -4. Его максимальная степень - единица. Но если система тестирует модули, то ответ будет 2. Так что нужно уточнение задачи.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 18:50 #9
Цитата Сообщение от Olga_ Посмотреть сообщение
Не по теме:
полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...
e-olimp.com - по формату задачи видно ))
0
soon
2542 / 1307 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
11.08.2011, 18:51 #10
Я не про это
Я имел ввиду, что входные данные не показываются пользователю
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 18:52 #11
Olga_, вот http://www.e-olimp.com/problems/1208
0
soon
2542 / 1307 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
11.08.2011, 18:52 #12
Цитата Сообщение от Dani Посмотреть сообщение
e-olimp.com

Не по теме:

о да. Они не дали мне решить задачу №2 через std::string. И через преобразование в char. Мне лень считать количество цифр в числе, и я ушел оттуда.

0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 18:54 #13
Цитата Сообщение от soon Посмотреть сообщение
Я не про это
Я имел ввиду, что входные данные не показываются пользователю
На ацмп такое будет: заплатишь денег - решение и тесты покажут

Добавлено через 1 минуту
Цитата Сообщение от soon Посмотреть сообщение
о да. Они не дали мне решить задачу №2 через std::string. И через преобразование в char. Мне лень считать количество цифр в числе, и я ушел оттуда.
e-olimp мне тоже не понравился... Хоть там можно через файлы задачи решать
0
soon
11.08.2011, 18:54
  #14

Не по теме:

деньги из воздуха

0
Dani
11.08.2011, 18:56     Точная P-ая степень
  #15

Не по теме:

На этом и построен бизнес

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 18:56
Привет! Вот еще темы с ответами:

степень - C++
создать класс для вычисления числа n в степени k, перегрузить оператор * умножения. помогите перегрузить оператор, желательно с...

Степень - C++
Хочу реализовать 2 в 3 степени .. но не могу докумекать как это сделать .. Каким циклом сделать лучше ? 2*2*2=8 ВНИМАНИЕ НЕ...

Возведение в степень - C++
Вывести на экран таблицу степеней &quot;к&quot;, где те изменяются от 1 до 10,к-вещественое число.оперцию возведения вещественого числа в степень...

Степень симметрии - C++
Только прошу сделайте чем по проще. и через cin cout. Степенью симметрии натурального числа назовём количество пар его десятичных...


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

Или воспользуйтесь поиском по форуму:
15
11.08.2011, 18:56
Ответ Создать тему
Опции темы

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