Chào các bạn,

ChuyenHVT.net thành lập 2005 - Nơi lưu trữ rất nhiều kỉ niệm của các thế hệ học sinh trong 15 năm qua. Tuy chúng mình đã dừng hoạt động được vài năm rồi. Hiện nay diễn đàn chỉ đăng nhập và post bài từ các tài khoản cũ (không cho phép các tài khoản mới đăng ký mới hoạc động). Mong ChuyenHVT.net sẽ là một phần kỉ niệm thanh xuân đẹp nhất của các bạn.


M.

Kết quả 1 đến 8 của 8

Chủ đề: Ứng dụng phương pháp quy nạp toán học

  1. #1
    Moderator thử việc HLN1994's Avatar
    Ngày tham gia
    11-08-2009
    Tuổi
    25
    Bài viết
    1,187
    Cảm ơn
    766
    Đã được cảm ơn 364 lần ở 185 bài viết

    Mặc định Ứng dụng phương pháp quy nạp toán học

    Trong toán học, quy nạp là một phương pháp đơn giản nhưng hiệu quả để chứng minh các bài toán. Ở bài viết này tôi xin đưa ra một ứng dụng nhỏ của nó trong việc giải các bài toán tin học:

    1. Thuật toán quy nạp quy nạp(nhắc lại):

    Giả sử có bài toán F cần chứng minh đúng với mọi n thuộc N. Ta chứng minh bài toán đúng bằng cách quy nạp, cần tiến hành các bước sau:
    - n = 1: mệnh đề cần chứng minh đúng.
    - Giả sử n = k: mệnh đề cần chứng minh đúng.
    - n = k + 1: ta cần chứng nó cũng đúng. Vậy theo nguyên lý quy nạp bài toán đúng với mọi N.
    Trong tin học, thuật toán nay cũng được áp dụng. Tuy thuật toán đơn giản nhưng nó lại được áp dụng một cách rất linh động và khéo léo trong các bài toán tin.

    2. Phát biểu bài toán tổng quát giải bằng quy nạp:

    Thông thường bài toán giải bằng quy nạp không phải là một bài toán tối ưu hoá. Nó chỉ đơn giản là bài toán cần chỉ ra cách biến đổi theo quy luật cho trước để thu được kết quả mong đợi. Và bài toán đó thường được phát biểu như sau:Cho N đối tượng và một số thao tác biến đổi. Yêu cầu sử dụng các thao tác biến đổi để thu được kết mong đợi.
    Cách làm thông thường:
    - Nếu n = 0; 1: ta luôn có cách biến đổi đúng.
    - Nếu có n > 1 mà ta luôn chỉ ra một cách biến đổi sao cho giản bớt được số đối tượng mà điều kiện bài toán vẫn không thay đổi.
    - Như vậy vì số đối tượng trong một bài toán tin học luôn là hữu hạn nên sau một số hữu hạn bước thì số lượng đối tương bằng 1 hoặc 0. Suy ra bài toán được giải quyết một cách hoàn toàn.

    3. Các ví dụ cụ thể:

    P1. Cho N vecto v1, v2, …, vn độ dài nhỏ hơn L cho trước. Cần đặt trước các vecto một dấu cộng hoặc trừ sao cho vecto tổng thu được có độ dài nhỏ hơn căn 2 nhân L.Input: Segment.In
    - Dòng đầu ghi số N ( 1 < N ≤ 10000) và L (0 < L ≤ 15000.00)
    - N dòng tiếp theo mỗi dòng ghi một cặp số xi, yi là toạ độ của vecto thứ i. (|xi|, |yi| ≤ 10000).
    Ouput: Segment.out
    - Dòng thứ nhất ghi YES nó có thể đặt các dấu cộng trừ thoả mãn yêu cầu bài toán, NO trong trường hợp ngược lại.
    - Nếu là YES dòng thứ hai ghi N kí tự cộng hoặc trừ cần đặt trước các vecto sao cho tổng vecto nhỏ hơn sprt(2)*L.

    Thuật giải:

    - n = 1 bài toán đã đúng.
    - n = 2 có trường hợp xảy ra với hai vecto:
    + góc giữa hai vecto nhỏ hơn 90 độ, lấy vecto 1 trừ cho vecto 2 lúc đó ta thu được 1 vecto co độ dài nhỏ hơn sqrt(2) * L.
    + góc giữa hai vecto lớn hơn hoặc bài một 90 độ, lấy vecto 1 cộng cho vecto 2 lúc đó ta thu được 1 vecto có độ dài nhỏ hơn sqrt(2) * L.
    - n ≥ 3 suy ra luôn có 2 vecto mà góc giữa hai phương của vecto nhỏ hơn hoặc 60 bằng độ có hai trường xảy ra:
    + góc giữa hai vecto đó nhỏ hơn hoặc bằng 60 độ, trừ vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được.
    + góc giữa hai vecto đó lớn hơn hoặc bằng 120 độ, cộng vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được. Lưu ý sau này nếu trừ vecto mới nhận được phải trừ (đổi dấu) toàn vecto bộ hình thành lên nó, vecto mới nhận được có độ dài nhỏ hơn L, số đoạn thẳng giảm 1.
    Như vậy đây là bài toán luôn có lời giải, độ phức tạp O(N^2) nếu xử lý khéo có thể giản xuống O(n*log(n)). Chương trình mô tả thuật giải:

    Code:
    Procedure Xuly (n: integer //* số đối tượng *//);
    Begin
    If n <= 1 then exit else
    If n = 2 then 
    Begin
    If goc (v1, v2) <= 90 độ Then đổi dấu (v2);
    //* đổi dấu tức là đổi dấu toàn bộ vecto thành phần *//
    Thay hai vecto bằng 1 vecto (v1 + v2);
    //* vecto mới gồm các thành phần của v1 và v2 *//
    //* lúc này v2 nếu cần thiết đã đổi dấu rồi *//
    Exit;
    End else
    Begin
    Lấy 3 vecto bất kỳ;
    Chọn ra được 2 vecto v1, v2 sao cho 
    Góc nhỏ giữa phương 2 vec to nhỏ 60;
    If goc (v1, v2) <= 60 then đổi dấu (v2);
    Thay hai vecto này bằng (v1 + v2);
    End;
    End;
    P2: Utopia (IOI 2002)

    Đất nước Utopia tươi đẹp bị chiến tranh tàn phá. Khi chiến tranh tạm ngừng, đất nước bị chia cắt thành bốn miền bởi một đường kinh tuyến (đường theo hướng Bắc-Nam) và một đường vĩ tuyến (đường theo hướng Đông-Tây). Giao điểm của hai đường này xem như điểm (0, 0). Tất cả các miền này đều muốn mang tên Utopia, theo thời gian các miền này được gọi là Utopia 1 (phía Đông Bắc), Utopia 2 (phía Tây Bắc), Utopia 3 (phía Tây Nam), Utopia 4 (phía Đông Nam). Một điểm trong bất kỳ miền nào cũng được xác định bởi khoảng cách theo hướng Đông và khoảng cách theo hướng Bắc của nó so với điểm (0, 0). Bộ hai khoảng cách này được gọi là toạ độ của điểm. Các thành phần của toạ độ có thể là số âm; do đó một điểm miền Utopia 2 có toạ độ (âm, dương), một điểm miền Utopia 3 có toạ độ (âm, âm), một điểm miền Utopia 4 có toạ độ (dương, âm), một điểm miền Utopia 1 có toạ độ (dương, dương) (Giống như các góc phần tư trong hệ toạ độ đề các).
    Một vấn đề là các công dân không được phép đi qua biên giới giữa các miền. May thay, một số thí sinh tham dự IOI của Utopia sáng chế ra một loại máy an toàn để vận chuyển từ xa. Máy này cần các số mã, mỗi số mã chỉ có thể được dùng một lần. Bây giờ, nhóm thí sinh tham dự và bạn phải hướng dẫn máy vận chuyển từ xa xuất phát từ vị trí ban đầu (0, 0) đến các miền của Utopia theo một trình tự cho trước. Khi bạn nhận được một dãy N số hiệu miền mà theo trình tự đó máy vận chuyển từ xa phải hạ cánh, với mỗi miền, bạn không cần phải quan tâm đến việc hạ cánh tại điểm nào của miền đó miễn là điểm đó thuộc miền yêu cầu. Người ta có thể yêu cầu máy hạ cánh liên tiếp hai lần hay nhiều lần hơn ở cùng một miền. Sau khi rời khỏi điểm ban đầu (0, 0), bạn không được hạ cánh trên các đường biên giới.
    Bạn sẽ nhận được input là một dãy 2N số mã và phải viết chúng thành một dãy gồm N cặp mã, sau khi đặt một dấu + hoặc một dấu - thích hợp trước mỗi số. Nếu hiện tại bạn ở điểm (x,y) và sử dụng cặp mã số (+u,-v), bạn sẽ được chuyển tới điểm (x+u,y-v). Bạn có 2N số và bạn có thể sử dụng các số này theo thứ tự bạn muốn, mỗi số kèm theo một dấu + hoặc một dấu -.
    Giả sử bạn có các số mã 7, 5, 6, 1, 3, 2, 4, 8 và phải hướng dẫn máy vận chuyển từ xa lần lượt đến các miền thuộc dãy miền 4, 1, 2, 1. Dãy các cặp mã (+7, -1), (-5, +2), (-4, +3), (+8, +6) đáp ứng yêu cầu này vì nó đưa bạn từ (0,0) lần lượt đến các vị trí (7, -1), (2, 1), (-2, 4) và (6, 10). Những điểm này nằm tương ứng ở Utopia 4, Utopia 1, Utopia 2 và Utopia 1.

    Nhiệm vụ:

    Cho 2N số mã khác nhau và một dãy N số hiệu miền là dãy các miền mà máy vận chuyển từ xa phải lần lượt hạ cánh. Hãy xây dựng một dãy các cặp mã từ các số đã cho để hướng dẫn máy vận chuyển từ xa lần lượt đi đến các miền thuộc dãy đã cho.

    Input

    Chương trình của bạn phải đọc từ input chuẩn. Dòng đầu gồm một số nguyên dương N (1 ≤ N ≤ 10000). Dòng thứ hai gồm 2N số mã nguyên khác nhau, tất cả đều là các số nguyên dương không lớn hơn 100000. Dòng cuối cùng gồm một dãy N số hiệu miền, mỗi một trong các số đó là 1, 2, 3 hoặc 4. Hai số liên tiếp trên một dòng cách nhau đúng một dấu trống.

    Output

    Chương trình của bạn phải viết ra output chuẩn. Ouput gồm N dòng, mỗi dòng chứa một cặp số mã mà trước mỗi số có dấu + hoặc dấu -. Đó là các cặp mã sẽ hướng dẫn cho máy vận chuyển đến dãy miền đã cho. Chú ý rằng không được có dấu trống sau dấu + hoặc dấu - nhưng phải có một dấu trống sau số mã thứ nhất.Nếu có nhiều lời giải, chương trình của bạn có thể đưa ra một lời giải bất kỳ trong số đó. Nếu không có lời giải, chương trình của bạn phải đưa ra một số 0 duy nhất.

    Thuật giải:

    Đây cũng là bài toàn luôn giải được để giải bài toán trên ta cần giải bài toán nhỏ sau:Cho một gồm N số nguyên dương khác nhau a1 < a2 < … < an. Cần sắp xếp lại và thêm các dấu vào các số ai sao cho tổng các số từ 1 đến vị trí i là dương hoặc âm biết trước:
    Ví dụ:
    Dãy 3 số: 1 2 3
    Dấu cần xây dựng: +-+
    Một cách thêm dấu và sắp xếp: +1 -2 + 3
    Bổ đề:
    Nếu dãy có dãy {ai} dương tăng và một chuỗi dấu cần biến đổi thì ta luôn có cách thêm dấu và thay đổi vị trí sao cho tổng cách số từ 1 đến i mang đấu của chuỗi dấu biết trước.
    Chứng minh:
    - số an mang dấu cuối cùng của chuỗi trên, các số còn lại đan dấu. (điều kiện về dấu để luôn xây được dãy) Ví dụ: {ai} = {1, 5, 10}; S = ‘++-‘; suy ra dãy {ai} được đánh dấu như sau: -1, +5, -10;
    - nhận xét rằng: tổng của n số trên cuối cùng sẽ mang dấu của S[n]
    - với n = 1 ta nhận được dãy cần tìm.
    - Giả sử n =k ta xây dựng được chuỗi như trên.
    - n = k + 1 chia hai trường hợp:
    + s[n-1] cùng dấu s[n]: đặt a[1] vào vị trí cuối cùng và lấy phần tử a[1] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu (vẫn thoả mãn điều kiện về dấu)
    + s[n - 1] và s[n] khác dấu: đặt a[n] vào vị trí cuối cùng và lấy phần tử a[n] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu. Theo giả thiết quy nạp thì dãy còn lại luôn xây dựng được.

    Chương trình:

    Code:
    Procedure Xuly (Var a, dau, q: array [1…10000] of integer; n, cd, ct : integer);
    //*ta đang xử lý dãy các số từ a[cd] đến a[ct] có dấu từ dấu[1] đến dấu[n] *//
    Begin
    If n <= 1 then exit;
    If dau[n - 1] = dau[n] then
    Begin
    Q[n] := a[cd];
    Xuly (a, dau, q, n - 1, cd + 1, ct);
    End else
    Begin
    Q[n] := a[ct];
    Xuly (a, dau, q, n - 1, cd, ct - 1);
    End;
    End;
    //* mảng q thu được là kết quả cần tìm*//
    Ở bài toán trên các dấu tọa độ x, y là đã xác định: Chia dãy 2N phần tử khác nhau thành hai gồm N phần tử làm hoành độ và tung độ, sau đó sắp tăng. Tiến hành thuật giải trên ta thu được hai dãy toạ độ thoả mãn điều kiện về dấu, đó cũng chính là dãy toạ độ cần tìm.

    P3: (Bài tập tự giải) 2N point (POI)

    Cho 2N diểm trên mặt phẳng gồm N diểm màu xanh và N điểm màu trắng sao cho không có ba điểm nào thẳng hàng. Hãy tìm N đoạn thẳng mà mỗi đoạn thẳng nối giữa một điểm màu xanh và một điểm màu trắng và các doạn nay không cắt nhau.

    Input: 2Npoint.Int

    - Dòng dầu ghi số N. (1 ≤ N ≤ 5000)
    - N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu xanh (|xi|, |yi| ≤ 10000).
    - N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu trắng (|xi|, |yi| ≤ 10000).

    Output: 2Npoint.Out

    - Gồm N dòng mỗi dòng ghi hai số a, b để chỉ điểm màu xanh thứ a, nối với điểm màu trắng thứ b.

    4. Lời kết:

    .Mọi tư duy toán học đều có thể vận dụng một cách linh động trong tin học. Tôi hy vọng sau bài viết này, ngoài việc học thêm được một hướng giải mới, các bạn sẽ tìm tòi thêm các ứng dụng toán học khác vào tin học.

    (Nguồn:Thầy Nguyễn Duy Khương-vnoi.info)
    Nguồn từ: http://chuyenhvt.net

    Các bài viết cùng chuyên mục:

    ...DTH£N...

  2. Những người đã cảm ơn :


  3. #2
    Thành viên mới Kiều Ank's Avatar
    Ngày tham gia
    25-11-2010
    Tuổi
    26
    Bài viết
    3
    Cảm ơn
    0
    Đã được cảm ơn 0 lần ở 0 bài viết

    Mặc định

    Suốt ngày học tyn chán hơn con gián chả hiểu nổi mấy cái thuật toán này
    Nguồn từ: http://chuyenhvt.net
    HLN1994 - 05:40 PM 29-11-2010
    @Kiều Ank: Tin học hay mà
    Kiều Ank - 06:38 PM 29-11-2010
    úi zời ... khó lòi ra cậu học giỏi thỳ thấy hay...tớ ngu tớ thấy chán

  4. #3
    Thành viên tích cực luunhuhoa's Avatar
    Ngày tham gia
    26-01-2010
    Tuổi
    32
    Bài viết
    223
    Cảm ơn
    291
    Đã được cảm ơn 347 lần ở 115 bài viết

    Mặc định

    Cám ơn Nhân vì những bài viết có ích,hy vọng em tiếp tục đóng góp cho diễn đàn
    Nguồn từ: http://chuyenhvt.net
    HLN1994 - 05:40 PM 29-11-2010
    Vâng,em cám ơn anh

  5. Những người đã cảm ơn :


  6. #4
    Thành viên gắn bó titi_toto's Avatar
    Ngày tham gia
    02-04-2009
    Tuổi
    27
    Bài viết
    3,944
    Cảm ơn
    806
    Đã được cảm ơn 960 lần ở 491 bài viết

    Mặc định

    dạo này a thấy e cũng hay post những topic về học tập nhưng chưa thu hút nhiều ng xem cho lắm
    nên xem mọi người cần ji thì mình làm về phần đấy như kiểu thị trường cần ji thì mình sản xuất cái đấy ( đang học kinh tế vi mô nên thế )
    những topic liên quan trực tiếp đến thi đại học hoặc 1 topic để giải đáp những câu hỏi nhỏ hay bài tập mà các bạn chưa làm đc chắc sẽ thu hút sự chú ý mọi ng hơn
    Nguồn từ: http://chuyenhvt.net
    ____TM____

  7. Những người đã cảm ơn :


  8. #5
    Thành viên gắn bó titi_toto's Avatar
    Ngày tham gia
    02-04-2009
    Tuổi
    27
    Bài viết
    3,944
    Cảm ơn
    806
    Đã được cảm ơn 960 lần ở 491 bài viết

    Mặc định

    VD như 1 câu hỏi nhỏ như này
    muốn giãn các dòng trong 1 ô excel thì làm như nào?
    trong word thì đơn giản còn trong excel thì khó thế
    Nguồn từ: http://chuyenhvt.net
    snow_chan - 12:58 PM 02-12-2010
    Ơ cái này thì bôi đen mấy cái ô cần giãn -> format -> row-> height -> gõ kích thước ô là xong mà anh >.<
    @titi_toto:
    Hay cái này chỉ là VD nhỉ?
    titi_toto - 01:10 PM 02-12-2010
    ko phải
    như này trong 1 ô excel có 3 dòng thì 3 dòng này phải giãn như này
    sjskjfkà

    sjkkjàkjà




    shfjafafafk
    nghĩa là khoảng cách giữa các dòng trong cùng 1 ô là khác nhau ấy @snow_chan:
    snow_chan - 01:12 PM 02-12-2010
    À ra thế. Thế cứ alt+enter (thủ công) ko đc ạ? Hay là tốn thời gian quá nên anh muốn tìm cách nào nhanh @titi_toto:
    titi_toto - 10:27 PM 02-12-2010
    đấy là xuống dòng chứ k phải giãn dòng
    chả ai biết thì kt cứ alt enter mấy phát vậy
    hjx
    @snow_chan:
    ____TM____

  9. #6
    Moderator thử việc HLN1994's Avatar
    Ngày tham gia
    11-08-2009
    Tuổi
    25
    Bài viết
    1,187
    Cảm ơn
    766
    Đã được cảm ơn 364 lần ở 185 bài viết

    Mặc định

    @titi_toto:Rất cám ơn anh đã góp ý .Nói thật là việc lập một topic như anh nói là rất đúng,nhưng thường em để ý thấy những người hỏi bài trong Box chủ yếu đều là những mem mới,còn đa phần thành viên 4rum của chúng ta lên 4rum chủ yếu là để giao lưu là chính. Em đang không biết nên thu hút mọi người chú ý đến Box này sao cho nó mang một cái hiệu quả thật sự cho việc học tập.
    Nguồn từ: http://chuyenhvt.net
    ...DTH£N...

  10. #7
    Thành viên tích cực luunhuhoa's Avatar
    Ngày tham gia
    26-01-2010
    Tuổi
    32
    Bài viết
    223
    Cảm ơn
    291
    Đã được cảm ơn 347 lần ở 115 bài viết

    Mặc định

    Cá nhân anh nghĩ,em viết bài thế nào là quyền của em. Thích viết gì thì viết,ai quan tâm không thì kệ Mình viết lại coi như là 1 cách ghi nhớ lại kiến thức,nếu có người trao đổi cũng tốt,ko có ai trao đổi thì thôi @-(
    Còn nếu mục đích của em là để hấp dẫn mọi người đến với box học tập thì sẽ gần như ko bao h thực hiện được .
    Anyway,just enjoy.

    Bài viết về quy nạp trên rất hay
    Nguồn từ: http://chuyenhvt.net

  11. Những người đã cảm ơn :


  12. #8
    Moderator thử việc HLN1994's Avatar
    Ngày tham gia
    11-08-2009
    Tuổi
    25
    Bài viết
    1,187
    Cảm ơn
    766
    Đã được cảm ơn 364 lần ở 185 bài viết

    Mặc định

    @luunhuhoa: Em nghĩ là không phải thu hút mọi người là quan trọng mà em nghĩ rằng phải làm sao để cho mọi người quan tâm và tìm tòi nhiều hơn các bộ môn tự nhiên,và những bài viết không chỉ là dành riêng cho mình mà còn dành cho tất cả mọi người .Rất cám ơn ý kiến của anh .
    Còn việc hấp dẫn mọi người đến với box học tập thì đúng như anh nói là bất khả thi vì đa phần thảnh viên của 4rum chúng ta chủ yếu lên 4rum để chém(trong đó có cả em)
    Nguồn từ: http://chuyenhvt.net
    ...DTH£N...

Thông tin về chủ đề này

Users Browsing this Thread

Có 1 người đang xem chủ đề. (0 thành viên và 1 khách)

Đánh dấu

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •