SLIDE1

Saturday, January 31, 2015

[oop c++] bài tập về doanh thu bán hàng, thuế, số lượng, giá tiền

[oop c++] bài tập về doanh thu bán hàng, thuế, số lượng, giá tiền
viết chương trình theo phong cách hướng đối tượng c++ thiết kế chuong trình nhập vào số lượng hồ sơ bán ra với giá à có thuế hay khong thì tùy nhập vào. xuất ra thông tin đã nhập và tính tổng doanh thu bán hàng. với thuế có 2 loại là 7% hoặc 8%. đồng thời thiết kế chương trình theo phương pháp enu lựa chọn.
bài này mình chia ra làm nhiều fle nhỏ để dễ quản lý và viết code hơn.


[oop c++] tính chu vi, diện tích, tọa đô trọng tâm, trực tâm

[oop c++] tính chu vi, diện tích, tọa đô trọng tâm, trực tâm của tam giác nhập vào tọa độ 3 đỉnh

#include<iostream>
using namespace std;
class diem
{
private:
float x,y;
public:
diem(void);
~diem(void);
float getx();
float gety();
void nhapdiem();
void xuatdiem();
float tinhkhoangcach(diem);
};
diem::diem(void)
{
}
diem::~diem(void)
{
}
float diem::getx()
{
return x;
}
float diem::gety()
{
return y;
}
void diem::nhapdiem()
{
cout<<"hoanh do: ";cin>>x;
cout<<"tung do: ";cin>>y;
}
void diem::xuatdiem()
{
cout<<"("<<x<<" , "<<y<<")";
}
float diem::tinhkhoangcach(diem b)
{
return sqrt(pow((x-b.x),2)+pow((y-b.y),2));
}
class tamgiac
{
private:
diem a,b,c;
public:
tamgiac(void);
~tamgiac(void);
void nhaptamgiac();
void xuattamgiac();
float tinhchuvi();
float tinhdientich();
void diemtrongtam();
void diemtructam();
};
tamgiac::tamgiac(void)
{
}
tamgiac::~tamgiac(void)
{
}
void tamgiac::nhaptamgiac()
{
int kt;
do
{
kt=0;
float ab,ac,bc;
cout<<"\tnhap diem A:\n";
a.nhapdiem();
cout<<"\tnhap diem B:\n";
b.nhapdiem();
cout<<"\tnhap diem c:\n";
c.nhapdiem();
ab=a.tinhkhoangcach(b);
ac=a.tinhkhoangcach(c);
bc=b.tinhkhoangcach(c);
if(ab+ac<=bc || ab+bc<=ac || ac+bc<=ab)
{
cout<<"\n3 diem khong tao thanh am giac! nhap lai!\n\n";
kt=1;
}
}while(kt);
}
void tamgiac::xuattamgiac()
{
cout<<"\nA:";a.xuatdiem();
cout<<"\nB:";b.xuatdiem();
cout<<"\nC:";c.xuatdiem();
}
float tamgiac::tinhchuvi()
{
float ab,ac,bc;
ab=a.tinhkhoangcach(b);
ac=a.tinhkhoangcach(c);
bc=b.tinhkhoangcach(c);
return ab+ac+bc;
}
float tamgiac::tinhdientich()
{
float p=tinhchuvi()/2,ab,bc,ac;
ab=a.tinhkhoangcach(b);
ac=a.tinhkhoangcach(c);
bc=b.tinhkhoangcach(c);
return sqrt(p*(p-ab)*(p-ac)*(p-bc));
}
void tamgiac::diemtrongtam()
{
float x,y;
x=(a.getx()+b.getx()+c.getx())/3;
y=(a.gety()+b.gety()+c.gety())/3;
cout<<"("<<x<<" , "<<y<<")";
}
void tamgiac::diemtructam()
{
float dx,dy,d;
d=4*(b.getx()-b.getx())*(c.gety()-a.gety())-4*(c.getx()-a.getx())*(b.gety()-a.gety());
dx=(pow(b.getx(),2)+pow(b.gety(),2)-pow(a.getx(),2)-pow(a.gety(),2))*2*(c.gety()-a.gety())
-(pow(c.getx(),2)+pow(c.gety(),2)-pow(a.getx(),2)-pow(a.gety(),2))*2*(b.gety()-a.gety());
dy=(pow(c.getx(),2)+pow(c.gety(),2)-pow(a.getx(),2)-pow(a.gety(),2))*2*(b.getx()-a.getx())
-(pow(b.getx(),2)+pow(b.gety(),2)-pow(a.getx(),2)-pow(a.gety(),2))*2*(c.getx()-a.getx());
cout<<"("<<dx/d<<" , "<<dy/d<<")";
}
void main()
{
tamgiac t;
t.nhaptamgiac();
t.xuattamgiac();
cout<<"\nchu vi = "<<t.tinhchuvi();
cout<<"\ndien tich = "<<t.tinhdientich();
cout<<"\ndiem trong tam = ";t.diemtrongtam();
cout<<"\ndiem truc tam = ";t.diemtructam();
}

PHẠM VI LỚP VÀ TRUY CẬP CÁC THÀNH VIÊN LỚP C++

PHẠM VI LỚP VÀ TRUY CẬP CÁC THÀNH VIÊN LỚP C++
  • Các thành viên dữ liệu của một lớp (các biến khai báo trong định nghĩa lớp) và các hàm thành viên (các hàm khai báo trong định nghĩa lớp) thuộc vào phạm vi của lớp. 
  • Trong một phạm vi lớp, các thành viên của lớp được truy cập ngay lập tức bởi tất cả các hàm thành viên của lớp đó và có thể được tham chiếu một cách dễ dàng bởi tên. 
  • Bên ngoài một phạm vi lớp, các thành viên của lớp được tham chiếu thông qua hoặc một tên đối tượng, một tham chiếu đến một đối tượng, hoặc một con trỏ tới đối tượng.
  •  Các hàm thành viên của lớp có thể được đa năng hóa (overload), nhưng chỉ bởi các hàm thành viên khác của lớp.
  •  Để đa năng hóa một hàm thành viên, đơn giản cung cấp trong định nghĩa lớp một prototype cho mỗi phiên bản của hàm đa năng hóa, và cung cấp một định nghĩa hàm riêng biệt cho mỗi phiên bản của hàm.
  •  Các hàm thành viên có phạm vi hàm trong một lớp – các biến định nghĩa trong một hàm thành viên chỉ được biết tới hàm đó. 
  • Nếu một hàm thành viên định nghĩa một biến cùng tên với tên một biến trong phạm vi lớp, biến phạm vi lớp được dấu bởi biến phạm vi hàm bên trong phạm vi hàm. 
  • Như thế một biến bị dấu có thể được truy cập thông qua toán tử định phạm vi.
  •  Các toán tử được sử dụng để truy cập các thành viên của lớp được đồng nhất với các toán tử sử dụng để truy cập các thành viên của cấu trúc. 
  • Toán tử lựa chọn thành viên dấu chấm (.) được kết hợp với một tên của đối tượng hay với một tham chiếu tới một đối tượng để truy cập các thành viên của đối tượng. 
  • Toán tử lựa chọn thành viên mũi tên (->)được kết hợp với một con trỏ trỏ tới một truy cập để truy cập các thành viên của đối tượng. 
  • Ví dụ 3.4: Chương trình sau minh họa việc truy cập các thành viên của một lớp với các toán tử lựa chọn thành viên

1: #include <iostream.h> 
2:  
3: class Count 
4: {
5:     public:
6:     int X;
7:     void Print()
8:     {
9:         cout << X << endl; 
10:     } 
11: }; 
12: 
13: int main() 
14: { 
15:     Count Counter, //Tạo đối tượng Counter 
16:     *CounterPtr = &Counter, //Con trỏ trỏ tới Counter 
17:     &CounterRef = Counter; //Tham chiếu tới Counter 
18: 
19:     cout << "Assign7 to X and Print using the object's name: "; 
20:     Counter.X = 7; //Gán 7 cho thành viên dữ liệu X 
21:     Counter.Print(); //Gọi hàm thành viên Print 
22: 
23:     cout << "Assign 8 to X and Print using a reference: "; 
24:     CounterRef.X = 8; //Gán 8 cho thành viên dữ liệu X 
25:     CounterRef.Print(); //Gọi hàm thành viên Print 
26: 
27:     cout << "Assign 10 to X and Print using a pointer: "; 
28:     CounterPtr->X = 10; // Gán 10 cho thành viên dữ liệu X 
29:     CounterPtr->Print(); //Gọi hàm thành viên Print 
30:     return 0; 
31: }

Lớp CLASS trong C++ || Lập trình OOP

