Tối ưu hóa thuật toán

Tiêu đề: Tối ưu hóa thuật toán Wed Sep 01, 2010 11:54 pm

đây là bài toán số hữu nghị.chạy đc nhưng quá là nhậm
mọi người nghĩ cách tối ưu nó nha
#include<conio.h>
#include<iostream.h>
int tongUocSo(int n)
{
int s=0;
for(int i=1;i<n;i++)
if(n%i==0) s+=i;
return s;
}
int main()
{
int a,b;
int i,j;
do{
cout<<"nhap [a,b]:"<<"\n";
cin>>a>>b;
if(a<b) break;
else cout<<"nhap lai";
}while(1);
cout<<"cac cap so huu nghi:";
for(i=a;i<=b;i++)
for(j=i+1;j<=b;j++)
if(i==tongUocSo(j)&&j==tongUocSo(i))
cout<<'('<<i<<','<<j<<')';
getch();
}

Tiêu đề: Re: Tối ưu hóa thuật toán Thu Sep 02, 2010 6:20 am

p va q là hai số hữu nghị khi: tongUoc(p)==q||tongUoc(q)=p chứ
p=tongUoc(q)=>p>q
và q=tongUoc(p)=>q>p====>vô lý

nhớ nhầm

Tiêu đề: [a,b] Thu Sep 02, 2010 6:23 am

xin bổ xung đây là tìm số hữu nghị trong khoảng [a,b]
và 2 số đc gọi là hữu nghị khị tổng ước số của số này bằng số kia và ngược lại(ước không bao gồm chính nó nhưng gồm 1)
bài này mình chạy thử cho kết quả chính xác nhưng chậm do vòng lặp.mọi người nghĩ cách khác tối ưu hơn

Tiêu đề: Re: Tối ưu hóa thuật toán Thu Sep 02, 2010 9:17 am

Thử cách này xem sao
Đảm bảo nhanh hơn nhiều:

#include<conio.h>
#include<iostream.h>
int tongUocSo(int n)
{
int s=0;
for(int i=1;i<n;i++)
if(n%i==0) s+=i;
return s;
}
int main()
{
int a,b;
int i,j;
do{
cout<<"nhap [a,b]:"<<"\n";
cin>>a>>b;
if(a<b) break;
else cout<<"nhap lai";
}while(1);
int*A=new int[b-a+1];
for(i=a;i<=b;i++)
A[i]=tongUocSo(i);
cout<<"cac cap so huu nghi:";
for(i=a;i<=b;i++)
for(j=i+1;j<=b;j++)
if(i==A[j]&&j==A[i])
cout<<'('<<i<<','<<j<<')';
getch();
}

Tiêu đề: Re: Tối ưu hóa thuật toán Sat Sep 04, 2010 8:37 pm

đề nghị admin đọc kĩ lại định nghĩa nhá Very Happy

.cách của hưng là rất chuẩn.nhanh hơn rất nhiều.
VIỆC KHAI BÁO THÊM 1 MẢNG A LÀ RẤT HAY.BRAVO

Tiêu đề: Re: Tối ưu hóa thuật toán Sun Sep 05, 2010 1:20 am

Kết quả:
Ttrong đoạn: [1;9999] có 5 cặp số hữu nghị:
(220,284);(1184,1210);(2620,2924);(5020,5564);(6232,6368)

Tiêu đề: Re: Tối ưu hóa thuật toán Sun Sep 05, 2010 9:30 am

ec nham nhot mot teo
ba con thong cam

Tiêu đề: Re: Tối ưu hóa thuật toán Sun Sep 26, 2010 11:43 pm

Không biết phần truyền theo trị, con trỏ, tham biến có phải là tối ưu hóa thuật toán ko
Mọi người có kinh nghiệm phần này vào chia sẻ nhỉ

Đoạn code hôm trước tôi sửa lại như sau có tối ưu đc chút nào ko ?

#include<iostream>
#include<conio.h>
#include<iomanip>
#include<string.h>
using namespace std;

struct SV{
char ht[25];
char ms[10];
float diem;
};
typedef struct node{
SV info;
struct node *next;
struct node *prev;
}*Node;

Node Head;

