Prostsze rozwiązanie zadania dotyczącego ciągu rekurencyjnego
Ostatnio zmodyfikowano 2017-05-12 14:59
rudykot Temat założony przez niniejszego użytkownika |
Prostsze rozwiązanie zadania dotyczącego ciągu rekurencyjnego » 2017-05-10 21:34:03 Poszukuję prostszego rozwiązania zadania o treści:Oblicz n-ty wyraz następującego ciągu:a 1 = A a 2*k = B*a k a 2*k + 1 = a 1 + a 2*kWejścieNa wejściu podane są trzy liczby całkowite A, B i n. Możesz założyć, że wynik zmieści się w zakresie typu int. WyjścieZwróć n-ty element ciągu. PrzykładDla danych wejściowych 2 3 3 poprawną odpowiedzią jest 8 Dla danych wejściowych 5 7 49 poprawną odpowiedzią jest 96045 Moje rozwiązanie:#include <iostream>
using namespace std;
int main()
{
int n, A, B, k;
cin >> A;
cin >> B;
cin >> n;
int tab[ n ];
fill_n( tab, n, 0 );
for( int i = 1; i <= n; i++ )
{
tab[ 1 ] = A;
if( i % 2 == 0 )
k = tab[ i / 2 ] * B;
if( i % 2 > 0 )
k = tab[ i - 1 ] + A;
tab[ i ] = k;
}
cout << tab[ n ];
return 0;
}
|
|
pekfos |
» 2017-05-10 21:57:55 Twoje rozwiązanie jest błędne, źle używasz i tworzysz tablice. Ten problem nawet nie wymaga tablicy i wystarczy prosta pętla. Prościej i szybciej, bo o złożoności logarytmicznej od n, a nie liniowej. |
|
rudykot Temat założony przez niniejszego użytkownika |
» 2017-05-11 20:59:20 Proszę o podpowiedź, ponieważ nie potrafię odnaleźć zależności by wykorzystać ją w pętli. Być może rozwiązanie jest oczywiste jednak nie widzę go zupełnie. |
|
pekfos |
» 2017-05-11 21:09:19 Lepiej to widać po nieco innym zapisaniu ciągu:
a1 = A
a2k = B * ak
a2k+1 = A + B * ak
Dziel k całkowicie przez 2 aż do osiągnięcia wartości 1. Jeśli k jest w jakimś momencie nieparzyste, do dodaj do wyniku A*Bx.
|
|
rudykot Temat założony przez niniejszego użytkownika |
» 2017-05-12 14:59:32 Dziękuję bardzo, rozpisałem 20 kolejnych wyrazów ciągu i każdy z nich sprowadziłem do sumy iloczynów A*(B^x). Faktycznie rozwiązanie było oczywiste, ale go nie widziałem. #include <iostream>
#include <math.h>
using namespace std;
int main()
{
int A, B, n, w = 0, x = 0;
cin >> A;
cin >> B;
cin >> n;
do {
if( n % 2 > 0 )
w = w + A * pow( B, x );
x = x + 1;
n = n / 2;
} while( n >= 1 );
cout << w;
return 0;
}
Zamykam |
|
| « 1 » |