Các lớp cho phép lập trình viên mô hình các đối tượng mà có các thuộc tính (biểu diễn như các thành viên dữ liệu – Data members) và các hành vi hoặc các thao tác (biểu diễn như các hàm thành viên – Member functions). Các kiểu chứa các thành viên dữ liệu và các hàm thành viên được định nghĩa thông thường trong C++ sử dụng từ khóa class, có cú pháp như sau:  class <class-name> { <member-list> //Thân của lớp }; Trong đó: class-name: tên lớp. member-list: đặc tả các thành viên dữ liệu và các hàm thành viên. Các hàm thành viên đôi khi được gọi là các phương thức (methods) trong các ngôn ngữ lập trình hướng đối tượng khác, và được đưa ra trong việc đáp ứng các message gởi tới một đối tượng. Một message tương ứng với việc gọi hàm thành viên. Khi một lớp được định nghĩa, tên lớp có thể được sử dụng để khai báo đối tượng của lớp theo cú pháp sau: <class-name> <object-name>; Chẳng hạn, cấu trúc Time sẽ được định nghĩa dưới dạng lớp như sau: class Time { public: Time(); void SetTime(int, int, int) void PrintMilitary(); void PrintStandard() private: int Hour; // 0 - 23 int Minute; // 0 - 59 int Second; // 0 - 59  };  Trong định nghĩa lớp Time chứa ba thành viên dữ liệu là Hour, Minute và Second, và cũng trong lớp này, chúng ta thấy các nhãn public và private được gọi là các thuộc tính xác định truy cập thành viên (member access specifiers) gọi tắt là thuộc tính truy cập.  Bất kỳ thành viên dữ liệu hay hàm thành viên khai báo sau public có thể được truy cập bất kỳ nơi nào mà chương trình truy cập đến một đối tượng của lớp. Bất kỳ thành viên dữ liệu hay hàm thành viên khai báo sau private chỉ có thể được truy cập bởi các hàm thành viên của lớp. Các thuộc tính truy cập luôn luôn kết thúc với dấu hai chấm (:) và có thể xuất hiện nhiều lần và theo thứ tự bất kỳ trong định nghĩa lớp. Mặc định thuộc tính truy cập là private. Định nghĩa lớp chứa các prototype của bốn hàm thành viên sau thuộc tính truy cập public là Time(), SetTime(), PrintMilitary() và PrintStandard(). Đó là các hàm thành viên public (public member function) hoặc giao diện (interface) của lớp. Các hàm này sẽ được sử dụng bởi các client (nghĩa là các phần của một chương trình mà là các người dùng) của lớp xử lý dữ liệu của lớp. Có thể nhận thấy trong định nghĩa lớp Time, hàm thành viên Time() có cùng tên với tên lớp Time, nó được gọi là hàm xây dựng (constructor function) của lớp Time. Một constructor là một hàm thành viên đặc biệt mà khởi động các thành viên dữ liệu của một đối tượng của lớp. Một constructor của lớp được gọi tự động khi đối tượng của lớp đó được tạo.  Thông thường, các thành viên dữ liệu được liệt kê trong phần private của một lớp, còn các hàm thành viên được liệt kê trong phần public. Nhưng có thể có các hàm thành viên private và thành viên dữ liệu public. Khi lớp được định nghĩa, nó có thể sử dụng như một kiểu trong phần khai báo như sau: Time Sunset, // Đối tượng của lớp Time ArrayTimes[5], // Mảng các đối tượng của lớp Time *PTime, // Con trỏ trỏ đến một đối tượng của lớp Time &DinnerTime = Sunset; // Tham chiếu đến một đối tượng của lớp Time
#include<iostream>
using namespace std;
class time
{
public:
time();
void settime(int ,int ,int);
void inkieu1();
void inkieu2();
private:
int hour;
int minute;
int second;
};
time::time()
{
hour=minute=second=0;
}
void time::settime(int h,int m,int s)
{
hour=(h>=0 && h<24)?h:0;
minute=(m>=0 && m<59)? m:0;
second=(s>=0 && s<59)?s:0;
}
void time::inkieu1()
{
cout<<(hour<10?"0":"")<<hour<<":"<<(minute<10?"0":"")<<minute<<":"<<(second<10?"0":"")<<second;
}
void time::inkieu2()
{
cout<<((hour==0 || hour==12)?12:hour%12)<<":"<<(minute<10?"0":"")<<minute<<":"<<(second<10?"0":"")<<second<<(hour<12?" AM":" PM");
}
void main()
{
time t;
int h,m,s;
cout<<"nhap hour,minute,second:\n";
cin>>h>>m>>s;
cout<<"gio mac dinh: \n";
cout<<"kieu 1: ";t.inkieu1();
cout<<"\nkieu 2: ";t.inkieu2();
cout<<"\n\ngio da thiet lap:\n";
t.settime(h,m,s);
cout<<"kieu 1: ";t.inkieu1();
cout<<"\nkieu 2: ";t.inkieu2();
cout<<"\n\nnhap vao gio sai:\n";cin>>h>>m>>s;
t.settime(h,m,s);
cout<<"kieu 1: ";t.inkieu1();
cout<<"\nkieu 2: ";t.inkieu2();
}

Friday, January 30, 2015

[Olympic Tin Học] Đề Thi Sinh Viên Cao Đẳng 2014

Bài 1. Tính tổng (30 điểm)

Viết chương trình đọc vào hai số thực dương a và b và tính tổng tất cả các số nguyên 

không nhỏ hơn a và không lớn hơn b.

Dữ liệu: Vào từ file văn bản SUM.INP gồm một dòng chứa hai số thực dương a, b.

Kết quả: Đưa ra file văn bản SUM.OUT gồm một dòng chứa một số nguyên là tổng tất cả

các số nguyên không nhỏ hơn a và không lớn hơn b.

Ví dụ:

SUM.INP SUM.OUT

0.3 2.89

SUM.OUT
 3

Chú ý:

- Có 50% số test có 0 < a ≤ b ≤ 1000;

- Có 50% số test còn lại có 0 < a ≤ b ≤ 109


#include<stdio.h>
#include<stdlib.h>
void main()
{
float a,b;
long i,t=0;
FILE *in,*out;
in=fopen("SUM.INP ","r");
out=fopen("SUM.OUT ","w");
if(in==NULL || out==NULL)
{
printf("error");exit(0);
}
fscanf(in,"%f%f",&a,&b);
fprintf(in,"%f %f",a,b);
for(i=long(a);i<=long(b);i++)
if(i>=a && i<=b) t+=i;
fprintf(out,"%ld",t);
fcloseall();
}

Bài 2. Dãy số (30 điểm)

Cho dãy số gồm n số nguyên a1, a2, . . . , an. Một đoạn con của dãy đã cho là dãy ai

(1 ≤ i ≤ j ≤ n), dãy có độ dài (j − i + 1) và có trọng số bằng tổng (ai+. . . +aj). 

Yêu cầu: Tìm đoạn con có độ dài là một số chia hết cho 3 và có trọng số lớn nhất.

Dữ liệu: Vào từ file văn bản SEQ.INP có định dạng như sau:

 Dòng đầu ghi số nguyên n (n ≥ 3);

 Dòng thứ hai ghi n số nguyên a1, a2, . . . , an (|ai

Kết quả: Ghi ra file văn bản SEQ.OUT giá trị trọng số của đoạn con tìm được.

OLP’14 - Đề thi khối Cá nhân Cao đẳng Trang 1/2

Ví dụ:

SEQ.INP
11

SEQ.OUT
1 1 1 -9 1 1 1 1 -1 1 -9

Chú ý:

- Có 30% số test có n ≤ 300;

- Có 30% số test khác có n ≤ 3000;

- Có 40% số test còn lại có n ≤ 300000.


#include<stdio.h>
#include<stdlib.h>
void main()
{
FILE *in,*out;
in=fopen("SEQ.INP","r");
out=fopen("SEQ.OUT","w");
if(in==NULL || out==NULL)
{
printf("error");exit(0);
}
int n,i=0,j,k;
long a[100],max=-99999999,t;
fscanf(in,"%d",&n);
while(fscanf(in,"%ld",&a[i])!=EOF) i++;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
if((j-i+1)%3==0)
{
t=0;
for(k=i;k<=j;k++) t+=a[k];
if(max<t)max=t;
}
fprintf(out,"%ld",max);
fcloseall();
}

Bài 3. Giao đấu hữu nghị (40 điểm)

Để tạo không khí vui vẻ náo nhiệt, trong buổi giao lưu giữa sinh viên các trường tham dự 

OLP – ACM, trường đăng cai OLP năm tới đề xuất tổ chức một cuộc thi đấu game online 

tay đôi giữa sinh viên trường mình với sinh viên trường sở tại. Mỗi trường cử ra một đội n

người, tạo thành n cặp đấu, sinh viên cùng trường không đấu với nhau. Trò chơi được chọn 

là một trò chơi rất phổ biến, được các bạn trẻ yêu thích, ai cũng biết và đã từng chơi nhiều 

trước đó. Mọi người đều biết chỉ số năng lực của mình trong trò chơi này và biết rằng nếu 

đấu tay đôi, ai có năng lực cao hơn sẽ thắng. Trong các trận đấu tay đôi, người thắng sẽ 

được 1 điểm, người thua – 0 điểm. Thời gian chơi được quy định đủ để phân biệt thắng 

thua. Các trận hòa sẽ kéo dài vô hạn và sẽ bị hủy kết quả khi hết thời gian.Với tinh thần 

fair play các bạn trường đề xuất ngồi vào vị trí thi đấu, truy nhập vào hệ thống và gửi về 

máy chủ chỉ số năng lực của mình. Trưởng đoàn của trường sở tại có 1 giây để xử lý thông 

tin, phân công ai đấu với ai để tổng số điểm thu được là lớn nhất.

Yêu cầu: Hãy xác định, với cách bố trí tối ưu các cặp đấu, đội của trường sở tại sẽ có bao 

nhiêu điểm.

Dữ liệu: Vào từ file văn bản FAIRPLAY.INP:

 Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105

 Dòng thứ 2 chứa n số nguyên a1, a2, . . . , an, trong đó ai – chỉ số năng lực của 

người thứ i thuộc đội của trường đề xuất, 1 ≤ ai ≤ 109

 Dòng thứ 3 chứa n số nguyên b1, b2, . . . , bn, trong đó bi – chỉ số năng lực của người 

thứ i thuộc đội của trường sở tại, 1 ≤ bi ≤ 109

Kết quả: Đưa ra file văn bản FAIRPLAY.OUT một số nguyên – số điểm đội trường sở tại 

có thể đạt được với cách bố trí cặp chơi tối ưu.

Ví dụ:

FAIRPLAY.INP

5

10 15 30 20 25

28 24 20 16 14

FAIRPLAY.OUT

4

Chú ý:

- Có 25% số test có n ≤ 3;

- Có 25% số test khác có n ≤ 8;

- Có 25% số test khác có n ≤ 1000;

- Có 25% số test còn lại có n ≤ 105


#include<iostream>
using namespace std;
#include<stdlib.h>
void doi(long &a,long &b)
{
long t=a;a=b;b=t;
}
void xep(long *a,int n)
{
for(int i=0;i<n-1;i++)
{
int m=i;
for(int j=i+1;j<n;j++)
if(a[m]>a[j])m=j;
doi(a[m],a[i]);
}
}
int maxdiem(FILE *t)
{
long a[100],b[100];
int n,i=0,j=0,max=0;
fscanf(t,"%d",&n);
while(i<n){ fscanf(t,"%ld",&a[i]);i++;}
i=0;
while(fscanf(t,"%ld",&b[i])!=EOF) i++;
xep(a,n);xep(b,n);
for(i=0;i<n;i++)
{
if(j==n) break;
while(j<n) if(b[j]>a[i]) {max++;break;} else j++;
}
return max;
}
void main()
{
int i,n;
long a;
FILE *in=fopen("FAIRPLAY.INP","r");
FILE *out=fopen("FAIRPLAY.OUT","w");
if(in==NULL || out==NULL) 
{
cout<<"error";exit(0);
}
fprintf(out,"%d",maxdiem(in));
fclose(in);fclose(out);
}


viết chương trình c chuyển đổi hệ đếm nhị phân, bát phân, thập lục phân

viết chương trình c chuyển đổi hệ đếm nhị phân, bát phân, thập lục phân.
 DEC,BIN,HEX,OCT. 
 Viết chương trình in bảng của các số từ 1 đến 256 dưới dạng nhị phân, bát phân và thập lục phân tương ứng

#include<iostream>
using namespace std;
long sodu(int a,int b)
{
return a-b*int(a/b);
}
void dao(char *s)
{
char a;
for(int i=0;i<strlen(s)/2;i++)
{
a=s[i];s[i]=s[strlen(s)-1-i];s[strlen(s)-1-i]=a;
}
}
void to2(long n,char *s)
{

int i=0;
while(n>0)
{
s[i++]=sodu(n,2)+48;        //so 0 co ma 48
n/=2;
}
s[i]='\0';
dao(s);
}
void to8(long n,char *s)
{
int i=0;
while(n>0)
{
s[i++]=sodu(n,8)+48;//so 0 co ma 48
n/=8;
}
s[i]='\0';
dao(s);
}
void to16(long n,char *s)
{
int i=0,m;
while(n>0)
{
m=sodu(n,16);
if(m<10) s[i++]=m+48;
else switch(m)
{
case 10:s[i++]='A';break;
case 11:s[i++]='B';break;
case 12:s[i++]='C';break;
case 13:s[i++]='D';break;
case 14:s[i++]='E';break;
case 15:s[i++]='F';break;
}
n/=16;
}
s[i]='\0';
dao(s);
}
void main()
{
char a[100];
char b[100];
char c[100];
int i;
printf("DEC   :   BIN      : OCT    : HEX   \n-----------------------------------\n");
for(i=150;i<=256;i++)
{
to2(i,a);to8(i,b);to16(i,c);
printf("%-5d : %-10s : %-6s : %-6s\n\n",i,a,b,c);
}
}

Thursday, January 29, 2015

lập trình tìm các bộ số pitago | lập trình c/c++

lập trình tìm các bộ số pitago | lập trình c/c++. 
 Một tam giác vuông có thể có tất cả các cạnh là các số nguyên. Tập của ba số nguyên của các cạnh của một tam giác vuông được gọi là bộ ba Pitago. Đó là tổng bình phương của hai cạnh bằng bình phương của cạnh huyền, chẳng hạn bộ ba Pitago (3, 4, 5). Viết chương trình tìm tất cả các bộ ba Pitago như thế sao cho tất cả các cạnh không quá 500.

#include<iostream>
#include<math.h>
using namespace std;
int sochinhphuong(float n)
{
if ((float)sqrt(n) - (int)sqrt(n) == 0) return 1;
return 0;
}
void pitago()
{
int i, j;
for (i = 2; i < 500; i++)
for (j = i; j < 500; j++)
{
if (sqrt(i*i+j*j)>500) break;
if (sochinhphuong(i*i + j*j)) cout << " (" << i << "," << j << "," << sqrt(i*i + j*j) << ") \n";
}
}
void main()
{
pitago();

}

viết hàm in các tam giác bằng dấu sao *

viết hàm in các tam giác bằng dấu sao *

Viết chương trình nhập vào số nguyên dương h (2<h<23), sau đó in ra các tam giác có chiều cao là h.viết hàm in các tam giác có chiều cao h=N nhập vào
#include<iostream>
using namespace std;
void tamgiac1(int n)
{
int i,j;
for (i = n; i >=1; i--)
{
for (j = i; j <= n; j++)cout << "  ";
for (j = 1; j <= 2 * i - 1; j++) cout << "* ";
cout << "\n\n";
}
cout << "\n\n";

thuật toán tìm kiếm tuyến tính cải tiến trên dãy đã sắp xếp


thuật toán tìm kiếm tuyến tính cải tiến trên dãy đã sắp xếp
#include<iostream>
using namespace std;
int tim(int *a,int n,int x)
{
int i=0;
while(a[i]!=x && i<n) i++;
if(i==n) return 0;
return i;
}
int tim1(int *a,int n,int x)
{
int i=0;
a[n]=x;
while(a[i]!=x) i++;
if(i==n) return 0;
return i;

thuật toán tìm kiếm nhị phân bằng đệ quy


//thuật toán tìm kiếm nhị phân bằng đệ quy
#include<iostream>
using namespace std;
int tim(int *a,int left,int right,int x)
{
int m;
if(left>right) return 0;
m=(left+right)/2;
if(a[m]==x) return m;
if(x<a[m]) return tim(a,left,m-1,x);
return tim(a,m+1,right,x);
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int x;
cout<<"tim so: ";cin>>x;
if(int z=tim(a,0,9,x)) cout<<"tim thay tai vi tri: "<<z<<"\n";
else cout<<"khong tim thay\n";

}

viết hàm kiểm tra số chính phương


in ra màn hình số chính phương lớn nhất trong dãy. nếu không có só chính phương nào thì in ra dãy không có số chính phương nào.
viết hàm kiểm tra 1 số có phải là số chính phương hay không.
#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int sochinhphuong(float n)
{
if((float)sqrt(n)-(int)sqrt(n)==0) return 1;
return 0;
}
void main()
{
int max=0;
int *a=(int*)malloc(91*sizeof(int));
for(int i=10;i<=100;i++) a[i-10]=i;
for(int i=0;i<91;i++)
if(sochinhphuong(a[i]) && max<a[i]) max=a[i];
cout<<"day:";
for(int i=0;i<91;i++) cout<<" "<<a[i];
if(max==0) cout<<"\nday khong co so chinh phuong nao\n";
else cout<<"\nso chinh phuong lon nhat trong day: "<<max<<"\n";
}

Tuesday, January 27, 2015

Tính Giá Trị Biểu Thức Nhập Từ Bàn Phím


//lập trình c tính giá trị của 1 biểu thức bất kỳ nhập từ bàn phím gồm các phép tính cộng, trừ, nhân, chia (+-/*). biểu thức nhập ở dạng chuỗi. giống máy tính bỏ túi casio
#include<iostream>
#include<string.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
float tinhgiatri(char *s);
void sohang(char *s,float *a,int &n);
void dau(char *s,char *b);
int kiemtra(char *s);
void main()
{
char s[1000],c;
       cout<<"TRẦN KHÁNH TOÀN\n-------------------------------------------------------------------";
loop:;
do
{
cout << "\n->nhap bieu thuc:\n\t";
fflush(stdin);
gets(s);
if(!kiemtra(s)) cout<<"\nnhap bieu thuc khong chua <space>,ky tu,phep tinh lien ke...\n\tNHAP LAI\n\n";
}while(!kiemtra(s));
cout<<"\t= "<<tinhgiatri(s)<<"\n\n\t---------------------\n\t| tiep tuc: <space> |\n\t| ket thuc: bat ky  |\n\t---------------------\n";
if(c=getch()==32) goto loop;
}
float tinhgiatri(char *s)
{
float kq,a[1000];
int i,j,n;
char b[1000];
sohang(s,a,n);
dau(s,b);
for(i=0;i<strlen(b);i++)
{
if(b[i]=='*')
{
(float)a[i]*=(float)a[i+1];
for(j=i+1;j<n-1;j++) a[j]=a[j+1];
n--;
for(j=i;j<strlen(b)-1;j++)b[j]=b[j+1];
b[strlen(b)-1]='\0';
i--;
}
if(b[i]=='/')
{
(float)a[i]/=(float)a[i+1];
for(j=i+1;j<n-1;j++) a[j]=a[j+1];
n--;
for(j=i;j<strlen(b)-1;j++) b[j]=b[j+1];
b[strlen(b)-1]='\0';
i--;
}
}
(float)kq=(float)a[0];
for(i=0;i<strlen(b);i++)
{
if(b[i]=='+') kq+=(float)a[i+1];
else kq-=(float)a[i+1];
}
return kq;
}
void sohang(char *s,float *a,int &n)
{
char z[1000];
int i,k,j,x;
n=0;
for(i=0;i<strlen(s);i++)
{
k=0;
while(s[i]>='0' && s[i]<='9') z[k++]=s[i++];
z[k]='\0';
x=atoi(z);
a[n++]=(float)x;
}
}
void dau(char *s,char *b)
{
int i,k=0;
for(i=0;i<strlen(s);i++)
if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
b[k++]=s[i];
b[k]='\0';
}
int kiemtra(char *s)
{
if(strlen(s)==0) return 0;
for(int i=0;i<strlen(s);i++)
if(s[i]==' ' ||
(s[i]>='a' && s[i]<='z') ||
(s[i]>='A' && s[i] <='Z') ||
((s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')&& (s[i+1]=='+' || s[i+1]=='-' || s[i+1]=='*' || s[i+1]=='/')))
return 0;
return 1;
}

Saturday, January 24, 2015

thuật toán tìm kiếm nhị phân

/*thuật toán tìm kiếm nhị phân
Được áp dụng trên mảng đã có thứ tự.
Ý tưởng: .
Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có
ai-1<ai<ai+1
Nếu X>ai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1]
Nếu X<ai thì X chỉ có thể xuất hiện trong đoạn [a0,   ai-1]
Ý tưởng của giải thuật là tại mỗi bước ta so sánh X với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành.
Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các bước của giải thuật như sau:
Bước 1: left=0; right=N-1;
Bước 2:
mid=(left+right)/2; //chỉ số phần tử giữa dãy hiện hành
So sánh a[mid] với x. Có 3 khả năng
a[mid]= x: tìm thấy. Dừng
a[mid]>x :  Right= mid-1;
a[mid]<x : Left= mid+1;
Bước 3: Nếu Left <=Right ; //  còn phần tử trong dãy hiện  hành
+ Lặp lại bước 2
Ngược lại : Dừng
Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm trả về giá trị 0

*/
#include<iostream>
using namespace std;
int tim(int a[], int left,int right, int x)
{
do
{
if (x == a[(left + right) / 2]) return 1;
if (a[(left + right) / 2] > x) right = (left + right) / 2 - 1;
else left = (left + right) / 2 + 1;
} while (left <= right);
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << tim(a, 0, 9, 1);
}

thuật toán tìm kiếm tuyến tính

/*thuật toán tìm kiếm tuyến tính
Cho danh sách có n phần tử a0, a1, a2…, an-1.
Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính.
Tìm phần tử có khoá bằng X trong mảng
Giải thuật tìm kiếm tuyến tính (tìm tuần tự)
Giải thuật tìm kiếm nhị phân
Lưu ý: Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C.
Ý tưởng : So sánh X lần lượt với phần tử thứ 1, thứ 2,…của mảng a cho đến khi gặp được khóa cần tìm, hoặc tìm hết mảng mà không thấy.
Các bước tiến hành
Bước 1: Khởi gán i=0;
Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng
Nếu i==N: Hết mảng. Dừng;
Ngược lại: Lặp lại bước 2;
Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0:
int LinearSearch(int a[],int n, int x)
{
int i=0;
while((i<n)&&(a[i]!=x))
i++;
if(i==n)
return 0; //Tìm không thấy x
else
return 1; //Tìm thấy
}Nhận xét: Số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n.
Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán, ta thêm phần tử “lính canh” vào cuối dãy.
int LinearSearch(int a[],int n, int x)
{ int i=0; a[n]=x;   // a[n] là phần tử “lính canh”
while(a[i]!=x) 
i++;
if(i==n)
return 0; // Tìm không thấy x
else
return 1; // Tìm thấy
}

*/
#include<iostream>
using namespace std;
int tim(int a[], int n,int x)
{
for (int i = 0; i < n;i++) if (x == a[i]) return i+1;
return 0;
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int x;
cout << "nhap gia tri muon tim: ";
cin >> x;
int vt = tim(a, 10, x);
if (vt !=0) cout << "tim thay tai vi tri: " << vt << "\n";
else cout << "khong tim thay\n";
}

thuật toán selection sort

/*thuật toán selection sort
Ý tưởng:
Chọn phần tử nhỏ nhất trong N phần tử trong dãy hiện hành ban đầu.
Đưa phần tử này về vị trí đầu dãy hiện hành
Xem dãy hiện hành chỉ còn N-1 phần tử của dãy hiện hành ban đầu
Bắt đầu từ vị trí thứ 2;
Lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử
Bước 1:   i = 0;
Bước 2:  Tìm phần tử a[min] nhỏ nhất trong    dãy hiện hành từ a[i] đến a[N]
Bước 3 :  Đổi chỗ a[min] và a[i]
Bước 4 :  Nếu  i < N-1 thì
i = i+1; Lặp lại Bước 2;                Ngược lại: Dừng.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
int i, j, m,t;
for (i = 0; i < n - 1; i++)
{
m = i;
for (j = i + 1; j < n; j++) if (a[m]>a[j]) m = j;
t = a[i]; a[i] = a[m]; a[m] = t;
}
}
void main()
{
int a[10] = { 5, 4, 7, 8, 2, 3, 1, 9, 6, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

thuật toán interchange sort

/*thuật toán interchange sort
Ý tưởng: Xuất phát từ đầu dãy, tìm tất các các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế trong dãy.
Bước 1: i = 0;  // bắt đầu từ đầu dãy
Bước 2: j = i+1; //tìm các nghịch thế với a[i]
Bước 3:
Trong khi j < N thực hiện
Nếu a[j]<a[i] //xét cặp a[i], a[j]
Swap(a[i],a[j]);
j = j+1;
Bước 4: i = i+1;
Nếu  i < N-1: Lặp lại Bước 2.
Ngược lại:  Dừng.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
for (int i = 0; i < n - 1;i++)
for (int j = i + 1; j < n;j++)
if (a[i]>a[j])
{
a[i] += a[j]; a[j] = a[i] - a[j]; a[i] = a[i] - a[j];
}
}
void main()
{
int a[10] = { 3, 7, 4, 1, 8, 9, 2, 5, 6, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

thuật toán bubble sort

/*thuật toán bubble sort
Ý tưởng:
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i.
Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
Bước 1 : i = 0; // lần xử lý đầu tiên
Bước 2 : j = N-1;//Duyệt từ cuối dãy ngược về vị trí i
Trong khi (j > i) thực hiện:
Nếu a[j]<a[j-1]
Doicho(a[j],a[j-1]);
j = j-1;
Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu  i =N: Hết dãy. Dừng
Ngược lại : Lặp lại Bước 2.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
int i, j, t;
for (i = 0; i < n - 1;i++)
for (j = n - 1; j>i;j--)
if (a[j] < a[j - 1])
{
t = a[j]; a[j] = a[j - 1]; a[j - 1] = t;
}
}
void main()
{
int a[10] = { 3, 4, 5, 2, 8, 7, 6, 1, 9, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

thuật toán sắp xếp shaker sort

/*thuật toán sắp xếp shaker sort
Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau:
Lượt đi: đẩy phần tử nhỏ về đầu mảng.
Lượt về: đẩy phần tử lớn về cuối mảng.
Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
Bước 1: l=0; r=n-1; //Đoạn l->r là đoạn cần được sắp xếp
k=n; //ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sơ thu hẹp đoạn l->r
Bước 2:
Bước 2a:
j=r; //đẩy phần tử nhỏ về đầu mảng
Trong khi j>l
nếu a[j]<a[j-1] thì {Doicho(a[j],a[j-1]): k=j;}
j--;
l=k; //loại phần tử đã có thứ tự ở đầu dãy
Bước 2b: j=l
Trong khi j<r
nếu a[j]>a[j+1] thì {Doicho(a[j],a[j+1]); k=j;}
j++;
r=k; //loại phần tử đã có thứ tự ở cuối dãy
Bước 3: Nếu l<r lặp lại bước 2
Ngược lại: dừng

*/
#include<iostream>
using namespace std;
inline void doi(int &a, int &b)
{
int t = a; a = b; b = t;
}
void xep(int a[], int n)
{
int left = 0, right = n - 1, k,i,j;
while (left < right)
{
for (i = left; i < right; i++) if (a[i]>a[i + 1]) { doi(a[i], a[i + 1]); k = i; };
right = k;
for (j = right; j>left; j--) if (a[j] < a[j - 1]){ doi(a[j], a[j - 1]); k = j; }
left = k;
}
}
void main()
{
int a[10] = { 2, 8, 9, 5, 6, 3, 4, 7, 1, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

Wednesday, January 21, 2015

Đối số mảng truyền cho hàm - con trỏ

xuat(int a[10]) hoàn toàn tương đương với xuat(int *a), tức đối số là biến con trỏ, do đó khi printf phải thêm dấu * để chuyển thành giá trị để in.
vì a là mảng ( là 1 chuổi ô nhó liên tiếp nhau, mặt định a là ô nhớ đầu tiên == a[0]) khi truyền mảng vào hàm thức chất là truyền địa chỉ của ô nhớ đầu tiên trong mảng, còn n là biến thông thường, xuat(int n) hoàn toàn khác với xuat(int *n).
mảng a trong main là nơi ta khai báo, mặt định trong main() lúc này là biến giá trị thông thường, nếu ta khai báo trong hàm xuat() mảng a[10] này thì trong hàm xuất nó mặt định là biến giá trị, khi printf không thêm dấu * gì hết, mà dùng a[i], chứ không được phép dùng a++