给出一个整数n,将n分解为至少两个整数之和,使得这些整数的乘积最大化,输出能够获得的最大的乘积。
例如:
2=1+1,输出1;
10=3+3+4,输出36。
/**
* 整数成绩最大化
* 给出一个整数n,将n分解为至少两个整数之和,使得这些整数的乘积最大化,输出能够获得的最大的乘积。
* 例如:
* 2=1+1,输出1;
* 10=3+3+4,输出36。
* 输入描述:
* 输入为1个整数
* 输出描述:
* 输出为1个整数
* 输入例子1:
* 10
* 输出例子1:
* 36
*
* @author shijiacheng
*/
public class MaxIntMulti {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = n / 3;
if (n == 1) {
System.out.println(1);
}
if (n % 3 == 0) {
System.out.println((int) Math.pow(3, k));
} else if (n % 3 == 1) {
System.out.println((int) Math.pow(3, k - 1) * 4);
} else {
System.out.println((int) Math.pow(3, k) * 2);
}
}
}
var n = Number(readline()); if (n < 5) { var arr = [0,0,1,2,4]; console.log(arr[n]); } else { var x = 2,y = 0; for (var i = 5; i <= n; i++) { if (x == 2 || x == 1) { x--; y++; } else if (x == 0) { x = 2; y--; } } var result = (Math.pow(2,x))*(Math.pow(3,y)); console.log(result); }
#include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ if(n==2) cout<<1<<endl; else if(n==3) cout<<2<<endl; else{ int a3 = n/3; for(int i = a3;i>=0;i--){ int a2 = (n-3*i)/2; if(3*a3+2*a2==n) cout<<int(pow(3,a3)*pow(2,a2))<<endl; } } } return 0; }
网上大多做法是寻找尽可能多的3,算是找到了数学规律,我之前没接触到这个,根据不等式,当且仅当都相等时取等号,所以认为最大值肯定处于分解的数比较均匀的地方,然后分解的数目太多和太少都会导致结果比较小,所以先单调递增然后单调递减,我只要把这个最大值找出来。
#include <iostream> using namespace std; int main() { int n = 0; cin >> n; int res = 0; for (int i = 2; i <= n; i++) { int a = n / i; int r = n % i; int temp = 1; for (int j = 0; j < i - r; j++)temp *= a; ++a; for (int j = 0; j < r; j++)temp *= a; if(temp > res) { res = temp; } else { break; } } cout << res; return 0; }
#include <bits/stdc++.h>
using namespace std;
int maxsum = 0;
//当前乘积,待分解的数,最大乘积
void dfs(int mulsum, int n)
{
if (n <= 0)
return;
for (int i = 2; i <= n; i++)
{
maxsum = max(maxsum, mulsum * i);
dfs(mulsum * i, n - i);
}
}
int main()
{
int n;
cin >> n;
int mulsum = 1;
dfs(mulsum, n);
cout << maxsum;
return 0;
}
#include<iostream>#include<vector>using namespace std;int main() {int n;cin >> n;vector<int> mul;while(n>=3 && n!=4) {mul.push_back(3);n -= 3;}if(n) mul.push_back(n);int mulRes = 1;for(int i=0; i<mul.size(); ++i) {mulRes *= mul[i];}cout << mulRes << endl;return0;}
import java.util.Scanner;
public class Zhengshuchengjizuidahua_Wangyi {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int n = scan.nextInt();//输入的整数
int num3 = 1;
int left = 0;
for (int i = n - 3; i > 0; i -= 3) {
if (i % 2 == 0) {
int temp = i / 2;
if (temp <= 2) {
left = i;
break;
}
}
num3++;
}
int num2 = left / 2;
int ji = 1;
for (int i = 0; i < num3; i++) {
ji *= 3;
}
for (int i = 0; i < num2; i++) {
ji *= 2;
}
System.out.println(ji);
}
}
}
#include <iostream> #include <math.h> #include <vector> using namespace std; int process(int n) { if (n <= 2) { return 1; } vector<int> dp(n + 1, 1); dp[2] = 2; for (int i = 1; i <= n; ++i) { // 考虑各个位置 for (int j = 1; j < i; ++j) { dp[i] = max(dp[i], j * max(i - j, dp[i - j])); } } return dp[n]; } int main() { int n = 0; while (cin >> n) { cout << process(n) << endl; } return 0; }
#include <iostream> #include <vector> using namespace std; class Solution { public: int getMax(int n) { vector<int> tmp(n + 1); int max1, max2; tmp[2] = 1; for (int i = 3; i <= n; i++) { max1 = 0; for (int j = 1; j <= i / 2; j++) { if (j*(i - j) >= j*tmp[i - j]) { max2 = j*(i - j); } else { max2 = j*tmp[i - j]; } if (max2 > max1) { max1 = max2; } } tmp[i] = max1; } return tmp[n]; } }; int main() { int n; Solution s; while (cin >> n) { cout << s.getMax(n) << endl; } return 0; }