Lăn hai con xúc xắc xác suất con trăn

Chương này được lấy từ cuốn sách A Primer on Scientific Programming with Python của H. P. Langtangen, tái bản lần thứ 5, Springer, 2016

Phần này trình bày việc thực hiện một số trò chơi đơn giản dựa trên việc rút các số ngẫu nhiên. Các trò chơi có thể được chơi bởi hai người, nhưng ở đây chúng tôi xem xét một người so với máy tính

Đoán một số

Tro choi

Máy tính xác định một số bí mật và người chơi sẽ đoán số. Đối với mỗi lần đoán, máy tính sẽ cho biết con số quá cao hay quá thấp

Việc thực hiện

Chúng tôi để máy tính vẽ một số nguyên ngẫu nhiên trong một khoảng thời gian mà người chơi biết, giả sử \[ [1,100] \]. Trong vòng lặp

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

1, chương trình nhắc người chơi đoán, đọc số đoán và kiểm tra xem số đoán cao hơn hay thấp hơn số đã rút. Một thông báo thích hợp được viết ra màn hình. Chúng tôi nghĩ rằng thuật toán có thể được biểu thị trực tiếp dưới dạng mã Python thực thi

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

Chương trình có sẵn dưới dạng tệp Guess_number. py. dùng thử. Bạn có thể đưa ra một chiến lược để giảm số lần thử không? . Điều tra các chiến lược đoán để điều tra tự động hai chiến lược có thể

Lăn hai con xúc xắc

Tro choi

Người chơi có nhiệm vụ tung hai viên xúc xắc và đoán trước tổng số của các mắt. Nếu đoán tổng là \[ n \] và nó đúng, người chơi sẽ kiếm được \[ n \] euro. Nếu không, người chơi phải trả 1 euro. Máy cũng chơi như vậy nhưng dự đoán số mắt của máy là số phân bố đều trong khoảng từ 2 đến 12. Người chơi xác định số vòng, \[ r \], để chơi và nhận \[ r \] euro làm vốn ban đầu. Người chiến thắng là người có số tiền euro lớn nhất sau \[ r \] vòng quay hoặc người tránh bị mất tất cả số tiền

Việc thực hiện

Có ba hành động mà chúng ta có thể thực hiện một cách tự nhiên như các chức năng. [i] tung hai con xúc xắc và tính tổng; . Người ta sẽ sớm nhận ra rằng việc thực hiện trò chơi này với số lượng xúc xắc tùy ý cũng dễ dàng như đối với hai con xúc xắc. Do đó, chúng tôi có thể giới thiệu

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

2 là số lượng xúc xắc. Ba chức năng có các hình thức sau

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

Bây giờ chúng tôi có thể triển khai một vòng trong trò chơi cho người chơi hoặc máy tính. Vòng bắt đầu với vốn, đoán được thực hiện bằng cách gọi đúng chức năng để đoán và vốn được cập nhật

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

Ở đây,

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

3 hoặc là

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

4 hoặc là

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

5

Với chức năng

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

6, chúng tôi có thể chạy một số vòng liên quan đến cả hai người chơi

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

Tên của chương trình là ndice. py

Thí dụ

Đây là một phiên [với hạt giống cố định là 20]

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

0

bài tập 12. So sánh hai chiến lược chơi yêu cầu bạn thực hiện mô phỏng để xác định xem liệu một chiến lược nhất định có thể khiến người chơi chiến thắng máy tính về lâu dài hay không

Một phiên bản lớp học

Chúng ta có thể truyền đoạn mã trước đó trong một lớp. Nhiều người sẽ lập luận rằng việc triển khai dựa trên lớp gần với vấn đề đang được mô hình hóa hơn và do đó dễ dàng sửa đổi hoặc mở rộng hơn

Một lớp tự nhiên là

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

7, có thể ném xúc xắc

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

8

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

3

Một lớp tự nhiên khác là

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

9, có thể thực hiện các hành động của người chơi. Sau đó, các chức năng có thể sử dụng

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

9 để thiết lập trò chơi. Một

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

9 có tên, vốn ban đầu, một bộ xúc xắc và một đối tượng

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

7 để ném đối tượng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

8

Dự đoán của máy tính và người chơi được chỉ định bởi các chức năng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

9

Chức năng chính để chơi toàn bộ trò chơi, sử dụng lớp

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

