劍指offer筆記面試題14----剪繩子

題目：給你一根長度為n的繩子，請把繩子剪成m段（m，n都是整數，n > 1 并且m > 1），每段繩子的長度記為k[0], k[1], ...k[m]，請問k[0] x k[1] x ... x k[m]可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18，

測驗用例：

• 功能測驗（繩子的初始長度大于5），
• 邊界值測驗（繩子的初始長度分別為0、1、2、3、4），

測驗代碼：

void test(const char* testName, int length, int expected)
{
    int result1 = maxProductAfterCutting_solution1(length);
    if(result1 == expected)
        std::cout << "Solution1 for " << testName << " passed." << std::endl;
    else
        std::cout << "Solution1 for " << testName << " FAILED." << std::endl;

    int result2 = maxProductAfterCutting_solution2(length);
    if(result2 == expected)
        std::cout << "Solution2 for " << testName << " passed." << std::endl;
    else
        std::cout << "Solution2 for " << testName << " FAILED." << std::endl;
}
void test1()
{
    int length = 1;
    int expected = 0;
    test("test1", length, expected);
}
void test2()
{
    int length = 2;
    int expected = 1;
    test("test2", length, expected);
}
void test3()
{
    int length = 3;
    int expected = 2;
    test("test3", length, expected);
}
void test4()
{
    int length = 4;
    int expected = 4;
    test("test4", length, expected);
}
void test5()
{
    int length = 5;
    int expected = 6;
    test("test5", length, expected);
}
void test6()
{
    int length = 6;
    int expected = 9;
    test("test6", length, expected);
}
void test7()
{
    int length = 7;
    int expected = 12;
    test("test7", length, expected);
}
void test8()
{
    int length = 8;
    int expected = 18;
    test("test8", length, expected);
}
void test9()
{
    int length = 9;
    int expected = 27;
    test("test9", length, expected);
}
void test10()
{
    int length = 10;
    int expected = 36;
    test("test10", length, expected);
}
void test11()
{
    int length = 50;
    int expected = 86093442;
    test("test11", length, expected);
}

本題考點：

• 考查應聘者的抽象建模能力，應聘者需要把一個具體的場景抽象成一個能夠用動態規劃或者貪婪演算法解決的模型，
• 考查應聘者對動態規劃和貪婪演算法的理解，能夠靈活運用動態規劃解決問題的關鍵是具備從上到下分析問題、從下到上解決問題的能力，而靈活運用貪婪演算法則需要扎實的數學基本功，

動態規劃：

int maxProductAfterCutting_solution1(int length)
{
    if(length < 2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;
    int* products = new int[length + 1];
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;
    int max = 0;
    for(int i = 4; i <= length; ++i)
    {
        max = 0;
        for(int j = 1; j <= i / 2; ++j)
        {
            int product = products[j] * products[i - j];
            if(max < product)
                max = product;

            products[i] = max;
        }
    }
    max = products[length];
    delete[] products;
    return max;
}

貪婪演算法：

int maxProductAfterCutting_solution2(int length)
{
    if(length < 2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;
    // 盡可能多地減去長度為3的繩子段
    int timesOf3 = length / 3;
    // 當繩子最后剩下的長度為4的時候，不能再剪去長度為3的繩子段，
    // 此時更好的方法是把繩子剪成長度為2的兩段，因為2*2 > 3*1，
    if(length - timesOf3 * 3 == 1)
        timesOf3 -= 1;
    int timesOf2 = (length - timesOf3 * 3) / 2;
    return (int) (pow(3, timesOf3)) * (int) (pow(2, timesOf2));
}

標籤：其他

上一篇：演算法題--回文數

下一篇：演算法天天練771：查找字串出現的次數