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

Đề tài: Thuật toán lính canh trong tìm số hoàn thiện lớn nhất. Mọi người xem code đã tối ưu chưa?

  1. #1
    Ngày gia nhập
    09 2011
    Bài viết
    26

    Mặc định Thuật toán lính canh trong tìm số hoàn thiện lớn nhất. Mọi người xem code đã tối ưu chưa?

    Lúc nãy em thắc mắc có tiêu đề rõ ràng mà bị admin move sang thùng rác. Em ko cố ý spam bài đâu. Mọi người xem thử code em có tối ưu chưa? Em mới học đặt lính canh và đây là bài tập đầu nên không rõ lắm.
    Code:
    #include <stdio.h>
    void main()
    {
    	int n,max,S=0;
    	printf("\n Nhap n: ");
    	scanf("%d", &n);
    	for (int i=1; i<n; i++)
    	{
    		if(n%i==0)
    			max=i;
    		break;
    	}
    	for (int i=1;i<n;i++)
    	{
    		if(n%i==0 && i>max)
    			max=i;
    	}
    	printf("\n So hoan thien lon nhat la: %d \n", max);
    
    }

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

    Bài của bạn hình như là tìm ước số lớn nhất thì phải.
    Code:
    #include "stdio.h"
    #include "conio.h"
    
    
    void main()
    {
    	int n,max,S=0;
    	printf("\n Nhap n: ");
    	scanf("%d", &n);
    	max = 1;
    	for (int i=1;i<n;i++)
    	{
    		if(n%i==0 && i>max)
    			max=i;
    	}
    	printf("\n Uoc so lon nhat la: %d \n", max);
    
    }

  3. #3
    Ngày gia nhập
    08 2011
    Nơi ở
    /pentest
    Bài viết
    44

    vòng lặp for 1 khi i = 1 n sẽ chia hết cho 1 nên max = 1 sau đó break luôn, thoát khỏi vòng for 1 max = 1.

    vòng lặp for 2 sẽ tìm max là ước lớn nhất của n.

    code chả liên quan tới đề hì.

  4. #4
    Ngày gia nhập
    09 2011
    Bài viết
    26

    Lúc nãy code nhầm. vẫn cái đề như trên chứ ko phải là tìm ước lớn nhất,
    Code:
    #include <stdio.h>
    void main()
    {
    	printf("\n Day la chuong trinh kiem tra so hoan thien lon nhat nho hon n.");
    	int n,max,S=0,i,j;
    	printf("\n Nhap n: ");
    	scanf("%d", &n);
    	for (i=1;i<n;i++)
    	{
    		for (j=1;j<i;j++)
    		{
    			if(i%j==0)
    				S=S+j;
    			if(S==i)
    				max=i;
    				break;
    		}
    		break;
    	}
    	for (i=1;i<n;i++)
    	{
    		for (j=1;j<i;j++)
    		{
    			if(i%j==0)
    				S=S+j;
    			if(S==i && max<i)
    				max=i;
    		}
    	}
    	printf("\n So hoan thien lon nhat la: %d", max);
    }
    Vẫn không ra. mong mọi người chỉ giúp!

  5. #5
    Ngày gia nhập
    08 2011
    Nơi ở
    /pentest
    Bài viết
    44

    C Code:
    1.     for (i=1;i<n;i++)
    2.     {
    3.         for (j=1;j<i;j++)
    4.         {
    5.             if(i%j==0)
    6.                 S=S+j;
    7.             if(S==i)
    8.                 max=i;
    9.                 break;
    10.         }
    11.         break;
    12.     }
    Chỉ xét ở vòng lặp này khi i = 1 và j = 1 thì j%i = 0 -> S = 0+1 = 1 lúc này S = i = 1 -> max = 1 tới lênh break thoát khỏi vòng lặp chỉ số j sau đó tới break thoát luôn khỏi vòng lặp chỉ số i -> bạn sử dụng break kiểu sướng thì dùng

    Mình góp ý một chút khi tìm số hoàn thiện lớn nhất nhở hơn n thì trước hết phải xây dựng hàm kiểm tra xem một số có phải là số hoàn thiện không đã (cái này search trong diễn đàn) sau đó thực hiện một vòng lặp cho i : n-1->1 nếu là số hoàn thiện thì break luôn:

    C Code:
    1. #include <stdio.h>
    2. int main() {
    3.   // nhập n;
    4.   for (int i = n-1; i >= 1; --i)
    5.     if(isPerfect(i)) {
    6.       maxPerfectNum = i;
    7.       break;
    8.     }
    9.   // do something
    10.   return 0;
    11. }
    Đã được chỉnh sửa lần cuối bởi meterpreter : 24-09-2011 lúc 10:37 AM. Lý do: chỉnh i<=1 thành i>=1 vòng for

  6. #6
    Ngày gia nhập
    09 2011
    Bài viết
    26

    Mặc định Thuật toán lính canh trong tìm số hoàn thiện lớn nhất. Mọi người xem code đã tối ưu chưa?

    C Code:
    1. #include<stdio.h>
    2. void nhap(int &n)
    3. {
    4.     printf("Nhap n: ");
    5.     scanf("%d", &n);
    6. }
    7.  
    8. int kiemtrahoanthien(int n)
    9. {
    10.     int S=0,flag=0;
    11.     for(int i=1;i<n;i++)
    12.     {
    13.         if(n%i==0)
    14.             S=S+i;
    15.     }
    16.     if(S==n)
    17.         flag=1;
    18.         return flag;
    19. }
    20.  
    21. int kiemtra_hoanthien_dautien(int n)
    22. {
    23.     for(int i=1;i<n;i++)
    24.     {
    25.         int kq=kiemtrahoanthien(i);
    26.         if(kq==1)
    27.             return i;
    28.     }
    29. }
    30.  
    31. int hoanthien_lonnhat(int n)
    32. {
    33.     int max=kiemtra_hoanthien_dautien(n);
    34.     for(int i=1;i<n;i++)
    35.     {
    36.         int kq=kiemtrahoanthien(i);
    37.         if (kq==1 && max<i)
    38.             max=i;
    39.     }
    40.     return max;
    41. }
    42.  
    43. void xuat(int max)
    44. {
    45.     printf("\n hoan thien lon nhat la: %d", max);
    46. }
    47.  
    48. void main()
    49. {
    50.     int n;
    51.     nhap(n);
    52.     int kq=hoanthien_lonnhat(n);
    53.     xuat(kq);
    54. }
    Cuối cùng cũng đã làm được. Mọi người xem thử code này có tối ưu chưa?
    Đã được chỉnh sửa lần cuối bởi vtd93 : 23-09-2011 lúc 06:21 PM.

  7. #7
    Ngày gia nhập
    08 2011
    Nơi ở
    /pentest
    Bài viết
    44

    Bài của bạn trên mình thấy vẫn chưa tối ưu, ở chỗ trong hàm kiểm tra nguyên tố bạn có thể kiểm tra điều kiện của S ngay ở vòng for :
    for(int i=1;i<n;i++)
    Nếu mà làm theo cách của mình ở trên thì chương trình của bạn sẽ ngắn hơn và có vẻ sẽ tối ưu hơn mình tes thử với số 100.000 trên code::block 10.05 gcc compile của bạn mất khoảng 35s của mình mất khoảng 32s.

    Đây là code của mình:
    C Code:
    1. #include <stdio.h>
    2. int isPerfect(int n)
    3. {
    4.   int j,sum = 0;
    5.   for (j = 1; sum<=n && j<n; ++j)
    6.     if (n%j == 0)
    7.       sum += j;
    8.   if (sum == n)
    9.     return 1;
    10.   else return 0;
    11. }
    12. int main() {
    13.   int n,i, maxPerfectNum = -1;
    14.   printf("n = "); scanf("%d", &n);
    15.   for (i = n-1; i >= 1; --i)
    16.     if(isPerfect(i)) {
    17.       maxPerfectNum = i;
    18.       break;
    19.     }
    20.   if (maxPerfectNum == -1)
    21.     printf("no perfect number.\n");
    22.   else printf("max perfectnumber is %d", i);
    23.   return 0;
    24. }
    We are oft to blame in this...'Tis too much proved.
    - That with devotion's visage and pious action we do sugar o'er the devil himself.

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

    Trích dẫn Nguyên bản được gửi bởi meterpreter Xem bài viết
    Bài của bạn trên mình thấy vẫn chưa tối ưu, ở chỗ trong hàm kiểm tra nguyên tố bạn có thể kiểm tra điều kiện của S ngay ở vòng for :


    Nếu mà làm theo cách của mình ở trên thì chương trình của bạn sẽ ngắn hơn và có vẻ sẽ tối ưu hơn mình tes thử với số 100.000 trên code::block 10.05 gcc compile của bạn mất khoảng 35s của mình mất khoảng 32s.

    Đây là code của mình:
    C Code:
    1. #include <stdio.h>
    2. int isPerfect(int n)
    3. {
    4.   int j,sum = 0;
    5.   for (j = 1; sum<=n && j<n; ++j)  // sum=n lại dư ra lần lặp nữa và j-->>sqrt(n) thì sao.
    6.     if (n%j == 0)                         // thử với n=6
    7.       sum += j;                           // j=1 -->sum=1 <=6  || j=2-->sum=3<=6 ||j=3--<sum=6<=6
    8.                                               //(j=3<6) lại tiếp j=4 sum=6 ; j=5 thoát ( LẢNG PHÍ thêm lần lặp)
    9.   if (sum == n)
    10.     return 1;
    11.   else return 0;
    12. }
    Nếu quả bạn bắt lỗi đến như vậy thì mình nghỉ vẫn chưa tối ưu hoàn toàn. mình chỉ nghĩ đến đấy không biết còn tối ưu hơn nữa không

  9. #9
    Ngày gia nhập
    08 2011
    Nơi ở
    /pentest
    Bài viết
    44

    @Ghost: Nothings

    C++ Code:
    1. bool perfect(int n)
    2. {
    3.     if (n > 496)
    4.         return n == 8128 || n == 33550336;
    5.     return n == 6 || n == 28 || n == 496;
    6. }

  10. #10
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi meterpreter Xem bài viết
    @Ghost: Nothings

    C++ Code:
    1. bool perfect(int n)
    2. {
    3.     if (n > 496)
    4.         return n == 8128 || n == 33550336;
    5.     return n == 6 || n == 28 || n == 496;
    6. }
    hihi, code này thì tối ưu miễn chê luôn =))

    @Ghost: Code tính toán nghiêm chỉnh thì mình thử tối ưu thêm 1 chút đây:
    C Code:
    1. int isPerfect(int n)
    2. {
    3.     int j, jmax = 0.1 + sqrt(n);
    4.     int sum = (n == jmax*jmax ? 1 - jmax : 1);  // n là số chính phương?
    5.     for (j = 2; j <= jmax; ++j)
    6.         if (n%j == 0)
    7.             if ((sum += j + n/j) > n) return 0;
    8.     return sum == n;
    9. }

    Chạy thử so với code trước thì kết quả đo trên máy mình là 94ms (mới) / 23406ms (cũ) với n = 100000

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

  1. Lập trình C Bài toán in ra 2 tam giác đổi đỉnh ( đặc) - đã có thuật toán nhưng chưa hoàn thiện code. Xin được góp ý!
    Gửi bởi harrybui1910 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 22
    Bài viết cuối: 08-08-2012, 12:32 PM
  2. Canh hàng code tự động trong Visual C++?
    Gửi bởi quangphuoc00 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 3
    Bài viết cuối: 18-07-2012, 03:11 PM
  3. Liền kề Vân Canh HUD - Biệt thự Vân Canh HUD - ĐÃ XÂY THÔ HOÀN THIỆN CHỈ - BÁN GIÁ GỐC
    Gửi bởi dangmailinh 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: 23-05-2012, 02:29 PM
  4. Thuật toán Chu-Liu/Edmonds trong cây phủ tối thiểu
    Gửi bởi dthanb trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 13-12-2011, 05:07 PM
  5. code tìm cây có trọng lượng nhỏ nhất bằng giải thuật prim-cách chạy tay code này
    Gửi bởi ruacon_206 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: 25-04-2011, 02:27 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