[Mảng 1 Chiều Cơ Bản]. Bài 11. Liệt kê và đếm số Fibonacci

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Java 12.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

28tech.com.vn

Nguồn bài:

28Tech

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng số nguyên A[] gồm N phần tử, hãy liệt kê các số trong mảng là số Fibonacci.

Đầu vào

Dòng đầu tiên là số nguyên dương N
Dòng thứ 2 gồm N số nguyên viết cách nhau một vài khoảng trắng

Giới hạn

1<=N<=10^6
0<=A[i]<=8.10^18

Đầu ra

In ra các số là số Fibonacci trong dãy theo thứ tự xuất hiện. Nếu trong mảng không tồn tại số Fibonacci nào thì in ra "NONE".

Ví dụ :

Input 01

6
1597 25358 7318 5878 0 2634

Output 01

1597 0

Bình luận

Hãy đọc nội quy trước khi bình luận.

snow đã bình luận lúc 6, Tháng 8, 2026, 8:53

Code C full AC cho b nao can :v

#include<stdio.h>
#include<math.h>
long long f[1000];
      void fibo(){
        f[0] = 0;
        f[1] = 1;
        for(int i = 2; i <= 92; i++){
            f[i] = f[i-1] + f[i-2];
          }
      }
      int ktra(long long n){
        for(int i = 0; i <= 92; i++){
          if(f[i] == n) return 1;
          else if(f[i] > n) return 0;
          }
          return 0;
      }
      int main(){
        fibo();
        int n;
        scanf("%d",&n);
        long long a[n];
        for(long long i = 0; i < n; i++){
            scanf("%lld",&a[i]);
          }
          int check = 0;
        for(long long i = 0; i < n; i++){
            if(ktra(a[i])){
             printf("%lld ",a[i]);
             check = 1;
        }
         }
         if(!check) printf("NONE");
    }

-1

Lam_Thang2014 đã bình luận lúc 27, Tháng 7, 2026, 12:41

include <bits/stdc++.h>

include <iomanip>

include <cmath>

include <climits>

define ll long long

using namespace std; ll a[10000011]; ll cnt = 0; ll fi(ll n){ ll f[100]; f[0] = 0, f[1] = 1; for(ll i = 2; i <= 92; i++){ f[i] = f[i - 1] + f[i - 2]; } for(ll i = 0; i <= 92; i++){ if(n == f[i]){ return true; } } return false; } int main(){ ll n; cin >> n; for(ll i = 0; i < n; i++){ cin >> a[i]; } for(ll i = 0; i < n; i++){ if(fi(a[i])){ cout << a[i] << " "; }else cnt++; } if(cnt == n) cout << "NONE"; return 0; }

0

duc093919 đã bình luận lúc 25, Tháng 3, 2026, 18:49

include <stdio.h>

void nhap(long long int b[], int n){ for (int i=0;i<n;i++){ scanf("%lld", &b[i]); } } int main(){ long long a[100]; a[0]=0; a[1]=1; for(int i=2;i<93;i++){ a[i]=a[i-1]+a[i-2]; } int n; long long b[100000]; scanf("%d",&n); if (n<0){printf("error");} nhap(b,n); for (int i = 0;i<n;i++){ for (int j=0;j<93;j++){ if (b[i]==a[j]){ printf("%lld ",b[i]); break; } } } } em bị runtime error 2 test cuối ai giúp với ạ

0
AAAAAAAAAA đã bình luận lúc 4, Tháng 2, 2026, 10:46
include<bits/stdc++.h>

using namespace std;

define ll long long

define endl '\n'

ll a[1000001],f[1001]; map<ll,ll> m; void snt() { f[0]=0; f[1]=f[1]=1; for(ll i=3;i<=100;i++) { f[i]=f[i-1]+f[i-2]; } } int main() { iosbase::syncwith_stdio(false); cin.tie(0);cout.tie(0); ll n,right=0,left=0; cin>>n; snt(); for(ll i=0;i<n;i++) { cin>>a[i]; } ll t=false; for(ll i=0;i<n;i++) { for(ll j=0;j<=100;j++) { if(f[j]==a[i]) { cout<<a[i]<<" "; t=true; break;

} } } if(!t)cout<<"NONE";

}

code full AC(chỉ duy nhất bài này)

-1
anhthuy_ đã bình luận lúc 15, Tháng 11, 2025, 2:25
FULL AC, sinh trước fib[0 -> 92]

include <bits/stdc++.h>

define iosf ios::syncwithstdio(false);cin.tie(nullptr); cout.tie(nullptr);

define ef else if

define el else

using namespace std; using ll = long long;

set<ll> fib = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429,};

int main(){ iosf

int n; cin >> n; for(int i = 0; i < n; i++){ ll num; cin >> num; if (fib.count(num)) { cout << num << " "; } } return 0;

}

0
AAAAAAAAAA đã bình luận lúc 4, Tháng 2, 2026, 10:45
bạn nghĩ nhiều hay là bạn chưa học lưu fibo nhể ?

