New FAMILUG

The PyMiers

Thursday 21 May 2015

[CodeMath] Giải "Bài toán lớp 3 có số lượng đáp án khổng lồ"

Một bài toán làm náo loạn cộng đồng mạng =)) vậy giải hoy còn chờ gì :3
Đã có lời giải bằng Golang, mời các bạn đóng góp lời giải bằng ngôn ngữ khác và cùng đối chiếu kết quả :D

http://vnexpress.net/tin-tuc/giao-duc/bai-toan-lop-3-co-so-luong-dap-an-khong-lo-3220439.html

với các biến a,b,c,d,e,f,g,h,i là các số nằm trong khoảng 1-9 (các biến có thể có giá trị giống nhau), dạng biểu thức:
a + 13 * b / c + d + 12 * e – f – 11 + g * h / i – 10 = 66
1. Câu hỏi cho học sinh lớp 3: Tìm các số từ a đến i thoả mãn bài toán (tìm một nghiệm của bài toán)
2. Câu hỏi cho cử nhân, kỹ sư, lập trình viên, hacker blah blah: BÀI TOÁN NÀY CÓ BAO NHIÊU NGHIỆM?
3. Câu hỏi cho fan thỏ bảy màu và chaien: Có bao nhiêu phần trăm hư cấu trong câu nói : "Tôi đã dùng ngôn ngữ lập trình Maple để thử tìm hết tất cả đáp án của bài toán và chỉ 3-4 phút đã cho tới 74 trang A4 các đáp số" của thạc sĩ ở đầu bài viết?
4. Tính xấp xỉ số trang A4 - 1 mặt, để in hết kết quả của bài toán với font Time new roman size14, line giãn cách default, mỗi dòng chứa tối đa số đáp án có thể viết được (ví dụ viết 9 số liền nhau rồi tách với đáp án khác bằng một dấu cách).
Phân tích chém gió:
Bài này tính một cách thô sẽ có: 9 biến, mỗi biến có 9 cách chọn, vậy có tất cả 9*9 :
In [5]: 9 ** 9
Out[5]: 387420489 # "ba trăm triệu có lẻ" khả năng.
Thuật toán tối ưu để giải là trừ dần đi để giảm giới hạn của các biến về sau.

Lời giải:

Golang: http://play.golang.org/p/euUskIcgtE
$ time ./toanlop3 # on Intel core i7 2.7GHz
2015/05/22 01:10:34 There are 453542 roots.

real    0m0.193s
user    0m0.189s
sys    0m0.003s
Hết.
hvn@familug.org

Bạn muốn học python? Bơi ngay vào đây http://www.familug.org/2015/05/hanoi-hoc-lap-trinh-python-tai-lop-hoc.html

4 comments:

  1. :| hóng cái thuật toán mà không nói :D

    ReplyDelete
  2. Code python:
    In [14]: time len([(a, b, c, d, e, f, g, h,i) for a in range(1, 10) for b in range(1, 10) for c in range(1, 10) for d in range(1, 10) for e in range(1, 10) for f in range(1, 10) for g in range(1, 10) for h in range(1, 10) for i in range(1, 10) if a + 13 * b / c + d + 12 * e - f + g * h / i == 87])
    CPU times: user 284.55 s, sys: 0.04 s, total: 284.59 s
    Wall time: 284.84 s
    ===> Lâu vãi :D

    ReplyDelete
    Replies
    1. lời giải này sai do sử dụng phép chia trong Python không đúng cách:
      - khi chia 2 số nguyên cho nhau, python sẽ chỉ trả về phần chia hết
      (VD: 5/2 = 2)
      - để chia 2 số theo nghĩa bình thường, cần biến một số thành kiểu float, có thể viết (5.0/2 hoặc 5/2.0, hoặc sử dụng thư viện decimal để tính toán với số float được chuẩn xác hơn https://docs.python.org/2/library/decimal.html )

      Delete
  3. Giảm đi một biến, thời gian giảm đi còn 57 s =))
    http://pastebin.com/KJJLVEMg

    thanhnguyen@thanhnguyen:~/bitbucket$ time python toanlop3.py
    3359844

    real 0m57.452s
    user 0m57.212s
    sys 0m0.164s

    ReplyDelete