Tìm trong dãy một số fibonacci có giá trị lớn nhất

[nakaru_snow]

Đề:
Fibonacci
source: fib.cpp
input: fib.inp
output: fib.out
Dãy số fibonacci là dãy số được tính theo công thức sau:
A0 = 1;
A1 = 1;
Ai = Ai-2 + Ai-1
Ví dụ: Dãy sau là dãy Fibonacci: 1 1 2 3 5 8 13 21 34
Một số được gọi là số fibonacci khi nó thuộc dãy số fibonacci.
Ví dụ: 8 là số fibonacci; 9 không phải là số fibonacci
Cho dãy số N số nguyên dương (N<=10.000), mỗi số 0<ai<2.000.000.000
Tìm trong dãy trên số fibonacci có giá trị lớn nhất.
Dữ liệu nhập vào từ file fib.inp với dòng đầu tiên ghi số N, dòng tiếp theo ghi N số nguyên.
Dữ liệu ra ghi vào file fib.out với 1 số nguyên. Hoặc số 0 nếu trong dãy không có số fibonacci nào cả.
input: fib.inp
7
1 9 8 3 25 15 20
output: fib.out
8

#include <stdio.h>#include <conio.h>#define LENGTH 1000 main(){      FILE *fi;      FILE *fo;      char *fileInput = "fib.inp";      char *fileOutput = "fib.out";      int N,i,start,end,mid,check;      long A[LENGTH],temp,fibMax=0;      A[0] = 1;      A[1] = 1;      for(i=2;i<N;i++)      {                         A[i] = A[i-1]+A[i-2];                              if(A[i]<0)                                   break;      }      fi = fopen(fileInput,"r");      fscanf(fi,"%d",&N);      for(i=0;i<LENGTH;i++)      {                      check = 0;                      start = 0;                      end = LENGTH-1;                      fscanf(fi,"%ld",&temp);                      while(start<=end)                      {                                      mid = (start+end)/2;                                      if(temp==A[mid]);                                      {                                      check = 1;                                          break;                                          }                                                                               if(temp>A[mid])                                           start = mid+1;                                      else                                           end = mid-1;                                                     }                      if(check)                               if(fibMax<A[mid])                                                fibMax = A[mid];                                                                                                      }                          fclose(fi);      fo = fopen(fileOutput, "w");      fprintf(fo,"%ld",fibMax);      fclose(fo);      getch();      return 0;}

