Đánh giá, nhận xét, review các công ty tuyển dụng
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

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

  1. #1
    Ngày gia nhập
    12 2007
    Nơi ở
    Mình đang sống tại Đà Nẵng
    Bài viết
    5

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

    Đề:
    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



    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #define LENGTH 1000
    4.  
    5. main()
    6. {
    7.       FILE *fi;
    8.       FILE *fo;
    9.       char *fileInput = "fib.inp";
    10.       char *fileOutput = "fib.out";
    11.       int N,i,start,end,mid,check;
    12.       long A[LENGTH],temp,fibMax=0;
    13.       A[0] = 1;
    14.       A[1] = 1;
    15.       for(i=2;i<N;i++)
    16.       {
    17.                          A[i] = A[i-1]+A[i-2];    
    18.                          if(A[i]<0)
    19.                                    break;
    20.       }
    21.       fi = fopen(fileInput,"r");
    22.       fscanf(fi,"%d",&N);
    23.       for(i=0;i<LENGTH;i++)
    24.       {
    25.                       check = 0;
    26.                       start = 0;
    27.                       end = LENGTH-1;
    28.                       fscanf(fi,"%ld",&temp);
    29.                       while(start<=end)
    30.                       {
    31.                                       mid = (start+end)/2;
    32.                                       if(temp==A[mid]);
    33.                                       {
    34.                                       check = 1;
    35.                                           break;
    36.                                           }  
    37.                                      
    38.                                       if(temp>A[mid])
    39.                                            start = mid+1;
    40.                                       else
    41.                                            end = mid-1;
    42.                                
    43.                       }
    44.                       if(check)
    45.                                if(fibMax<A[mid])
    46.                                                 fibMax = A[mid];
    47.                                                
    48.                                                
    49.       }                    
    50.       fclose(fi);
    51.       fo = fopen(fileOutput, "w");
    52.       fprintf(fo,"%ld",fibMax);
    53.       fclose(fo);
    54.       getch();
    55.       return 0;
    56. }

    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 :(
    Luôn học hỏi là cách để tự hoàn thiện bản thân.

  2. #2
    Ngày gia nhập
    04 2008
    Bài viết
    20

    C Code:
    1.       A[0] = 1;
    2.       A[1] = 1;
    3.       for(i=2;i<N;i++)
    4.       {
    5.                          A[i] = A[i-1]+A[i-2];    
    6.                          if(A[i]<0)
    7.                                    break;
    8.       }
    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.


    C Code:
    1.                       while(start<=end)
    2.                       {
    3.                                       mid = (start+end)/2;
    4.                                       if(temp==A[mid]);
    5.                                       {
    6.                                       check = 1;
    7.                                           break;
    8.                                           }  
    9.                                      
    10.                                       if(temp>A[mid])
    11.                                            start = mid+1;
    12.                                       else
    13.                                            end = mid-1;
    14.                                
    15.                       }
    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.

  3. #3
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    705

    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.

  4. #4
    Ngày gia nhập
    10 2007
    Bài viết
    32

    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
    PHP Code:
    int max //  số fibonaci nhỏ nhất
    for(int i 0N;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!
    Đã được chỉnh sửa lần cuối bởi fedo : 15-04-2008 lúc 09:02 PM.

  5. #5
    Ngày gia nhập
    04 2008
    Bài viết
    20

    @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ì"
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 16-04-2008 lúc 06:18 PM.

  6. #6
    Ngày gia nhập
    10 2007
    Bài viết
    32

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

    Trích dẫn Nguyên bản được gửi bởi reaper Xem bài viết
    @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.

  7. #7
    Ngày gia nhập
    02 2008
    Bài viết
    63

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

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

    Công thức toán học Latex

    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.
    Công thức toán học Latex
    Đã được chỉnh sửa lần cuối bởi mushu : 16-04-2008 lúc 07:12 PM. Lý do: Đánh công thức toán không được

  8. #8
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    705

    Đố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.
    C Code:
    1. #include "stdio.h"
    2. #include "stdlib.h"
    3. #define MAX 6000
    4.     char *input="d:\\fib.inp";
    5.     char *output="d:\\fib.out";
    6.     int N;      /* so cac so nguyen duong */
    7.     long  A[MAX];   /* luu cac so nguyen duong */
    8.     long  FIB[MAX]; /* luu day so fibonaci */
    9.     int m;      /* phan tu cuoi cung cua day Fib */
    10.  
    11.     void read()
    12.         {
    13.             FILE *fp;
    14.             int j;
    15.             fp=fopen(input,"r");
    16.                 fscanf(fp,"%d",&N);
    17.                 for (j=1;j<=N;j++)    fscanf(fp,"%ld",&A[j]);
    18.             fclose(fp);
    19.  
    20.         }
    21.     /* di tim phan tu cuoi cung cua day FIB */
    22.     void xay_dung_day()
    23.         {
    24.             int j;
    25.                FIB[0]=1;FIB[1]=1;
    26.                m=1;
    27.                do
    28.               {
    29.                 m++;
    30.                 FIB[m]=FIB[m-1]+FIB[m-2];
    31.               }
    32.                while (m<45);          /* minh tinh duoc rang FIB[45]=1836311903 */
    33.         }
    34.     /* sap xep lai mang A theo chieu tang dan --> Viec nay co the lam giam dang ke thoi gian chay chuong trinh */
    35.     void quick_sort(int l,int r)
    36.         {
    37.             long tg,pivot;
    38.             int i,j;
    39.             if (l<r)
    40.                 {
    41.                     i=l;j=r;pivot=A[random(r-l+1)+l];
    42.                     do
    43.                         {
    44.                             while (A[i]<pivot) i++;
    45.                             while (A[j]>pivot) j--;
    46.                             if (i<=j)
    47.                             {
    48.                                 tg=A[i];A[i]=A[j];A[j]=tg;
    49.                                 i++;j--;
    50.                             }
    51.                         }
    52.                     while (i<=j);
    53.                     quick_sort(l,j);
    54.                     quick_sort(i,r);
    55.                 }
    56.         }
    57.     /* ham kiem tra xem F co phai la so FIB khong
    58.     su dung thuat toan tim kiem nhi phan */
    59.     int is_FIB(long F)
    60.         {
    61.             int top,bottom;
    62.             long X;
    63.             top=m;bottom=0;
    64.             while (top>=bottom)
    65.                 {
    66.                   X=FIB[(top+bottom)/2];
    67.                   if (X==F) return 1;   /* F la so fibonaci */
    68.                   else  if (X>F) top=(top+bottom)/2-1;
    69.                     else     bottom=(top+bottom)/2+1;
    70.                 }
    71.             return 0;           /* F khong la so fibonaci */
    72.         }
    73.     void xu_ly()
    74.         {
    75.             int j;
    76.             FILE *fp;
    77.             for (j=N;j>=1;j--)
    78.                if (is_FIB(A[j])) break;
    79.             fp=fopen(output,"w");
    80.                 if (j>=1) fprintf(fp,"%ld",A[j]);   /* viet so vua tim duoc */
    81.                 else      fprintf(fp,"%d",-1);      /* khong co so fibonaci trong day da cho */
    82.             fclose(fp);
    83.         }
    84.  
    85.     void main()
    86.         {
    87.             read();
    88.             xay_dung_day();
    89.             quick_sort(1,N);
    90.             xu_ly();
    91.         }
    PS:mình đã test vài ví dụ và thấy chương trình chạy đúng.
    Đã được chỉnh sửa lần cuối bởi G.Perelman : 20-04-2008 lúc 09:42 PM.

  9. #9
    Ngày gia nhập
    03 2009
    Bài viết
    2

    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

  10. #10
    Ngày gia nhập
    01 2009
    Nơi ở
    Hà Nội
    Bài viết
    205

    Trích dẫn Nguyên bản được gửi bởi Cold Xem bài viết
    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.

    C Code:
    1. #include <conio.h>
    2. #include <stdio.h>
    3. main()
    4. {
    5.     int n;
    6.     unsigned long a=1,b=1,c;
    7.     do{
    8.     printf("Nhap N = ");
    9.     scanf("%d",&n);
    10.     }while(n<1);
    11.     printf("\nDay Fibonaxi :\n");
    12.     if(n==1) printf("1");
    13.     else if(n==2) printf("1 1");
    14.          else{
    15.             printf("1 1 ");
    16.             for(int i=1;i<=n;i++)
    17.             {
    18.                 c=a+b;
    19.                 printf("%lu ",c);
    20.                 a=b;b=c;
    21.             }
    22.         }
    23.     getch();
    24. }

Các đề tài tương tự

  1. tìm vị trí số nguyên tố lớn nhất trong mảng + kiểm tra dãy fibonacci
    Gửi bởi ellis trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 20
    Bài viết cuối: 27-07-2013, 05:18 PM
  2. Bài toán dãy số FIBONACCI
    Gửi bởi khanh1202 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 7
    Bài viết cuối: 28-05-2013, 11:52 PM
  3. Trả lời: 1
    Bài viết cuối: 30-03-2013, 08:19 AM
  4. [Help] tìm số Fibonacci lớn nhất bé hơn n cho trước.
    Gửi bởi superdanger trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 8
    Bài viết cuối: 09-11-2012, 06:07 PM
  5. Bài tập C Tìm phần tử chẵn trong dãy Fibonacci (có điều kiện)
    Gửi bởi cr9 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 05-04-2011, 02:18 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn