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ố 12 kết quả

Đề tài: Giải thuật Tìm BSC nhỏ nhất cho 1 dãy số. KO biết có đúng ko?

  1. #1
    Ngày gia nhập
    01 2008
    Bài viết
    120

    Wink Giải thuật Tìm BSC nhỏ nhất cho 1 dãy số. KO biết có đúng ko?

    Chào bạn. Con em mình nó đang học C++ thì có 1 đề bài khiến mình hơi hóc như sau :
    7. Cho các số nguyên dương x1, x2,..., xn (được lưu trong file, dòng đầu tiên là số phần tử n dòng tiếp theo là các phần tử trong dãy), trong đó, 1 <= n <= 100 và 1 <= xi <= 200. Tìm bội số chung nhỏ nhất của chúng. Ví dụ dãy 4, 5, 4, 6, 1, 5, 8 có bội số chung nhỏ nhất là 120.

    //------------------Hic------------------------
    MÌnh có tìm đc code tìm BSCNN của 2 số chứ ko phải dãy số.
    //-----------------Cú-----------------------------
    THế quái nào mình lại nghĩ ra 1 cách như sau, nhưng ko biết có đúng ko và sợ thầy giáo bắt bẻ con e mình nên muốn bạn cho mình kiểm chứng với nhé.
    Cách đó là :
    + Sắp xếp mảng này theo thứ tự giảm dần 8 6 5 5 4 4 1
    + Gán BSC=a[0]*a[1] ( tức BSC=6*8=48)
    + Duyệt từ 2-n; For(i=2;i<n;i++)
    If( BSC% a[i]!=0) BSC*=a[i]; -> Ra kết quả rùi
    --------------------------
    Tớ đang băn khoăn cái cách này, bạn cho ý kiến với nhé
    Đã mất công nghĩ thì nghĩ mẹ cái thật lớn vào !
    Y!H: trinhhoaithanh1905

  2. #2
    Ngày gia nhập
    03 2009
    Nơi ở
    Ở địa ngục
    Bài viết
    667

    Trời ơi!
    Cách này sai vd: 16,8, 4, 4, ==> BCNN là 16*8=128 trong khi BCNN là 16.
    Nếu Biết giải thuật tìm BCNN 2 số rồi thì sao không dùng cách này:
    Tìm BCNN 2 số dầu tiên, rồi tìm BCNN của BCNN và một số khác. Cứ thế. Tội gì phải sắp xếp.
    Cách này cũng học trên diễn đàn thôi.
    Đã được chỉnh sửa lần cuối bởi trungkien45 : 16-04-2009 lúc 03:02 PM. Lý do: chưa đọc kĩ giải thuật phần sắp xếp

  3. #3
    Ngày gia nhập
    01 2008
    Bài viết
    120

    Ec. Tui thu rùi. Nhưng ....
    Cảm ơn bạn đã góp ý, nếu theo ý bạn, mình chỉ cần sửa nó lại như sau

    + Sắp xếp mảng này theo thứ tự giảm dần 16 8 4 4
    + Gán BSC=a[0] ( tức BSC=16)
    + Duyệt từ 1-n; For(i=1;i<n;i++)
    If( BSC% a[i]!=0) BSC*=a[i]; -> Ra kết quả rùi
    Đã mất công nghĩ thì nghĩ mẹ cái thật lớn vào !
    Y!H: trinhhoaithanh1905

  4. #4
    Ngày gia nhập
    03 2009
    Nơi ở
    Ở địa ngục
    Bài viết
    667

    Vẫn sai!
    Nếu dãy có ước chung !=1.
    VD: 8, 6, 4
    Thì BCNN =a[0]=8.
    Sau đó vì 8%6=2, 2!=0 nên lấy BCNN = 6*8=48.
    Trong khi BCNN là 24

    Chắc bạn biết cách tìm ƯCLN 2 số thôi hả, nếu vậy thì cho bạn giải thuật tìm ƯCLN dãy số: Tìm ƯCLN của 2 số bất kì sau đó Tương tự cách tìm BCNN của mình trên.

    Sau đó thì bạn còn một cách tìm BCNN là lấy tích toàn bộ dãy chia cho ƯCLN.
    Đã được chỉnh sửa lần cuối bởi trungkien45 : 16-04-2009 lúc 02:59 PM.

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

    Sau đó thì bạn còn một cách tìm BCNN là lấy tích toàn bộ dãy chia cho ƯCLN.
    Cũng sai nốt.
    VD lấy ngay cái ví dụ của cậu: 8,6,4--> UCLN=2---> BCNN=8*6*4/2 == 24 ??? ko biết cái này có đúng ko nữa

  6. #6
    Ngày gia nhập
    03 2009
    Nơi ở
    Ở địa ngục
    Bài viết
    667

    Mặc định Giải thuật Tìm BSC nhỏ nhất cho 1 dãy số. KO biết có đúng ko?

    Ờ cảm ơn nhé. đúng là sai thật. tru ba vuong có cách gì hay không?

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

    Code đây, vừ mới make xong, còn nóng đó
    C Code:
    1. #include <conio.h>
    2. #include <stdio.h>
    3. main()
    4. {
    5.     int a[100],n,k=1,max;
    6.     long b;
    7.     printf("\nBao nhieu phan tu : ");
    8.     scanf("%d",&n);
    9.     for(int i=0;i<n;i++)
    10.     {
    11.         printf("\nNhap a[%d] = ",i+1);
    12.         scanf("%d",&a[i]);
    13.         if(i==0) max=a[0];
    14.         else if(a[i]>max) max=a[i];
    15.     }
    16.     do{
    17.     b=max*k++;
    18.     for(i=0;i<n;i++)
    19.     {
    20.         if(b%a[i]) break;
    21.         else if(i==n-1&&b%a[n-1]==0) goto finished;
    22.     }
    23.     }
    24.     while(1);
    25.     finished:
    26.     printf("\nBCNN cua day tren la : %ld",b);
    27.     getch();
    28. }

  8. #8
    Ngày gia nhập
    09 2008
    Bài viết
    18

    mình thấy code trên vẫn chưa đúng lắm. bạn hãy thử xét dãy số trên với {3,5,9,7,10} xem BCNN của nó có phải là 630 không?? cái này mình chưa nghĩ ra thuật toán cho nó. chắc phải tìm cách khác để tìm BCNN của dãy số.
    --------------------------------------

  9. #9
    Ngày gia nhập
    02 2008
    Nơi ở
    AYS 107
    Bài viết
    41

    Thì mình cứ tìm BCNN của 2 số đi. Sau đó tìm BCNN của 2 số đó với các số còn lại trong dãy (đệ qui ấy)
    BCNN(a[0],a[1],...,a[n]) = BCNN(BCNN(a[0],a[1]),a[2],...,a[n]);
    Post tạm cái code này:
    C Code:
    1. #include <stdio.h>
    2.  
    3. int BCNN(int a, int b)
    4. {
    5.   int BCNN;
    6.   if(a>b) BCNN=a;
    7.   else BCNN=b;
    8.   while(BCNN%a || BCNN%b) BCNN++;
    9.   return BCNN;
    10. }
    11.  
    12. int main()
    13. {
    14.   int a[100],n,m,i;
    15.   printf("Nhap so phan tu cua mang: ");
    16.   scanf("%d",&n);
    17.   printf("Nhap cac phan tu cua mang: ");
    18.   for(i=0;i<n;i++) scanf("%d",&a[i]);
    19.   m=a[--n];
    20.   while(--n>=0) m=BCNN(m,a[n]);
    21.   printf("BCNN cua day so: %d\n",m);
    22.   return 0;
    23. }
    I don't wanna waste another day

  10. #10
    Ngày gia nhập
    05 2009
    Bài viết
    3

    Smile Tìm BCNN của dãy số

    Mình nghĩ bài này cũng khá đơn giản. Sau đây là bài làm hoàn chỉnh, mình viết bằng C++.
    Code:
    #include <iostream> 
    #include <fstream> 
    #include <cstdlib> 
    #include <vector> 
    
    using namespace std; 
    
    typedef unsigned int uint; 
    
    uint ucln(uint a, uint b) 
    {
    	if (a == 0) return b;
    	return ucln(b % a, a);
    }
    
    uint bcnn(uint a, uint b) 
    {
    	return (a * b) / ucln(a,b);
    }
    
    uint bcnn(const vector< uint > &v) 
    {
    	uint kq = v[0]; 
    	size_t size = v.size();
    	for (size_t i = 0; i < size; i++) {
    		kq = bcnn(kq, v[i]);
    	}
    	return kq; 
    }
    
    void input(const char *fileName, vector< uint > &v) 
    {
    	ifstream inFile(fileName, ios::in); 
    	if (!inFile) {
    		cerr << "Can not open file" << endl; 
    
    		exit( 1 );
    	}
    	int size; 
    	int val; 
    
    	inFile >> size; 
    	v.resize(size); 
    	for (int i = 0; i < size; i++) {
    		inFile >> val; 
    		v[i] = val;
    	}
    	inFile.close(); 
    }
    
    int main() 
    {
    	vector< uint > v;
    	input("input.txt", v);//tap tin input co dinh dang nhu trong de
    	int kq = bcnn(v); 
    	cout << "kq = " << kq << endl;
    
    	return 0; 
    }
    Đã được chỉnh sửa lần cuối bởi tqthe : 05-05-2009 lúc 04:36 PM. Lý do: edit code

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

  1. Algorithm Thuật toán tính số câu đúng trên 100 câu trả lời gần nhất!
    Gửi bởi hungknorton trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 21-06-2013, 11:13 PM
  2. Hiện thực hoá giải thuật Roundrobin với C++ ! hàm calc chạy chưa đúng! sửa giúp mình.
    Gửi bởi code_c trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 0
    Bài viết cuối: 26-11-2011, 12:32 AM
  3. Bài tập C Lỗi chạy không đúng thuật toán sắp xếp và trung bình cộng dãy vừa nhập
    Gửi bởi dzung72 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 12-08-2011, 07:33 PM
  4. Thuật toán giải nén Huffman, ai biết giúp mình?
    Gửi bởi haian trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 2
    Bài viết cuối: 13-03-2011, 06:12 PM
  5. Giải thuật biến đổi chuỗi thành Palindrome ?
    Gửi bởi drak77 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 14-02-2011, 10:44 AM

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