Created
January 29, 2018 19:04
-
-
Save jianminchen/f3b294cdc3b6e7345e27f1bc602b564e to your computer and use it in GitHub Desktop.
Float numbers and operators - try to put n - 1 operators to get maximum value, n is the float number's length
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace FindMaximumNumber | |
{ | |
/* | |
Keyword: | |
a list of float number | |
four operator: +, -, *, / algebra | |
insert operator between each consecutive pair of numbers | |
Ask: | |
Find maximimum value -> greedy algorithm | |
Constraints: | |
equal precedence order - 1 + 2 * 3 = 1 + 6 = 7 - No | |
1 + 2 * 3 = 3 * 3 = 9 - Yes | |
evaluation order is from left to right | |
-> scan the float number from left to right | |
1, 12, -3, maximum number is 1 - 12 * (-3) = 33 | |
1 | |
/ / \ \ | |
-11 13 1/12 12 -> Maximum and Minimum | |
*/ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
RunTestcase(); | |
} | |
public static void RunTestcase1() | |
{ | |
var result = GetMaxNumber(new double[] { 1, 12}); | |
} | |
public static void RunTestcase() | |
{ | |
var input = new double[] { 1, 12, -3 }; | |
var result = GetMaxNumber(input); | |
Debug.Assert(result[0] == 33); | |
} | |
public static double[] GetMaxNumber(double[] numbers) | |
{ | |
if (numbers == null || numbers.Length == 0) | |
{ | |
return new double[] { }; | |
} | |
return GetMaxNumberHelper(numbers, 1, new double[] { numbers[0], numbers[0] }); | |
} | |
/// <summary> | |
/// code review 1/29/2018 | |
/// </summary> | |
/// <param name="numbers"></param> | |
/// <param name="startIndex"></param> | |
/// <param name="original"></param> | |
/// <returns></returns> | |
public static double[] GetMaxNumberHelper(double[] numbers, int startIndex, double[] original) | |
{ | |
if (startIndex >= numbers.Length) | |
{ | |
return original; | |
} | |
var length = numbers.Length; | |
var visit = numbers[startIndex]; | |
var fourOperations = getFourOperations(original, visit); | |
var current = new double[] { fourOperations.Max(), fourOperations.Min() }; | |
return GetMaxNumberHelper(numbers, startIndex + 1, current); | |
} | |
/// <summary> | |
/// code review 1/29/2018 | |
/// </summary> | |
/// <param name="maxMin"></param> | |
/// <param name="number2"></param> | |
/// <returns></returns> | |
private static double[] getFourOperations(double[] maxMin, double number2) | |
{ | |
var addition = maxMin[0] + number2; | |
var addition2 = maxMin[1] + number2; | |
var subtraction = maxMin[0] - number2; | |
var subtraction2 = maxMin[1] - number2; | |
var multiplication = maxMin[0] * number2; | |
var multiplication2 = maxMin[1] * number2; | |
var division = maxMin[0] / number2; | |
var division2 = maxMin[1] / number2; | |
return new double[] { addition, addition2, subtraction, subtraction2, multiplication, multiplication2, division, division2 }; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment