Wczytywanie liczb Fibonacciego i błędna odpowiedź – dlaczego?

Cześć mam które brzmi następująco:

W pierwszym wierzy masz podać ilość Testów x<=100
W następnych liniach T liczby Ni<=10^9+7
Dla każdego testu w osobnej linii Ni-ta liczba ciągu fibonacciego modulo 10^9+7

oto mój kod:

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


int fib(int n)
{

	const unsigned int M = 1000000007;
int elementA=0;
int elementB=1;
int wynik=0;

if(n<2)
	return n;

for(int i=2;i<=n;i++){

wynik=(elementA+elementB)%M ;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{
int n;

 int ile;
 cin>>ile;
 if(ile>100)
	 return 100;
 for(int i=0;i<ile;i++){
	cin>>n;

	cout<< fib(n);
	
	
 }
return 0;

}

Na spoju mój problem brzmi "Błąd odpowiedzi". W czym problem i jak go zjeść ?

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


int fib(int n)
{

	
int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;

if(n<2)
	return n;

for(int i=2;i<=n;i++){
	
wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{
int n;

 int ile;
 cin>>ile;
 if(ile>100)
	 return 100;
 for(int i=0;i<ile;i++){
	cin>>n;
	
	cout<< fib(n)<<endl;;
	
}
 
return 0;
 
}

Kod poprawiony i wyrzuca bląd Przekroczono limit czasu .

Jesli(a + b) mod m = c to (a mod m + b mod m) mod m = c. Czyi Masz za Malo mod:). Testuj sobie dla malych liczb I Sprawdzaj wyniki.

Nie wiem czy ciebie dobrze rozumiem mój bląd jest w tym miejscu tak ?

for(int i=2;i<=n;i++){
	
wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

powinno być ?

for(int i=2;i<=n;i++){
	
wynik=(elementA%M+elementB%M)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik

No to teraz kombinuj jak przyspieszy obliczania. Jest kilka sposobów.
Twój obecny algorytm ma złożoność o(n) a da się szybciej .
Jeśli przedstawisz obliczania ciągu Fibonacciego jako rachunek macierzowy, to potem można użyć algorytmu szybkiego potęgowania. i dostaniesz złożoność o(log n).

A jeszcze popraw tak, żeby IO nie było wąskim gardłem:

int main()
{
    int n;
    int ile;

    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> ile;
    for (int i = 0; i < ile; i++) {
        cin >> n;

        cout << fib(n) << '\n';
    }
    return 0;
}

Rzuc okiem na to
https://en.m.wikipedia.org/wiki/Pisano_period

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


int fib(int n)
{

	
int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;

if(n<2)
	return n;

for(int i=2;i<=n;i++){
	
wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{
	
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int ile;
cin >> ile;

if(ile>100)
	 return 100;

for(int i=0;i<ile;i++){
	cin>>n;
	
	cout<< fib(n)<<'\n';
	}
 return 0;
 
}

Teraz kod wygląda w następujący sposób lecz problemem jest przekroczony limit czasu , poprzednio nie miałem zakończenia linii i wyskakiwał mi błąd złego odczytu , teraz z tym przekroczeniem limitu czasu nie wiem co jest grane

Chcę nadmienić iż wolałbym pozostać przy takiej formie kodu niż bawić się z macierzami,jeśli ktoś z was wie z czym zjeść problem przekroczonego czasu . bardzo bym prosił o radę

Kod z użyciem scanfa również wyświetla błąd "przekroczony limit czasu"

#include<iostream> 
#include<cstdlib> 
#include <cmath>
#include <cstdio>
#include<stdio.h>
 
int fib(int n)
{
 
int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;
 
if(n<2)
    return n;
 
for(int i=2;n>=i;i++){
wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;
 
}
 
int main()
{
 

int n;
int ile;
scanf("%i",&ile);
 
if(ile>100)
     return 100;
 
for(int i=0;ile>i;i++){
   scanf("%i",&n);
 
    std::cout<< fib(n)<<'\n';
    }
 return 0;
 
}

Zobacz na moj ostatni post.

lion137 napisał(a):

Zobacz na moj ostatni post.

No patrze patrze i za bardzo nie czaje jakbym mógł go użyć w swoim kodzie .Przecież wynik jest zawsze i tak modulo a teraz mi przekracza czas

Ale, moze Pisano period jest mniejszy niz 10^9, moze ma 10 milionow, a moze milion? Widzisz, ze zlozonosc = Pisano period.

Masz rację na pewno masz rację , ale nie za bardzo wiem jak ugryźć Pisano Period o mój kod i aby końcowy wynik był jak najbardziej pozytywny.

Zapewne jesteś już doświadczonym programistą i dla ciebie taki algorytm co ja mam to śmiech na sali , ale ja w odróżnieniu do ciebie dopiero raczkuję z tym językiem

@lion137: heh, tak się składa, że nie, okres ten jest równy 2*10^9+6.

A odnośnie problemów autora - nie rozumiem co w maciarzach jest do bawienia, ale nie dostaniesz accepta algorytmem liniowym.

Macierzy nie używam bo po prostu nie potrafię , ale gdy mi napisałeś że ten algorytm w formie linowej nie dostanie akcepta to niestety poddaje się ...

To jest macierz dwa na dwa + https://en.wikipedia.org/wiki/Exponentiation_by_squaring, Spróbuj.
https://nbviewer.jupyter.org/github/lion137/blog/blob/master/Matrix_Exponetiation_Fibo.ipynb
https://brilliant.org/wiki/fast-fibonacci-transform/

oto mój najnowszy kod , odpowiedz którą wyrzuca spoj to błędna odpowiedz

#include <iostream>

int get_pisano_period(int m) {
    int  a = 0, b = 1, c = a + b;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1) return i + 1;
    }
}

int get_fibonacci_huge(int n, int m) {
    long long remainder = n % get_pisano_period(m);

    int first = 0;
    int second = 1;

   int res = remainder;
   if(n<2)
    return n;

    for (int i = 2; i <= remainder; i++) {
        res = (first + second) % m;
        first = second;
        second = res;
    }

    return res % m;
}

int main() {

    int n, m;
	int ile;
	scanf("%i",&ile);
	
	if(ile>100)
     return 100;

	for(int i=0;i<ile;i++){
	
	std::cin >> n ;
    std::cout << get_fibonacci_huge(n, 1000000007) << '\n';
	}

    

	return 0;
}

Z tym zmodyfikowanym kodem przekroczono limit czasu

#include <iostream>
 
long get_pisano_period( long m) {
    long long  a = 0, b = 1, c = a + b;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1) return i + 1;
    }
}
 
 long get_fibonacci_huge(long n,  long m) {
    long long remainder = n % get_pisano_period(m);
 
    long  first = 0;
    long  second = 1;
 
   long  res=remainder ;
   
   if(n<2)
    return n;
 
    for (int i = 2; i <= remainder; i++) {
        res = (first + second) % m;
        first = second;
        second = res;
    }
 
    return res % m;
}
 
int main() {
 
    long  n, m;
    int ile;
    scanf("%i",&ile);
 
    if(ile>100)
     return 100;
 
    for(int i=0;i<ile;i++){
 
    std::cin >> n ;
    std::cout << get_fibonacci_huge(n, 1000000007) << '\n';
    }
 
    return 0;
}

Dobra zerżnąłeś kod z stąd: https://medium.com/competitive/huge-fibonacci-number-modulo-m-6b4926a5c836
Ale go zupełnie nie zrozumiałeś i nie masz pojęcia jak go użyć.

W programie pomocniczym weź policz i wypisz get_pisano_period(1000000007) bo to jest stała, którą możesz wpisać w swój kod i możesz użyć w kodzie wysłanym do SPOJ.

Oto mój kod którzy przerobiony na macierze :

#include <iostream>
using namespace std;

int main(){
	cout<<"PODAJ LICZBE:";
	int fibonaci  [1][2]=   {5,8};
	
	int fibonaci2 [2][2]=	{0 ,1,
					        1 ,1};

	int mnozenie[1][2]={{0}};

	for(int i=0;i<1;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
			mnozenie[i][j]=mnozenie[i][j]+fibonaci[i][k]*fibonaci2[k][j];
			cout<<mnozenie[i][j]<<endl;
	}
		for(int i=0;i<1;i++){
				for(int j=0;i<j;j++)
				cout<<mnozenie[i][j]<<endl;
			}
			system("pause");
			
		return 0;
	}
}

Jak teraz wstawić N abyMając daną liczbę N oblicz N-tą liczbę fibonacciego modulo 1000000007 = 10^9 +7

Po kolei. Najpierw napisz funkcję mnożącą dwie macierze. To co masz to jakaś proteza.

Chyba jednak jest dla Ciebie nadzieja, wybierając losowo modyfikację:), przepisałem swoje fast fibo, tak, że liczy modulo n - u mnie to k:

def fibo(n, k):
    if n == 0: return 0

    def matr_power(a, n):
        def matr_mul(M1, M2):
            a11 = (M1[0][0] * M2[0][0] % k + M1[0][1] * M2[1][0] % k) % k
            a12 = (M1[0][0] * M2[0][1] % k + M1[0][1] * M2[1][1] % k) % k

            a21 = (M1[1][0] * M2[0][0] % k + M1[1][1] * M2[1][0] % k) % k
            a22 = (M1[1][0] * M2[0][1] % k + M1[1][1] * M2[1][1] % k) % k
            r = [[a11, a12], [a21, a22]]
            return r

        if n == 1:
            return a
        elif not n % 2 == 0:
            return matr_mul(a, matr_power(matr_mul(a, a), (n - 1) // 2))
        else:
            return matr_power(matr_mul(a, a), n // 2)

    m = [[1, 1], [1, 0]]
    return matr_power(m, n)[1][0]

Teraz tylko przepisać to do c++ i upload.

pokazuje zlywynik

#include <iostream> 

void multiply(int F[2][2], int M[2][2]); 
  
void power(int F[2][2], int n); 
  

int fib(int n) 
{ 
  int F[2][2] = {{1,1},	
				{1,0}}; 
  if (n == 0) 
    return 0; 
  power(F, n-1); 
  return F[0][0]; 
} 
  

void power(int F[2][2], int n) 
{ 
  if( n == 0 || n == 1) 
      return ; 
  int M[2][2] = {{1,1},
				{1,0}}; 
  
  power(F, n/2); 
  multiply(F, F); 
  
  if (n%2 != 0) 
     multiply(F, M); 
} 
  
void multiply(int F[2][2], int M[2][2]) 
{ 
const int m=1000000007;
  int x =  (F[0][0]*M[0][0]%m + F[0][1]*M[1][0]%m)%m;
  int y =  (F[0][0]*M[0][1]%m + F[0][1]*M[1][1]%m)%m; 
  int z =  (F[1][0]*M[0][0]%m + F[1][1]*M[1][0]%m)%m; 
  int w =  (F[1][0]*M[0][1]%m + F[1][1]*M[1][1]%m)%m; 
  
  
  F[0][0] = x; 
  F[0][1] = y; 
  F[1][0] = z; 
  F[1][1] = w; 
} 
  

int main() 
{ 
  int n; 
  int ile;
  std::cin>>ile;
  
 
  for(int i=0;i<ile;i++){
	  std::cin>>n;
	  	
  printf("%d", fib(n)); 

  }
  system("pause");
  return 0; 
} 

Twoja funkcja multiply nic nie robi. Nie zdziwiłbym się, gdyby kompilator optymalizujący całkowicie się jej pozbył.

Błędna odpowiedz. Czy ktoś mi może napisać jak ten kod powinien wyglądac ?

#include <iostream> 
 
void multiply(int F[2][2], int M[2][2]); 
 
void power(int F[2][2], int n); 
 
int fib(int n) 
{ 
  int F[2][2] = {{1,1}, 
                {1,0}}; 
  if (n == 0) 
    return 0; 
  power(F, n-1); 
  return F[0][0]; 
} 
 
void power(int F[2][2], int n) 
{ 
  if( n == 0 || n == 1) 
      return ; 
  int M[2][2] = {{1,1},
                {1,0}}; 
 
  power(F, n/2); 
  multiply(F, F); 
 
  if (n%2 != 0) 
     multiply(F, M); 
} 
 
void multiply(int F[2][2], int M[2][2]) 

{ 
const int m=1000000007;
int mnozenie[2][2]={{0}};
for(int i=0;i<1;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++)
            mnozenie[i][j](mnozenie[i][j]+F[i][k]*M[k][j)%m)%m;
            cout<<mnozenie[i][j]<<endl;
    }
        for(int i=0;i<1;i++){
                for(int j=0;i<j;j++)
                cout<<mnozenie[i][j]<<endl;
            }
 
int main() 
{ 
  int n; 
  int ile;
  std::cin>>ile;
 
  for(int i=0;i<ile;i++){
      std::cin>>n;
 
  printf("%d", fib(n)); 
 
  }
  system("pause");
  return 0; 
} 

power(5, 0) powinno wyjść 5 czy 1? Edit - to nie ma wpływu na wyniki.
na dodatek klamry się nie zgadzają: http://format.krzaq.cc/

Spróbuj takie dane wejściowe:

3
2
4
8

I porównaj swój wynik z prawidłowym

Widzę jeszcze jeden bug 1000000006^2 mieści się w int czy nie?

MarekR22 napisał(a):

power(5, 0) powinno wyjść 5 czy 1?
na dodatek klamry się nie zgadzają: http://format.krzaq.cc/

Spróbuj takie dane wejsciowe:

3
2
4
8

I porównaj swój wynik z prawidłowym

Widzę jeszcze jeden bug 1000000006^2 mieści się w int czy nie?

Sorry że tak dręczę tymi pytaniami , ale czy mógłbyś mój kod pokazać w takiej dobrej formie , masz wiedzę i proszę cię abyś mój kod został ukazany w prawidłowym wykonaniu. Łatwiej jest analizować dobry kod niż utwierdzać się w przekonaniu że niedobre jest dobre. Jeszcze raz dzięki za chęci.

Po po uruchomieniu tego kodu widać podstawowe problemy.
Użycie odpowiedniego typu naprawia kod.

Stąd moje pytanie , czy mając mój kod który ci wysłałem kilka linijek wcześniej możesz go przerobić na działający kod ? , teraz piszę to wszystko na telefonie i nie mam możliwości sprawdzenia czy to wszystko działa poprawnie. Za pomoc z góry dziękuję.

Mogę i to zrobiłem, ale że dałem wystarczająco wskazówek co zrobić to nie widzę potrzeby, żeby pokazać efekt.
Jako, że podejrzewam, iż nie jesteś innym wcieleniem @Cisi204 (który się napracował, by zrobić to samemu z naszą pomocą), to nie widzę powodu by pokazać poprawki.