//Khoi tao nut moi
Node Khoitao(SV &x)
{
Node p=new struct node;
p->info=x;
p->next=NULL;
p->prev=NULL;
return p;
}
//Kiem tra danh sach rong
int IsEmpty()
{
if(Head==NULL) return 1;
return 0;
}
//Them sv vao cuoi danh sach
void Add_last(SV &x)
{
Node p;
p=Khoitao(x);
if(IsEmpty())
{
Head=p;
p->next=Head;
p->prev=Head;
cout<<" Day la sinh vien dau tien\n";
}
else
{
p->next=Head;
p->prev=Head->prev;
Head->prev->next=p;
Head->prev=p;
cout<<" Da them thanh cong\n";
}
}
//Tìm kiếm sinh vien
void Find(char name[25])
{
Node sv=Head;
int count=0;
if(IsEmpty())
cout<<"\n Khong tim thay";
else
{
cout<<"\n "<<setw(25)<<"HO TEN"<<setw(10)<<"MSSV"<<setw(8 )<<"DIEM";
while(sv->next!=Head)
{
if(strcmp(sv->info.ht,name)==0)
{
cout<<"\n+"<<setw(25)<<sv->info.ht<<setw(10)<<sv->info.ms<<setw(8 )<<sv->info.diem;
count++;
}
sv=sv->next;
}
if(strcmp(Head->prev->info.ht,name)==0)
{
cout<<"\n+"<<setw(25)<<sv->info.ht<<setw(10)<<sv->info.ms<<setw(8 )<<sv->info.diem;
count++;
}
if(!count) cout<<"\n Khong tim thay";
}
}
//Xoa sinh vien
void Delete(char mssv[10])
{
Node p,q;
p=Head;
if(IsEmpty())
{
cout<<"\n Danh sach rong";
return;
}
else
{
if(strcmp(p->info.ms,mssv)==0)
{
q=p->next;
if(q==Head) Head=NULL;
else
{
p->prev->next=q;
q->prev=p->prev;
Head=q;
}
delete p;
cout<<"\n Xoa thanh cong";
return;
}
while(1)
{
p=p->next;
if(strcmp(p->info.ms,mssv)==0)
{
q=p->next;
p->prev->next=q;
q->prev=p->prev;
delete p;
cout<<"\n Xoa thanh cong";
}break;
}
}
}
//Nhap thong tin sinh vien
void Nhap()
{
SV x;
cout<<"\n Nhap thong tin ve sinh vien";
cout<<"\n Nhap '123' de hoan thanh\n";
do{
cout<<"\n+Ho ten: ";
cin.ignore(1);
cin.get(x.ht,25);
if(strcmp(x.ht,"123")==0) break;
cout<<" MSSV: ";
cin.ignore(1);
cin.get(x.ms,10);
cout<<" Diem: ";
cin>>x.diem;
Add_last(x);
}while(1);
}
//Hien thi thong tin sinh vien
void Hienthi()
{
Node sv=Head;
if(IsEmpty())
{
cout<<"\n Danh sach rong";
return;
}
cout<<"\n THONG TIN SINH VIEN";
cout<<setiosflags(ios::fixed)<<setprecision(2);
cout<<"\n"<<setw(25)<<"HO TEN"<<setw(10)<<"MSSV"<<setw(8 )<<"DIEM";
while(sv->next!=Head)
{
cout<<"\n+"<<setw(25)<<sv->info.ht<<setw(10)<<sv->info.ms<<setw(8 )<<sv->info.diem;
sv=sv->next;
}
if(sv->next=Head)
cout<<"\n+"<<setw(25)<<sv->info.ht<<setw(10)<<sv->info.ms<<setw(8 )<<sv->info.diem;
}
int main()
{
Head=new struct node;
Head=NULL;
char chon,mssv[10],name[25];
while(1)
{
cout<<"\n -----------MENU--------------";
cout<<"\n 1.Hien thi danh sach sinh vien";
cout<<"\n 2.Them sinh vien vao danh sach";
cout<<"\n 3.Tim kiem sinh vien";
cout<<"\n 4.Xoa sinh vien";
cout<<"\n 5.Xoa man hinh";
cout<<"\n 6.Exit";
cout<<"\n\n Chon chuc nang: ";
cin>>chon;
switch(chon)
{
case '1': Hienthi();break;
case '2': Nhap();break;
case '3':
cout<<"\n Nhap ten sinh vien: ";
cin.ignore(1);
cin.get(name,25);
Find(name);break;
case '4':
cout<<"\n Nhap MSSV: ";
cin.ignore(1);
cin.get(mssv,10);
Delete(mssv);break;
case '5': system("cls");break;
case '6': exit(0);break;
default: cout<<"\n Khong co chuc nang nay";break;
}
}
_getch();
}

Tiêu đề: Re: Tối ưu hóa thuật toán Wed Sep 29, 2010 5:02 am

tớ đóng góp tý nha.
tớ thấy bài số hưu nghi còn có thể cải tiến để chạy nhanh hơn
bài của hưng là rất ok.minh muốn cải tiến thêm chỗ này
for(i=a;i<=b;i++)
for(j=i+1;j<=b;j++)
if(i==A[j]&&j==A[i])
cout<<'('<<i<<','<<j<<')';
getch();
}

chỗ này mình có thẻ cải tiến để giảm được 1 vong for tốc độ sẽ tăng đáng kể
for (i=a;i<=b;i++)
if((a[i]>i)&&(a[i]<=b)&&(a[a[i]]==i))
cout<<"("<<i<<","<<a[i]<<")";
getch();
}

va cho nay nua sẽ giảm đi được một nua số công việc phải làm
for(int i=1;i<n;i++)
if(n%i==0) s+=i;
return s;
}

mình cải tiến thêm tý nha

for(int i=1;i<=n/2;i++)
if(n%i==0) s+=i;
return s;
}

Tiêu đề: Re: Tối ưu hóa thuật toán Thu Apr 14, 2011 8:47 pm

mình công nhận cái này rất hay, nói chung mình tham khảo từ trên xuống các bạn đưa ra ý kiến và đóng góp bổ sung cho nhau, mình thấy thuật ngữ này rất hữu ích cho người khi đọc được cái này đó . mình thanks các bạn nhiều nha hiiii cheers

Mua ban |
Dien thoai di dong
May tinh xach tay

» Bài tập Kĩ thuật lập trình
» toán tử trong C++
» toán rời rạc- nghia dai ca