PDA

View Full Version : 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?



vtd93
21-09-2011, 10:13 PM
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.

#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);

}

tuvan1011
21-09-2011, 10:41 PM
Bài của bạn hình như là tìm ước số lớn nhất thì phải.

#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);

}

meterpreter
21-09-2011, 11:09 PM
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ì.

vtd93
21-09-2011, 11:20 PM
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,

#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!

meterpreter
21-09-2011, 11:55 PM
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;
}
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:


#include <stdio.h>
int main() {
// nhập n;
for (int i = n-1; i >= 1; --i)
if(isPerfect(i)) {
maxPerfectNum = i;
break;
}
// do something
return 0;
}

vtd93
23-09-2011, 11:36 AM
#include<stdio.h>
void nhap(int &n)
{
printf("Nhap n: ");
scanf("%d", &n);
}

int kiemtrahoanthien(int n)
{
int S=0,flag=0;
for(int i=1;i<n;i++)
{
if(n%i==0)
S=S+i;
}
if(S==n)
flag=1;
return flag;
}

int kiemtra_hoanthien_dautien(int n)
{
for(int i=1;i<n;i++)
{
int kq=kiemtrahoanthien(i);
if(kq==1)
return i;
}
}

int hoanthien_lonnhat(int n)
{
int max=kiemtra_hoanthien_dautien(n);
for(int i=1;i<n;i++)
{
int kq=kiemtrahoanthien(i);
if (kq==1 && max<i)
max=i;
}
return max;
}

void xuat(int max)
{
printf("\n hoan thien lon nhat la: %d", max);
}

void main()
{
int n;
nhap(n);
int kq=hoanthien_lonnhat(n);
xuat(kq);
}
Cuối cùng cũng đã làm được. Mọi người xem thử code này có tối ưu chưa?

meterpreter
24-09-2011, 10:35 AM
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:

#include <stdio.h>
int isPerfect(int n)
{
int j,sum = 0;
for (j = 1; sum<=n && j<n; ++j)
if (n%j == 0)
sum += j;
if (sum == n)
return 1;
else return 0;
}
int main() {
int n,i, maxPerfectNum = -1;
printf("n = "); scanf("%d", &n);
for (i = n-1; i >= 1; --i)
if(isPerfect(i)) {
maxPerfectNum = i;
break;
}
if (maxPerfectNum == -1)
printf("no perfect number.\n");
else printf("max perfectnumber is %d", i);
return 0;
}

ghost.love
24-09-2011, 11:47 PM
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:

#include <stdio.h>
int isPerfect(int n)
{
int j,sum = 0;
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.
if (n%j == 0) // thử với n=6
sum += j; // j=1 -->sum=1 <=6 || j=2-->sum=3<=6 ||j=3--<sum=6<=6
//(j=3<6) lại tiếp j=4 sum=6 ; j=5 thoát ( LẢNG PHÍ thêm lần lặp)
if (sum == n)
return 1;
else return 0;
}

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

meterpreter
25-09-2011, 12:26 AM
@Ghost: Nothings


bool perfect(int n)
{
if (n > 496)
return n == 8128 || n == 33550336;
return n == 6 || n == 28 || n == 496;
}

fbchicken
25-09-2011, 12:39 AM
@Ghost: Nothings


bool perfect(int n)
{
if (n > 496)
return n == 8128 || n == 33550336;
return n == 6 || n == 28 || n == 496;
}

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:

int isPerfect(int n)
{
int j, jmax = 0.1 + sqrt(n);
int sum = (n == jmax*jmax ? 1 - jmax : 1); // n là số chính phương?
for (j = 2; j <= jmax; ++j)
if (n%j == 0)
if ((sum += j + n/j) > n) return 0;
return sum == n;
}


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

meterpreter
25-09-2011, 01:10 AM
bool perfect(int n)
{
if (n > 496) // n là số nguyên có dấu 32 bit
return n == 8128 || n == 33550336;
return n == 6 || n == 28 || n == 496;
}

Code này ko thể gọi là tối ưu được. Đây chỉ hoàn toàn là một sự khôn lỏi thôi, 33550336 là số hoàn hảo thứ 5, số 6 code này ko tính được, tất nhiên là nếu tìm số hh dưới số hh thứ 5 thì cái này chạy ko cái nào sánh kịp chỉ có hạn chế là ko thể tìm số lơn hơn số hh thứ 5 thôi. Các code trên chạy với n = 100.000.000 thì die cả loạt :D

vtd93
25-09-2011, 12:43 PM
Chà mấy anh chị bàn luận sôi nổi quá. Em mới học C thôi nên chắc ngâm cứu code mấy ac trước mới hiểu được chứ đọc sơ qua chẳng hiểu gì mấy. Phải lấy giấy ra chạy mới được. hihi

ghost.love
25-09-2011, 03:55 PM
@Ghost: Nothings


bool perfect(int n)
{
if (n > 496)
return n == 8128 || n == 33550336;
return n == 6 || n == 28 || n == 496;
}

Nói thực là HỌC THUỘC GIỎI NHỈ. Vậy theo mình nghỉ thì thật tốt nếu bạn viết 1 chương trình sẳn in 1 mảng số hoàn hảo từ 0-> 1000000000000000 rồi làm theo cách của bạn. in ra khi người dùng nhập trong khoảng đó. Đó là cách tối ưu hơn cách của bạn.
Vấn đề là mình chỉ suy nghỉ giải thuật là đúng. cách tối ưu thì hãy khoan suy nghỉ đã vì mình chưa đến trình độ tối ưu code. vậy nên mình mới BẺ cậu thôi. kekkkê có gì Xin LƯỢNG THỨ,:D