Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.50/10: Рейтинг темы: голосов - 10, средняя оценка - 4.50
sasha19
0 / 0 / 0
Регистрация: 05.05.2014
Сообщений: 92
#1

Определить, является ли натуральное число степенью другого числа

30.12.2014, 05:19. Просмотров 1873. Ответов 21
Метки нет (Все метки)

Помогите написать программу используя while или do...while. :
Составить программу для определения, является ли натуральное число к степенью некоторого числа.

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.12.2014, 05:19
Ответы с готовыми решениями:

Определить, является ли натуральное число k степенью числа
2. Составить программу для определения, является ли натуральное число k...

Является ли число степенью другого числа
Нужна функция которая проверяет, является ли число степенью какого либо другого...

Дано натуральное число n. Определите, является ли оно степенью числа 2, и если является, то выведите значение этой степени
Дано натуральное число n. Определите, является ли оно степенью числа 2, и если...

Определить, является ли введённое натуральное число целой степенью тройки
Определить, является ли введённое натуральное число целой степенью числа 3

Помогите, ГОС экзамен! Является ли число степенью другого числа
Нужно написать программу определения является ли натуральное число степенью...

21
biolog41
1 / 1 / 3
Регистрация: 10.12.2014
Сообщений: 26
30.12.2014, 11:46 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
int main() {
int n;
cin>>n;
while (n>2) {  n=n/3;}
if (n==1) {cout<<"Da";} else    
cout<<"Net";
getch();
return 0;
}
0
zss
Модератор
Эксперт С++
6985 / 6547 / 4151
Регистрация: 18.12.2011
Сообщений: 17,277
Завершенные тесты: 1
30.12.2014, 12:07 #3
C++
1
2
3
4
5
int x=(int)sqrt((double)n);
if(x*x==n)
   cout<<"Yes";
else    
   cout<<"No";
Если надо через while:
C++
1
2
3
4
5
6
7
int i=2;
while(i*i<n)
     i++;
if(i*i==n)
   cout<<"Yes";
else    
   cout<<"No";

biolog41, На каком примере Вы тестили свой алгоритм.
Возьмем n=10.
10/3=3
3/3=1
Ответ - да.
0
ir24
74 / 74 / 97
Регистрация: 21.12.2014
Сообщений: 185
Завершенные тесты: 1
30.12.2014, 12:59 #4
Только с циклом for получилось.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <math.h>
 
void main()
{
    int n, k, i, x=0;
 
    printf("vvedite chislo ");
    scanf_s("%d", &n);
 
        for (i = 2; (i < n && x!=n); i++)
        for (k = 2; (k < n && x != n); k++)
        {
            x = pow(i, k);
            if (x == n) printf("true");  }
 
        if (x != n) printf("false");
    _getch();
}
0
Ilot
Эксперт С++
1828 / 1186 / 342
Регистрация: 16.05.2013
Сообщений: 3,127
Записей в блоге: 5
Завершенные тесты: 1
30.12.2014, 13:00 #5
zss, не факт, что речь идет о второй степени. Вот простенький пример как разложить число на множители. Если число одинаковых множителей кратно, то очевидно перед нами некоторая степень некоторого числа:
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
#include <cstdlib>
#include <iostream>
#include <set>
int main() {
    long int n;
    std::multiset<int> coll;
    std::cout << "Input N: "; std::cin >> n;
    while (n > 1) {
        for(long int i = 2; i <= n; ++i) {
            ldiv_t dv = std::div(n,i);
            if(dv.rem == 0) {
                n = dv.quot;
                coll.insert(i);
                break;
            }
        }
    }
    for(const auto& x: coll)
        std::cout << x << ' ';
    std::cout << std::endl;
 
    if(coll.size() & 1) {
        long int sum = 0;
        long int count = coll.size();
        for(const auto& x: coll)
            sum += x;
        if(std::div(sum, count).rem == 0)
            std::cout << "Number is pow.\n";
        else
            std::cout << "Number not is pow.\n";
 
    }
    else {
        long mask = 0;
        for(const auto& x: coll)
            mask ^= x;
        if(mask == 0)
            std::cout << "Number is pow.\n";
        else
            std::cout << "Number not is pow.\n";
    }
    return 0;
}
К сожалению не нашел простого способа проверить нечетную степень. Тут надо поразмыслить....
Такой вариант вроде работает, но я в нем не уверен.
1
Boleon
Guardian of Asgaard
373 / 316 / 197
Регистрация: 11.11.2013
Сообщений: 1,046
Завершенные тесты: 1
30.12.2014, 13:24 #6
с for'ом:
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
#include <iostream>
 
using namespace std;
 
bool check(int value) {
    if ( value == 1 ) {
        return true;
    }
    
    for ( int i = 2; i*i <= value; i++ ) {
        for ( int degree = 1; degree <= value; ) {
            degree *= i;
            if ( degree == value ) {
                return true;
            }
        }
    }
    return false;
}
 
int main() {
    int number;
    
    cin >> number;
    
    check(number) ? cout << "Yes" : cout << "No";
    
    return 0;
}
2
Байт
Эксперт C
17839 / 11866 / 2467
Регистрация: 24.12.2010
Сообщений: 23,849
30.12.2014, 13:36 #7
Чистый брут-форс
C++
1
2
3
4
5
6
7
8
if (n==1) printf("1=1^2");
else {
  for(i=2; ; i++) {
     for(p=i*i, j=2; p<n; p*=i, j++) ;
     if (p==n) printf("%d^%d=%d", i, j, n);
     else if (j<3) break;
  }
}
0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
30.12.2014, 13:39 #8
C++
1
2
3
4
5
6
7
8
int k, some_number, temp;
cin>>k;
some_number=sqrt(k);
do{
temp=k;
while(!temp%some_number) temp/=some_number;
if(temp==1) cout<<k<<" is power of "<<some_number;
}while(--some_number);
Нечистый брутфорс с оптимизацией по корню))
1
Байт
Эксперт C
17839 / 11866 / 2467
Регистрация: 24.12.2010
Сообщений: 23,849
30.12.2014, 13:48 #9
Похоже на код Boleon. Но у него поаккуратнее оформлено.
И еще я забыл, что нужно использывать while
C++
1
2
3
4
5
6
i = 2; j=3;
while(j>=3) {
     for(p=i*i, j=2; p<n; p*=i, j++) ;
     if (p==n) printf("%d^%d=%d", i, j, n);
     i++;
}
Добавлено через 4 минуты
Fallenworld, есть подозрение, что при some_number==1 произойдет зацикливание. Нет?

Добавлено через 1 минуту
Для проверки возьми k=2
1
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
30.12.2014, 13:52 #10
Цитата Сообщение от Байт Посмотреть сообщение
Fallenworld, есть подозрение, что при some_number==1 произойдет зацикливание. Нет?
Добавлено через 1 минуту
Для проверки возьми k=2
угу, у меня везде эта проблема с деталями

C++
1
2
3
4
5
6
7
8
int k, some_number, temp;
cin>>k;
some_number=sqrt(k);
do{
temp=k;
while(!temp%some_number&&some_number!=1) temp/=some_number;
if(temp==1) cout<<k<<" is power of "<<some_number;
}while(--some_number);
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
30.12.2014, 13:53 #11
C++ (Qt)
1
cout << "YES " << k << " == " << k << "^1" << endl;
2
Байт
Эксперт C
17839 / 11866 / 2467
Регистрация: 24.12.2010
Сообщений: 23,849
30.12.2014, 13:57 #12
Цитата Сообщение от Fallenworld Посмотреть сообщение
Нечистый брутфорс с оптимизацией по корню
ИМХО, наши коды по эффективности практически совпадают. Просто ты меняешь some_number сверху вниз, а я снизу вверх. Я умножаю, а ты делишь.

Добавлено через 2 минуты
Цитата Сообщение от SlavaSSU Посмотреть сообщение
cout << "YES " << k << " == " << k << "^1" << endl;
Конечно хорошо, что вы это заметили, но у нас тут такие не очень точные формулировки на каждом шагу. Попривыкли уже. Читаем между строк.

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от Fallenworld Посмотреть сообщение
у меня везде эта проблема с деталями
Вся наша жизнь - детали! (ария программиста):D

0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
30.12.2014, 13:59 #13
Байт, а да вижу, у тебя закончится цикл при j=2, i тоже до корня проверяется. Так что совпадают совсем.
0
Байт
Эксперт C
17839 / 11866 / 2467
Регистрация: 24.12.2010
Сообщений: 23,849
30.12.2014, 14:38 #14
Цитата Сообщение от Fallenworld Посмотреть сообщение
брутфорс
а вот подход Ilot очень даже интересный. Детально не разглядывал, но идея понятна. И эффективность на порядки выше. Но код, естественно, посложней.
0
sasha19
0 / 0 / 0
Регистрация: 05.05.2014
Сообщений: 92
30.12.2014, 14:39  [ТС] #15
Огромное спасибо!!!
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
30.12.2014, 20:30 #16
Хорошая задачка. Вижу лаконичный вариант решения, поэтому продублирую тему в другом разделе
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
30.12.2014, 22:42 #17
Лучший ответ Сообщение было отмечено Ilot как решение

Решение

O(log2(n) ^ 3)
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
#include <iostream>
#include <map>
#include <cmath>
 
typedef unsigned long long ull;
 
 
ull pow(int a, int b)
{
    if(!b)
        return 1;
    if(b & 1)
        return pow(a, b-1) * a;
    ull tmp = pow(a, b >> 1);
    return tmp * tmp;
}
 
 
int main()
{
    int n;
    std::cin >> n;
    bool ans = false;
    int ceil = std::ceil(log(n) / log(2));
    for(int i = 2; i <= ceil; ++i)
    {
        ull l = 1, r = n + 1;
        while(r - l > 1)
        {
            ull m = (l + r) >> 1;
            if(pow(m, i) > n)
                r = m;
            else
                l = m;
        }
        ans |= (pow(l, i) == n) | (pow(r, i) == n);
    }
 
    std::cout << (ans ? "YES" : "NO");
    return 0;
}
(p.s. переполнения не убирал, но и с ними должно в 99% работать)
2
Ilot
Эксперт С++
1828 / 1186 / 342
Регистрация: 16.05.2013
Сообщений: 3,127
Записей в блоге: 5
Завершенные тесты: 1
06.01.2015, 20:01 #18
Dani, навеяно вашими идеями, за константное время:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
typedef unsigned long long ull;
int main()
{
    ull n;
    std::cin >> n;
    for(int i = 2; i <= sizeof(ull); ++i) {
        if(std::pow(std::pow(n, 1.0/i), i) == n) {
            std::cout << "yes\n";
            return 0;
        }
    }
    std::cout << "no\n";
    return 0;
}
1
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
07.01.2015, 01:04 #19
Код крутой получился!
Только не всегда верно работает - примеры чисел, на которых ваша программа работает некорректно: 11, 14, 17, 19, 20...
А вот если так сделать, то получается правильнее
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
typedef unsigned long long ull;
int main()
{
    ull n;
    std::cin >> n;
    for(int i = 2; i <= sizeof(ull); ++i) {
        if(std::pow((int)std::pow(n, 1.0/i), i) == n) {
            std::cout << "yes\n";
            return 0;
        }
    }
    std::cout << "no\n";
    return 0;
}
Но все равно не работает на числах 125, 216, 343, 512...
А если сделать вот так, то все работает лучше (ну как лучше - чисел, на которых моя с вашей программы дают разные результаты не нашел, кроме 1):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cmath>
typedef unsigned long long ull;
 
int round(double x)
{
    return std::floor(x + 0.5); //похоже, что в VS2012 еще нету round
}
 
int main()
{
    ull n;
    std::cin >> n;
    for(int i = 2; i <= sizeof(ull); ++i) {
        if(std::pow(round(std::pow(n, 1.0/i)), i) == n) {
            std::cout << "YES";
            return 0;
        }
    }
    std::cout << "NO";
    return 0;
}
Добавлено через 2 минуты
А, хотя нет - нашло число 2048.

Добавлено через 9 минут
Кстати, по поводу константного времени - в цикле вызывается функция pow, не думаю что она будет работать за константу

Добавлено через 3 минуты
Цитата Сообщение от Dani Посмотреть сообщение
sizeof(ull)
Если я правильно понял, здесь должно было быть sizeof(ull) * 8, т.к. в байте 8 бит
Тогда выглядит вот так (и самое главное - вроде работает!)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cmath>
typedef unsigned long long ull;
 
int round(double x)
{
    return std::floor(x + 0.5); //похоже, что в VS2012 еще нету round
}
 
int main()
{
    ull n;
    std::cin >> n;
    for(int i = 2; i <= 8 * sizeof(ull); ++i) {
        if(std::pow(round(std::pow(n, 1.0/i)), i) == n) {
            std::cout << "YES";
            return 0;
        }
    }
    std::cout << "NO";
    return 0;
}
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
07.01.2015, 01:55 #20
Решая целочисленные задачи через плавающие типы, хорошо бы сразу оговаривать границы и диапазоны применимости метода. А то ведь и за ull числа бывают.
ЗЫ насколько я помню эту задачу (продублировал тему в другом разделе), я решил через факторизацию, имхо неплохо, но конечно факторизация даже через решето Эратосфена занимает время на больших числах.
0
07.01.2015, 01:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2015, 01:55

Функцию которая определяет, является ли натуральное число N степенью числа 5. Перевести с Pascal
Нужно перевести функцию которая определяет, является ли натуральное число N...

While. Определить, является ли натуральное N (вводить с клавиатуры) степенью числа 4 или нет
Помогите пожалуйста 2.2. Цикл с предусловием – while: Определить, является ли...

Определить является ли заданное целое число степенью числа 5
Необходимо составить программу, определяющую, является ли заданное целое число...


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

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

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