整数は異なる加数の最大積に分解される
ライブラリ建設
タイトル
nを自然数とすると、nはいくつかの異なる自然数の和に分解することができ、このような分法には多くの種類があり、例えばn=10、10は:10=5+4+1に分解することができる.10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4; 10=,7+2+1; 10=6+3+1;….これらすべての分割法において、各加算積が最大であるのは30であり、(10=5+3+2の加算の積は5*3*2=30)である.プログラムを作成して、各種の分解方法の中で各加数の積の最大値を求めます.
入力要件:入力は1行のみで、自然数n.
出力要求:出力も1行のみで,すべての分解方法における各加算積の最大値である.
コード#コード#
1つの法則を発見します:連続する整数の積が最大で、例えば12:12=2+3+4+3=3+4+5=2+4+6発見3*4*5最大13=2+3+4+4=3+4+6最大はまとめることができます:2から順次連続する加数因子を求めて、最後に残りの数を平均して前の因子に分けます(もしあれば)、例えば9=2+3+4は分けなくて、13のような平均点が終わった後も1が残っているので、それはきっと最大の数に加算されます.
タイトル
nを自然数とすると、nはいくつかの異なる自然数の和に分解することができ、このような分法には多くの種類があり、例えばn=10、10は:10=5+4+1に分解することができる.10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4; 10=,7+2+1; 10=6+3+1;….これらすべての分割法において、各加算積が最大であるのは30であり、(10=5+3+2の加算の積は5*3*2=30)である.プログラムを作成して、各種の分解方法の中で各加数の積の最大値を求めます.
入力要件:入力は1行のみで、自然数n.
出力要求:出力も1行のみで,すべての分解方法における各加算積の最大値である.
コード#コード#
1つの法則を発見します:連続する整数の積が最大で、例えば12:12=2+3+4+3=3+4+5=2+4+6発見3*4*5最大13=2+3+4+4=3+4+6最大はまとめることができます:2から順次連続する加数因子を求めて、最後に残りの数を平均して前の因子に分けます(もしあれば)、例えば9=2+3+4は分けなくて、13のような平均点が終わった後も1が残っているので、それはきっと最大の数に加算されます.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n = 0;//
cin >> n;
int factor[50] = { 0 };//
int i = 0;
// 2
for (int j = 2; j <= n; j++) {
factor[i++] = j;
n -= j;
}
if (0 != n) {
if (n == i + 1) {// n , ,
factor[i - 1]++;
n--;
}
for (int j = 0; j < n; j++) {// 1
factor[i - j - 1]++;
}
}
int max = 1;
for (int j = 0; j < i; j++) {
max *= factor[j];
}
cout << max << endl;
return 0;
}