wczytanie n i sprawdzenie czy jest potęga liczby naturalnej.
Czy moze ktos mi wytłumaczyć jakie warunki tu muszą zachodzic?
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.
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.
pomógłbys mi napisac to ? bo nie potrafie za bardzo a internet tez nie pomaga
A Spróbuj taką funkcję:
int is_square(int a){
return (int) sqrt(a) * (int) sqrt(a) == a;
}
Zwraca jeden jak n jest kwadratem.
wszystko działa super, ale ciezki kodzik do zrozumienia ;)
robertos18 napisał(a):
wszystko działa super, ale ciezki kodzik do zrozumienia ;)
Zostawiłem Ci przyjemność odczytania tego kawałka kodu:)
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
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...
z tą potęgą mógłbys mi pomoc ?
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)
tak patrze to fajnie działa program ;) ale np dla 225 wypisuje 0 mimo ze jest 225=15^2 :D
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));
}
?
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
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?
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 :)
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.
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;
}
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.
no faktycznie teraz działa poprawnie, ale jak na razie ten kod to dla mnie kosmos, ale wielkie dziekuje za pomoc :)
Kod głównej funkcji Ci opisałem, a szybkie potęgowanie - Przestudiuj dokładnie artykuł na Wikipedii.
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
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)
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.