分割乘积
题目描述
给定一个整数，求插入两个乘号将该整数分割成三个数之后，三个数的的最大乘积。
关于输入
只有一行，一个整数。
关于输出
所求出的最大乘积。
例子输入
4242
例子输出
336
提示信息
整数有正有负，注意，不是求“绝对值”最大的乘积。
输入保证，如果按题目要求的乘法操作，不会使int发生溢出。
解题分析
目标是找到一个整数分割成三个部分后，这三个部分乘积的最大值。程序首先读取一个整数，但为了方便处理，它将这个整数作为字符串读入。这样可以轻松地在不同位置“切割”这个数字。
程序使用两个嵌套的循环来尝试所有可能的切割位置。第一个循环确定第一个乘号的位置，第二个循环确定第二个乘号的位置。每次循环都会根据这两个乘号的位置将数字分割成三部分。
分割后，程序将这三部分从字符串转换为长整型数字，然后计算这三个数字的乘积。程序会持续追踪遇到的最大乘积。在尝试了所有可能的分割方式后，程序输出找到的最大乘积值。
整个思路的核心是穷举法，即尝试所有可能的分割方式，然后找出其中乘积最大的一种。这种方法简单直接，适用于这个问题，因为整数的长度有限，所以可能的分割方式也是有限的。
代码实现
（方法一）c语言风格
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
int main() {
char temp[12],numStr[12]; // 假设输入的整数不超过10位
int flag=0;
scanf("%s", temp);
if(temp[0]=='-'){
flag=1;
strcpy(numStr,temp+1);
}
else{
strcpy(numStr,temp);
}
int len = strlen(numStr);
long maxProduct = LONG_MIN;
for (int i = 1; i < len; ++i) {
for (int j = i + 1; j < len; ++j) {
// 将字符串划分为三部分
char part1[11], part2[11], part3[11];
strncpy(part1, numStr, i);
part1[i] = '\0';
strncpy(part2, numStr + i, j - i);
part2[j - i] = '\0';
strcpy(part3, numStr + j);
// 将字符串转换为整数并计算乘积
long num1 = atol(part1);
long num2 = atol(part2);
long num3 = atol(part3);
long product;
if(!flag)
product = num1 * num2 * num3;
else product = -1*num1 * num2 * num3;
// 更新最大乘积
if (product > maxProduct) {
maxProduct = product;
}
}
}
printf("%ld\n", maxProduct);
return 0;
}
（方法二）c++风格
#include <iostream>
#include <string>
#include <climits>
using namespace std;
// C++初始模板程序
int main() {
string num; cin>>num;
int flag=0;
if(num[0]=='-'){
num=num.substr(1);
flag=1;
}
int len=num.size(); long long int max=-INT64_MAX;
for(int i=1;i<=len-2;i++){
string temp1=num.substr(0,i);
long long int n1=stoll(temp1);
for(int j=1;j<len-i;j++){
string temp2=num.substr(i,j);
long long int n2=stoll(temp2);
string temp3=num.substr(i+j);
long long int n3=stoll(temp3);
if(!flag)
max=max>n1*n2*n3?max:n1*n2*n3;
else{
//cout<<n1<<" "<<n2<<" "<<n3<<endl;
max=max>(-1)*n1*n2*n3?max:(-1)*n1*n2*n3;
}
}
}
cout<<max<<endl;
return 0;
}
进一步拓展
strncpy 和 strcpy 都是 C 语言标准库中的字符串处理函数，它们用于复制字符串，但在使用方式上有所不同。
strcpy
strcpy 函数用于将一个字符串复制到另一个字符串。它的原型如下：
char *strcpy(char *dest, const char *src);
dest：目标字符串的指针，用于存放复制的内容。src：源字符串的指针。
strcpy 会将 src 指向的字符串（包括结束符 \0）复制到 dest 指向的位置。复制过程会覆盖 dest 原有的内容，并且在 src 字符串的结尾添加 \0 以确保 dest 是一个完整的字符串。
strncpy
strncpy 函数类似于 strcpy，但它允许指定最大复制长度。其原型如下：
char *strncpy(char *dest, const char *src, size_t n);
dest：目标字符串的指针。src：源字符串的指针。n：最多复制的字符数。
strncpy 会从 src 指向的字符串复制最多 n 个字符到 dest。如果 src 的长度小于 n，则 strncpy 会在 dest 之后添加额外的 \0 字符，直到总共复制了 n 个字符。如果 src 的长度大于或等于 n，则不会在 dest 的末尾添加 \0 字符。
使用注意事项
- 当使用
strcpy时，必须确保dest有足够的空间来存储src的内容，包括结尾的\0字符。否则可能会发生缓冲区溢出，导致不可预测的行为。 - 在使用
strncpy时，如果n小于src的长度，dest将不会以\0结尾。这可能导致后续操作出现问题，因为大多数字符串处理函数都假设字符串是以\0结尾的。 - 使用这些函数时需要特别注意目标字符串的大小，以避免溢出或未初始化的内存访问。