Test dùm mình bài này không hiểu sao kết quả in ra không đưa ra số lớn nhất :(

[reaper]

      A[0] = 1;      A[1] = 1;      for(i=2;i<N;i++)      {                         A[i] = A[i-1]+A[i-2];                              if(A[i]<0)                                   break;      }

1.Chỗ này của bạn sai, N = ?, khó hiểu nữa là lệnh if(A[i] < 0) -> để làm gì ? Bạn sửa lại cho lệnh fscanf() lên trước đoạn lệnh này đi.

                      while(start<=end)                      {                                      mid = (start+end)/2;                                      if(temp==A[mid]);                                      {                                      check = 1;                                          break;                                          }                                                                               if(temp>A[mid])                                           start = mid+1;                                      else                                           end = mid-1;                                                     }

2. Bạn tối ưu nó quá mức -> gây mất dữ liệu, chịu khó bỏ đi một số gán lại start = mid và end = mid thôi, bỏ đi một số chắc cũng không đến lỗi ảnh hưởng đến thuật toán đâu.

[G.Perelman]

Bạn hiểu sai đề bài rồi (N ở đây là số số nguyên dương trong file input chứ không phải là cho từ 1 đến N ) mà mỗi số nguyên dương a[i] thỏa mãn 0<a[i]<2.000.000.000 nên nếu làm theo cách của bạn phải dùng mảng A[x] sao cho A[x] >=2.000.000.000 bạn hiểu ý mình không nhỉ?
Mình sẽ về nghĩ cách làm,hi vọng sẽ trả lời bạn sớm.

[fedo]

Chào bạn,
Hướng giải quyết bài này của mình như sau
1./Viêt một hàm kiểm tra số nguyên n có phải là số fibonaci hay không?
2./ Đọc và khởi tạo mảng các số nguyên từ file fib.inp.
3./ Dùng một biến max = 1( số fibonaci nhỏ nhất).Sau khi có được mảng các số nguyên tiến hành duyệt mảng và kiểm tra từng phần tử có phải là số fibonaci không. Nếu là số fibonaci thì so sánh với max. Nếu a[i] > max thì max = a[i]. Kết thúc vòng lặp thì max là số fibonaci lớn nhất. Dưới đây là code minh họa phần thứ 3

int max = 1 //  số fibonaci nhỏ nhất
for(int i = 0; i < N;i++)
{
     if(IsFibonaciNumber(a[i]) == 1) // a[i] là số fibonaci
     {
          if(a[i] > max)
          {
               max = a[i];
          }
     }
}
return max; 

Chúc bạn nhanh giải quyết bài toán này!

[reaper]

@fedo : Cách củ chuối này thì nói làm gì !
@tanglung117: A[x] >= 2 tỉ thì đã vấn đề gì, mới có 10 con số.

---------
Dùng từ ngữ đúng nội quy nha bạn. "Củ chuối là gì"

[fedo]

@fedo : Cách củ chuối này thì nói làm gì !

Chào bạn, bạn có thể chỉ cho mình những điểm chuối trong cách của mình không. Mình rất muốn biết để rút kinh nghiệm, tại mình nghĩ mãi mà chỉ có mỗi hướng đó để làm bài này thôi.

[mushu]

Em nghĩ dùng công thức tổng quát là tốt nhất.


Trong đó là nghiệm dương và là nghiệm âm của phương trình nghiệm lần lượt là và .
Vừa mất điện thông cảm nhé!!!
Chờ mình rút gọn nhé.



Vậy thôi rút gọn có vẻ còn phức tạp hơn có thì đưa con 2 ra ngoài thôi.

[G.Perelman]

Đối với bài của bạn mình làm như sau :
do số nguyên dương lớn nhất trong file input có thể là 2.000.000.000 nên mình sẽ xây dựng 1 mảng FIB[m] lưu trữ dãy FIBONACI sao cho FIB[m]=MAX(x) với x thuộc dãy fibonaci && x<=2.000.000.000 ,làm bằng tay mình tính được m=45.
Sau khi đọc xong A[N] số nguyên dương từ file input mình tiến hành sắp xếp lại theo chiều tăng dần (A[i]<=A[i+1]) bằng thủ tục quick_sort.
Tiếp đó mình xây dựng hàm is_FIB(long F) kiểm tra xem F có thuộc dãy Fibonaci không ? (cái này sử dụng thuật toán tìm kiếm nhị phân giống của bạn )
Cuối cùng mình chỉ cần duyệt từ A[N]->A[1] nếu gặp A[k] thuộc dãy Fibonaci thì dừng lại và lưu ý đây là số lớn nhất cần tìm do dãy đã được sắp xếp.
còn nếu đã duyệt hết các phần tử (j==0) thì không thấy.
Hi vọng bạn hiểu chương trình của mình.
Sau đây là code của mình.

#include "stdio.h"#include "stdlib.h"#define MAX 6000    char *input="d:\\fib.inp";    char *output="d:\\fib.out";    int N;      /* so cac so nguyen duong */    long  A[MAX];   /* luu cac so nguyen duong */    long  FIB[MAX]; /* luu day so fibonaci */    int m;      /* phan tu cuoi cung cua day Fib */     void read()        {            FILE *fp;            int j;            fp=fopen(input,"r");                fscanf(fp,"%d",&N);                for (j=1;j<=N;j++)    fscanf(fp,"%ld",&A[j]);            fclose(fp);         }    /* di tim phan tu cuoi cung cua day FIB */    void xay_dung_day()        {            int j;               FIB[0]=1;FIB[1]=1;               m=1;               do              {                m++;                FIB[m]=FIB[m-1]+FIB[m-2];              }               while (m<45);          /* minh tinh duoc rang FIB[45]=1836311903 */        }    /* sap xep lai mang A theo chieu tang dan --> Viec nay co the lam giam dang ke thoi gian chay chuong trinh */    void quick_sort(int l,int r)        {            long tg,pivot;            int i,j;            if (l<r)                {                    i=l;j=r;pivot=A[random(r-l+1)+l];                    do                        {                            while (A[i]<pivot) i++;                            while (A[j]>pivot) j--;                            if (i<=j)                            {                                tg=A[i];A[i]=A[j];A[j]=tg;                                i++;j--;                            }                        }                    while (i<=j);                    quick_sort(l,j);                    quick_sort(i,r);                }        }    /* ham kiem tra xem F co phai la so FIB khong    su dung thuat toan tim kiem nhi phan */    int is_FIB(long F)        {            int top,bottom;            long X;            top=m;bottom=0;            while (top>=bottom)                {                  X=FIB[(top+bottom)/2];                  if (X==F) return 1;   /* F la so fibonaci */                  else  if (X>F) top=(top+bottom)/2-1;                    else     bottom=(top+bottom)/2+1;                }            return 0;           /* F khong la so fibonaci */        }    void xu_ly()        {            int j;            FILE *fp;            for (j=N;j>=1;j--)               if (is_FIB(A[j])) break;            fp=fopen(output,"w");                if (j>=1) fprintf(fp,"%ld",A[j]);   /* viet so vua tim duoc */                else      fprintf(fp,"%d",-1);      /* khong co so fibonaci trong day da cho */            fclose(fp);        }     void main()        {            read();            xay_dung_day();            quick_sort(1,N);            xu_ly();        }

PS:mình đã test vài ví dụ và thấy chương trình chạy đúng.

[Cold]

bác ơi mình dùng c free mình đã copy cái code nì mà mình ko chạy dc.Yều cầu bài của mình chỉ là in ra cái dãy fibonacci này thôi.Bác giúp mình với thanks

[trubavuong]

bác ơi mình dùng c free mình đã copy cái code nì mà mình ko chạy dc.Yều cầu bài của mình chỉ là in ra cái dãy fibonacci này thôi.Bác giúp mình với thanks

In ra thì quá easy.

#include <conio.h>#include <stdio.h>main(){    int n;    unsigned long a=1,b=1,c;    do{    printf("Nhap N = ");    scanf("%d",&n);    }while(n<1);    printf("\nDay Fibonaxi :\n");    if(n==1) printf("1");    else if(n==2) printf("1 1");         else{            printf("1 1 ");            for(int i=1;i<=n;i++)            {                c=a+b;                printf("%lu ",c);                a=b;b=c;            }        }    getch();}