算法试题：从一串数字中构造出能被15整除的最大整数

上周末布置的算法试题：

给定一行只包含数字的字符串（1到1000个数字），求使用字符串中的某些字符，构造一个能被15整除的最大整数，要求字符串中的每个字符最多只能使用一次。

该试题需要考虑什么数能被3整除和被5整除，涉及排序，当不能被3整除时需要考虑如何舍去某些数字。

 

我今天用C++编程实现了，估计应该能对。

 

一、首先编写测试用例，每对值中给出待测试的数字串和预期的结果：

 

bool AssertPair(const char* instr, const char* check);

bool Test()
{
    return AssertPair("0", "")
        && AssertPair("5", "")
        && AssertPair("1", "")
        && AssertPair("12", "")
        && AssertPair("50", "")
        && AssertPair("125", "15")
        && AssertPair("120", "210")
        && AssertPair("102", "210")
        && AssertPair("012", "210")
        && AssertPair("102", "210")
        && AssertPair("051", "510")
        && AssertPair("12310", "3210")
        && AssertPair("12320", "3210")
        && AssertPair("0223", "30")
        && AssertPair("123110", "31110")
        && AssertPair("123220", "32220");
}

 

二、编码实现代码：

 

#include <iostream>
#include <string>
using namespace std;

// 按从大到小顺序插入排序
void Sort(char* buf)
{
    for (int i = 0; buf[i]; i++)            // 对每一个输入的数字
    {
        for (int j = 0; j < i; j++)         // 按从大到小顺序插入
        {
            if (buf[i] > buf[j])            // 将 buf[i] 插入到 j 位置
            {
                char c = buf[i];
                for (int k = i; k > j; k--)
                {
                    buf[k] = buf[k - 1];
                }
                buf[j] = c;
                break;
            }
        }
    }
}

// 找到5，放到末尾
bool Move5ToEnd(string& str)
{
    size_t pos = str.find('5');

    if (pos == string::npos)
    {
        return false;
    }
    str += str[pos];
    str.erase(pos, 1);

    return true;
}

// 从倒数第二个开始往前找一个数字移除，该数字除以3的余数为指定数
bool RemoveOneChar(string& str, int rem)
{
    for (int i = (int)str.size() - 2; i >= 0; i--)
    {
        if ((str[i] - '0') % 3 == rem)
        {
            str.erase(i, 1);
            return str != "0";
        }
    }

    return false;
}

// 从倒数第二个开始往前找两个数字移除，该数字之和除以3的余数为指定数
bool RemoveTwoChars(string& str, int rem)
{
    for (int i = (int)str.size() - 2; i >= 0; i--)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if ((str[i] - '0' + str[j] - '0') % 3 == rem)
            {
                str.erase(i, 1);
                str.erase(j, 1);
                return str != "0";
            }
        }
    }

    return false;
}

// 将一行中各个数字组成能被15整除的最大整数
bool GetMaxInt(string& str)
{
    // 去掉不是数字的字符
    for (int t = (int)str.size() - 1; t >= 0; t--)
    {
        if (!isdigit(str[t]))
        {
            str.erase(t, 1);
        }
    }

    // 从大到小排序
    Sort(&str[0]);

    // 如果末位不是0，则找到5，放到末尾，这样就能被5整除
    if (*str.rbegin() != '0' && !Move5ToEnd(str))
    {
        return false;
    }

    // 求所有数字之和
    int sum = 0;
    for (size_t i = 0; i < str.size(); i++)
    {
        sum += str[i] - '0';
    }

    // 根据除以3的余数，从倒数第二个开始往前找数字移除
    return sum > 0 &&                       // 0不能被整除
        (sum % 3 == 0                       // 正好被3整除
        || RemoveOneChar(str, sum % 3)      // 移除一个数字，该数字除3余指定数
        || RemoveTwoChars(str, sum % 3));   // 移除两个数字，其和除3余指定数
}

int main()
{
    printf(Test() ? "Test OK.\n" : "Test fail.\n");
    string str;

    cout << "请输入多行数字，将输出每行中各数字组成的能被15整除的最大整数。\n";

    for (;;)
    {
        cin >> str;
        if (str.empty() || str[0] == 'q')
        {
            break;
        }

        if (GetMaxInt(str))
        {
            printf("%s\n\n", str.c_str());
        }
        else
        {
            printf("Imporssible.\n\n");
        }
    }

    return 0;
}

bool AssertPair(const char* instr, const char* check)
{
    string str(instr);
    bool ret = GetMaxInt(str)
        ? strcmp(check, str.c_str()) == 0
        : strcmp(check, "") == 0;

    printf("%s\tinput: %s\toutput: %s\tcheck: %s\n",
        ret ? "OK." : "Fail.",
        instr, str.c_str(),
        *check ? check : "Imporssible");

    return ret;
}