add and tested horner evaluate

Mooophy · Mooophy · commit 71d63c859b39 · 2015-04-06T11:04:29.000+12:00
diff --git a/ch02/src/polynomial.hpp b/ch02/src/polynomial.hpp
@@ -20,5 +20,16 @@ namespace clrs
 
 			return y;
 		}
+
+		template<typename Sequence>
+		typename Sequence::value_type horner_evaluate(Sequence const& seq, typename Sequence::value_type x)
+		{
+			using Value = typename Sequence::value_type;
+
+			auto y = Value(0);
+			for (auto coefficient = seq.crbegin(); coefficient != seq.crend(); ++coefficient)
+				y = *coefficient + x*y;
+			return y;
+		}
 	}
 }
diff --git a/ch02/test/test_polynomial.cpp b/ch02/test/test_polynomial.cpp
@@ -41,5 +41,35 @@ namespace test
 			Assert::AreEqual(expect, actual);
 		}
 
+		TEST_METHOD(horner_evaluate_case1)
+		{
+			auto sample = std::vector < int > { 1 }; //y = 1
+			auto x = 2;
+			auto expect = 1;
+			auto actual = clrs::ch02::horner_evaluate(sample, x);
+
+			Assert::AreEqual(actual, expect);
+		}
+
+		TEST_METHOD(horner_evaluate_case2)
+		{
+			auto sample = std::vector < int > { 1, 2 }; // y = 1 + 2x
+			auto x = 2;
+			auto expect = 5;
+			auto actual = clrs::ch02::horner_evaluate(sample, x);
+
+			Assert::AreEqual(actual, expect);
+		}
+
+		TEST_METHOD(horner_evaluate_case3)
+		{
+			auto sample = std::vector < int > { 5, 2, 0, 7};	// y = 5 + 2x + 0x^2 + 7x^3
+			auto x = 2;											//	 = 5 + 4  + 0    + 56 = 65					
+			auto expect = 65;
+			auto actual = clrs::ch02::horner_evaluate(sample, x);
+
+			Assert::AreEqual(expect, actual);
+		}
+
 	};
 }

Original file line number	Diff line number	Diff line change
`@@ -20,5 +20,16 @@ namespace clrs`
`20`	`20`
`21`	`21`	`return y;`
`22`	`22`	`}`
	`23`	`+`
	`24`	`+ template<typename Sequence>`
	`25`	`+ typename Sequence::value_type horner_evaluate(Sequence const& seq, typename Sequence::value_type x)`
	`26`	`+ {`
	`27`	`+ using Value = typename Sequence::value_type;`
	`28`	`+`
	`29`	`+ auto y = Value(0);`
	`30`	`+ for (auto coefficient = seq.crbegin(); coefficient != seq.crend(); ++coefficient)`
	`31`	`+ y = coefficient + xy;`
	`32`	`+ return y;`
	`33`	`+ }`
`23`	`34`	`}`
`24`	`35`	`}`