0 / 0 / 0
Регистрация: 05.05.2014
Сообщений: 92
1

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

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

Помогите написать программу используя while или do...while. :
Составить программу для определения, является ли натуральное число к степенью некоторого числа.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.12.2014, 05:19
Ответы с готовыми решениями:

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

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

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

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

21
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
Модератор
Эксперт С++
12451 / 10014 / 6026
Регистрация: 18.12.2011
Сообщений: 26,810
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
75 / 75 / 97
Регистрация: 21.12.2014
Сообщений: 185
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
Эксперт по математике/физикеЭксперт С++
1995 / 1325 / 379
Регистрация: 16.05.2013
Сообщений: 3,430
Записей в блоге: 6
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
Guardian of Asgaard
377 / 319 / 197
Регистрация: 11.11.2013
Сообщений: 1,046
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
26969 / 16844 / 3705
Регистрация: 24.12.2010
Сообщений: 37,815
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
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
26969 / 16844 / 3705
Регистрация: 24.12.2010
Сообщений: 37,815
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
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
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
30.12.2014, 13:53 11
C++ (Qt)
1
cout << "YES " << k << " == " << k << "^1" << endl;
2
Диссидент
Эксперт C
26969 / 16844 / 3705
Регистрация: 24.12.2010
Сообщений: 37,815
30.12.2014, 13:57 12
Цитата Сообщение от Fallenworld Посмотреть сообщение
Нечистый брутфорс с оптимизацией по корню
ИМХО, наши коды по эффективности практически совпадают. Просто ты меняешь some_number сверху вниз, а я снизу вверх. Я умножаю, а ты делишь.

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

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

Не по теме:

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

0
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
30.12.2014, 13:59 13
Байт, а да вижу, у тебя закончится цикл при j=2, i тоже до корня проверяется. Так что совпадают совсем.
0
Диссидент
Эксперт C
26969 / 16844 / 3705
Регистрация: 24.12.2010
Сообщений: 37,815
30.12.2014, 14:38 14
Цитата Сообщение от Fallenworld Посмотреть сообщение
брутфорс
а вот подход Ilot очень даже интересный. Детально не разглядывал, но идея понятна. И эффективность на порядки выше. Но код, естественно, посложней.
0
0 / 0 / 0
Регистрация: 05.05.2014
Сообщений: 92
30.12.2014, 14:39  [ТС] 15
Огромное спасибо!!!
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
30.12.2014, 20:30 16
Хорошая задачка. Вижу лаконичный вариант решения, поэтому продублирую тему в другом разделе
0
1404 / 646 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
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
Эксперт по математике/физикеЭксперт С++
1995 / 1325 / 379
Регистрация: 16.05.2013
Сообщений: 3,430
Записей в блоге: 6
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
1404 / 646 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
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
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
07.01.2015, 01:55 20
Решая целочисленные задачи через плавающие типы, хорошо бы сразу оговаривать границы и диапазоны применимости метода. А то ведь и за ull числа бывают.
ЗЫ насколько я помню эту задачу (продублировал тему в другом разделе), я решил через факторизацию, имхо неплохо, но конечно факторизация даже через решето Эратосфена занимает время на больших числах.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.01.2015, 01:55
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru