[PYTHON] Programming problem collection (Q11 to Q15)

Question 11: Divided quadrature method (rectangular approximation)

Rectangle approximation, trapezoidal law, Simpson's law, etc. are examples of the divisional quadrature method for numerically obtaining the integral. In the rectangle approximation, the sum of the rectangles obtained by multiplying the value $ f (x_i) $ at a certain point $ x_i $ by the width $ h $ is approximated as the integral value.

定積分

Solve the above equation numerically using rectangular approximation.

Answer example

Question 12: Divided quadrature method (trapezoidal rule)

Rectangle approximation, trapezoidal law, Simpson's law, etc. are examples of the divisional quadrature method for numerically obtaining the integral. According to the trapezoidal rule, the width $ by $ f (x_i) $ and $ f (x_ {i-1}) $ at a certain point $ x_i $ and the point before it $ x_ {i-1} $ </ sub> The sum of the trapezoids of h $ is approximated as the integral value.

定積分

Solve the above equation numerically using the trapezoidal law.

Answer example

Question 13: Divisional quadrature method (Simpson's law)

Rectangle approximation, trapezoidal law, Simpson's law, etc. are examples of the divisional quadrature method for numerically obtaining the integral. According to Simpson's law, a quadratic function that passes through a certain point $ x_i $, a point before it $ x_ {i-1} $, and a point after it $ x_ {i + 1} $ is derived, and its $ f (x_ { i-1}) Integral value from $ to $ f (x_ {i + 1}) $ $ h (f (x_ {i + 1}) + 4f (x_i) + f (x_ {i-1})) Approximate the sum of / 3 $ as the integral value.

定積分

Solve the above equation numerically using Simpson's law.

Answer example

Question 14: Eratosthenes sieve

If you enter the integer $ n $, create a function that returns the number of prime numbers less than or equal to $ n $. Also explain the algorithm.

However,

And.

Example 14-1

n = 10
4

Example 14-2

n = 100
25

Example 14-3

n = 1000
168

Example 14-4

n = 10000
1229

Example 14-5

n = 100000
9592

Answer example

Question 15: Number of grid points

There are two grid points $ P = (x_1, y_1) $, $ Q = (x_2, y_2) $ on the Euclidean plane. Create a function on the line segment $ PQ $ to calculate how many grid points exist in addition to $ P $ and $ Q $. Also explain the algorithm.

However,

And.

[Hint] You can reduce to the problem of finding the greatest common divisor. It can be solved efficiently by "Euclidean algorithm". </ font>

Example 15-1

x1 =  -2
y1 =  -9
x2 =  6
y2 =  7
7
#Illustrated and confirmed
%matplotlib inline
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot([x1, x2], [y1, y2])
ax.set_xticks(range(x1, x2 + 1, 1))
ax.set_yticks(range(y1, y2 + 1, 1))
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.grid()

9-1.png

Example 15-2

x1 =  -42
y1 =  -65
x2 =  62
y2 =  -91
25

Example 15-3

x1 =  908
y1 =  -307
x2 =  -86
y2 =  -679
0

Example 15-4

x1 =  -6326
y1 =  3211
x2 =  7048
y2 =  5822
0

Example 15-5

x1 =  -9675
y1 =  -2803
x2 =  3828
y2 =  -6349
2

Reference: How to make an example

import random
x1 = random.randint(-1000000, 1000000)
y1 = random.randint(-1000000, 1000000)
x2 = random.randint(-1000000, 1000000)
y2 = random.randint(-1000000, 1000000)

print("x1 = ", x1)
print("y1 = ", y1)
print("x2 = ", x2)
print("y2 = ", y2)

Answer example

  • https://qiita.com/maskot1977/private/10bac9b3829fefcd286f

Recommended Posts

Programming problem collection (Q16 to Q20)
Programming problem collection (Q11 to Q15)
Programming problem collection (Q31-Q35)
Programming problem "4 Queen Square"
AOJ Introduction to Programming Topic # 1, Topic # 2, Topic # 3, Topic # 4
[Python] Dynamic programming knapsack problem
AOJ Introduction to Programming Topic # 7, Topic # 8
AOJ Introduction to Programming Topic # 5, Topic # 6
An introduction to Python Programming
Programming to fight in the world ~ 5-1
Programming to fight in the world ~ 5-5,5-6
Programming to fight in the world 5-3
[Introduction to Python3 Day 1] Programming and Python
Programming to learn from books May 10
Programming to fight in the world-Chapter 4
Websites to help you learn programming
Programming to learn from books May 7
Programming to fight in the world ~ 5-2
I tried to solve the E qualification problem collection [Chapter 1, 5th question]