include<bits/stdc++.h>

using namespace std;

define ll long long

define endl '\n'

ll a[1000001],f[1001]; map<ll,ll> m; void snt() { f[0]=0; f[1]=f[1]=1; for(ll i=3;i<=100;i++) { f[i]=f[i-1]+f[i-2]; } } int main() { iosbase::syncwith_stdio(false); cin.tie(0);cout.tie(0); ll n,right=0,left=0; cin>>n; snt(); for(ll i=0;i<n;i++) { cin>>a[i]; } ll t=false; for(ll i=0;i<n;i++) { for(ll j=0;j<=100;j++) { if(f[j]==a[i]) { cout<<a[i]<<" "; t=true; break;

} } } if(!t)cout<<"NONE";

}

naipret đã bình luận lúc 16, Tháng 9, 2025, 12:54 ← sửa 3 →

Việc gì khó có __int128 lo:>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

istream& operator>>(istream& inp_stream, __int128& val) {
  string str;
  inp_stream >> str;

  val = 0;

  __int128 sign = 1;
  int start_idx = 0;
  if (!str.empty() && str[0] == '-') {
    sign = -1;
    start_idx = 1;
  }

  int loop_limit = static_cast<int>(str.length());
  for (int i = start_idx; i < loop_limit; ++i) {
    if (str[i] < '0' || str[i] > '9') {
      val = 0;
      return inp_stream;
    }
    val = val * 10 + (str[i] - '0');
  }

  val *= sign;
  return inp_stream;
}

ostream& operator<<(ostream& out_stream, const __int128& val) {
  if (val == 0) {
    return out_stream << "0";
  }

  __int128 tmp = val;
  bool is_negative = false;
  if (tmp < 0) {
    is_negative = true;
    tmp = -tmp;
  }

  string str = "";
  while (tmp > 0) {
    str += (tmp % 10) + '0';
    tmp /= 10;
  }

  if (is_negative) {
    str += '-';
  }

  reverse(str.begin(), str.end());
  return out_stream << str;
}

bool IsFibonacci(__int128 val) {
  if (val < 0) return false;
  if (val == 0 || val == 1) return true;

  __int128 first_fi = 0;
  __int128 second_fi = 1;
  __int128 current_fi;
  while (second_fi < val) {
    current_fi = first_fi + second_fi;
    first_fi = second_fi;
    second_fi = current_fi;
  }

  return second_fi == val;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int num;
  cin >> num;

  vector<__int128> vec(num);
  for (__int128& ele : vec) {
    cin >> ele;
  }

  int res_cnt = 0;
  for (__int128 ele : vec) {
    if (IsFibonacci(ele)) {
      cout << ele << ' ';
      res_cnt++;
    }
  }
  if (res_cnt == 0) {
    cout << "NONE";
  }
}

-4

dquan0337 đã bình luận lúc 7, Tháng 9, 2025, 4:03

Code AC !full test ...

include <bits/stdc++.h>

const int nmax = 1e6+5;

using namespace std;

int n, a[nmax];

int main() {

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;

for (int i = 0; i < n; i++) cin >> a[i];


bool kt = false;
for (int i = 0; i < n; i++){
    if (a[i] == a[i - 1] + a[i - 2]|| a[i] == 0){
       cout << a[0] << ' ' << a[i] << ' ';
       kt = true;
    }
}

if (!kt) cout << "NONE";
return 0;

}

-7

nduc1907 đã bình luận lúc 9, Tháng 7, 2025, 15:20

mình bị sai 2 test case cuối mng help mình với

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

4
dungdeptrai đã bình luận lúc 10, Tháng 7, 2025, 3:31
code của bạn vài chỗ không cần thiết và cũng không đúng.

Mảng a bạn chỉ khai báo kích thước 1005 trong khi giới hạn tối đa cần có là 10^6 nên dẫn đến lỗi RE truy cập ngoài mảng

mảng a có kích thước tối đa 10^6 nên khai báo ngoài hàm main. Mảng x lưu các số fibo thì chỉ cần khai báo x[100] là quá đủ vì nhớ không nhầm thì, số fibo cuối cùng trước khi vượt qua kiểu long long là số thứ 92 hay thứ 93 ấy

x[0] = 0 chứ k phải x[0] = 1

Trong cái else, bạn chỉ cần chạy j từ 2-92 nên chỉ cần khai báo kiểu dữ liệu là int thôi

0

nduc1907 đã bình luận lúc 10, Tháng 7, 2025, 3:49

mình sửa lại r camon b

-1
Hwue đã bình luận lúc 24, Tháng 6, 2025, 4:30
def generatefibonacciupto(maxval): fib = [0, 1] while fib[-1] + fib[-2] <= max_val: fib.append(fib[-1] + fib[-2]) return set(fib)

def main(): try: N = int(input()) A = list(map(int, input().split())) if len(A) != N: print("NONE") return

max_a = max(A) fib_set = generate_fibonacci_up_to(max_a) result = [str(x) for x in A if x in fib_set] print(" ".join(result) if result else "NONE") except: print("NONE")

