Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 22 kết quả

Đề tài: [ Solved ]Các bài toán về số.

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

    Mặc định [ Solved ]Các bài toán về số.

    Mình đang muốn sưu tập 1 số bài toán giải quyết về số ví dụ như : Số nguyên tố, số hoàn hảo, ... , tìm ước chung lớn nhất, giai thừa ... Lập ra đề tài này hi vọng có nhiều người nhiệt tình tham gia, post bài chia sẻ kinh nghiêm, tìm ra những thuật toán tốt nhất, giải quyết các bài toán với những số lớn, thời gian thực hiện tốt nhất có thể. Mình xin mở đầu với mấy bài nhỏ này hi vọng mọi người coi xong giúp đỡ cho ý kiến và chia sẻ những bài của mình lên nhé !
    Tính giai thừa của 1 số tự nhiên:
    Code:
    int factorial1 ( int N )
      {
         if( N == 0 ) return 1;
         return N * factorial1( N-1 );
      }
    int factorial2 ( int N )
      {
         int result = 1;
         for( int i = 1; i <= N; i++ )
             result *= i;
         return result;
      }
    Tính số dư của N! cho M.
    Code:
    int ModFactorial( int N, int M )
      {
        if( N >= M ) return 0;
        int result = 1;
        for ( int i = 2; i <= N; i++ )
           {
             result *= i;
             if( result > M ) result = result % M;
           }
        return result;
    
      }
    Tính số chữ số 0 tận cùng của N! - N! luôn chứa số thừa số 2 nhiều hơn 5 nên ta chỉ cần tìm số mũ n của 5^n trong N! là đủ. Có nhận xét sau đây :
    Số c/s 0 trong N! = ( N div 5 ) * Số c/s 0 trong ( N div 5) !
    Code:
    int TimesOfZero( int N )
      {
         if( N == 0 ) return 0;
         N /= 5 ;
         return N + TimesOfZero( N );
      }
    Trong chương trình 2 mình không chắc chắn lắm với kết quả chương trình đưa ra với những số N,M đủ lớn. Ví dụ như khi result chưa vượt quá M ( chưa thực hiện phép result = result % M ) , nhưng result * i lại vượt quá INT_MAX , mình lưỡng lự không biết có nên cho thêm điều kiện if ( result < INT_MAX / i ) hay không vì làm vậy chắc sẽ giảm thời gian thực hiện rất nhiều vì có rất nhiều vòng lặp.

  2. #2
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    Trong chương trình 2 mình không chắc chắn lắm với kết quả chương trình đưa ra với những số N,M đủ lớn. Ví dụ như khi result chưa vượt quá M ( chưa thực hiện phép result = result % M ) , nhưng result * i lại vượt quá INT_MAX , mình lưỡng lự không biết có nên cho thêm điều kiện if ( result < INT_MAX / i ) hay không vì làm vậy chắc sẽ giảm thời gian thực hiện rất nhiều vì có rất nhiều vòng lặp.
    Code:
    int ModFactorial( int N, int M )
      {
        if( N >= M ) return 0;
        int result = 1;
        for ( int i = 2; i <= N; i++ )
           {
             result *= i;
             if( result > M ) result = result % M;
           }
        return result;
    
      }
    áp dụng công thức (m*n)mod x= m mod x * n mod x

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

    Trong trường hợp này thì m và n đều nhỏ hơn x mà. Hơn nữa cái công thức đó phải sửa lại là (m*n)mod x= ( m mod x * n mod x ) mod x ;
    Đã được chỉnh sửa lần cuối bởi aMember : 08-08-2008 lúc 10:44 AM.

  4. #4
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Ủng hộ aMember nhé:
    - Kiểm tra một số có phải là số nguyên tố không:
    Code:
    int primeNumber1(int n)
    {
         int i,t;
         if (n<=1)return 0;
         t=sqrt(n);
         for (i=2;i<=t;i++)
              if (n%i==0)return 0;
         return 1;
    }
    Dựa vào lý thuyết: mọi số không phải là nguyên tố đều là bội của 2 or 3 or 5 or 7
    Code:
    int primeNumber2(int n)
    {
         int i;
         if (n<=1)return 0;
         if (n<=3)return 1;
         if (n==5||n==7)return 1;
         if (n%2==0 || n%3==0 || n%5==0 || n%7==0)return 0;
         return 1;
    }

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

    Dựa vào lý thuyết: mọi số không phải là nguyên tố đều là bội của 2 or 3 or 5 or 7
    Lý thuyết nghe lạ quá ^^.Bạn thử các số này không phải là nguyên tố nhưng đều không phải bội của các số đó : 121,169,...vv rất nhiều số miễn sao số ấy là tích của các số nguyên tố lớn hơn 7 : ví dụ : 121=11*11; 169=13*13;hoặc 143=11*13 ...còn rất nhiều
    Đã được chỉnh sửa lần cuối bởi SmallInt : 08-08-2008 lúc 12:06 PM.

  6. #6
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Mặc định [ Solved ]Các bài toán về số.

    Híc thôi chết, cái lý thuyết đó chỉ trong 120 số đầu tiên http://vi.wikipedia.org/wiki/S%E1%BB...AAn_t%E1%BB%91
    Sorry mọi người T_T

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

    Trong trường hợp này thì m và n đều nhỏ hơn x mà. Hơn nữa cái công thức đó phải sửa lại là (m*n)mod x= ( m mod x * n mod x ) mod x ;
    sai rồi cậu ah
    chứng minh trên giấy đi,đơn giản thôi

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

    Lấy ví dụ nhé 3 mod 5 = 3 ; 4 mod 5 = 4 ; theo bạn thì 3*4 mod 5 = 3 * 4 = 12 lớn hơn 5 rồi. Cái công thức đó hoàn toán chính xác.

  9. #9
    Ngày gia nhập
    08 2008
    Bài viết
    28

    Trích dẫn Nguyên bản được gửi bởi QuangHoang Xem bài viết
    Híc thôi chết, cái lý thuyết đó chỉ trong 120 số đầu tiên http://vi.wikipedia.org/wiki/S%E1%BB...AAn_t%E1%BB%91
    Sorry mọi người T_T
    Cái đó là sàng số nguyên tố Eratosthene, dùng để in ra các số nguyên tố nhỏ hơn n. Chắc là bạn hiểu nhầm rồi , đằng sau các số 2,3,5,7 đó chắc chắn phải có dấu 3 chấm^^. Mình lấy code về và viết lại trên C++ như sau :
    Code:
    #include <iostream.h>
    #include <conio.h>
    #include <math.h>
    void main()
    {
     const int N = 1000 ;
     int Prime[N+1] ;
     int i, j, k;
     Prime[1] = 0;
     k=0;
     while( k < sqrt(N) )
       {
          i = k + 1;
          while( ! Prime[i] ) i++;
          k = i;
          j = 2;
          Prime[k] = 1;
          while( k * j <= N )
            {
              Prime[k*j] = 0 ;
              j++ ;
            }
       }
     for ( i = 2; i <= N; i++ )
       if( Prime[i] ) cout << i << "  ";
     getch();
    
    }
    Đầu tiên người ta lưu các giá trị từ 2 đến n vào 1 mảng ( gọi là cái sàng ^^).
    Giữ lại 2 và xoá toàn bộ các số lớn hơn 2 mà chia hết cho 2.
    Đi tới phần tử tiếp theo không bị xoá ( là 3) : Giữ lại 3 và xoá toàn bộ các số lớn hơn 3 mà chia hết cho 3.
    Đi tới phần tử tiếp theo không bị xoá ( là 5) : Giữ lại 5 và xoá toàn bộ các số lớn hơn 5 mà chia hết cho 5.
    Cứ tiếp tục như vậy cho tới sqrt(n) ;

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

    Số hoàn hảo là những số có tính chất: Tổng các ước của số đó (trừ số đó) bằng chính số đó

    Đây là hàm con kiểm tra một số có phải số hoàn hảo không, nếu có trả về giá trị 1, ngược lại trả về 0 :
    Code:
    int is_perfect_number (int n)
    {
      int i,sum=0;
      for(i=1;i<n;i++)
         if(n%i==0)
             sum+=i;
      if(sum==n)
        return 1; 
      return 0;
    }
    Tìm ước chung lớn nhất của 2 số

    Mình có mấy cách như thế này đều dùng được:

    Code:
    int gcd(int a, int b)
    {
      if(b==0)
       return a;
      return gcd(b,a%b);
    }
    Code:
    int gcd(int a, int b)
    {
      int t;
      while(b!=0)
        t=a%b,a=b,b=t;
      return a;
    }
    Code:
    int gcd(int a, int b)
    {
      while(a!=b){
        if(a>b)
          a=a-b;
        else
          b=b-a;
      }
      return a;
    }
    Mình xét số dương thui nhé
    Đã được chỉnh sửa lần cuối bởi developer : 09-08-2008 lúc 09:27 AM.
    I don't wanna waste another day

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

  1. [ Solved ]Xây dựng lớp ĐỒTHI
    Gửi bởi bluesky_123078 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: 09-11-2008, 09:34 AM
  2. [Solved] Hỏi về con trỏ
    Gửi bởi RedHatLinux9 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 17-09-2008, 08:01 AM
  3. [ Solved ]Cấp phát động
    Gửi bởi demontaihack trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 07-09-2008, 08:23 PM
  4. [ Solved ]Cần hướng dẫn về bài tập màng!!
    Gửi bởi itthuyloi 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: 03-06-2008, 03:00 PM
  5. [ Solved ]Sắp xếp hai dãy số
    Gửi bởi thuchanh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 20-04-2008, 11:47 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