Lösen mit Ruby und Python AtCoder ARC 059 C Minimum-Quadrat-Methode

Einführung

• AtCoder-Probleme * Verwendet Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

• AtCoder Regular Contets C - Zusammen * Difficulty: 656

Dieses Thema ist die Methode der kleinsten Quadrate

Ruby (vollständige Suche)

Es ist ein wenig schwer zu verstehen, selbst wenn Sie die Problemstellung lesen, aber wenn Sie die Erklärung des Ausgabebeispiels lesen, * [Minimum square method -wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E5 Sie können sehen, dass% B0% 8F% E4% BA% 8C% E4% B9% 97% E6% B3% 95) * sich eine lineare Funktion mit einer Steigung von "0" vorstellt. Erstens, da der Rechenaufwand so klein wie "-100 ≤ a [i] ≤ 100" ist, kann er offen durch vollständige Suche gelöst werden.

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
min = Float::INFINITY
a.min.upto(a.max) do |x|
  b = a.map{|y| (x - y) ** 2}.inject(:+)
  min = b if min > b
end
puts min

Rubin (Minimum-Quadrat-Methode)

Als nächstes kommt die mathematische Lösung. Da die lineare Funktion "y = ax + b" eine Steigung von "a = 0" hat, ist "y = b".

Daher kann das "b" erhalten werden, das die kumulative Summe der Quadrate der Fehler minimiert. $b = 22 / 2 / 3$

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
b = (a.inject(:+).to_f / n).round
min = a.map{|x| (x - b) ** 2}.inject(:+)
puts min

Ruby (Minimum Square Method-Matrix)

Aufzählbare Module wie Map führen sequentielle Operationen für jedes Element aus, Matrizen führen jedoch Operationen für alle Elemente gleichzeitig aus.

ruby.rb

require 'matrix'

n = gets.to_f
a = Matrix[(gets.split.map(&:to_i))]
b = (a.inject(:+) / n).round
min = a - Matrix[(Array.new(n, b))]
puts (min * min.row_vectors[0])[0]

Python (vollständige Suche)

python.py

import sys

n = int(input())
a = list(map(int, input().split()))
m = sys.maxsize
for x in range(min(a), max(a) + 1):
    b = sum([(x - y) ** 2 for y in a])
    if m > b:
        m = b
print(m)

Es scheint, dass die Variable "min" nicht verwendet werden kann.

Python (Minimum Square Methode)

python.py

n = int(input())
a = list(map(int, input().split()))
b = round(sum(a) / n)
m = sum([(x - b) ** 2 for x in a])
print(m)

Python (Minimum Square Methode --numpy)

numpy.py

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split()))], dtype = np.int32)
b = np.around(np.sum(a) / n)
m = a - b
print(int(np.sum(np.power(m, 2))))

Es ist nur eine rudimentäre Verwendung.

Zusammenfassung

• Gelöster ARC 059 C.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut

Referenzierte Site

• Beachten Sie, dass ich den Algorithmus der kleinsten Quadrate verstehe. Und ich habe es in Python geschrieben. *