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ính nhanh bình phương của một số có n chữ số 1, với n <= 1triệu

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

    Mặc định Tính nhanh bình phương của một số có n chữ số 1, với n <= 1triệu

    Đề bài :
    Mình dùng 2 vòng for lòng nhau để tính, nhưng kết quả khi test trên http://www.spoj.pl là chạy chậm. Có cách nào để tính nhanh kết quả khi tính bình phương ?

    Code:
    Cho số S = 111...11 (n chữ số 1, hệ thập phân), tính S2.
    
    Input
    
    - Dòng đầu tiên: số lượng test k (k<=40).
    
    - k dòng tiếp, mỗi dòng ghi số n - số lượng chữ số 1 của S. (1 <= n <= 1000000)
    
    Output
    
    - Với mỗi test ghi kết quả trên 1 dòng.
    
    Example
    
    Input:
    2
    1
    2
    
    Output:
    1
    121

    code của mình

    Code:
    void Nhan(long n)
    {
    	long *a = new long[MAX];
    	long *b = new long[MAX];
    	for(long i=0; i<n; i++)
    		a[i] = 1;
    	for(long i=0; i<n*2-1; i++)
    		b[i] = 0;
    	for(long i=0; i<n; i++)
    	{
    		int d=0, sum =0;
    		for(long j=0; j<n; j++)
    		{
    			sum = b[i+j] + a[j] + d;
    			if(sum > 9)
    			{
    				d=sum / 10;
    				sum = sum % 10;				
    			}
    			else
    			{
    				d=0;
    			}
    			b[i + j] = sum;
    		}
    	}
    	
    }

  2. #2
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Tìm quy luật của số kết quả xem:
    C Code:
    1.      1 * 1      =      1
    2.     11 * 11     =     121
    3.    111 * 111    =    12321
    4.   1111 * 1111   =   1234321
    5.  11111 * 11111  =  123454321
    6. 111111 * 111111 = 12345654321
    7.  
    8.   11
    9.  *
    10.   11
    11.  ___
    12.  11
    13. 11
    14. ___
    15. 121
    16.  
    17.    111
    18.   *
    19.    111
    20.    ___
    21.   111
    22.  111
    23. 111
    24. ______
    25. 12321
    26.  
    27.      1111
    28.     *
    29.      1111
    30.      ___
    31.     1111
    32.    1111
    33.   1111
    34.  1111
    35. _______
    36. 1234321
    Đã được chỉnh sửa lần cuối bởi doicanhden : 28-11-2012 lúc 01:15 PM.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

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

    mình thấy qui luật đến 9 thôi, qua 10 là hết rồi
    vd:
    8: => 123456787654321
    9 = > 12345678987654321
    nhưng
    10: => 1234567900987654321
    12: => 12345679012320987654321

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

    Tui thấy tuy qua 9 nó vẫn có quy luật riêng, và số dài bao nhiêu đi nữa nó vẫn có quy luật, và hàm giải ở đây chỉ cần 1 hàm cộng chuỗi là đủ

  5. #5
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,007

    [void Nhan(long n)
    {
    long *a = new long[MAX];
    long *b = new long[MAX];
    for(long i=0; i<n; i++)
    a[i] = 1;
    for(long i=0; i<n*2-1; i++)
    b[i] = 0;
    for(long i=0; i<n; i++)
    {
    int d=0, sum =0;
    for(long j=0; j<n; j++)
    {
    sum = b[i+j] + a[j] + d;
    if(sum > 9)
    {
    d=sum / 10;
    sum = sum % 10;
    }
    else
    {
    d=0;
    }
    b[i + j] = sum;
    }
    }

    }
    Code của bạn hơi thô sơ, nhập 1 triệu vào ko bít có sống ko?
    ^_,^

    Facebook : https://www.facebook.com/langmaninternet

    Bùi Tấn Quang

  6. #6
    Ngày gia nhập
    01 2010
    Bài viết
    306

    Mặc định Tính nhanh bình phương của một số có n chữ số 1, với n <= 1triệu

    Trích dẫn Nguyên bản được gửi bởi langman Xem bài viết
    Code của bạn hơi thô sơ, nhập 1 triệu vào ko bít có sống ko?
    O(n^2), sống bằng niềm tin :((

    Chủ thớt làm theo hướng này xem sao
    VD nhé : tính 111111^2:
    111111 * 111111 = (111000 + 111)*(111000 + 111) = 111000*111000 + 2*111000*111 + 111*111
    = 111*111* 1000000 + 2 * 111 * 111 * 1000 + 111*111
    => Ta đã hạ cấp từ phép bình phương số có 6 chữ số xuống phép bình phương số có 3 chữ số.

    Trường hợp số chữ số là số lẻ thì có thể làm thế này, hạ nó xuống 1 cấp:
    (11111*11111) = (10000+1111)*(10000+1111)

    => Thuật toán : Nếu n nhận vào quá lớn thì áp dụng thuật toán để chuyển xuống tính với n/2, n/4 ....v...v... cho đến khi n là đủ nhỏ để có thể tính đc, hoặc đơn giản nhất là chỉ dừng lại khi n<10
    Có thể thấy là thuật toán có độ phức tạp tỷ lệ với n log2(n)

  7. #7
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    http://vn.spoj.com/problems/MULONE/
    Bài này chỉ print thôi mà

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  8. #8
    Ngày gia nhập
    01 2010
    Bài viết
    306

    Trích dẫn Nguyên bản được gửi bởi hunterphu Xem bài viết
    http://vn.spoj.com/problems/MULONE/
    Bài này chỉ print thôi mà
    print thế nào cậu bày giúp với Từ 10 trở lên, mình nhìn chả thấy nó có cái qui luật gì sất => chỉ biết làm cách chia đôi chiều dài của nó rồi tính tiếp

  9. #9
    Ngày gia nhập
    04 2012
    Bài viết
    42

    Mình search được công thức + mã nguồn . Và dưới đây là công thức đó. Hy vọng giúp được chủ thớt.

    PHP Code:
    1. { 11..1^2 (n chso1)=(99..9/9)^2=((10^n-1)/9)^2
    2.                    = (10^2n-2*10^n+1)/81        
    3.                    =  99..980001 /81
    4.                   ( n-1 chso 9, n-1 chso 0 )    
    5.                                                }
    C Code:
    1. while (!silly)
    2.     cout<<"Study everything !";

  10. #10
    Ngày gia nhập
    01 2010
    Bài viết
    306

    Trích dẫn Nguyên bản được gửi bởi kimlama Xem bài viết
    Mình search được công thức + mã nguồn . Và dưới đây là công thức đó. Hy vọng giúp được chủ thớt.

    PHP Code:
    1. { 11..1^2 (n chso1)=(99..9/9)^2=((10^n-1)/9)^2
    2.                    = (10^2n-2*10^n+1)/81        
    3.                    =  99..980001 /81
    4.                   ( n-1 chso 9, n-1 chso 0 )    
    5.                                                }
    Ra vậy, hóa ra là phải nhân nó với 9. Túm lại là phải ngồi thực hiện 1 phép chia số lớn. Cái này thì đúng là O(n) rồi
    Mấy cậu cứ biểu là có qui luật, có qui luật, nhưng nhìn vào mấy cái kết quả muốn mờ mắt luôn mà có cái qui luật nào đâu

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

  1. Cùng HK đón tết nào........... Nhanh Nhanh
    Gửi bởi hoang201222 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 21-01-2013, 03:39 PM
  2. Nhanh tay nhanh mắt nhanh chân>"<
    Gửi bởi hoang201222 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 05-01-2013, 09:35 AM
  3. Thiết kế nhanh, in nhanh Brochure, Folder
    Gửi bởi hocbongvnh trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 17-01-2012, 02:22 PM
  4. Thiết kế website rẻ nhanh và chuyên nghiệp với đăng ký tên miền nhanh chóng
    Gửi bởi minhq9 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 24-11-2011, 03:35 PM
  5. Bài này khó đây, Cứu nhanh nhanh.
    Gửi bởi CNTT tưởng dễ hóa khó trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 9
    Bài viết cuối: 26-07-2007, 09:29 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