Mình đang theo dõi vài blog này, nhiều kiến thức quá
http://vuontoanblog.blogspot.com/2015/04/Taylor-series.html
http://thichhoctoan.net/page/2/
https://vuhavan.wordpress.com/
Ảnh
Chủ Nhật, 26 tháng 4, 2015
Thứ Bảy, 25 tháng 4, 2015
Đi tìm bội chung nhỏ nhất (3 số). BCNN của 3 số liên tiếp.
Hôm nay lên đồng, từ cái chương trình cơ bản phát triển lên thành chương trình tối ưu luôn (maybe) :D
Có một bạn, chia sẻ trên daynhauhoc một chương trình để tìm BCNN của 3 số.
Các bước tìm của bạn ấy như sau:
Có một bạn, chia sẻ trên daynhauhoc một chương trình để tìm BCNN của 3 số.
Các bước tìm của bạn ấy như sau:
- Tìm max của 3 số, ta gọi là GREATEST
- Vào for cho i chạy từ GREATEST đến vô cùng, nếu i chia hết cho 3 số thì là số cần tìm.
Lang thang vào, thấy hợp lý quá. Cơ mà, để ý, thằng GREATEST+1, GREATEST+2 cũng không chia hết cho GREATEST. Ít nhất thì nó cũng phải bằng 2 lần GREATEST thì mới chia hết cho GREATEST chứ. Thế là một cải tiến mới ra đời. (Cải tiến 1)
- Tìm max của 3 số, ta gọi là GREATEST
- Kiểm tra GREATEST có phải BCNN hay không.
- Vào for cho i chạy từ GREATEST*2 đến vô cùng, nếu i chia hết cho 3 số thì là số cần tìm.
Lại lên đồng, mình thấy thằng (GREATEST*2)+1 cũng đâu có chia hết cho GREATEST đâu. Thằng (GREATEST*3)+1 cũng không chia hết luôn. Rồi, cải tiến, again (Cải tiến 2)
- Tìm max của 3 số, ta gọi là GREATEST
- Vào for cho i chạy từ 1 đến vô cùng, nếu i*GREATEST chia hết cho 2 số thì là số cần tìm.
Vậy còn cải tiền nào nữa không?
Còn!!! Chúng ta có thể cải tiến thằng (Cải tiến 1) lên theo hướng khác. Nếu chúng ta biết các số còn lại có chứa các số nguyên tố nào mà GREATEST chưa có. Ta chỉ cần nhân vào và kiểm tra tịnh tiến cho i tăng dần. Có thể dễ thấy với trường hợp sau.
a=10 b=6 c=18. GREATEST=18, tồn tại 3 snt là 2,3 và 5, 2 và 3 thì ở trong 18 rồi vậy thì . ta sẽ kiểm tra số 18*5.
Cách này thì dùng cho 3 số với khoảng cách lớn và số cũng phải bự nữa.
Vậy BCNN có gì phải chú ý nữa không. Với những cảm giác như ở những cải tiến trước, ta cảm thấy 3 số liên tiếp nhau sẽ có BCNN là tích của 3 số. Ồ, sau khi ngủ dậy mình lại có một cảm giác khác. nếu a là số chẵn thì BCNN bằng tích 3 số chia 2. nếu a lẻ thì bằng tích 3 số. Muốn biết rõ hay không thì phải chứng minh đã. Chứng minh = yên tâm.
Xét trường hợp a và c là số lẻ, b là số chẵn.
a=2k+1, b=2k+2, c=2k+3
tìm bội chung nhỏ nhất của 2 số a và c đã. Ta có BCNN=(a*c)/UCLN(a,c)
UCLN của a và c có thể tìm theo thuật toán Euler và UCLN của 2 số đó = 1.
Vậy BCNN của a và c là a*c.
Ta sẽ phải tìm BCNN của a*c và b. Tích a*c=4k^2+8k+3
Xét trường hợp a và c là số lẻ, b là số chẵn.
a=2k+1, b=2k+2, c=2k+3
tìm bội chung nhỏ nhất của 2 số a và c đã. Ta có BCNN=(a*c)/UCLN(a,c)
UCLN của a và c có thể tìm theo thuật toán Euler và UCLN của 2 số đó = 1.
Vậy BCNN của a và c là a*c.
Ta sẽ phải tìm BCNN của a*c và b. Tích a*c=4k^2+8k+3
Về bài toán tìm bộ ba Pytago có tổng bằng một số
Bài này làm lâu rồi, hôm nay thấy nên khui lại.
Đề: Tìm bộ ba a, b, c thỏa mãn a^2+b^2=c^2, đồng thời a+b+c=X.
Mình dùng phương pháp bộ 3 số pytago tổng quát. Trong bài này thì mình sẽ lấy X=1000:D.
Công thức sau tổng quát tất cả các bộ ba số Pythagoras (không đơn trị):
a = k*(2mn)
b = k*(m2 - n2)
c = k*(m2 + n2)
trong đó m và n là hai số nguyên dương với m > n và k là số nguyên dương tùy ý.
ok, a+b+c=1000 <=> k*(2mn+2m2) = 1000 <=> k*m*(m+n)=500 (*)
Mà các số k,m,n là các số nguyên dương vậy số 1000/2 phải có ít nhất 2 ước số (k có thể bằng 1). Cách này có thể dùng để kiểm tra bài toán có nghiệm hay không với mỗi X.
Để tìm nghiệm nhanh hơn thì mình sẽ dùng ước số của 500 để chọn nhanh hơn.
Ta có 500=2.2.5.5.5 có 5 nhân tử. trong (*) ta nhận thấy có 3 thành phần là k,m và (m+n). Vậy thì có bao nhiêu cách chia 5 phần tử 2,2,5,5,5 thành 3 nhóm. Ta có thể chia 1-1-3,1-2-2, và các hoán vị.
Đề: Tìm bộ ba a, b, c thỏa mãn a^2+b^2=c^2, đồng thời a+b+c=X.
Mình dùng phương pháp bộ 3 số pytago tổng quát. Trong bài này thì mình sẽ lấy X=1000:D.
Công thức sau tổng quát tất cả các bộ ba số Pythagoras (không đơn trị):
a = k*(2mn)
b = k*(m2 - n2)
c = k*(m2 + n2)
trong đó m và n là hai số nguyên dương với m > n và k là số nguyên dương tùy ý.
ok, a+b+c=1000 <=> k*(2mn+2m2) = 1000 <=> k*m*(m+n)=500 (*)
Mà các số k,m,n là các số nguyên dương vậy số 1000/2 phải có ít nhất 2 ước số (k có thể bằng 1). Cách này có thể dùng để kiểm tra bài toán có nghiệm hay không với mỗi X.
Để tìm nghiệm nhanh hơn thì mình sẽ dùng ước số của 500 để chọn nhanh hơn.
Ta có 500=2.2.5.5.5 có 5 nhân tử. trong (*) ta nhận thấy có 3 thành phần là k,m và (m+n). Vậy thì có bao nhiêu cách chia 5 phần tử 2,2,5,5,5 thành 3 nhóm. Ta có thể chia 1-1-3,1-2-2, và các hoán vị.
Thứ Sáu, 24 tháng 4, 2015
Về câu chuyện du hành thời gian
Suốt 12 năm học phổ thông, môn lý là môn học đã nhất, gần gũi với thực tiễn. Đến năm lớp 10, cũng không nhớ năm nào nhưng mà cái năm học về các định luật bảo toàn. Mấy cái định luật bảo toán mới là mấu chốt của vấn đề, từ đấy các định luật đấy mới thi triển ra hàng ngàn công thức khác nhau. Bài dễ thì áp công thức vào, còn bài khó thì cứ lôi các định luật bảo toàn ra, quây quần vật lộn với nó ắt sẽ ra, không ra nữa thì chắc đề sai. Đến khi học về thuyết tương đối, cái thuyết này cũng một dạng bảo toàn, năng lượng và khối lượng có thể chuyển hóa cho nhau đều được.
Sau này, có nghe về sự tương đối giữa không-thời gian. Cũng chả nhớ đọc ở đâu hay nghe từ ai về cái gọi là "tương đối giữa không-thời gian", chắc là Star Trek. Cơ mà mình nghĩ thế này, thời gian nó cũng chỉ là một cái mốc để đánh dấu không gian, và không gian cũng là một cái mốc để đánh dấu thời gian. Ví dụ bạn đi coi phim ngoài rạp, bạn đến lúc 6:00 thì đó chính là cột mốc để đánh dấu "không gian" phim age of ultron. Còn bạn đi coi age of ultron thì đó chính là một cột mốc đánh dấu bạn đang ở "thời gian" 6:00.
Nhưng để nói rõ về không gian đã. Không gian là một trạng thái, nó rất nhiều yếu tố, nhiệt độ, ấp suất,... tất cả các yếu tố mà chúng ta cố gắng kể ra được vẫn chỉ là một phần nhỏ so với các yếu tố mà không gian đó có. Thời gian, nó không có đơn vị, nó chỉ là một cột mốc thôi, và chúng ta không thấy nó, nhưng chúng ta so sánh nó với thời gian khác cũng được.
Đó là suy nghĩ của mình về cái gọi là "tương đối không-thời gian". Và không thời gian này sẽ giống như một dòng sông, trôi theo một hướng nhất định. Ví dụ, bạn để một trái banh trên máng trượt, thả tay ra, sau một thời gian, banh lăn xuống. Thời điểm ban đầu, bạn đánh dấu trạng thái bằng không gian, ở trên đỉnh máng. Thời điểm sau bạn đánh dấu bằng trạng thái banh trượt xuống máng. Tức là nó sẽ trôi, không gian sẽ trôi, thời gian cũng sẽ trôi. Nếu bạn ở một không gian A, thì thời điểm tiếp theo bạn sẽ phải trôi đến một không gian B, không thể trôi đến không gian C. Nếu bạn đặt trái banh lên đầu máng thì nó sẽ trôi đến cuối máng. không thể trôi ra ngoài, nếu trôi ra ngoài thì tức là không gian A đã bị biến đổi. Vậy muốn nó ngừng trôi, hãy dừng tất cả lại. Vậy muốn nó trôi ngược, hãy đảo ngược các bước.
Vậy còn về chuyện tiên đoán tương lai, có rất nhiều người làm được điều đó đấy chứ. Lưu ý rằng chúng ta chỉ tiên đoán được trong một tương lai "gần". Vì sao nó lại "gần" vì chúng ta thu hẹp không gian lại. Chúng ta thu hẹp không gian lại thành một không gian hoàn hảo, ít yếu tố hơn. Lại một sự tương quan nữa giữa không-thời gian. Thời gian nhỏ, không gian nhỏ, thời gian lớn, không gian lớn. Thời điểm càng gần nhau, không gian càng ít sự thay đổi.
Và du hành thời gian <=> sắp xếp lại trật tự không gian ở một thời điểm nào đó. Bạn ở một không gian nhất định thì bạn cũng sẽ ở một thời gian nhất định. Vậy nếu có 2 không gian giống y hết nhau tại 2 thời điểm khác nhau thì chuyện gì sẽ xảy ra. Vâng, chúng ta sẽ trôi theo một vòng tròn hoặc vòng số 8 :)).
Vậy thì ở đời thực có thể gặp không gian giống nhau tại 2 thời điểm khác nhau hay không. E rằng rất khó, vũ trụ đang nở ra, không gian thay đổi ngay lập tức, rất khó. Nhưng đừng lo, có một giả thuyết cho rằng, sau khi vũ trụ đã nở ra hết sức thì nó sẽ thu lại. Nhưng hãy nhớ rằng, đó là truyện của vũ trụ, còn trái đất của chúng ta thì đang bị tàn phá, đến nỗi không khôi phục được, huống chi là chuyện du hành thời gian. Nhưng hãy cứ hi vọng, có thể chúng ta sẽ gặp lại nhau tại bài viết này lần sau... :))
Sau này, có nghe về sự tương đối giữa không-thời gian. Cũng chả nhớ đọc ở đâu hay nghe từ ai về cái gọi là "tương đối giữa không-thời gian", chắc là Star Trek. Cơ mà mình nghĩ thế này, thời gian nó cũng chỉ là một cái mốc để đánh dấu không gian, và không gian cũng là một cái mốc để đánh dấu thời gian. Ví dụ bạn đi coi phim ngoài rạp, bạn đến lúc 6:00 thì đó chính là cột mốc để đánh dấu "không gian" phim age of ultron. Còn bạn đi coi age of ultron thì đó chính là một cột mốc đánh dấu bạn đang ở "thời gian" 6:00.
Nhưng để nói rõ về không gian đã. Không gian là một trạng thái, nó rất nhiều yếu tố, nhiệt độ, ấp suất,... tất cả các yếu tố mà chúng ta cố gắng kể ra được vẫn chỉ là một phần nhỏ so với các yếu tố mà không gian đó có. Thời gian, nó không có đơn vị, nó chỉ là một cột mốc thôi, và chúng ta không thấy nó, nhưng chúng ta so sánh nó với thời gian khác cũng được.
Đó là suy nghĩ của mình về cái gọi là "tương đối không-thời gian". Và không thời gian này sẽ giống như một dòng sông, trôi theo một hướng nhất định. Ví dụ, bạn để một trái banh trên máng trượt, thả tay ra, sau một thời gian, banh lăn xuống. Thời điểm ban đầu, bạn đánh dấu trạng thái bằng không gian, ở trên đỉnh máng. Thời điểm sau bạn đánh dấu bằng trạng thái banh trượt xuống máng. Tức là nó sẽ trôi, không gian sẽ trôi, thời gian cũng sẽ trôi. Nếu bạn ở một không gian A, thì thời điểm tiếp theo bạn sẽ phải trôi đến một không gian B, không thể trôi đến không gian C. Nếu bạn đặt trái banh lên đầu máng thì nó sẽ trôi đến cuối máng. không thể trôi ra ngoài, nếu trôi ra ngoài thì tức là không gian A đã bị biến đổi. Vậy muốn nó ngừng trôi, hãy dừng tất cả lại. Vậy muốn nó trôi ngược, hãy đảo ngược các bước.
Vậy còn về chuyện tiên đoán tương lai, có rất nhiều người làm được điều đó đấy chứ. Lưu ý rằng chúng ta chỉ tiên đoán được trong một tương lai "gần". Vì sao nó lại "gần" vì chúng ta thu hẹp không gian lại. Chúng ta thu hẹp không gian lại thành một không gian hoàn hảo, ít yếu tố hơn. Lại một sự tương quan nữa giữa không-thời gian. Thời gian nhỏ, không gian nhỏ, thời gian lớn, không gian lớn. Thời điểm càng gần nhau, không gian càng ít sự thay đổi.
Và du hành thời gian <=> sắp xếp lại trật tự không gian ở một thời điểm nào đó. Bạn ở một không gian nhất định thì bạn cũng sẽ ở một thời gian nhất định. Vậy nếu có 2 không gian giống y hết nhau tại 2 thời điểm khác nhau thì chuyện gì sẽ xảy ra. Vâng, chúng ta sẽ trôi theo một vòng tròn hoặc vòng số 8 :)).
Vậy thì ở đời thực có thể gặp không gian giống nhau tại 2 thời điểm khác nhau hay không. E rằng rất khó, vũ trụ đang nở ra, không gian thay đổi ngay lập tức, rất khó. Nhưng đừng lo, có một giả thuyết cho rằng, sau khi vũ trụ đã nở ra hết sức thì nó sẽ thu lại. Nhưng hãy nhớ rằng, đó là truyện của vũ trụ, còn trái đất của chúng ta thì đang bị tàn phá, đến nỗi không khôi phục được, huống chi là chuyện du hành thời gian. Nhưng hãy cứ hi vọng, có thể chúng ta sẽ gặp lại nhau tại bài viết này lần sau... :))
Thứ Năm, 16 tháng 4, 2015
Destructor, tưởng rõ mà vẫn chưa rõ
Như mình được học thì có 3 cách truyền tham số vào một hàm:
- Truyền tham trị
- Truyền tham chiếu (cho C++)
- Truyền địa chỉ (aka chuyền tham số, mà không rõ nên để địa chỉ nhé)
Hồi đầu mình học C/C++, thì mình chủ yếu dùng truyền địa chỉ và truyền tham trị. Nếu biến truyền vào hàm để thay đổi thì mình thích dùng truyền địa chỉ hơn vì nó rõ ràng. Địa chỉ là một thứ rất rõ ràng, phân biệt giữa ô nhớ này với ô nhớ kia. Truyền vào hàm sử dụng cũng đơn giản nữa. Nếu muốn dùng địa chỉ cho việc gì đó cứ để tên biến. Muốn truy xuất giá trị của ô có địa chỉ đó thì dùng phương thức dereference (đặt * trước tên biến).
Còn truyền tham chiếu? Ông này thì của C++. Cả một tháng nay toàn sài cái này. Cũng không có gì phức tạp lắm nếu truyền bình thường, y chang thằng truyền địa chỉ mà đỡ phức tạp hơn khi sử dụng. Thấy sài sướng quá nên chuyển hẳn qua tham chiếu sài. Sài cho đã mới biết là chưa đọc hướng dẫn sử dụng... (tai hại chưa)
Rồi hôm nay có làm về struct, cụ thể là làm cái destructor cho List. Oái ăm, chương trình bị lỗi, cái danh sách liên kết tự nhiên bị destruct hết, đáng lẽ sau khi thoát chương trình thì nó sẽ destruct chứ, sao đang chạy mà lại destruct. Hàm đầu tiên cho thằng List vào là hàm input(vì danh sách thay đổi nên mình cho nó truyền tham chiếu vào hàm). Sau đó mình cho nó vào hàm output(không có thay đổi gì trong danh sách nên cho truyền tham trị thôi). Ngon lành, in ra hết giá trị trong List, rồi giờ cho thằng List nhảy sang hàm khác làm, ngay khúc này bị lỗi. Cứng người, debug thì phát hiện ra sau khi thoát hàm output thì cái List cũng tự động thực hiện destructor luôn. LẠ, lên mạng tìm hiểu. Có ba thứ cần tìm hiểu:
- Phương thức destructor(when, how)
- Reference(what, how)
- Passing by Reference and Pointer(giống nhau và khác nhau)
Gặp những trường hợp lỗi này đúng là quý báu, lỗi 1 mà học được 10. cái thứ 3 thì cũng biết một ít thôi, 2 anh Ref và Poi này chỉ khác nhau một chút. Poi là một biến nhưng giá trị nó chứa là địa chỉ, Ref anh này chỉ là một alias (một nick name khác). Khi chúng ta gọi tên của một biến, thì chương trình sẽ tìm xem ô nhớ nào có tên như thế (tùy vào scope) -> Tức là một ô nhớ sẽ có nhiều tên, và thằng Ref sẽ là cách để ô nhớ đó có thêm một tên. không có gì ghê gớm lắm. Vậy mình dùng Pointer cũng bị lỗi này thôi.
Tìm trên mạng cũng không có gì thêm về ý 2 và 3. Vậy thì chắc là do anh destructor rồi.
Có 2 thời điểm destructor sẽ được thực hiện:
- Khi đối tượng ra khỏi scope của nó
- Khi ta gọi hàm hủy của đối tượng(chỉ thực sự bị hủy khi ra khỏi scope)
Nói chung là ra khỏi scope của nó thì nó sẽ gọi destructor. Ok, xem lại trưởng hợp lỗi nào, để xem scope của List ở đâu. Scope của một đối tượng là gì, đó chình là khu vực mà nó được biết đến, làm sao để biết đến, nó phải được khai báo. Ta xem lại hàm output, ta khai báo List như một tham trị (cách truyền này sẽ copy thằng List ra một bản sao khác), và tất nhiên sau khi out ra khỏi scope output thì nó sẽ hủy thằng List bản sao này, và thằng bản chính kia lại không sao. Xui thay thằng List lại chứa những địa chỉ. Thế thì khi hủy nó sẽ hủy đi các ô được cấp phát động được gọi sâu bên dưới, và thằng List bản chính chỉ giữ lại một đỉa chỉ trỏ đến một nơi hư không ~~
Vậy thì khi truyền tham chiếu thì như thế nào, tất nhiên scope của thằng List này sẽ nằm ở hàm main. Và khi kết thúc chương trình thì mới bị hủy theo kế hoạch.
Đăng ký:
Bài đăng (Atom)