if name == "main": main()

-1
bengokyeuanh99 đã bình luận lúc 8, Tháng 4, 2025, 12:25
import sys

def generatefibonacciup_to(n): fib = [0, 1] while fib[-1] + fib[-2] <= n: fib.append(fib[-1] + fib[-2]) return set(fib)

def main(): try: n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) if len(arr) != n: print("NONE") return

fib_set = generate_fibonacci_up_to(max(arr)) result = [str(x) for x in arr if x in fib_set] print(" ".join(result) if result else "NONE") except: print("NONE")

if name == "main": main()

-1

GodNona đã bình luận lúc 2, Tháng 2, 2025, 6:33

mn giúp e với ạ. E bị wrong answer 5 test ạ

include <bits/stdc++.h>

using namespace std;

define ll long long

ll a[1000006]; set<ll> se;

int main() { iosbase::syncwith_stdio(0); cin.tie(NULL);

int n; cin >> n;
for(int i = 0; i < n; i++)
    cin >> a[i];

ll f1 = 0, f2 = 1;
se.insert(f1);
se.insert(f2);
for(int i = 3; i <= 92; i++)
{
    ll f3 = f1 + f2;
    se.insert(f3);
    f1 = f2;
    f2 = f3;
}

int check = 0;
for(int i = 0; i < n; i++)
{
    if(se.find(a[i]) != se.end())
    {    
        cout << a[i] << " ";
        check = 1;
    }
}
if(check == 0)
    cout << "NONE";


return 0;

}

-1

VDev đã bình luận lúc 18, Tháng 1, 2025, 15:52 ← chỉnh sửa →

FULL AC

#include <bits/stdc++.h>
#include <iomanip>
#include <cmath>
#include <climits>
#define ll long long
using namespace std;
ll a[10000011];
ll cnt = 0;
ll fi(ll n){
    ll f[100];
    f[0] = 0, f[1] = 1;
        for(ll i = 2; i <= 92; i++){
        f[i] = f[i - 1] + f[i - 2];
        }
        for(ll i = 0; i <= 92; i++){
        if(n == f[i]){
            return true;
        }
        }
        return false;
}
int main(){
    ll n;
    cin >> n;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }
    for(ll i = 0; i < n; i++){
            if(fi(a[i])){
                cout << a[i] << " ";
            }else cnt++;
    }
    if(cnt == n) cout << "NONE";
    return 0;
}

0

khiem101701 đã bình luận lúc 3, Tháng 12, 2024, 10:14

include <iostream>

using namespace std; long long fibo[101];

void fibonacci(long long f[]){ f[0] = 0; f[1] = 1; for (int i = 2;i < 101;i++){ f[i] = f[i-1]+f[i-2]; } } int main(){ fibonacci(fibo); int n; cin>>n; long long arr[n]; for (int i = 0; i< n;i++){ cin>>arr[i]; } bool flag = true; for (int i = 0;i < n;i++){ for(int j = 0;j < 101;j++){ if(arr[i] == fibo[j]){ cout<<arr[i]<<" "; flag = false; break; } } } if(flag) cout<<"NONE"; return 0; }

-1

Dungx_2008 đã bình luận lúc 24, Tháng 11, 2024, 10:07

include <bits/stdc++.h>

define N 10000000

define ll long long

using namespace std; ll f[100],a[N],n; bool kt = true; set<ll> se; void fibo() { f[0] = 0; f[1] = 1; se.insert(0); se.insert(1); for(int i=2;i<=92;i++) { f[i] = f[i-1] + f[i-2]; se.insert(f[i]); } } int main() { fibo(); cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) { if(se.find(a[i]) != se.end()) { cout << a[i] << " "; kt = false; } } if(kt) cout << "NONE"; return 0; }

-2

HungDSQ2 đã bình luận lúc 1, Tháng 11, 2024, 9:35

có code k ae

-4

thainguyen2802 đã bình luận lúc 16, Tháng 6, 2024, 10:44

Mình dùng mảng số fibo bị tle 2 test cuối, ai có cách khác tối ưu hơn không ạ?

0

kytoLam đã bình luận lúc 26, Tháng 10, 2024, 9:07

có thể dùng binary search để tìm nha bạn, mà linear cũng đâu TLE đâu ta

2

thaomy đã bình luận lúc 18, Tháng 6, 2024, 14:30

mình thấy dùng được mà bạn

include <stdio.h>

long long Fi(long long n){ long long F[100]; F[0]=0, F[1]=1; for(int i=2; i<93; i++){ F[i]=F[i-1]+F[i-2]; } for(int i=0; i<93; i++){ if(n==F[i]) return 1; } return 0; } int main() { long long N; scanf("%lld", &N); long long A[N]; for(long long i=0; i<N; i++){ scanf("%lld", &A[i]); } long long res=0; for(long long i=0; i<N; i++){ if(Fi(A[i])==1) printf("%lld ", A[i]); else res++; } if(res==N) printf("NONE");

}