9 cho máy tính và người dùng, có thể được biểu thị bằng

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

1

Mã hoàn chỉnh được tìm thấy trong tệp ndice2. py. Không có chức năng mới nào so với triển khai

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

4, chỉ là cấu trúc mã mới và tốt hơn

Một trong những ứng dụng sớm nhất của số ngẫu nhiên là tính toán số của tích phân, đây thực sự là bài toán không ngẫu nhiên [tất định]. Tính toán tích phân với sự trợ giúp của các số ngẫu nhiên được gọi là tích phân Monte Carlo và là một trong những kỹ thuật toán học mạnh mẽ và được sử dụng rộng rãi nhất trong khoa học và kỹ thuật

Trọng tâm chính của chúng ta ở đây sẽ là tích phân loại \[ \int_a^b f[x]dx \] mà tích phân Monte Carlo không phải là một kỹ thuật cạnh tranh so với các phương pháp đơn giản như phương pháp Hình thang, phương pháp Điểm giữa hoặc phương pháp Simpson. Tuy nhiên, đối với tích phân hàm nhiều biến, phương pháp Monte Carlo là phương pháp tốt nhất mà chúng tôi có. Những tích phân như vậy luôn xuất hiện trong vật lý lượng tử, kỹ thuật tài chính và khi ước tính độ không đảm bảo của các phép tính toán học. Những gì bạn tìm hiểu về tích phân Monte Carlo của các hàm một biến [\[ \int_a^b f[x]dx \]] có thể chuyển trực tiếp sang các trường hợp ứng dụng quan trọng có nhiều biến liên quan

Nguồn gốc của tích hợp Monte Carlo

Có hai cách để giới thiệu tích phân Monte Carlo, một dựa trên phép tính và một dựa trên lý thuyết xác suất. Mục tiêu là để tính toán một xấp xỉ bằng số cho $$ \int_a^b f[x]dx\tp$$

Phương pháp tính toán thông qua định lý giá trị trung bình

Định lý giá trị trung bình từ phép tính nói rằng $$ \begin{equation} \int_a^b f[x]dx = [b-a]\bar f, \tag{7} \end{equation} $$ trong đó \[ \bar f . $$ \begin{equation} \bar f\approx \frac{1}{n}\sum_{i=0}^{n-1} f[x_i]\tp \tag{8} \end{equation} $ . ]

Có quyền tự do trong cách chọn điểm \[ x_0,\ldots,x_{n-1} \]. Ví dụ, chúng ta có thể đặt chúng cách đều nhau trong khoảng \[ [a, b] \]. Lựa chọn cụ thể $$ x_0 = a + ih + \frac{1}{2}h,\quad i=0,\ldots,n-1,\quad h=\frac{b-a}{n-1},$ . Theo trực giác, chúng tôi dự đoán rằng càng sử dụng nhiều điểm thì phép tính xấp xỉ \[ \frac{1}{n}\sum_if[x_i] \] thành giá trị trung bình chính xác \[ \bar f \] càng tốt. Đối với quy tắc Điểm giữa, người ta có thể chỉ ra bằng toán học hoặc ước tính bằng số thông qua các ví dụ, rằng sai số trong phép tính gần đúng phụ thuộc vào \[ n \] là \[ n^{-2} \]. Nghĩa là, nhân đôi số điểm sẽ giảm sai số xuống 1/4

Một tập hợp các điểm phân bố đều hơi khác một chút là $$ x_i = a + ih,\quad i=0,\ldots,n-1,\ldots,\quad h=\frac{b-1}{n-2}\ . nhân đôi số điểm chỉ giảm một nửa lỗi. Nghĩa là, việc tính toán nhiều giá trị hàm hơn để có ước tính tích hợp tốt hơn sẽ kém hiệu quả hơn với các điểm đặt này so với các điểm dịch chuyển nhẹ được sử dụng trong quy tắc Điểm giữa

Người ta cũng có thể đưa ra ý tưởng sử dụng một tập hợp các điểm ngẫu nhiên, được phân phối đồng đều trong \[ [a,b] \]. Đây là kỹ thuật tích hợp Monte Carlo. Lỗi bây giờ giống như \[ n^{-1/2} \], nghĩa là cần thêm nhiều điểm và đánh giá hàm tương ứng để giảm lỗi so với khi sử dụng phương pháp Điểm giữa. Tuy nhiên, một thực tế đáng ngạc nhiên là việc sử dụng các điểm ngẫu nhiên cho nhiều biến [trong không gian vectơ nhiều chiều] mang lại một kỹ thuật tích hợp rất hiệu quả, hiệu quả hơn nhiều so với việc mở rộng các ý tưởng về quy tắc Điểm giữa cho nhiều biến.

Phương pháp lý thuyết xác suất

Những người nghiên cứu về lý thuyết xác suất thường thích diễn giải tích phân như kỳ vọng toán học của một biến ngẫu nhiên. [Nếu bạn không phải là một trong số đó, bạn có thể chuyển sang phần Thực hiện tích phân Monte Carlo tiêu chuẩn một cách an toàn, nơi chúng tôi chỉ lập trình tổng đơn giản trong phương pháp tích hợp Monte Carlo. ] Chính xác hơn, tích phân \[ \int_a^b f[x]dx \] có thể được biểu diễn dưới dạng kỳ vọng toán học của \[ f[x] \] nếu \[ x \] là một biến ngẫu nhiên phân phối đều trên \[ [ . Kỳ vọng này có thể được ước tính bằng trung bình cộng của các mẫu ngẫu nhiên, kết quả là phương pháp tích phân Monte Carlo. Để thấy điều này, chúng ta bắt đầu với công thức hàm mật độ xác suất cho biến ngẫu nhiên phân phối đều \[ X \] trên \[ [a,b] \]. $$ p[x] =\left\lbrace\begin{array}{ll} [b-a]^{-1},& x\in [a,b]\\ 0, & \hbox{otherwise} \end{ . $$ Bây giờ chúng ta có thể viết công thức chuẩn cho kỳ vọng toán học \[ \mbox{E}[f[X]] \]. $$ \mbox{E}[f[X]] = \int_{-\infty}^{\infty} f[x]p[x]dx = \int_a^b f[x]\frac{1}{b-a . Một kỳ vọng thường được ước tính từ rất nhiều mẫu, trong trường hợp này là các số ngẫu nhiên được phân phối đồng đều \[ x_0,\ldots,x_{n-1} \] trong \[ [a,b] \] và tính giá trị trung bình của mẫu. $$ \mbox{E}[f[X]] \approx \frac{1}{n}\sum_{i=0}^{n-1} f[x_i]\tp$$ Do đó có thể ước lượng tích phân

Triển khai tích hợp Monte Carlo tiêu chuẩn

Tóm lại, tích hợp Monte Carlo bao gồm tạo \[ n \] số ngẫu nhiên phân bố đều \[ x_i \] trong \[ [a,b] \] rồi tính $$ \begin{equation} [b-a]\frac{1

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

3

Một người thường cần một \[ n \] lớn để có được kết quả tốt với phương pháp này, do đó, phiên bản vector hóa nhanh hơn của hàm

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

5 rất hữu ích

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

0

Các chức năng trên có trong file module MCint. py. Chúng tôi có thể kiểm tra mức tăng hiệu quả với

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

6 trong phiên IPython

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

1

Lưu ý rằng chúng tôi sử dụng

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

7 từ

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

8 trong hàm vô hướng

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

5 vì hàm này nhanh hơn đáng kể so với

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

7 từ

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

01

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

2

[Một thử nghiệm tương tự cho thấy rằng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

02 là 1. gọi chậm hơn gấp 3 lần

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

7 không có tiền tố. Sự khác biệt nhỏ hơn nhiều giữa

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

04 và cùng chức năng không có tiền tố. ]

Sự gia tăng hiệu quả bằng cách sử dụng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

05 thay vì

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

5 trong thử nghiệm trên hệ số 6-7, điều này không đáng kể. Ngoài ra, phiên bản vector hóa cần lưu trữ \[ n \] số ngẫu nhiên và giá trị hàm \[ n \] trong bộ nhớ. Một triển khai vector hóa tốt hơn cho \[ n \] lớn là chia các mảng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

07 và

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

08 thành các phần có kích thước cho trước

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

09 sao cho chúng ta có thể kiểm soát việc sử dụng bộ nhớ. Về mặt toán học, nó có nghĩa là chia tổng \[ \frac{1}{n}\sum_i f[x_i] \] thành tổng của các tổng nhỏ hơn. Một thực hiện thích hợp đọc

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

3

Với 100 triệu điểm,

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

30 nhanh hơn khoảng 10 điểm so với

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

5. [Lưu ý rằng hàm thứ hai phải sử dụng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

32 chứ không phải

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

33 cho \[ n \ ] quá lớn, nếu không, mảng được trả về bởi

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

33 có thể trở nên quá lớn để lưu trữ trong bộ nhớ trong một máy tính nhỏ. Hàm

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

32 tạo một

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

36 tại một thời điểm mà không cần lưu trữ tất cả các giá trị

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

36. ]

Thí dụ

Chúng ta hãy thử phương pháp tích phân Monte Carlo trên hàm tuyến tính đơn giản \[ f[x]=2+3x \], tích phân từ 1 đến 2. Hầu hết các phương pháp tích hợp số khác sẽ tích hợp chính xác một hàm tuyến tính như vậy, bất kể số lượng đánh giá hàm. Đây không phải là trường hợp tích hợp Monte Carlo

Sẽ rất thú vị khi xem chất lượng của phép tính gần đúng Monte Carlo tăng như thế nào với \[ n \]. Để vẽ biểu đồ tiến hóa của xấp xỉ tích phân, chúng ta phải lưu trữ các giá trị trung gian

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

38. Điều này yêu cầu một phương pháp

def play[nrounds, ndice=2]:
    player_capital = computer_capital = nrounds  # start capital

    for i in range[nrounds]:
        player_capital, throw, guess = \ 
             play_one_round[ndice, player_capital, player_guess]
        print 'YOU guessed %d, got %d' % [guess, throw]

        computer_capital, throw, guess = \ 
            play_one_round[ndice, computer_capital, computer_guess]

        print 'Machine guessed %d, got %d' % [guess, throw]

        print 'Status: you have %d euros, machine has %d euros' % \ 
              [player_capital, computer_capital]

        if player_capital == 0 or computer_capital == 0:
            break

    if computer_capital > player_capital:
        winner = 'Machine'
    else:
        winner = 'You'
    print winner, 'won!'

5 được sửa đổi một chút

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

4

Lưu ý rằng chúng tôi để

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

80 đi từ 1 đến

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

8, sao cho

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

80 phản ánh số điểm thực tế được sử dụng trong phương pháp. Vì

def play_one_round[ndice, capital, guess_function]:
    guess = guess_function[ndice]
    throw = roll_dice_and_compute_sum[ndice]
    if guess == throw:
        capital += guess
    else:
        capital -= 1
    return capital, throw, guess

8 có thể rất lớn, mảng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

38 có thể tiêu tốn nhiều bộ nhớ hơn những gì chúng ta có trên máy tính. Do đó, chúng tôi quyết định chỉ lưu trữ mọi giá trị \[ N \] của phép tính gần đúng. Việc xác định xem một giá trị có được lưu trữ hay không có thể được tính toán bằng hàm mod.

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

85 cho số dư khi chia

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

80 cho

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

87. Trong trường hợp của chúng tôi, chúng tôi có thể lưu trữ khi lời nhắc này bằng 0,

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

5

Công thức thực hiện một việc gì đó mỗi lần \[N \]-thứ trong các vòng lặp dài có rất nhiều ứng dụng trong điện toán khoa học. Chức năng hoàn chỉnh bây giờ có dạng sau

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

6

ứng dụng mẫu của chúng tôi đi như thế nào

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

7

Hình 4 cho thấy một biểu đồ của

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

88 so với số lượng đánh giá chức năng

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

80

hinh 4. Sự hội tụ của tích phân Monte Carlo được áp dụng cho \[ \int_1^2 [2 + 3x]dx \]

Nhận xét

Chúng tôi đã tuyên bố rằng phương pháp Monte Carlo là chậm đối với các hàm tích phân của một biến. Tuy nhiên, có nhiều kỹ thuật áp dụng những cách vẽ số ngẫu nhiên thông minh hơn, được gọi là kỹ thuật giảm phương sai, và do đó làm tăng hiệu quả tính toán

Tính diện tích bằng cách ném điểm ngẫu nhiên

Hãy nghĩ về một số vùng hình học \[ G \] trong mặt phẳng và một hộp giới hạn xung quanh \[ B \] với hình học \[ [x_L,x_H]\times[y_L,y_H] \]. Một cách tính diện tích của \[ G \] là vẽ \[ N \] điểm ngẫu nhiên bên trong \[ B \] và đếm xem có bao nhiêu điểm trong số đó, \[ M \], nằm bên trong \[ G \]. Khi đó, diện tích của \[ G \] bằng phân số \[ M/N \] [\[ G \] của diện tích \[ B \]] nhân với diện tích của \[ B \], \[ . Nói cách khác, phương pháp này là một loại trò chơi phi tiêu trong đó bạn ghi lại số lần ném trúng bên trong \[ G \] nếu mỗi lần ném đều trúng đích trong \[ B \]

Hãy để chúng tôi xây dựng phương pháp này để tính tích phân \[ \int_a^bf[x]dx \]. Quan sát quan trọng là tích phân này là diện tích bên dưới đường cong \[ y=f[x] \] và phía trên trục \[ x \], giữa \[ x=a \] và \[ x=b \]. Chúng tôi giới thiệu một hình chữ nhật \[ B \], $$ \begin{equation*} B = \{ [x,y]\,. \, a\leq x\leq b, \ 0\leq y\leq m \},\end{equation*} $$ trong đó \[ m\leq\max_{x\in [a,b]} f[x . Thuật toán để tính diện tích dưới đường cong là vẽ \[ N \] điểm ngẫu nhiên bên trong \[ B \] và đếm xem có bao nhiêu trong số chúng, \[ M \], nằm trên trục \[ x \] và bên dưới . Sau đó, diện tích hoặc tích phân được ước tính bằng $$ \begin{equation*} \frac{M}{N}m[b-a]\tp\end{equation*} $$

Hình 5. Phương pháp "phi tiêu" để tính tích phân. Khi \[ M \] trong số \[ N \] điểm ngẫu nhiên trong hình chữ nhật \[ [0,2]\times [0,2. 4] \] nằm dưới đường cong, diện tích dưới đường cong được ước tính bằng phân số \[ M/N \] của diện tích hình chữ nhật, i. e. , \[ [M/N] 2\cchấm 2. 4 \]

Đầu tiên, chúng tôi thực hiện "phương pháp phi tiêu" bằng một vòng lặp đơn giản trên các điểm

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

8

Lưu ý rằng phương pháp này rút ra gấp đôi số ngẫu nhiên như phương pháp trước đó

Một triển khai vectorized đọc

import random

def roll_dice_and_compute_sum[ndice]:
    return sum[[random.randint[1, 6] \ 
                for i in range[ndice]]]

def computer_guess[ndice]:
    return random.randint[ndice, 6*ndice]

def player_guess[ndice]:
    return input['Guess the sum of the no of eyes '\ 
                 'in the next throw: ']

9

Dòng không tầm thường duy nhất ở đây là biểu thức

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

90, áp dụng lập chỉ mục boolean để trích xuất các giá trị

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

91 nằm bên dưới đường cong

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

08. Tổng các giá trị boolean [được hiểu là 0 và 1] trong

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

93 cho số điểm bên dưới đường cong

Ngay cả đối với 2 triệu số ngẫu nhiên, phiên bản vòng lặp đơn giản không quá chậm vì nó thực thi trong vòng vài giây trên máy tính xách tay chậm. Tuy nhiên, nếu bạn cần tích hợp được lặp lại nhiều lần trong một phép tính khác, thì hiệu quả vượt trội của phiên bản vector hóa có thể rất quan trọng. Chúng ta có thể định lượng mức tăng hiệu quả bằng sự trợ giúp của bộ đếm thời gian

import random
number = random.randint[1, 100]
attempts = 0  # count no of attempts to guess the number
guess = 0
while guess != number:
    guess = eval[raw_input['Guess a number: ']]
    attempts += 1
    if guess == number:
        print 'Correct! You used', attempts, 'attempts!'
        break
    elif guess < number:
        print 'Go higher!'
    else:
        print 'Go lower!'

94 theo cách sau

Xác suất lăn 2 con xúc xắc là bao nhiêu?

Xác suất lăn 2 mặt sáu bằng 2 con xúc xắc là bao nhiêu?

Xác suất lăn 7 với 2 con xúc xắc là gì?

Xác suất xuất hiện mặt 10 khi tung 2 con xúc xắc là bao nhiêu?