Vẫn…

Thực tế thì tự nhiên chẳng cho con người – những cỗ máy sinh học một trách nhiệm nào hơn việc vận động để duy trì. Tuy nhiên, để cuộc sống ý nghĩa hơn mỗi người nên lãnh cho mình một trách nhiệm để vươn tới.
Chuyện xảy ra ba tháng trước như một cơn gió nhẹ nhưng cũng đủ để bùng lên tất cả những gì tốt đẹp nhất trong mình.
Thảm thê thay mình đã không nghĩ được như vậy sớm hơn.
Mỗi ngày mình đấu tranh vật lôn 24 giờ với chính mình.
Những nỗ lực của mình tuy chưa đủ sức phán ánh lên những thứ xung quanh mình.
Nhưng từ thẳm sâu nội tâm mình thấy đã có thay đổi lớn lao.
Một trong những niềm vui bây giờ của mình là:
Mĩnh vẫn đang bước trên con đườn mình đã chọn.

Sắp xếp trong hình học

Phần 1: sắp xếp độ dài các đoạn thẳng.

Bài toán: cho n điểm có tọa độ nguyên trên mặt phẳng (n<=1000), trong đó ko có 3 điểm nào thẳng hàng. Tìm số lượng tam giác cân tạo bởi 3 trong n điểm đó.

Input:  tamgiac.inp

-          dòng đầu là số n.

-          n dòng tiếp theo, mỗi dòng 2 số nguyên (giá trị tuyệt đối <=10000) là hoành độ và tung độ của mỗi điểm.

output: tamgiac.out

một dòng duy nhất là số tam giác tìm được.

Thuật giải: Từ 1 điểm, tìm số lượng tam giác cân mà điểm đó là đỉnh 2 cạnh bên. Với mỗi 1 điểm trong n điểm, tính khoảng cách từ điểm đó đến n-1 điểm còn lại. Sắp xếp lại n-1 khoảng cách đó theo thứ tự tăng dần. Cứ x khoảng cách bằng nhau ta sẽ tìm được x*(x-1)/2  tam giác cân.

Độ phức tạp tính toán là n^2log₂n.

Đến đây bạn sẽ tự hỏi, thuật toán này có đúng, khi xuất các tam giác đều. Vì nếu 3 điểm tạo thành 1 tam giác đều thì mỗi lần xét đến 1 trong 3 điểm, tam giác đó lại được tính 1 lần. Như vậy là ta lại phải đi tìm số lượng tam giác đều trong n điểm? Thực ra là ko cần phải làm vậy. Đơn giản vì không tồn tại trong mặt phẳng 1 tam giác đều mà cả 3 đỉnh đều có tọa độ nguyên. (Sử dụng 1 số kiến thức toán học, hoàn toàn có thể chứng minh được).

Chương trình:

const

finp=’tamgiac.inp’;

fout=’tamgiac.out’;

maxn=1001;

var

fi,fo: text;

n,m,kq: longint;

x,y: array[0..maxn] of longint;

a: array[0..maxn] of int64;

Procedure ofile;

begin

assign(fi,finp); reset(fi);

assign(fo,fout); rewrite(fo);

end;

Procedure cfile;

begin

close(fi); close(fo);

end;

Procedure nhap;

var i: longint;

begin

readln(fi,n);

for i:=1 to n do readln(fi,x[i],y[i]);

end;

function kc(i,j: longint): int64;

begin

kc := sqr(int64(x[i]-x[j])) + sqr(int64(y[i]-y[j]));

end;

Procedure sort(l,h: longint);

var i,j: longint; v,t: int64;

begin

if l>=h then exit;

i:=l; j:=h; v:=a[(l+h) div 2];

repeat

while a[i] < v do inc(i);

while a[j] > v do dec(j);

if i<=j then

begin

t:=a[i]; a[i]:=a[j]; a[j]:=t;

inc(i); dec(j);

end;

until i>j;

sort(l,j); sort(i,h);

end;

Procedure xuli;

var u,v,i,j: longint;

begin

kq:=0;

for i:=1 to n do

begin

m:=0;

for j:=1 to n do

if i<>j then

begin

inc(m);

a[m] := kc(i,j);

end;

sort(1,m);

u:=1;

repeat

v:=u;

while (v<=m) and (a[v] = a[u]) do inc(v);

inc(kq,( (v-u)*(v-u-1) ) div 2);

u:=v;

until u>m;

end;

writeln(fo,kq);

end;

begin

ofile;

nhap;

xuli;

cfile;

end.

Site về thông tin tuyển sinh đại học

Link: Http://ThongTinTuyenSinh.Vn

Ôn thi đại học

Nhằm giúp các bạn thuận tiện trong việc tra cứu để tìm hiểu và lựa chọn nơi học tập cho mình, website ”Thông tin Tuyển sinh” cung cấp thông tin tuyển sinh của tất cả các trường Đại học, Cao đẳng, Trung cấp trong hệ thống giáo dục quốc gia. Thông tin sẽ được cập nhật và chỉnh sửa trước mỗi kỳ tuyển sinh hàng năm.

Những thông tin mới nhất về tuyển sinh các hệ đào tạo Tại chức, Liên thông, Cao học, Từ xa, Văn bằng 2, Chương trình quốc tế… cũng được thường xuyên cập nhật, giúp các bạn dễ dàng chọn lựa nơi học phù hợp.

Ngoài ra, website cũng giới thiệu tóm tắt một số ngành nghề đang được đào tạo tại các trường Đại học & Cao đẳng nhằm giúp các thí sinh có định hướng trong việc lựa chọn ngành học cho mình. Những quy định, hướng dẫn có liên quan đến thủ tục tuyển sinh cũng được cập nhật trước mỗi kỳ tuyển sinh giúp các bạn có tài liệu tham khảo để làm hồ sơ tuyển sinh.

