potęga liczby naturalnej

0

wczytanie n i sprawdzenie czy jest potęga liczby naturalnej.
Czy moze ktos mi wytłumaczyć jakie warunki tu muszą zachodzic?

0

No, jak można przeczytać - n musi być możliwe do zapisania w formie a^b, gdzie a, b należą do zbioru liczb naturalnych.
Nie jest to inżynieria rakietowa.

0
n = a^b
a=1..n
b=log(a, n)
log(a, n) = log(n)/log(a)

Po obliczeniu b i zaokrągleniu, jeśli a^b = n to masz szukaną parę liczb.

0

pomógłbys mi napisac to ? bo nie potrafie za bardzo a internet tez nie pomaga

0

A Spróbuj taką funkcję:

int is_square(int a){
	return (int) sqrt(a) * (int) sqrt(a) == a;
}

Zwraca jeden jak n jest kwadratem.

0

wszystko działa super, ale ciezki kodzik do zrozumienia ;)

0
robertos18 napisał(a):

wszystko działa super, ale ciezki kodzik do zrozumienia ;)

Zostawiłem Ci przyjemność odczytania tego kawałka kodu:)

0

choociaz np gdy wpisze liczbe 8 ktora rowna sie 2^3 wyswietla mi 0,a przeciez liczbe 8 moge przedstawic w postaci potegi liczby naturalnej

0
robertos18 napisał(a):

choociaz np gdy wpisze liczbe 8 ktora rowna sie 2^3 wyswietla mi 0,a przeciez liczbe 8 moge przedstawic w postaci potegi liczby naturalnej

Potęgą, a ja zrobiłem kwadratem, ups...

0

z tą potęgą mógłbys mi pomoc ?

0

Jasne, trochę się pospieszyłem, dowolna potęga (przynajmniej naiwna wersja) też nie jest trudna:

int is_power(int a){
	int limit = (int) sqrt(a);
	int out = 0;
	int ind = 2;
	for (int i = 2; i<= limit; i++){
		while (out <= a) {
			out = pow(i, ind);
			if (out == a) return 1;
			ind += 1;
		}
		ind = 2;
		out = 0;
	}
	return 0;
}

Jak widać, ustalamy limit szukania (dalej jak do pierwiastka nie idziemy, oczywiście, to będzie sprawdzenie czy jest kwadratem); potem startujemy z liczbą potęgowaną out i indeksem ind i w pętli for po kolei potęgujemy: 2 do 2, 2 do 3 , i tak dalej aż nie przekroczymy n, w międzyczasie sprawdzając czy nie mamy potęgi (wtedy return 1 i koniec); na końcu petli for resetujemy out i ind, jak petla zakończy działanie dla całego zakresu, zwracamy 0 (to znaczy, że nie znaleźlismy potęgi)

0

tak patrze to fajnie działa program ;) ale np dla 225 wypisuje 0 mimo ze jest 225=15^2 :D

0

U mnie poprawnie zwraca 1 (Compilator g++ 5.4.0), a jakie Masz potęgowanie, bo ja używam algorytmu opartego na tym: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

int square(int x){ return x * x;}
int even(int x) {return x % 2 == 0;}

int sq_exp(int x, unsigned n){
	
	if (n == 0) 
		return 1;
	if (! even(n))
		return x * square((sq_exp(x, (n - 1) / 2)));
	return square(sq_exp(x, n / 2));
}

?

0

w jakim sensie jakie mam potegowanie? ja uzywam code:blocksa, zauwazylem ze dla liczb od 100,121,..... pokazuje 0 dla 144 juz 1 dla wyzszych liczb jest ok, hmm dziwne :D

0
robertos18 napisał(a):

w jakim sensie jakie mam potegowanie? ja uzywam code:blocksa, zauwazylem ze dla liczb od 100,121,..... pokazuje 0 dla 144 juz 1 dla wyzszych liczb jest ok, hmm dziwne :D

W kodzie, powyżej jest: pow(i, ind);. W jaki sposób jest to u Ciebie liczone, jaką funkcję Wołasz?

0

