Решение на Polynomial от Йоанна Николова
Към профила на Йоанна Николова
Резултати
- 15 точки от тестове
- 1 бонус точка
- 16 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-ks1sct/solution)
Finished dev [unoptimized + debuginfo] target(s) in 5.58 secs
Running target/debug/deps/solution-200db9172ea1f728
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/debug/deps/solution_test-e3c9eb714e09105e
running 15 tests
test solution_test::test_add_poly ... ok
test solution_test::test_add_poly_zero_one ... ok
test solution_test::test_arithmetic_properties ... ok
test solution_test::test_create_poly ... ok
test solution_test::test_div_poly_f64 ... ok
test solution_test::test_div_poly_f64_zero ... ok
test solution_test::test_fp_comparison ... ok
test solution_test::test_has_point ... ok
test solution_test::test_lagrange_poly_1 ... ok
test solution_test::test_lagrange_poly_2 ... ok
test solution_test::test_lagrange_poly_err_eq_x ... ok
test solution_test::test_mul_poly ... ok
test solution_test::test_mul_poly_f64 ... ok
test solution_test::test_mul_poly_f64_zero ... ok
test solution_test::test_mul_poly_zero_one ... ok
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Doc-tests solution
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
История (3 версии и 5 коментара)
Йоанна качи решение на 14.11.2017 00:50 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
const EPS: f64 = 1e-10;
macro_rules! get {
Супер! Ще ги погледна и ще го оправя. Мерси :)
($expr: expr) => {
match $expr{
Some(val) => val,
None => &0.0,
}
}
}
macro_rules! hasVal {
($expr: expr) => {
match $expr{
Some(_) => true,
None => false,
}
}
}
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs : Vec<f64>,
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
(self.evaluate(point.0) - point.1).abs() < EPS
}
- /// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
- /// по-долу.
- ///
- /// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
- /// е `x^2 + 2*x + 1`.
- ///
- /// Ако две точки имат равни X координати, върнете `None`.
- ///
- /// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
- /// стойности. Можете да го направите, разбира се, ако решите.
- ///
- ///!!!!!!!!!!TODO:
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
- for _ in points.into_iter(){
+ let mut res: Polynomial = Polynomial::default();
+
+ for cur_point in points.iter(){
+ let mut numerator:Polynomial = Polynomial::from(vec![1.0]);
+
+ for point in points.iter(){
+ if point != cur_point{
+ numerator = numerator * Polynomial::from(vec![1.0, - point.0]);
+ }
+ }
+ let denominator = numerator.evaluate(cur_point.0);
+
+ if denominator.abs() < EPS {
+ return None;
+ }
+
+ res = res + (numerator * cur_point.1 / denominator);
}
- None
+ Some(Polynomial{ coefs: Polynomial::normalize(res.coefs),})
}
- fn evaluate(&self, x: f64) -> f64 {
+ fn evaluate(&self,x: f64) -> f64 {
let mut res: f64 = 0_f64;
let mut x_on_power: f64 = 1_f64;
for coef in self.coefs.iter().rev(){
res += coef*x_on_power;
x_on_power *= x;
}
res
}
fn normalize(coefs: Vec<f64>) -> Vec<f64>{
coefs.into_iter().skip_while(|x| x.abs() < EPS).collect()
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
let vec = Polynomial::normalize(coefs);
Polynomial{ coefs: vec, }
}
}
impl Default for Polynomial {
fn default() -> Polynomial{
Polynomial{ coefs: Vec::new(), }
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
if self.coefs.len() != rhs.coefs.len(){
return false;
}
let size: usize = self.coefs.len();
for i in 0..size{
if (self.coefs[i] - rhs.coefs[i]).abs() > EPS{
return false;
}
}
true
}
}
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output{
let mut res_coefs : Vec<f64> = self.coefs.iter().map(|x| x * rhs).collect();
res_coefs = Polynomial::normalize(res_coefs);
Polynomial{coefs: res_coefs,}
}
}
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output{
if rhs.abs() > EPS{
self * (1 as f64 / rhs)
}
else{
panic!("Try to devide by zero");
}
}
}
impl Mul for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: Polynomial) -> Self::Output{
let size: usize = self.coefs.len() + rhs.coefs.len() - 1;
let mut res: Vec<f64> = vec![0.0; size];
- for (i, self_coef) in self.coefs.into_iter().enumerate(){
- for (j, rhs_coef) in rhs.coefs.clone().into_iter().enumerate(){
+ for (i, self_coef) in self.coefs.iter().enumerate(){
+ for (j, rhs_coef) in rhs.coefs.clone().iter().enumerate(){
res[i + j] += self_coef*rhs_coef;
}
}
res = Polynomial::normalize(res);
Polynomial{ coefs: res,}
}
}
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output{
let mut self_it = self.coefs.iter().rev();
let mut rhs_it = rhs.coefs.iter().rev();
let mut res: Vec<f64> = Vec::new();
let mut self_coef = self_it.next();
let mut rhs_coef = rhs_it.next();
while hasVal!(self_coef) || hasVal!(rhs_coef){
res.push(get!(self_coef) + get!(rhs_coef));
self_coef = self_it.next();
rhs_coef = rhs_it.next();
}
res.reverse();
res = Polynomial::normalize(res);
Polynomial{ coefs : res, }
}
}
Йоанна качи решение на 14.11.2017 01:00 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
const EPS: f64 = 1e-10;
-macro_rules! get {
- ($expr: expr) => {
- match $expr{
- Some(val) => val,
- None => &0.0,
- }
- }
-}
-
-macro_rules! hasVal {
- ($expr: expr) => {
- match $expr{
- Some(_) => true,
- None => false,
- }
- }
-}
-
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs : Vec<f64>,
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
(self.evaluate(point.0) - point.1).abs() < EPS
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut res: Polynomial = Polynomial::default();
for cur_point in points.iter(){
let mut numerator:Polynomial = Polynomial::from(vec![1.0]);
for point in points.iter(){
if point != cur_point{
- numerator = numerator * Polynomial::from(vec![1.0, - point.0]);
+ numerator = numerator * Polynomial::from(vec![1.0, -point.0]);
}
}
let denominator = numerator.evaluate(cur_point.0);
if denominator.abs() < EPS {
return None;
}
res = res + (numerator * cur_point.1 / denominator);
}
Some(Polynomial{ coefs: Polynomial::normalize(res.coefs),})
Нещо дребно, което може да ти опрости кода: Вместо да конструираш полином "ръчно" (тук и по-долу), можеш да викаш from навсякъде. Нещо повече, тъй като from вика normalize, ако консистентно ползваш него, ще избегнеш ръчното викане на normalize. Което, дори ако забравиш на едно място, ще си вкараш дребен, но подъл бъг.
As a general rule, добър навик е да създаваш конструктори (било то и "изкуствени" като from, или new), които правят всичко необходимо, за да нормализират данните, така че да създадат валидна инстанция на типа. По този начин, няма как никъде да създадеш невалиден тип, accidentally.
}
fn evaluate(&self,x: f64) -> f64 {
let mut res: f64 = 0_f64;
let mut x_on_power: f64 = 1_f64;
for coef in self.coefs.iter().rev(){
res += coef*x_on_power;
x_on_power *= x;
}
res
}
fn normalize(coefs: Vec<f64>) -> Vec<f64>{
coefs.into_iter().skip_while(|x| x.abs() < EPS).collect()
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
let vec = Polynomial::normalize(coefs);
Polynomial{ coefs: vec, }
}
}
impl Default for Polynomial {
fn default() -> Polynomial{
Polynomial{ coefs: Vec::new(), }
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
if self.coefs.len() != rhs.coefs.len(){
return false;
}
let size: usize = self.coefs.len();
for i in 0..size{
if (self.coefs[i] - rhs.coefs[i]).abs() > EPS{
return false;
}
}
true
}
}
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output{
let mut res_coefs : Vec<f64> = self.coefs.iter().map(|x| x * rhs).collect();
res_coefs = Polynomial::normalize(res_coefs);
Polynomial{coefs: res_coefs,}
}
}
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output{
if rhs.abs() > EPS{
self * (1 as f64 / rhs)
}
else{
panic!("Try to devide by zero");
}
}
}
impl Mul for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: Polynomial) -> Self::Output{
let size: usize = self.coefs.len() + rhs.coefs.len() - 1;
let mut res: Vec<f64> = vec![0.0; size];
for (i, self_coef) in self.coefs.iter().enumerate(){
- for (j, rhs_coef) in rhs.coefs.clone().iter().enumerate(){
+ for (j, rhs_coef) in rhs.coefs.iter().enumerate(){
res[i + j] += self_coef*rhs_coef;
}
}
res = Polynomial::normalize(res);
Polynomial{ coefs: res,}
}
}
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output{
let mut self_it = self.coefs.iter().rev();
let mut rhs_it = rhs.coefs.iter().rev();
let mut res: Vec<f64> = Vec::new();
let mut self_coef = self_it.next();
let mut rhs_coef = rhs_it.next();
- while hasVal!(self_coef) || hasVal!(rhs_coef){
- res.push(get!(self_coef) + get!(rhs_coef));
+ while self_coef.is_some() || rhs_coef.is_some(){
+ res.push(self_coef.unwrap_or(&0.0) + rhs_coef.unwrap_or(&0.0));
self_coef = self_it.next();
rhs_coef = rhs_it.next();
}
res.reverse();
res = Polynomial::normalize(res);
Polynomial{ coefs : res, }
}
}
Добра работа със задачата, и доста навреме. Тъй като си предала цялостно решение доста преди крайния срок, получаваш от мене една бонус точка за прилежност. Keep up the good work :)
Нещо дребно, което може да ти опрости кода: Вместо да конструираш полином "ръчно" (тук и по-долу), можеш да викаш
fromнавсякъде. Нещо повече, тъй катоfromвикаnormalize, ако консистентно ползваш него, ще избегнеш ръчното викане наnormalize. Което, дори ако забравиш на едно място, ще си вкараш дребен, но подъл бъг.As a general rule, добър навик е да създаваш конструктори (било то и "изкуствени" като
from, илиnew), които правят всичко необходимо, за да нормализират данните, така че да създадат валидна инстанция на типа. По този начин, няма как никъде да създадеш невалиден тип, accidentally.