[C++] Czy liczba jest potęgą 3

[Ktos_88]

Mam problem z zadaniem. Napisać program sprawdzający, czy dana liczba jest potęgą 3. Nie wiem co mam źle. Proszę o pomoc

Kod: Zaznacz cały

#include<iostream>

#include<math.h>
using namespace std;
int main()
{
    int a,i, wynik=3;
    cout<<"Wpisz liczbe 
";
    cin>>a;
    for(i=0; i<=a; i++)
    {
        wynik=wynik*pow(3,i);
    }
    if(wynik==a)
        cout<<"jest 
";
    else if(a==1)
        cout<<"jest 
";
    else   
        cout<<"nie jest 
";
    
    system("pause");
}

[tiraeth]

Może zacznijmy od rozwiązania matematycznego, ale uwzględniającego ograniczenia języka C++.

Otóż najlepiej jest policzyć logarytm o podstawie 3 z danej liczby, a następnie sprawdzić, czy liczba ta jest całkowita (tudzież: czy jej podłoga i sufit jest równa temu samemu). Oczywiście operujemy na liczbach zmiennoprzecinkowych (rzeczywistych).

Ponieważ nie ma funkcji w C++, która pozwalałaby nam policzyć logarytm o podstawie 3, musimy wykorzystać wzór na iloraz logarytmów o tej samej podstawie (i użyjemy liczby e, jako podstawy).

\(\displaystyle{ \frac{\log_ca}{\log_cb} = \log_ba}\)

Kod: Zaznacz cały

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
  double liczba;

  cout << "Podaj liczbe: ";
  cin >> liczba;

  double logliczba = log(liczba);
  double logpodstawa = log(3);
  double log3liczba = logliczba/logpodstawa;

  if (ceil(log3liczba) == floor(log3liczba))
    cout << "Jest potega 3! 3^" << log3liczba << endl;
  else
    cout << "Nie jest potega 3!" << endl;
}

[Ktos_88]

dzieki, tylko w poleceniu jest napisane, żeby użyć pętli

[miki999]

Kod autorki:

Załóżmy, że podaję liczbę \(\displaystyle{ a=27}\).
W pętli wykonywane jest:
\(\displaystyle{ wynik=3 \cdot 3^1 \\ wynik=9 \cdot 3^2 \\ wynik= 81 \cdot 3^3 \\ ...}\)
I tak jeszcze 25 iteracji. W konsekwencji otrzymujesz jakąś dużą liczbę.
Potem sprawdzasz czy ta liczba jest równa \(\displaystyle{ a}\)- oczywiście nie jest.


Proponuję w pętli sprawdzać, czy podana liczba jest równa \(\displaystyle{ 3^i}\).

[Ktos_88]

Kod: Zaznacz cały

{
    int a,i, wynik=1;
    cout<<"Wpisz liczbe 
";
    cin>>a;
    for(i=0; i<=a; i++)
    {
        wynik=wynik*pow(3,i);
    }
    if(wynik==a)
        cout<<"jest 
";
    else if(a==1)
        cout<<"jest 
";
    else   
        cout<<"nie jest 
";
    
    system("pause");
}

tak też nie działa

[miki999]

Nie widzę zmian w kodzie. Nadal robisz to samo.

[tiraeth]

Kod: Zaznacz cały

int liczba, potega = 1;
cin >> liczba;

if (liczba == potega)
  cout << "Jest! 3^0." << endl;

while (true)
{
  potega = potega * 3;

  if (potega == liczba)
  { // jesli potega rowna to mamy wynik
    cout << "Jest!" << endl;
    break; // wyskakujemy z petli
  }
  else if (potega > liczba)
  { // jesli wieksza, to juz nic nie zrobimy wiecej, wiec nie jest
    cout << "Nie jest!" << endl;
    break; // wyskakujemy z petli
  }
}

[miki999]

Tak na oko to powinno chodzić. Jaki jest rezultat?

edit:
aha, to nie był post autorki tematu

[ksisquare]

funkcję sprawdzającą można zapisać tak:

Kod: Zaznacz cały

int P3(unsigned int n){
	unsigned int j;
	for( j=1; j<=n; j *= 3 )
		if( n == j )
			return 1; 
	return 0; }

Ale...
Czy dla wszystkich n jest poprawna?
j *= 3; mamy tu niejawne \(\displaystyle{ mod\quad 2^{32}}\)
dla \(\displaystyle{ n\le 1\ 431\ 655\ 765}\) sprawa jest czysta, bo \(\displaystyle{ 3\cdot 1431655765 = 2^{32}-1}\)

1. czy istnieje n dla którego funkcja zwróci błędną odpowiedź?
2. czy pętla for(...) może "obrócić się" więcej niż 20 razy?

na Ideone testowanie

Kod: Zaznacz cały

for(i=1; i<130 000 000; i++) 
    if( P3(i) )
        printf("%d ", i);

trwa około 3 sekund,
dodanie if( n%3 != 0 ) return 0; poprawiło czas do 2 sekund
jak można to przyśpieszyć?
napisałem inaczej i przyśpieszyło do 0.48 sekundy