wywołuje cout<<is_power(100);
sprawdziłem na innym kompilatorze i działa poprawnie dziwne to jest dla mnie.. ale dziekuje bardzo za pomoc :)

0
robertos18 napisał(a):

wywołuje cout<<is_power(100);
sprawdziłem na innym kompilatorze i działa poprawnie dziwne to jest dla mnie.. ale dziekuje bardzo za pomoc :)

Nie rozumiemy się, w funkcji, która Ci podałem jest linijka: out = pow(i, ind);, dlaczego ona działa u Ciebie? t ofunkcja z biblioteki cmath, jakaś inna? Spróbuj uzyć sq_exp, którą podałem, i będzie działąć w kazdym kompilatorze.

0

wiesz ja chyba nie rozumiem, moj kod :

#include <math.h>
#include<cmath>
#include <iostream>
using namespace std;

int sq_exp(int a)
{
    int limit = (int) sqrt(a);
    int out = 0;
    int ind = 2;
    for (int i = 2; i<= limit; i++)
    {
        while (out <= a)
        {
            out = pow(i, ind);
            if (out == a)
                return 1;
            ind += 1;
        }
        ind = 2;
        out = 0;
    }
    return 0;
}

int main()
{
    cout<<sq_exp(100);
    return 0;
}

0
robertos18 napisał(a):

wiesz ja chyba nie rozumiem, moj kod :

Widzę, że nie Rozumiesz, out = pow(i, ind), ta linijka ma liczyć i podniesione do potęgi ind. W tym celu wołasz jakąś funkcję pow. Podam Ci w takim razie cały kod:

int square(int x){ return x * x;}
int even(int x) {return x % 2 == 0;}

int sq_exp(int x, unsigned n){
	
	if (n == 0) 
		return 1;
	if (! even(n))
		return x * square((sq_exp(x, (n - 1) / 2)));
	return square(sq_exp(x, n / 2));
}


int is_power(int a){
	int limit = (int) sqrt(a);
	int out = 0;
	int ind = 2;
	for (int i = 2; i<= limit; i++){
		while (out <= a) {
			out = sq_exp(i, ind);
			if (out == a) return 1;
			ind += 1;
		}
		ind = 2;
		out = 0;
	}
	return 0;
}
int main(int argc, char **argv)
{	
	
	cout << is_power(100)<<endl; // -> 1
	cout << is_power(225)<<endl; // -> 1
	cout << is_power(121)<<endl; // -> 1
	cout << is_power(101)<<endl; // -> 0
	
	return 0;
}

Używająć potęgowania w integerach działa poprawnie.

0

no faktycznie teraz działa poprawnie, ale jak na razie ten kod to dla mnie kosmos, ale wielkie dziekuje za pomoc :)

0

Kod głównej funkcji Ci opisałem, a szybkie potęgowanie - Przestudiuj dokładnie artykuł na Wikipedii.

0

Implementacja tego co wyżej napisałem:

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n, a, b, cnt;
	while(cin >> n) {
		cnt = 0;
		for(int a=1; a < n; a++) {
			b = nearbyint(log(n)/log(a));
			if ((int)nearbyint(pow(a, b)) == n) {
				cout << n << " = " << a << " ^ " << b << endl;
				cnt++;
			}
		}
		if (cnt == 0) {
			cout << "For " << n << " there are no powers\n";
		}
	}
	return 0;
}

Dla:

1528
6561
125

Wynik:

For 1528 there are no powers
6561 = 3 ^ 8
6561 = 9 ^ 4
6561 = 81 ^ 2
125 = 5 ^ 3

https://ideone.com/aUSjIO

0

Bardzo ładny kod ;)
nearbyint(log(n)/log(a)); - zaokrągla te logarytmy do czesci całkowitej ??
nie rozumiem tez tego kawałka:
if ((int)nearbyint(pow(a, b)) == n)

0

Tak, niestety zwykly round w C++ nie dziala tak jak moznaby sie tego spodziewac.

A to drugie sprawdza czy po podniesieniu do potegi na pewno mamy wartosc wejsciowa.

1 użytkowników online, w tym zalogowanych: 0, gości: 1