Chuyên mục “TH Phổ thông” chỉ giới thiệu thông tin tuyển sinh đầu cấp của các trường THPT Dân lập và Tư thục ở khu vực TP.Hà Nội và TP. HCM nhằm giúp các bậc phụ huynh, các em học sinh ở các tỉnh và những học sinh đã tốt nghiệp THCS tại 2 thành phố này (nhưng không thi đậu hoặc không muốn vào lớp 10 công lập) có thể tham khảo để lựa chọn nơi học tập tiếp theo ở bậc học phổ thông.

Chúng tôi xin cám ơn và sẵn sàng đón nhận sự hợp tác của các cơ sở đào tạo và dạy nghề cả nước trong việc cung cấp các thông tin tuyển sinh mới hoặc chỉnh sửa các thông tin không phù hợp trên website này.

Xin liên hệ: Email: admin@thongtintuyensinh.vn

P/S: cũng vì vụ đại học mà bố mẹ cẩm khoản máy tính, thành ra blog, đành, thôi, ngậm ngùi, break,… (

Đề thi và đáp án đại học Toán, Lý, Hóa ban A từ năm 2002 đến 2009

Đang cần mấy cái này để ôn thi. Download được trọn bộ rồi đóng gói lên đây chia sẻ .Đây là đề thi và đáp án của 3 môn Toán, Lý, Hóa ban A các năm từ 2002 đến 2009.

Download

Đồ thị và các thuật toán

Download

Tác giả: Phạm Tiến Sơn

Tổng quan nội dung:

Lời nói đầu
1. Đại cương về đồ thị
2. Các số cơ bản của đồ thị
3. Các bài toán về đường đi
4. Cây
5. Bài toán Euler và bài toán Hamilton
6. Đồ thị phẳng
7. Mạng vận tải
A Thư viện Graph
Tài liệu tham khảo

Thuật toán tính âm lịch

Bài viết sau giới thiệu cách tính âm lịch Việt Nam và mô tả một số thuật toán dùng để chuyển đổi giữa ngày dương lịch và ngày âm lịch. Các thuật toán mô tả ở đây đã được đơn giản hóa nhiều để bạn đọc tiện theo dõi và dễ dàng sử dụng vào việc lập trình, do đó độ chính xác của chúng thấp hơn độ chính xác của chương trình âm lịch trực tuyến tại http://www.informatik.uni-leipzig.de/~duc/amlich/. (Một phiên bản cũ của bài viết này giới thiệu vài thuật toán hơi khác, có thể khó thực hiện hơn một chút. Bản cũ này có thể xem tại đây.)

Quy luật của âm lịch Việt Nam

Âm lịch Việt Nam là một loại lịch thiên văn. Nó được tính toán dựa trên sự chuyển động của mặt trời, trái đất và mặt trăng. Ngày tháng âm lịch được tính dựa theo các nguyên tắc sau:

1. Ngày đầu tiên của tháng âm lịch là ngày chứa điểm Sóc
2. Một năm bình thường có 12 tháng âm lịch, một năm nhuận có 13 tháng âm lịch
3. Đông chí luôn rơi vào tháng 11 âm lịch
4. Trong một năm nhuận, nếu có 1 tháng không có Trung khí thì tháng đó là tháng nhuận. Nếu nhiều tháng trong năm nhuận đều không có Trung khí thì chỉ tháng đầu tiên sau Đông chí là tháng nhuận
5. Việc tính toán dựa trên kinh tuyến 105° đông.

Sóc là thời điểm hội diện, đó là khi trái đất, mặt trăng và mặt trời nằm trên một đường thẳng và mặt trăng nằm giữa trái đất và mặt trời. (Như thế góc giữa mặt trăng và mặt trời bằng 0 độ). Gọi là “hội diện” vì mặt trăng và mặt trời ở cùng một hướng đối với trái đất. Chu kỳ của điểm Sóc là khoảng 29,5 ngày. Ngày chứa điểm Sóc được gọi là ngày Sóc, và đó là ngày bắt đầu tháng âm lịch.

Trung khí là các điểm chia đường hoàng đạo thành 12 phần bằng nhau. Trong đó, bốn Trung khí giữa bốn mùa là đặc biệt nhất: Xuân phân (khoảng 20/3), Hạ chí (khoảng 22/6), Thu phân (khoảng 23/9) và Đông chí (khoảng 22/12).

Bởi vì dựa trên cả mặt trời và mặt trăng nên lịch Việt Nam không phải là thuần âm lịch mà là âm-dương-lịch. Theo các nguyên tắc trên, để tính ngày tháng âm lịch cho một năm bất kỳ trước hết chúng ta cần xác định những ngày nào trong năm chứa các thời điểm Sóc (New moon) . Một khi bạn đã tính được ngày Sóc, bạn đã biết được ngày bắt đầu và kết thúc của một tháng âm lịch: ngày mùng một của tháng âm lịch là ngày chứa điểm sóc. Sau khi đã biết ngày bắt đầu/kết thúc các tháng âm lịch, ta tính xem các Trung khí (Major solar term) rơi vào tháng nào để từ đó xác định tên các tháng và tìm tháng nhuận.

Đông chí luôn rơi vào tháng 11 của năm âm lịch. Bởi vậy chúng ta cần tính 2 điểm sóc: Sóc A ngay trước ngày Đông chí thứ nhất và Sóc B ngay trước ngày Đông chí thứ hai. Nếu khoảng cách giữa A và B là dưới 365 ngày thì năm âm lịch có 12 tháng, và những tháng đó có tên là: tháng 11, tháng 12, tháng 1, tháng 2, …, tháng 10. Ngược lại, nếu khoảng cách giữa hai sóc A và B là trên 365 ngày thì năm âm lịch này là năm nhuận, và chúng ta cần tìm xem đâu là tháng nhuận. Để làm việc này ta xem xét tất cả các tháng giữa A và B, tháng đầu tiên không chứa Trung khí sau ngày Đông chí thứ nhất là tháng nhuận. Tháng đó sẽ được mang tên của tháng trước nó kèm chữ “nhuận”.

Khi tính ngày Sóc và ngày chứa Trung khí bạn cần lưu ý xem xét chính xác múi giờ. Đây là lý do tại sao có một vài điểm khác nhau giữa lịch Việt Nam và lịch Trung Quốc.Ví dụ, nếu bạn biết thời điểm hội diện là vào lúc yyyy-02-18 16:24:45 GMT thì ngày Sóc của lịch Việt Nam là 18 tháng 2, bởi vì 16:24:45 GMT là 23:24:45 cùng ngày, giờ Hà nội (GMT+7, kinh tuyến 105° đông). Tuy nhiên theo giờ Bắc Kinh (GMT+8, kinh tuyến 120° đông) thì Sóc là lúc 00:24:45 ngày yyyy-02-19, do đó tháng âm lịch của Trung Quốc lại bắt đầu ngày yyyy-02-19, chậm hơn lịch Việt Nam 1 ngày.

Ví dụ 1: Âm lịch năm 1984

Chúng ta áp dụng quy luật trên để tính âm lịch Việt nam năm 1984.

• Sóc A (ngay trước Đông chí năm 1983) rơi vào ngày 4/12/1983, Sóc B (ngay trước Đông chí năm 1984) vào ngày 23/11/1984.
• Giữa A và B là khoảng 355 ngày, như thế năm âm lịch 1984 là năm thường. Tháng 11 âm lịch của năm trước kéo dài từ 4/12/1983 đến 2/01/1984, tháng 12 âm từ 3/1/1984 đến 1/2/1984, tháng Giêng từ 2/2/1984 đến 1/3/1984 v.v.

Ví dụ 2: Âm lịch năm 2004

• Sóc A – điểm sóc cuối cùng trước Đông chí 2003 – rơi vào ngày 23/11/2003. Sóc B (ngay trước Đông chí năm 2004) rơi vào ngày 12/12/2004.
• Giữa 2 ngày này là khoảng 385 ngày, như vậy năm âm lịch 2004 là năm nhuận. Tháng 11 âm của năm 2003 bắt đầu vào ngày chứa Sóc A, tức ngày 23/11/2003.
• Tháng âm lịch đầu tiên sau đó mà không chứa Trung khí là tháng từ 21/3/2004 đến 18/4/2004 (Xuân phân rơi vào 20/3/2004, còn Cốc vũ là 19/4/2004). Như thế tháng ấy là tháng nhuận.
• Từ 23/11/2003 đến 21/3/2004 là khoảng 120 ngày, tức 4 tháng âm lịch: tháng 11, 12, 1 và 2. Như vậy năm 2004 có tháng 2 nhuận.

Thuật toán chuyển đổi giữa ngày dương và âm

Trong tính toán thiên văn người ta lấy ngày 1/1/4713 trước công nguyên của lịch Julius (tức ngày 24/11/4714 trước CN theo lịch Gregorius) làm điểm gốc. Số ngày tính từ điểm gốc này gọi là số ngày Julius (Julian day number) của một thời điểm. Ví dụ, số ngày Julius của 1/1/2000 là 24515455.

Dùng các công thức sau ta có thể chuyển đổi giữa ngày/tháng/năm và số ngày Julius. Phép chia ở 2 công thức sau được hiểu là chia số nguyên, bỏ phần dư: 23/4=5.

Đổi ngày dd/mm/yyyy ra số ngày Julius jd

a = (14 - mm) / 12
y = yy+4800-a
m = mm+12*a-3

Lịch Gregory:

jd = dd + (153*m+2)/5 + 365*y + y/4 - y/100 + y/400 - 32045

Lịch Julius:

jd = dd + (153*m+2)/5 + 365*y + y/4 - 32083

Đổi số ngày Julius jd ra ngày dd/mm/yyyy

Lịch Gregory (jd lớn hơn 2299160):

a = jd + 32044;
b = (4*a+3)/146097;
c = a - (b*146097)/4;

Lịch Julius:

b = 0;
c = jd + 32082;

Công thức cho cả 2 loại lịch:

d = (4*c+3)/1461;
e = c - (1461*d)/4;
m = (5*e+2)/153;
dd = e - (153*m+2)/5 + 1;
mm = m + 3 - 12*(m/10);
yy = b*100 + d - 4800 + m/10;

Nếu ngôn ngữ lập trình bạn dùng không hỗ trợ phép chia số nguyên bỏ phần dư (VD: JavaScript), bạn có thể định nghĩa một hàm INT(x) để lấy số nguyên lớn nhất không vượt quá x: INT(5)=5, INT(3.2)=3, INT(-5)=-5, INT(-3.2)=-4 v.v. Khi đó, INT(m/10) sẽ trả lại kết quả của phép chia số nguyên. (Nhiều ngôn ngữ có sẵn hàm floor() cho phép làm việc này.)

Các phép chuyển đổi giữa ngày tháng và số ngày Julius có thể được thực hiện với mã JavaScript như sau:

function jdFromDate(dd, mm, yy)

var a, y, m, jd;
a = INT((14 - mm) / 12);
y = yy+4800-a;
m = mm+12*a-3;
jd = dd + INT((153*m+2)/5) + 365*y + INT(y/4) - INT(y/100) + INT(y/400) - 32045;
if (jd < 2299161) {
	jd = dd + INT((153*m+2)/5) + 365*y + INT(y/4) - 32083;
}
return jd;

function jdToDate(jd)

var a, b, c, d, e, m, day, month, year;
if (jd > 2299160) { // After 5/10/1582, Gregorian calendar
	a = jd + 32044;
	b = INT((4*a+3)/146097);
	c = a - INT((b*146097)/4);
} else {
	b = 0;
	c = jd + 32082;
}
d = INT((4*c+3)/1461);
e = c - INT((1461*d)/4);
m = INT((5*e+2)/153);
day = e - INT((153*m+2)/5) + 1;
month = m + 3 - 12*INT(m/10);
year = b*100 + d - 4800 + INT(m/10);
return new Array(day, month, year);

Trong các công thức sau, timeZone là số giờ chênh lệch giữa giờ địa phương và giờ UTC (hay GMT). (Để tính lịch Việt Nam, lấy timeZone = 7.0). Các phương pháp sau được giới thiệu với mã JavaScript. Bạn có thể tải thư viện JavaScript hoặc thư viện PHP hoàn chỉnh để tham khảo.

Tính ngày Sóc

Như trên đã nói, để tính được âm lịch trước hết ta cần xác định các tháng âm lịch bắt đầu vào ngày nào.

Thuật toán sau tính ngày Sóc thứ k kể từ điểm Sóc ngày 1/1/1900. Kết quả trả về là số ngày Julius của ngày Sóc cần tìm.

function getNewMoonDay(k, timeZone)

var T, T2, T3, dr, Jd1, M, Mpr, F, C1, deltat, JdNew;
T = k/1236.85; // Time in Julian centuries from 1900 January 0.5
T2 = T * T;
T3 = T2 * T;
dr = PI/180;
Jd1 = 2415020.75933 + 29.53058868*k + 0.0001178*T2 - 0.000000155*T3;
Jd1 = Jd1 + 0.00033*Math.sin((166.56 + 132.87*T - 0.009173*T2)*dr); // Mean new moon
M = 359.2242 + 29.10535608*k - 0.0000333*T2 - 0.00000347*T3; // Sun's mean anomaly
Mpr = 306.0253 + 385.81691806*k + 0.0107306*T2 + 0.00001236*T3; // Moon's mean anomaly
F = 21.2964 + 390.67050646*k - 0.0016528*T2 - 0.00000239*T3; // Moon's argument of latitude
C1=(0.1734 - 0.000393*T)*Math.sin(M*dr) + 0.0021*Math.sin(2*dr*M);
C1 = C1 - 0.4068*Math.sin(Mpr*dr) + 0.0161*Math.sin(dr*2*Mpr);
C1 = C1 - 0.0004*Math.sin(dr*3*Mpr);
C1 = C1 + 0.0104*Math.sin(dr*2*F) - 0.0051*Math.sin(dr*(M+Mpr));
C1 = C1 - 0.0074*Math.sin(dr*(M-Mpr)) + 0.0004*Math.sin(dr*(2*F+M));
C1 = C1 - 0.0004*Math.sin(dr*(2*F-M)) - 0.0006*Math.sin(dr*(2*F+Mpr));
C1 = C1 + 0.0010*Math.sin(dr*(2*F-Mpr)) + 0.0005*Math.sin(dr*(2*Mpr+M));
if (T < -11) {
	deltat= 0.001 + 0.000839*T + 0.0002261*T2 - 0.00000845*T3 - 0.000000081*T*T3;
} else {
	deltat= -0.000278 + 0.000265*T + 0.000262*T2;
};
JdNew = Jd1 + C1 - deltat;
return INT(JdNew + 0.5 + timeZone/24)

Với hàm này ta có thể tính được tháng âm lịch chứa ngày N bắt đầu vào ngày nào: giữa ngày 1/1/1900 (số ngày Julius: 2415021) và ngày N có khoảng k=INT((N-2415021)/29.530588853) tháng âm lịch, như thế dùng hàm getNewMoonDay sẽ biết ngày đầu tháng âm lịch chứa ngày N, từ đó ta biết ngày N là mùng mấy âm lịch.

Tính tọa độ mặt trời

Để biết Trung khí nào nằm trong tháng âm lịch nào, ta chỉ cần tính xem mặt trời nằm ở khoảng nào trên đường hoàng đạo vào thời điểm bắt đầu một tháng âm lịch. Ta chia đường hoàng đạo làm 12 phần và đánh số các cung này từ 0 đến 11: từ Xuân phân đến Cốc vũ là 0; từ Cốc vũ đến Tiểu mãn là 1; từ Tiểu mãn đến Hạ chí là 2; v.v.. Cho jdn là số ngày Julius của bất kỳ một ngày, phương pháp sau này sẽ trả lại số cung nói trên.

function getSunLongitude(jdn, timeZone)

var T, T2, dr, M, L0, DL, L;
T = (jdn - 2451545.5 - timeZone/24) / 36525; // Time in Julian centuries from 2000-01-01 12:00:00 GMT
T2 = T*T;
dr = PI/180; // degree to radian
M = 357.52910 + 35999.05030*T - 0.0001559*T2 - 0.00000048*T*T2; // mean anomaly, degree
L0 = 280.46645 + 36000.76983*T + 0.0003032*T2; // mean longitude, degree
DL = (1.914600 - 0.004817*T - 0.000014*T2)*Math.sin(dr*M);
DL = DL + (0.019993 - 0.000101*T)*Math.sin(dr*2*M) + 0.000290*Math.sin(dr*3*M);
L = L0 + DL; // true longitude, degree
L = L*dr;
L = L - PI*2*(INT(L/(PI*2))); // Normalize to (0, 2*PI)
return INT(L / PI * 6)

Với hàm này ta biết được một tháng âm lịch chứa Trung khí nào. Giả sử một tháng âm lịch bắt đầu vào ngày N1 và tháng sau đó bắt đầu vào ngày N2 và hàm getSunLongitude cho kết quả là 8 với N1 và 9 với N2. Như vậy tháng âm lịch bắt đầu ngày N1 là tháng chứa Đông chí: trong khoảng từ N1 đến N2 có một ngày mặt trời di chuyển từ cung 8 (sau Tiểu tuyết) sang cung 9 (sau Đông chí). Nếu hàm getSunLongitude trả lại cùng một kết quả cho cả ngày bắt đầu một tháng âm lịch và ngày bắt đầu tháng sau đó thì tháng đó không có Trung khí và như vậy có thể là tháng nhuận.

Tìm ngày bắt đầu tháng 11 âm lịch

Đông chí thường nằm vào khoảng 19/12-22/12, như vậy trước hết ta tìm ngày Sóc trước ngày 31/12. Nếu tháng bắt đầu vào ngày đó không chứa Đông chí thì ta phải lùi lại 1 tháng nữa.

function getLunarMonth11(yy, timeZone)

var k, off, nm, sunLong;
off = jdFromDate(31, 12, yy) - 2415021;
k = INT(off / 29.530588853);
nm = getNewMoonDay(k, timeZone);
sunLong = getSunLongitude(nm, timeZone); // sun longitude at local midnight
if (sunLong >= 9) {
	nm = getNewMoonDay(k-1, timeZone);
}
return nm;

Xác định tháng nhuận

Nếu giữa hai tháng 11 âm lịch (tức tháng có chứa Đông chí) có 13 tháng âm lịch thì năm âm lịch đó có tháng nhuận. Để xác định tháng nhuận, ta sử dụng hàm getSunLongitude như đã nói ở trên. Cho a11 là ngày bắt đầu tháng 11 âm lịch mà một trong 13 tháng sau đó là tháng nhuận. Hàm sau cho biết tháng nhuận nằm ở vị trí nào sau tháng 11 này.

function getLeapMonthOffset(a11, timeZone)

var k, last, arc, i;
k = INT((a11 - 2415021.076998695) / 29.530588853 + 0.5);
last = 0;
i = 1; // We start with the month following lunar month 11
arc = getSunLongitude(getNewMoonDay(k+i, timeZone), timeZone);
do {
	last = arc;
	i++;
	arc = getSunLongitude(getNewMoonDay(k+i, timeZone), timeZone);
} while (arc != last && i < 14);
return i-1;

Giả sử hàm getLeapMonthOffset trả lại giá trị 4, như thế tháng nhuận sẽ là tháng sau tháng 2 thường. (Tháng thứ 4 sau tháng 11 đáng ra là tháng 3, nhưng vì đó là tháng nhuận nên sẽ lấy tên của tháng trước đó tức tháng 2, và tháng thứ 5 sau tháng 11 mới là tháng 3).

Đổi ngày dương dd/mm/yyyy ra ngày âm

Với các phương pháp hỗ trợ trên ta có thể đổi ngày dương dd/mm/yy ra ngày âm dễ dàng. Trước hết ta xem ngày monthStart bắt đầu tháng âm lịch chứa ngày này là ngày nào (dùng hàm getNewMoonDay như trên đã nói). Sau đó, ta tìm các ngày a11 và b11 là ngày bắt đầu các tháng 11 âm lịch trước và sau ngày đang xem xét. Nếu hai ngày này cách nhau dưới 365 ngày thì ta chỉ còn cần xem monthStart và a11 cách nhau bao nhiêu tháng là có thể tính được dd/mm/yy nằm trong tháng mấy âm lịch. Ngược lại, nếu a11 và b11 cách nhau khoảng 13 tháng âm lịch thì ta phải tìm xem tháng nào là tháng nhuận và từ đó suy ra ngày đang tìm nằm trong tháng nào.

function convertSolar2Lunar(dd, mm, yy, timeZone)

var k, dayNumber, monthStart, a11, b11, lunarDay, lunarMonth, lunarYear, lunarLeap;
dayNumber = jdFromDate(dd, mm, yy);
k = INT((dayNumber - 2415021.076998695) / 29.530588853);
monthStart = getNewMoonDay(k+1, timeZone);
if (monthStart > dayNumber) {
	monthStart = getNewMoonDay(k, timeZone);
}
a11 = getLunarMonth11(yy, timeZone);
b11 = a11;
if (a11 >= monthStart) {
	lunarYear = yy;
	a11 = getLunarMonth11(yy-1, timeZone);
} else {
	lunarYear = yy+1;
	b11 = getLunarMonth11(yy+1, timeZone);
}
lunarDay = dayNumber-monthStart+1;
diff = INT((monthStart - a11)/29);
lunarLeap = 0;
lunarMonth = diff+11;
if (b11 - a11 > 365) {
	leapMonthDiff = getLeapMonthOffset(a11, timeZone);
	if (diff >= leapMonthDiff) {
		lunarMonth = diff + 10;
		if (diff == leapMonthDiff) {
			lunarLeap = 1;
		}
	}
}
if (lunarMonth > 12) {
	lunarMonth = lunarMonth - 12;
}
if (lunarMonth >= 11 && diff < 4) {
	lunarYear -= 1;
}

Đổi âm lịch ra dương lịch

Cách làm cũng tương tự như đổi ngày dương sang ngày âm.

function convertLunar2Solar(lunarDay, lunarMonth, lunarYear, lunarLeap, timeZone)

var k, a11, b11, off, leapOff, leapMonth, monthStart;
if (lunarMonth < 11) {
	a11 = getLunarMonth11(lunarYear-1, timeZone);
	b11 = getLunarMonth11(lunarYear, timeZone);
} else {
	a11 = getLunarMonth11(lunarYear, timeZone);
	b11 = getLunarMonth11(lunarYear+1, timeZone);
}
off = lunarMonth - 11;
if (off < 0) {
	off += 12;
}
if (b11 - a11 > 365) {
	leapOff = getLeapMonthOffset(a11, timeZone);
	leapMonth = leapOff - 2;
	if (leapMonth < 0) {
		leapMonth += 12;
	}
	if (lunarLeap != 0 && lunarMonth != leapMonth) {
		return new Array(0, 0, 0);
	} else if (lunarLeap != 0 || off >= leapOff) {
		off += 1;
	}
}
k = INT(0.5 + (a11 - 2415021.076998695) / 29.530588853);
monthStart = getNewMoonDay(k+off, timeZone);
return jdToDate(monthStart+lunarDay-1);

Tính ngày thứ và Can-Chi cho ngày và tháng âm lịch

Ngày thứ lặp lại theo chu kỳ 7 ngày, như thế để biết một ngày d/m/y bất kỳ là thứ mấy ta chỉ việc tìm số dư của số ngày Julius của ngày này cho 7.

Để tính Can của năm Y, tìm số dư của Y+6 chia cho 10. Số dư 0 là Giáp, 1 là Ất v.v. Để tính Chi của năm, chia Y+8 cho 12. Số dư 0 là Tý, 1 là Sửu, 2 là Dần v.v.

Hiệu Can-Chi của ngày lặp lại theo chu kỳ 60 ngày, như thế nó cũng có thể tính được một cách đơn giản. Cho N là số ngày Julius của ngày dd/mm/yyyy. Ta chia N+9 cho 10. Số dư 0 là Giáp, 1 là Ất v.v. Để tìm Chi, chia N+1 cho 12; số dư 0 là Tý, 1 là Sửu v.v.

Trong một năm âm lịch, tháng 11 là tháng Tý, tháng 12 là Sửu, tháng Giêng là tháng Dần v.v. Can của tháng M năm Y âm lịch được tính theo công thức sau: chia Y*12+M+3 cho 10. Số dư 0 là Giáp, 1 là Ất v.v.

Ví dụ, Can-Chi của tháng 3 âm lịch năm Giáp Thân 2004 là Mậu Thìn: tháng 3 âm lịch là tháng Thìn, và (2004*12+3+3) % 10 = 24054 % 10 = 4, như vậy Can của tháng là Mậu.

Một tháng nhuận không có tên riêng mà lấy tên của tháng trước đó kèm thêm chữ “Nhuận”, VD: tháng 2 nhuận năm Giáp Thân 2004 là tháng Đinh Mão nhuận.

Tài liệu tham khảo

• Edward M. Reingold and Nachum Dershowitz, Calendrical Calculations
• Helmer Aslaksen, The Mathematics of the Chinese Calendar
• Eric Weisstein’s World of Astronomy
• Calendar FAQ
• projectpluto.com (Open source implementation of many astronomical functions)
• Hồ Ngọc Đức, Âm lịch Việt Nam qua các thời kỳ lịch sử
• Hồ Ngọc Đức, VietCalendar.java – Một chương trình Java nhỏ (300 dòng) để chuyển đổi âm dương lịch
• Hồ Ngọc Đức, JavaScript lunar calendar – Chương trình âm lịch Việt Nam bằng JavaScript (sử dụng bảng tính sẵn cho thời kỳ 1800-2199)
• Tính âm lịch dùng các ngôn ngữ khác: JavaScript, PHP, Visual Basic, Python (chương trình Visual Basic và Python do Nguyễn Quốc Sản đóng góp)

Hồ Ngọc Đức

Những ngôn ngữ lập trình thú vị

Có rất nhiều ngôn ngữ lập trình, và nếu ngồi liệt kê hết thì chắc tới sáng tớ cũng không kết thúc được. Tớ đã từng tiếp xúc với khá nhiều ngôn ngữ: từ PHP, JavaScript đến Perl, từ Pascal, C đến Python, Ruby,… nhưng nếu hỏi đâu là ngôn ngữ tạo ấn tượng mạnh nhất, thì dứt khoát tớ không thể không nhắc đến Brainfuck, Whitespace và Piet.

1. Brainfuck

Theo Wikipedia, ngôn ngữ này ra đời năm 1993, với mục tiêu trở thành ngôn ngữ có compiler mang kích thước khiêm tốn nhất (dưới 200 byte!).

Cả ngôn ngữ chỉ gồm 8 command, mỗi command là 1 ký tự: > < + – . , [ ]

Hoàn toàn không có sự xuất hiện của các ký tự alphabet, hay số má 0 – 9, hay bất cứ gì khác. Thế nên đoạn chương trình in ra dòng chữ “Hello World” của Brainfuck trông thật ấn tượng:

view plaincopy to clipboardprint?

1. ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.——.——–.>+.>.

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Tớ từng dành ra không dưới 15 phút đánh vật với đoạn code này để thay chữ “Hello World” bằng tên tớ, và tin tớ đi, đánh vật có nghĩa là đánh vật đấy!

2. Whitespace

Ngôn ngữ thú vị thứ 2 mang tên Whitespace, và chắc bạn có thể đoán được, nó bao gồm các… whitespace. Với chỉ 3 loại ký tự: khoảng trắng, tab và dấu xuống dòng, việc phải “đọc” một đoạn code viết bằng Whitespace biến Brainfuck trở thành ngôn ngữ dễ đọc nhất trên đời.

Bạn có thể nhìn thử đoạn chương trình Hello World viết bằng Whitespace ở đây, nếu muốn thử trình độ đọc hiểu của mình.

3. Piet

Nếu như khi code bằng các ngôn ngữ lập trình khác, bạn “chơi với các ký tự”, thì khi code bằng Piet, bạn sẽ… tập vẽ tranh trừu tượng.

Hãy nói “Hello World” bằng Piet:

Hay giải thử bài toán Tháp Hà Nội với ngôn ngữ này:

Nếu bạn cũng như tớ, không mê xem tranh trừu tượng thì có thể sẽ thích “bức tranh” này:

Bạn nghĩ chương trình này làm được gì? Dĩ nhiên là tính toán số Pi! Và đoán xem làm thế nào để tăng hay giảm độ chính xác của nó? Hãy làm cho hình tròn to lên hoặc bé lại…

Cả 3 ngôn ngữ tớ vừa nêu đều được xếp vào loại esoteric programming language (hay esolang). Danh sách các ngôn ngữ như vậy bạn có thể xem ở esolang wiki, và tớ nghĩ bạn sẽ không ngạc nhiên mấy, khi biết rằng bên cạnh Brainfuck còn có Brainfuck++…

http://onetruebrace.com/

Nghệ thuật tạo tranh trên nền cát

Đây là đoạn clip phần thi của cô gái đoạt giả nhất cuộc thi tài năng Ukraine

3 bài toán quy hoạch động hay

Minh họa cho vui

Sau đây mình xin giới thiệu tới các bạn 3 bài toán quy hoạch động khá thú vị. Thú vị ở  chỗ chúng có đề bài rất giống nhau, chỉ  khác ở chỗ rất nhỏ nhưng lại làm cho chúng có mức độ  khó tăng dần. Thực ra thì cũng không có gì lắm, nhưng dẫu sao cũng mời các bạn cùng “thưởng thức” :

Bài toán 1:

Cho ma trận A kích cỡ M*N (1<=M,N<=100, M dòng, N cột).Mỗi ô của ma trận có một giá trị nguyên nằm trong khoảng 1..100. Từ  mỗi ô (I,J) (I: chỉ số cột, J: chỉ số dòng) có thể đến được các ô sau (nếu có):  (I+1,J-1), (I+1,J), (I+1,J+1).

Hãy tìm một đường đi xuất phát từ ô bất kì của cột 1 và kết thúc tại ô bất kì của cột N sao cho tổng giá trị của các ô đi qua trên đường đi là nhỏ nhất.

>>Thuật giải: Không cần bàn nhiểu ta cũng thấy ngay được công thức quy hoạch động của bài này. Gọi Fx[I,J] là tổng giá trị nhỏ nhất để đi từ  một ô bất kì của cột 1 đến ô (I,J). Khi đó:

F[1,J]=A[1,J] (1<=J<=M)

F[I,J]=Min(F[I-1,J-1],F[I-1,J],F[I-1,J+1])+A[I,J] (2<=I<=N,1<=J<=M)

Truy vết in ra đường đi cũng không có gì khó khắn lắm

Bài toán 2: Tương tự  như  bài toán 1 nhưng  ô (I,J) có thể đến các ô sau: (I,J+1), (I,J-1), (I+1,J)

Khá là vấn đề khi áp dụng QHĐ do một ô có thể được đến từ  một ô khác ở cột liền trước bên trái hoặc một ô liền trên hoặc một ô liền dưới. Ở bài toán trên ta tính Fx lần lượt từ  cột 1 đến cột N do kết quả mỗi cột chỉ phụ thuộc vào cột trước nó đằng này bài 2 chúng ta bị ép 3 phía như thế ta không biết sẽ phải tính toán Fx theo thứ  tự  như  thế nào :-S Các của mình đưa ra là QHĐ kết hợp thêm chút ít “thủ công”

>>Thuật giải: Ta cũng thiết kế một mảng Fx[I,J] chức năng như  trên nhưng ta sẽ tính theo một cách khác. Đầu tiên cũng sẽ là gán F[1,J]:=A[1,J] với 1<=J<=M. Với mỗi ô (I,J) ta nhận thấy trên đường đi nhỏ nhất dẫn đến nó thì sẽ có một ô (I-1,X) để từ  ô (I-1,X) chuyển sang ô (I,X) rồi đi đến nó. Chỉ cần xác định được ô (I-1,X) tính được Fx[I,J]. Mà 1<=X<=M nên ta sẽ thử  lần lượt X từ 1 đến M rồi tìm Min. Khi tìm được ta nên lưu lại giá trị của X cho mỗi ô (I,J) để tiện cho việc truy vết. Sau đây là mã nguồn mình cài đặt cho thuật toán này:

Uses Crt;
Var Map:Array[1..100,1..100] Of Byte;
Rs:Array[1..100,1..100] Of Record {chính là mảng Fx, với value là giá trị nhỏ nhất còn Back là X)
Back:Byte;
Value:Longint;
End;
M,N,i,j:Byte;
{—————————–}
Procedure ReadDT;
Var I,J:Integer;
F:text;
Begin
assign(f,’fi.inp’);reset(F);
Readln(F,M,N);
For J:=1 To M Do
Begin
For I:=1 To N Do Read(f,Map[I,J]);
Readln(F);
End;
End;
{——————————–}
Function GetRs(X,Y,Back:Byte):Longint; (Tính xem giá trị của đường đi tới ô (X,Y) nếu X=Back)
Var S:Longint;
I:Byte;
Begin
S:=Map[X,Y]+Rs[X-1,Back].Value;
For I:=Back To Y-1 Do Inc(S,Map[X,I]);
For I:=Y+1 To Back Do Inc(S,Map[X,I]);
GetRs:=S;
End;
{——————————–}
Procedure GenRsTable; (tạo bảng giá trị (mảng Rs))
Var Back,I,J:Byte;
S:Longint;
Begin
For J:=1 To M Do Rs[1,J].Value:=Map[1,J];
For I:=2 To N Do
For J:=1 To M Do
Begin
Rs[I,J].Value:=GetRs(I,J,1);
Rs[I,J].Back:=1;
For Back:=2 To M Do
Begin
S:=GetRs(I,J,Back);
If S<Rs[I,J].Value Then
Begin
Rs[I,J].Value:=S;
Rs[I,J].Back:=Back;
End;
End;
End;
End;
{——————————–}
Procedure OutIJ(X,Y:Byte);
Var I:Byte;
Begin
If X=1 Then
Begin
Writeln(X,’ ‘,Y);
Exit;
End;
OutIJ(X-1,Rs[X,Y].Back);
For I:=Rs[X,Y].Back To Y-1 Do Writeln(X,’ ‘,I);
For I:=Rs[X,Y].Back DownTo Y+1 Do Writeln(X,’ ‘,I);
Writeln(X,’ ‘,Y);
End;
{——————————–}
Procedure WriteRs;
Var I,J,JMin:Byte;
SMin:Longint;
Begin
SMin:=Rs[N,1].Value;
JMin:=1;
For J:=1 To M Do
If Rs[N,J].Value<SMin Then Begin
SMin:=Rs[N,J].Value;
JMin:=J;
End;
Writeln(SMin);
OutIJ(N,JMin);
End;
{——————————–}
Begin
Clrscr;
ReadDT;
GenRsTable;
writeRs;
readln;
End.

3. Bài toán 3: Tương tự  như  bài toán 1 nhưng  ô (I,J) có thể đến các ô sau: (I,J+1), (I,J-1), (I+1,J), (I-1,J)

Lần này bị o ép từ 4 phía thì có vẻ như  quy hoạch động khá khó khăn.

>>Thuật giải: Coi mỗi ô của ma trận như  một đỉnh của đồ thị. Áp dụng dijkstral. Lưu ý chương trình của mình của mình không sử  dụng mạng hai chiều mà “dãn” ra thành mảng 1 chiểu. Hàm Conv(X,Y:Byte) cho vị trí ô (X,Y) trong mảng một chiều.

Var P,Map:Array[1..100*100] Of Byte;
L,R:Array[1..100*100] Of Integer;
M,N:Byte;
C,First,Last:Integer;
{——————-}
Function Conv(X,Y:Byte):Integer;
Begin
Conv:=Y*N-N+X;
End;
{——————–}
Procedure ReadDt;
Var I,J:Byte;
Begin
Readln(M,N);
For J:=1 To M Do
For I:=1 To N Do Read(Map[Conv(I,J)]);
End;
{——————}
Procedure Add(Id:Integer);
Begin
If Last=100*100 Then Last:=1 Else Inc(Last);
L[Last]:=Id;
Inc(C);
End;
{——————}
Function Pop:Integer;
Begin
Pop:=L[First];
If First=100*100 Then First:=1 Else Inc(First);
Dec(C);
End;
{——————-}
Procedure Proc(Id:Integer);
Var X,Y:Byte;
Begin
X:=Id Mod N; If X=0 Then X:=N;
Y:=Id Div N; If X<>N Then Inc(Y);
If X<N Then
If (R[Conv(X+1,Y)]>(Map[Conv(X+1,Y)]+R[ID]))Or(R[Conv(X+1,Y)]=0) Then
Begin
R[Conv(X+1,Y)]:=Map[Conv(X+1,Y)]+R[Id];
P[Conv(X+1,Y)]:=Id;
Add(Conv(X+1,Y));
End;
{”””””””}
If X>1 Then
If (R[Conv(X-1,Y)]>(Map[Conv(X-1,Y)]+R[Id]))Or(R[Conv(X-1,Y)]=0) Then
Begin
R[Conv(X-1,Y)]:=Map[Conv(X-1,Y)]+R[Id];
P[Conv(X-1,Y)]:=Id;
Add(Conv(X-1,Y));
End;
{”””””””}
If (Y<M)And(X<>1)And(X<>N) Then
If (R[Conv(X,Y+1)]>(Map[Conv(X,Y+1)]+R[Id]))Or(R[Conv(X,Y+1)]=0) Then
Begin
R[Conv(X,Y+1)]:=(Map[Conv(X,Y+1)]+R[Id]);
P[Conv(X,Y+1)]:=Id;
Add(Conv(X,Y+1));
End;
{”””””””}
If (Y>1)And(X<>1)And(X<>N) Then
If (R[Conv(X,Y-1)]>(Map[Conv(X,Y-1)]+R[Id]))Or(R[Conv(X,Y-1)]=0) Then
Begin
R[Conv(X,Y-1)]:=(Map[Conv(X,Y-1)]+R[Id]);
P[Conv(X,Y-1)]:=Id;
Add(Conv(X,Y-1));
End;

End;
{——————-}
Procedure OutRs;
Procedure DQ(Id:Integer);
Var X,Y:Byte;
Begin
X:=Id Mod N; If X=0 Then X:=N;
Y:=Id Div N; If X<>N Then Inc(Y);
If P[Id]=0 Then
Begin
Writeln(Y,’ ‘,X);
Exit;
End;
DQ(P[Id]);
Writeln(Y,’ ‘,X);
End;
{—————}
Var Min,PMin:Integer;
X,Y:Byte;
Begin
Min:=R[Conv(N,1)];
PMin:=Conv(N,1);
For Y:=2 To M Do
If R[Conv(N,Y)]<Min Then
Begin
Min:=R[Conv(N,Y)];
PMin:=Conv(N,Y);
End;
Writeln(Min);
DQ(PMin);
End;
{——————-}
Procedure GenRs;
Var I:Byte;
Begin
Last:=0;First:=1;
FillChar(R,SizeOf(R),0);
FillChar(P,SizeOf(P),0);
C:=0;
For I:=1 To M Do
Begin
Add(Conv(1,I));
R[Conv(1,I)]:=Map[Conv(1,I)];
End;
While C<>0 Do Proc(Pop);
End;
{——————-}
Begin
ReadDT;
GenRs;
OutRs;
End.

Lưu ý cấu trúc file Input:

- Dòng đầu: M và N

- M dòng sau mỗi dòng là N số nguyên tương ứng với giá trị của ô (I,J)

BLAST

Cho hai xâu A, B. Mở rộng của 1 xâu X là xâu thu được bằng cách chèn (0,1,2 ..) kí tự trống vào xâu. Ví dụ : X là ‘abcbcd’, thì ‘abcb-cd’, ‘-a-bcbcd-’ và ‘abcb-cd-’ là các mở rộng của X. (Dấu cách kí hiệu bằng ‘-‘).

A1,B1 là mở rộng của A và B, và giả sử chúng cùng độ dài. Khoảng cách giữa A1 và B1 là tổng khoảng cách giữa các kí tự cùng vị trí. Nếu hai kí tự không là dấu cách thì khoảng cách giữa 2 kí tự này là trị tuyệt đối mã ASCII của chúng. Còn ngược lại, khoảng cách là 1 số K cố định.

Cho hai xâu A, B. Tìm khoảng cách nhỏ nhất giữa hai xâu mở rộng của nó.

Input

Dòng 1 chứa A, dòng 2 chứa B, chỉ gồm chữ thường a-z và số kí tự <=2000.

Dòng thứ 3 là số K, khoảng cách của 1 kí tự bất kỳ với kí tự trống, 1 ≤ K ≤ 100.

Output

Khoảng cách nhỏ nhất.

Sample

blast.in 

cmc
snmn
2 

blast.out 

10 

blast.in 

koiv
ua
1 

blast.out 

5

blast.in 

mj
jao
4 

blast.out 

12 

const maxn=2000;
var s1,s2:ansistring;
 F:array[0..maxn,0..maxn] of longint;
 i,j,k:longint;
function min(x,y:longint):longint;
 begin
 if x>y then x:=y;
 min:=x;
 end;
BEGIN
 readln(s1);
 readln(s2);
 readln(k);
 f[0,0]:=0;
 for i:=1 to length(s1) do f[i,0]:=f[i-1,0]+k;
 for i:=1 to length(s2) do f[0,i]:=f[0,i-1]+k;
 for i:=1 to length(s1) do
 for j:=1 to length(s2) do
 begin
 f[i,j]:=min(min(f[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])),f[i-1,j]+k),min(f[i-1,j-1]+2*k,f[i,j-1]+k));
 end;
 writeln(f[length(s1),length(s2)]);
END.